nivellement de graphe utilisant BGL

Question

Pouvez-vous s'il vous plaît publier un exemple de code pour niveler un graphe orienté en utilisant BGL? Définition de la mise à niveau: Vertex a la propriété "niveau entier". Pendant la traversée BFS du graphe, quand un sommet est "examiné", regardez les niveaux de ses sommets prédécesseurs, prenez le maximum de ceux-ci, incrémentez et assignez-le au "niveau" de ce sommet.

Answer 1

Si vous parlez de la profondeur BFS, ceci est déjà intégré pour booster BFS et peut être obtenu facilement.

Il suffit d'utiliser un vecteur pour stocker les profondeurs et une profondeur BFS visiteur comme cet exemple, je fait:

#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; 
    } 

} 

sortie devrait ressembler à ceci:
sommets 9
bords 8
À partir de 0
sommet 0 0
sommet 1 1
sommet 2 2
sommet 3 3
sommet 4 1
sommet 5 2
sommet 6 3
sommet 7 4
sommet 8 5
partir de 4
sommet 0 0
sommet 1 0
sommet 2 0
sommet 3 0
sommet 4 0
sommet 5 1
sommet 6 2
sommet 7 3Lorsque vous commencez à 4, les autres sommets ne sont pas joignables, donc le vecteur contient des valeurs par défaut (0 dans ce cas). Cela devrait fonctionner pour non orienté aussi.