Jak przejść przez wykres w trybie doładowania BFS

Question

Mam problemy z kompilacją BFS bardzo prostego wykresu. Cokolwiek robię mam różne komunikaty kompilatora o niedopasowanych wywołań metod (Próbowałem boost::visitor i rozszerzenie boost::default_bfs_visitor etc.)

#include <stdint.h> 
#include <iostream> 
#include <vector> 
#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/breadth_first_search.hpp> 

int main() { 
    typedef boost::adjacency_list<boost::vecS, boost::hash_setS, boost::undirectedS, uint32_t, uint32_t, boost::no_property> graph_t; 
    graph_t graph(4); 
    graph_t::vertex_descriptor a = boost::vertex(0, graph); 
    graph_t::vertex_descriptor b = boost::vertex(1, graph); 
    graph_t::vertex_descriptor c = boost::vertex(2, graph); 
    graph_t::vertex_descriptor d = boost::vertex(3, graph); 
    graph[a] = 0; 
    graph[b] = 1; 
    graph[c] = 2; 
    graph[d] = 3; 
    std::pair<graph_t::edge_descriptor, bool> result = boost::add_edge(a, b, 0, graph); 
    result = boost::add_edge(a, c, 1, graph); 
    result = boost::add_edge(c, b, 2, graph); 
    class { 
    public: 
    void initialize_vertex(const graph_t::vertex_descriptor &s, graph_t &g) { 
     std::cout << "Initialize: " << g[s] << std::endl; 
    } 
    void discover_vertex(const graph_t::vertex_descriptor &s, graph_t &g) { 
     std::cout << "Discover: " << g[s] << std::endl; 
    } 
    void examine_vertex(const graph_t::vertex_descriptor &s, graph_t &g) { 
     std::cout << "Examine vertex: " << g[s] << std::endl; 
    } 
    void examine_edge(const graph_t::edge_descriptor &e, graph_t &g) { 
     std::cout << "Examine edge: " << g[e] << std::endl; 
    } 
    void tree_edge(const graph_t::edge_descriptor &e, graph_t &g) { 
     std::cout << "Tree edge: " << g[e] << std::endl; 
    } 
    void non_tree_edge(const graph_t::edge_descriptor &e, graph_t &g) { 
     std::cout << "Non-Tree edge: " << g[e] << std::endl; 
    } 
    void gray_target(const graph_t::edge_descriptor &e, graph_t &g) { 
     std::cout << "Gray target: " << g[e] << std::endl; 
    } 
    void black_target(const graph_t::edge_descriptor &e, graph_t &g) { 
     std::cout << "Black target: " << g[e] << std::endl; 
    } 
    void finish_vertex(const graph_t::vertex_descriptor &s, graph_t &g) { 
     std::cout << "Finish vertex: " << g[s] << std::endl; 
    } 
    } bfs_visitor; 
    boost::breadth_first_search(graph, a, bfs_visitor); 
    return 0; 
} 

Jak odwiedzić wykres używając bfs_visitor?

PS. Widziałem i kompilowałem "How to create a C++ Boost undirected graph and traverse it in depth first search (DFS) order?", ale to nie pomogło.

Answer 1

Możesz zobaczyć here listę przeciążeń breadth_first_search. Jeśli nie chcesz określać wszystkich parametrów, musisz użyć wersji nazwanego parametru. to będzie wyglądać następująco:

breadth_first_search(graph, a, boost::visitor(bfs_visitor)); 

to będzie działać jak gdybyś użył vecS jako przechowywania VertexList w swojej definicji wykresu lub jeśli już zbudowane i zainicjowany właściwość vertex_index wewnętrzną mapę. Ponieważ używasz hash_setS trzeba zmienić inwokację do:

breath_first_search(graph, a, boost::visitor(bfs_visitor).vertex_index_map(my_index_map)); 

Jesteś już przy użyciu mapy indeksu w swojej uint32_t dołączonego nieruchomości. Możesz użyć get(boost::vertex_bundle, graph), aby uzyskać do niego dostęp.

Wystąpił również problem z Twoim gościem. Powinieneś wyprowadzić go z poziomu boost::default_bfs_visitor, a parametr graph_t funkcji członkowskich musi być zakwalifikowany jako const.

Pełny kod:

#include <stdint.h> 
#include <iostream> 
#include <vector> 
#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/breadth_first_search.hpp> 

typedef boost::adjacency_list<boost::vecS, boost::hash_setS, boost::undirectedS, uint32_t, uint32_t, boost::no_property> graph_t; 


struct my_visitor : boost::default_bfs_visitor{ 

