boost-graph - 使用 BGL 的图形水平化

Question

您能否发布示例代码以使用 BGL 对有向图进行平整化？水平化的定义：顶点有一个属性“int level”。在图的 BFS 遍历期间，当“检查”一个顶点时，查看其前一个顶点的级别，取其中的最大值，递增，并将其分配给该顶点的“级别”。

Answer 1

如果您指的是 BFS 深度，那么这已经内置以提高 BFS 并且可以轻松获得。

只需使用一个向量来存储深度和一个深度 BFS 访问者，就像我制作的这个示例一样：

#include <iostream>
#include <vector>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/breadth_first_search.hpp>

using namespace std;
using namespace boost;

typedef adjacency_list < vecS, vecS, directedS,
                    property< vertex_index_t, size_t> ,
                    property< edge_index_t, size_t > > Graph;

typedef graph_traits<Graph>::vertex_descriptor Vertex;
typedef graph_traits<Graph>::edge_descriptor Edge;



int main(int argc, char* argv[]){

    Graph G;

    vector<Vertex> verts;

    for(size_t i = 0; i < 9; ++i){
        Vertex v = add_vertex(G);
        verts.push_back(v);
    }

   /*
    0          0
             /  \
    1        1    4
           /      \
    2      2        5
         /          \
    3   3            6
                      \
    4                  7
                        \
    5                    8
   */
    add_edge(verts.at(0),verts.at(1),G);
    add_edge(verts.at(1),verts.at(2),G);
    add_edge(verts.at(2),verts.at(3),G);
    add_edge(verts.at(0),verts.at(4),G);
    add_edge(verts.at(4),verts.at(5),G);
    add_edge(verts.at(5),verts.at(6),G);
    add_edge(verts.at(6),verts.at(7),G);
    add_edge(verts.at(7),verts.at(8),G);

    cout << "vertices " << num_vertices(G) << endl;
    cout << "edges    " << num_edges(G) << endl;


    //store depths
    vector<size_t> d(num_vertices(G));

    //get an index map, from Graph definition property< vertex_index_t, size_t>
    typedef boost::property_map< Graph, boost::vertex_index_t>::type VertexIndexMap;
    VertexIndexMap v_index = get(boost::vertex_index, G);

    // Create the external property map, this map wraps the storage vector d
    boost::iterator_property_map< std::vector< size_t >::iterator, VertexIndexMap >
        d_map(d.begin(), v_index);


    //Start at 0
    boost::breadth_first_search(G, verts.at(0),
        boost::visitor(boost::make_bfs_visitor(
          boost::record_distances(d_map, boost::on_tree_edge())
          )));

    cout << "Starting at 0" << endl;

    for(size_t i = 0; i < 9; ++i){
        //depth (level) of BFS
        cout << "vertex " << i << "\t" << d.at(i) << endl; 
    }

    vector<size_t> d2(num_vertices(G));



    cout << "Starting at 4" << endl;

    // Create the external property map, this map wraps the storage vector d
    boost::iterator_property_map< std::vector< size_t >::iterator, VertexIndexMap >
        d2_map(d2.begin(), v_index);

    //start at 4
    boost::breadth_first_search(G, verts.at(4),
        boost::visitor(boost::make_bfs_visitor(
          boost::record_distances(d2_map, boost::on_tree_edge())
          )));

    for(size_t i = 0; i < 9; ++i){
        //depth (level) of BFS
        cout << "vertex " << i << "\t" << d2.at(i) << endl; 
    }

}

输出应如下所示：
顶点 9
边 8
从 0
顶点开始 0 0
顶点 1 1
顶点 2 2
顶点 3 3
顶点 4 1
顶点 5 2
顶点 6 3
顶点 7 4
顶点 8 5
从 4
顶点开始 0 0
顶点 1 0
顶点2 0
顶点 3 0
顶点 4 0
顶点 5 1
顶点 6 2
顶点 7 3
顶点 8 4

当您从 4 开始时，其他顶点不可到达（定向），因此向量包含默认值（在本例中为 0）。这也适用于无向。