2

BGL を使用して有向グラフを平準化するサンプル コードを投稿していただけますか? レベライゼーションの定義: 頂点には「int レベル」というプロパティがあります。グラフの BFS トラバーサル中に、頂点が「検査」されているとき、その前の頂点のレベルを見て、これらの最大値を取得し、インクリメントして、これをこの頂点の「レベル」に割り当てます。

4

1 に答える 1

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) が含まれます。これは無向でも機能するはずです。

于 2013-12-18T22:47:38.547 に答える