無向グラフのDFS検索における先行レコードの記録

Question

このスレッドのコードをBoost DFS back_edgeとし、無作為のグラフにサイクルを記録しようとしました。これを行うには、back_edgeが見つかると、各dfsツリーにpredecessorsを格納する必要があります。これは無向グラフなので、直接on_back_edge()をEventVisitor Conceptから使うことはできないと思います。だから私は、コードの下のvoid back_edge()メソッドの先任者を記録することを考えていた。しかし、私はどのようにこれを行い、サイクルの頂点を返すかわかりません。ここで

は、コードと私は前任者を記録するための追加の部分である：ここでは簡単のポストだ

#include <boost/config.hpp> 
#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/depth_first_search.hpp> 

namespace { 
using namespace boost; 

    typedef adjacency_list<vecS, vecS, undirectedS, no_property, 
    property<edge_weight_t, int> > Graph; 
    typedef graph_traits<Graph>::edge_descriptor Edge; 
    typedef std::set<Edge> EdgeSet; 
} 

struct MyVisitorCycle : default_dfs_visitor { 
MyVisitorCycle(EdgeSet &tree_edges, vector<vector<vertex_t> > &cycles1) : 
     tree_edges(tree_edges), cycles(cycles1) {} 

    void tree_edge(Edge e, const Graph& g) const { 
    std::cerr << "tree_edge " << e << std::endl; 
    tree_edges.insert(e); 
    } 
    void back_edge(Edge e, const Graph& g) const { 
    if (tree_edges.find(e) == tree_edges.end()) 
     std::cerr << "back_edge " << e << std::endl; 

    /// I added this part 
    vertex_t s = vertex (0,g); 
    std::vector <vertex_t> p(num_vertices (g)); 
    depth_first_search (g, s, visitor (boost::record_predecessors (&p[0], 
            on_tree_edge())));/// here has problem 
    p.push_back (target (e,g)); /// close the cycle 
    cycles.push_back (p); 
    } 

    private: 
    EdgeSet& tree_edges; 
    vector<vector <vertex_t> > &cycles; 
}; 

int main() { 
    Graph g; 
    add_edge(0, 1, g); 
    add_edge(1, 2, g); 
    add_edge(2, 3, g); 
    add_edge(3, 0, g); 
    add_edge(1, 4, g); 
    add_edge(4, 5, g); 
    add_edge(5, 6, g); 
    add_edge(6, 3, g); 
    add_edge(2, 5, g); 

    std::set<Edge> tree_edges; 
    vector<vector <vertex_t> > cycles; 
    MyVisitorCycle vis(tree_edges, cycles); 

    depth_first_search(g, visitor(vis)); 
} 

Answer 1

、私は後で

Live On Coliru

いくつかのメモで戻ってきます

#include <iostream> 
#include <boost/config.hpp> 
#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/depth_first_search.hpp> 

namespace { 
    using namespace boost; 

    typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> > Graph; 
    typedef graph_traits<Graph>::edge_descriptor Edge; 
    typedef std::set<Edge> EdgeSet; 
} 

struct MyVisitor : default_dfs_visitor { 
    MyVisitor(EdgeSet& tree_edges) : tree_edges(tree_edges) {} 

    void tree_edge(Edge e, const Graph& g) const { 
     std::cerr << "tree_edge " << e << std::endl; 
     tree_edges.insert(e); 
    } 
    void back_edge(Edge e, const Graph& g) const { 
     if (tree_edges.find(e) == tree_edges.end()) 
      std::cerr << "back_edge " << e << std::endl; 
    } 

    private: 
    EdgeSet& tree_edges; 
}; 

int main() { 
    Graph g; 
    add_edge(0, 1, g); 
    add_edge(0, 2, g); 

    std::set<Edge> tree_edges; 
    MyVisitor vis(tree_edges); 


    std::vector<Graph::vertex_descriptor> pred(num_vertices(g), Graph::null_vertex()); 

    depth_first_search(g, visitor(boost::make_dfs_visitor(
      boost::record_predecessors(pred.data(), boost::on_back_edge{}) 
     ))); 

    for (auto v : make_iterator_range(vertices(g))) { 
     std::cout << "Predecessor for " << v << " is " << pred.at(v) << "\n"; 
    } 
} 

プリント

Predecessor for 0 is 2 
Predecessor for 1 is 18446744073709551615 
Predecessor for 2 is 18446744073709551615