使用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）。這應該也適用於無向。