BGL을 사용한 그래프의 평준화

Question

BGL을 사용하여 유향 그래프를 평준화하기위한 예제 코드를 게시 할 수 있습니까? 레벨 지정 정의 : Vertex에는 "int level"속성이 있습니다. 그래프의 BFS 통과 동안, 정점이 "조사"되면, 그것의 전임 정점의 레벨을보고, 최대치를 취하고 이것을 증가시켜이를이 정점의 "레벨"에 할당하십시오.

Answer 1

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
에서 시작

그냥 깊이와 내가 만든이 예와 같이 깊이 BFS 방문자를 저장하는 벡터를 사용 정점 0 0
정점 1
정점 2
정점 3/3
,451,515,정점 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)이 포함되도록 다른 꼭지점에 도달 할 수 없습니다. 이것도 undirected에도 작동합니다.