使用 Boost Graph Library 的简单示例是什么

Question

我正在尝试使用BGL，我发现文档很精确，但缺乏更多简单案例的示例。我的目标如下所述（阅读文档后我仍然无法做到这一点）：

struct Vertex
{
    double m_d;
    std::size_t m_id;
};

//or

struct Vertex
{
    double m_d;
    std::size_t id() const;
};

目标：

0. 有向图 G（除了 in_edges 之外，双向图和有向图有什么区别？）
1. G可以保存顶点类型Vertex。
2. 通过 id 从 G 获取顶点，并在需要时更改 Vertex 结构中的 m_d 值。
3. 添加、删除顶点和顶点之间的边，还支持成本，即成本（边）。

您能给我写一个关于如何使用 BGL 执行此操作的示例吗？我相信我需要MutableBidirectionalGraph？

Answer 1

0. 有向图G

   马上：

   struct Vertex {
       double m_d  = 0;
       size_t m_id = -1;
       // or std::size_t id() const;
   };
   
   struct Edge {
       double cost = 0;
   };
   
   using Graph =
       boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, Vertex, Edge>;
   

   （除了请之外，双向和定向有什么区别 in_edges？）

   当然，除了枚举传入边的复杂性保证以及插入边时的线性开销之外，没有其他区别

1. G可以保存顶点类型Vertex。

   参见 0。

2. 通过 id 获取顶点G

       auto find_by_id = [&g](size_t id) -> Vertex& {
           auto vv = boost::make_iterator_range(vertices(g));
           auto vd = find_if(vv, [&, id](auto vd) { return g[vd].m_id == id; });
           return g[*vd];
       };
   

   并在需要时更改结构m_d中的值。Vertex

   if (i_want()) {
       g[vd].m_id += 1;
   }
   

   或者，

   auto idmap = boost::get(&Vertex::m_id, g);
   
   if (i_want()) {
       idmap[vd] += 1;
   }
   

   甚至

   put(idmap, vd, 42);
   

   甚至更无标记：

   get(boost::vertex_bundle, g, vd).m_id = 999;
   

3. 添加、删除顶点

    remove_vertex(vd, g);
   

   和顶点之间的边

    clear_vertex(vd, g);
   

   并且还支持成本，即成本（边缘）。

   哇，这确实与上述任何内容无关。但它实际上与顶点 id 相同：

   if (i_want()) {
       g[ed].cost = new_cost;
   }
   

   或者，

   auto cost = boost::get(&Edge::cost, g);
   
   if (i_want()) {
       cost[ed] = new_cost;
   }
   

   甚至

   put(cost, ed, new_cost);
   

   甚至更无标记：

   get(boost::edge_bundle, g, ed).cost = new_cost;
   

现场演示

住在科里鲁

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/range/algorithm.hpp>
#include <iostream>

struct Vertex {
    double m_d  = 0;
    size_t m_id = -1;
    // or std::size_t id() const;
};

struct Edge {
    double cost = 0;
};

using Graph =
    boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, Vertex, Edge>;

using boost::make_iterator_range;

int main(){
    Graph g;
    auto v0 = add_vertex({0.1, 100}, g);
    auto v1 = add_vertex({0.2, 200}, g);
    auto v2 = add_vertex({0.3, 300}, g);
    auto v3 = add_vertex({0.4, 400}, g);
    auto v4 = add_vertex({0.5, 500}, g);
    auto v5 = add_vertex({0.6, 600}, g);

    add_edge(v0, v2, Edge{1.5}, g);
    add_edge(v1, v3, Edge{2.5}, g);
    add_edge(v4, v1, Edge{3.5}, g);
    add_edge(v2, v5, Edge{4.5}, g);

    auto idmap = boost::get(&Vertex::m_id, g);
    auto cost  = boost::get(&Edge::cost, g);

    auto find_by_id = [&g](size_t id) -> Vertex& {
        auto vv = boost::make_iterator_range(vertices(g));
        auto vd = find_if(vv, [&, id](auto vd) { return g[vd].m_id == id; });
        return g[*vd];
    };

    print_graph(g, idmap, std::cout << "original: ");

    auto i_want = [](auto vd) {
        return (vd % 2); // when I want
    };

    for (auto vd : make_iterator_range(vertices(g))) {
        if (i_want(vd))
            g[vd].m_id += 1;
        if (i_want(vd))
            idmap[vd] += 1;
        //put(idmap, vd, 42);
        //get(boost::vertex_bundle, g, vd).m_id = 999;
    }

    print_graph(g, idmap, std::cout << "altered: ");

    clear_vertex(v3, g);
    remove_vertex(v3, g); // undefined behaviour unless edges cleared

    print_graph(g, idmap, std::cout << "removed: ");

    for (auto ed : make_iterator_range(edges(g))) {
        std::cout << ed << " cost " << cost[ed] << "\n";
    }

    for (auto ed : make_iterator_range(edges(g))) {
        cost[ed] *= 111;
    }

    for (auto ed : make_iterator_range(edges(g))) {
        std::cout << ed << " cost " << cost[ed] << "\n";
    }
};

印刷

original: 100 --> 300 
200 --> 400 
300 --> 600 
400 --> 
500 --> 200 
600 --> 
altered: 100 --> 300 
202 --> 402 
300 --> 602 
402 --> 
500 --> 202 
602 --> 
removed: 100 --> 300 
202 --> 
300 --> 602 
500 --> 202 
602 --> 
(0,2) cost 1.5
(3,1) cost 3.5
(2,4) cost 4.5
(0,2) cost 166.5
(3,1) cost 388.5
(2,4) cost 499.5