我试图使用此线程中的代码:提升DFS back_edge https://stackoverflow.com/questions/19346820/boost-dfs-back-edge/19391511?noredirect=1#comment81785237_19391511,在无向图中记录循环。为此,我需要存储predecessors
对于每个 dfs 树,当它找到 back_edge 时。由于这是一个无向图我认为我们不能直接使用on_back_edge()
from 活动访客概念 http://www.boost.org/doc/libs/1_57_0/libs/graph/doc/EventVisitor.html。于是我就想把前辈们记录下来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));
}