在无向图的DFS搜索中记录前辈 [英] Recording predecessors in a DFS search in an undirected graph
问题描述
我正尝试使用此线程中的代码: Boost DFS back_edge ,以将循环记录在无向图中.为此,我需要为每个dfs树在找到back_edge时存储predecessors
.由于这是无向图,因此我认为我们不能直接从 EventVisitor概念.因此,我正在考虑在以下代码的void back_edge()
方法中记录其前身.但是我不确定如何执行此操作并返回循环顶点.
I was trying to use the code from this thread: Boost DFS back_edge, to record the cycles in an undirected graph. To do this I need to store the predecessors
for each dfs tree when it finds a back_edge. Since this is an undirected graph I think we can not use directly on_back_edge()
from EventVisitor Concept. So I was thinking to record the predecessors in the void back_edge()
method of below code. But I am not sure how to do this and return the cycle vertices.
这是我为录制前辈而添加的代码和部分:
Here is the code and the part I added for recording predecessors:
#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));
}
推荐答案
这里是一个快速的帖子,我稍后会再提供一些注释
Here's a quick post, I'll come back with some notes later
#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
这篇关于在无向图的DFS搜索中记录前辈的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!