Cách sử dụng biểu đồ đi ngang khi sử dụng tăng BFS

Question

Tôi gặp vấn đề khi biên dịch BFS của biểu đồ rất đơn giản. Bất cứ điều gì tôi làm tôi có thông điệp biên dịch khác nhau về các cuộc gọi phương pháp chưa từng có (Tôi đã thử boost::visitor và mở rộng boost::default_bfs_visitor, vv)

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

Làm thế nào để tham quan biểu đồ sử dụng bfs_visitor?

PS. Tôi đã xem và biên soạn "How to create a C++ Boost undirected graph and traverse it in depth first search (DFS) order?" nhưng nó không giúp được gì.

Answer 1

Bạn có thể xem here danh sách các tình trạng quá tải của breadth_first_search. Nếu bạn không muốn chỉ định từng tham số bạn cần sử dụng phiên bản có tên tham số. Nó sẽ giống như thế này:

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

này sẽ làm việc như là nếu bạn đã sử dụng vecS như lưu trữ VertexList của bạn trong định nghĩa đồ thị của bạn hoặc nếu bạn đã xây dựng và khởi tạo một bản đồ nội bộ tài sản vertex_index. Vì bạn đang sử dụng hash_setS bạn cần phải thay đổi để gọi:

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

Bạn đang sử dụng một bản đồ chỉ mục trong tài sản kèm uint32_t của bạn. Bạn có thể sử dụng get(boost::vertex_bundle, graph) để truy cập.

Cũng có sự cố với khách truy cập của bạn. Bạn nên lấy nó từ boost::default_bfs_visitor và tham số graph_t của các hàm thành viên của bạn cần phải đủ điều kiện.

Full mã:

#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

tôi phải đối mặt với cùng một vấn đề, nhưng so với các câu trả lời được cung cấp bởi user1252091 loại đỉnh của tôi là một struct mà không bao gồm một số nguyên có thể được sử dụng để tạo ra một vertex_index_map, do đó, dòng

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

sẽ không hoạt động trong trường hợp của tôi. Cuối cùng tôi đã tìm ra cách tạo ra một vertex_index_map bên ngoài (cũng nhờ vào this answer) và chuyển nó tới hàm breadth_first_search. Dưới đây là ví dụ hoạt động trong trường hợp nó giúp người khác:

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