    void initialize_vertex(const graph_t::vertex_descriptor &s, const graph_t &g) const { 
     std::cout << "Initialize: " << g[s] << std::endl; 
    } 
    void discover_vertex(const graph_t::vertex_descriptor &s, const graph_t &g) const { 
     std::cout << "Discover: " << g[s] << std::endl; 
    } 
    void examine_vertex(const graph_t::vertex_descriptor &s, const graph_t &g) const { 
     std::cout << "Examine vertex: " << g[s] << std::endl; 
    } 
    void examine_edge(const graph_t::edge_descriptor &e, const graph_t &g) const { 
     std::cout << "Examine edge: " << g[e] << std::endl; 
    } 
    void tree_edge(const graph_t::edge_descriptor &e, const graph_t &g) const { 
     std::cout << "Tree edge: " << g[e] << std::endl; 
    } 
    void non_tree_edge(const graph_t::edge_descriptor &e, const graph_t &g) const { 
     std::cout << "Non-Tree edge: " << g[e] << std::endl; 
    } 
    void gray_target(const graph_t::edge_descriptor &e, const graph_t &g) const { 
     std::cout << "Gray target: " << g[e] << std::endl; 
    } 
    void black_target(const graph_t::edge_descriptor &e, const graph_t &g) const { 
     std::cout << "Black target: " << g[e] << std::endl; 
    } 
    void finish_vertex(const graph_t::vertex_descriptor &s, const graph_t &g) const { 
     std::cout << "Finish vertex: " << g[s] << std::endl; 
    } 
    }; 

int main() { 
    graph_t graph(4); 
    graph_t::vertex_descriptor a = boost::vertex(0, graph); 
    graph_t::vertex_descriptor b = boost::vertex(1, graph); 
    graph_t::vertex_descriptor c = boost::vertex(2, graph); 
    graph_t::vertex_descriptor d = boost::vertex(3, graph); 
    graph[a] = 0; 
    graph[b] = 1; 
    graph[c] = 2; 
    graph[d] = 3; 
    std::pair<graph_t::edge_descriptor, bool> result = boost::add_edge(a, b, 0, graph); 
    result = boost::add_edge(a, c, 1, graph); 
    result = boost::add_edge(c, b, 2, graph); 

    my_visitor vis; 

    breadth_first_search(graph, a, boost::visitor(vis).vertex_index_map(get(boost::vertex_bundle,graph))); 
    return 0; 
} 

Answer 2

I w obliczu tego samego problemu, ale w porównaniu do odpowiedzi udzielonej przez user1252091 mój typ wierzchołka jest struktura, która nie zawiera liczbę całkowitą, która może być użyta do stworzenia vertex_index_map, dlatego linia

nie będzie działać w moim przypadku. W końcu zorientowałem się, jak utworzyć zewnętrzną mapę vertex_index_map (również dzięki this answer) i przekazać ją do funkcji breadth_first_search. Oto działający przykład na wypadek, gdyby pomógł innym:

#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/visitors.hpp> 
#include <boost/graph/breadth_first_search.hpp> 
#include <iostream> 

struct Person 
{ 
    std::string Name; 
    unsigned int YearBorn; 
}; 

typedef boost::adjacency_list <boost::vecS, boost::hash_setS, boost::bidirectionalS, Person, boost::no_property > FamilyTree; 
typedef boost::graph_traits<FamilyTree>::vertex_descriptor Vertex; 
typedef boost::graph_traits<FamilyTree>::edge_descriptor Edge; 

template <class Graph> 
class BfsVisitor : public boost::default_bfs_visitor 
{ 
public: 
    typedef typename boost::graph_traits<Graph>::vertex_descriptor VertexDescriptor; 
    typedef typename boost::graph_traits<Graph>::edge_descriptor EdgeDescriptor; 

    BfsVisitor(std::vector<VertexDescriptor>& nodesVisited) 
    : m_nodesVisited(nodesVisited){} 

    void tree_edge(EdgeDescriptor e, const Graph& g) const 
    { 
     VertexDescriptor u = source(e, g); 
     VertexDescriptor v = target(e, g); 
     m_nodesVisited.push_back(v); 
    } 

private: 
    std::vector<VertexDescriptor>& m_nodesVisited; 
}; 


const Person Abe_Simpson  {"Abe_Simpson", 0}; 
const Person Mona_Simpson  { "Mona_Simpson", 0}; 
const Person Herb_Simpson  { "Herb_Simpson", 0}; 
const Person Homer_Simpson  { "Homer_Simpson", 0}; 

const Person Clancy_Bouvier  { "Clancy_Bouvier", 0}; 
const Person Jacqueline_Bouvier { "Jacqueline_Bouvier", 0}; 
const Person Marge_Bouvier  { "Marge_Bouvier", 0}; 
const Person Patty_Bouvier  { "Patty_Bouvier", 0}; 
const Person Selma_Bouvier  { "Selma_Bouvier", 0}; 

const Person Bart_Simpson  { "Bart_Simpson", 0}; 
const Person Lisa_Simpson  { "Lisa_Simpson", 0}; 
const Person Maggie_Simpson  { "Maggie_Simpson", 0}; 
const Person Ling_Bouvier  { "Ling_Bouvier", 0}; 





int main(void) 
{ 
    std::cout << __FUNCTION__ << "\n"; 

    FamilyTree g; 


    // nodes 
    auto v_Abe_Simpson = boost::add_vertex(Abe_Simpson,g); 
    auto v_Mona_Simpson = boost::add_vertex(Mona_Simpson,g); 
    auto v_Herb_Simpson = boost::add_vertex(Herb_Simpson,g); 
    auto v_Homer_Simpson = boost::add_vertex(Homer_Simpson,g); 

    auto v_Clancy_Bouvier = boost::add_vertex(Clancy_Bouvier,g); 
    auto v_Jacqueline_Bouvier = boost::add_vertex(Jacqueline_Bouvier,g); 
    auto v_Marge_Bouvier = boost::add_vertex(Marge_Bouvier,g); 
    auto v_Patty_Bouvier = boost::add_vertex(Patty_Bouvier,g); 
    auto v_Selma_Bouvier = boost::add_vertex(Selma_Bouvier,g); 

    auto v_Bart_Simpson = boost::add_vertex(Bart_Simpson,g); 
    auto v_Lisa_Simpson = boost::add_vertex(Lisa_Simpson,g); 
    auto v_Maggie_Simpson = boost::add_vertex(Maggie_Simpson,g); 
    auto v_Ling_Bouvier = boost::add_vertex(Ling_Bouvier,g); 

    // connections 
    boost::add_edge(v_Abe_Simpson, v_Herb_Simpson, g); 
    boost::add_edge(v_Abe_Simpson, v_Homer_Simpson, g); 
    boost::add_edge(v_Mona_Simpson, v_Herb_Simpson, g); 
    boost::add_edge(v_Mona_Simpson, v_Homer_Simpson, g); 

    boost::add_edge(v_Clancy_Bouvier, v_Marge_Bouvier, g); 
    boost::add_edge(v_Clancy_Bouvier, v_Patty_Bouvier, g); 
    boost::add_edge(v_Clancy_Bouvier, v_Selma_Bouvier, g); 
    boost::add_edge(v_Jacqueline_Bouvier, v_Marge_Bouvier, g); 
    boost::add_edge(v_Jacqueline_Bouvier, v_Patty_Bouvier, g); 
    boost::add_edge(v_Jacqueline_Bouvier, v_Selma_Bouvier, g); 

    boost::add_edge(v_Homer_Simpson, v_Bart_Simpson, g); 
    boost::add_edge(v_Homer_Simpson, v_Lisa_Simpson, g); 
    boost::add_edge(v_Homer_Simpson, v_Maggie_Simpson, g); 
    boost::add_edge(v_Marge_Bouvier, v_Bart_Simpson, g); 
    boost::add_edge(v_Marge_Bouvier, v_Lisa_Simpson, g); 
    boost::add_edge(v_Marge_Bouvier, v_Maggie_Simpson, g); 

    boost::add_edge(v_Selma_Bouvier, v_Ling_Bouvier, g); 


    typedef std::map<Vertex, size_t>IndexMap; 
    IndexMap mapIndex; 
    boost::associative_property_map<IndexMap> propmapIndex(mapIndex); 
    size_t i=0; 
    FamilyTree::vertex_iterator vi, vi_end; 
    for (boost::tie(vi, vi_end) = boost::vertices(g); vi != vi_end; ++vi) 
    { 
     boost::put(propmapIndex, *vi, i++); 
    } 


    for (boost::tie(vi, vi_end) = boost::vertices(g); vi != vi_end; ++vi) 
    { 
     Vertex vParent = *vi; 

     std::vector<Vertex> vertexDescriptors; 
     BfsVisitor<FamilyTree> bfsVisitor(vertexDescriptors); 
     breadth_first_search(g, vParent, visitor(bfsVisitor).vertex_index_map(propmapIndex)); 


     std::cout << "\nDecendants of " << g[vParent].Name << ":\n"; 
     for (auto v : vertexDescriptors) 
     { 
      Person p = g[v]; 
      std::cout << p.Name << "\n"; 
     } 
    } 

    getchar(); 
    return 0; 
}