不断变化的图形内容在DFS的boost ::图 [英] DFS in boost::graph with changing the graphs content
问题描述
小例子:
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
struct vertex
{
int number;
};
struct edge {};
typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, vertex, edge> graph_t;
typedef boost::graph_traits<graph_t>::vertex_descriptor vertex_t;
typedef boost::graph_traits<graph_t>::edge_descriptor edge_t;
struct vertex_visitor : public boost::default_dfs_visitor
{
void discover_vertex(vertex_t v, graph_t& g)
{
g[v].number = 42;
}
};
int main()
{
graph_t g;
vertex_t v1 = boost::add_vertex(g);
vertex_t v2 = boost::add_vertex(g);
boost::add_edge(v1, v2, g);
vertex_visitor vis;
boost::depth_first_search(g, boost::visitor(vis));
return 0;
}
它不起作用,因为图需要为常量
在 vertex_visitor :: discover_vertex被引用()
。
有没有什么更好的方法,做我想做的不是写我自己的DFS算法(或使用的const_cast
)?此外,没有你的解决方案允许添加/删除边和顶点,同时发现一个顶点?
Is there any better method to do what I want than writing my own DFS algorithm (or using const_cast
)? Also, does your solution allow to add/delete edges and vertices while discovering a vertex?
推荐答案
看一看如何提升农具<一个href=\"http://www.boost.org/doc/libs/1_55_0/boost/graph/connected_components.hpp\">connected_components.为了存储组件id下面访问者使用
Have a look at how Boost implements connected_components. In order to store the component id the following visitor is used:
// This visitor is used both in the connected_components algorithm
// and in the kosaraju strong components algorithm during the
// second DFS traversal.
template <class ComponentsMap>
class components_recorder : public dfs_visitor<>
{
typedef typename property_traits<ComponentsMap>::value_type comp_type;
public:
components_recorder(ComponentsMap c,
comp_type& c_count)
: m_component(c), m_count(c_count) {}
template <class Vertex, class Graph>
void start_vertex(Vertex, Graph&) {
if (m_count == (std::numeric_limits<comp_type>::max)())
m_count = 0; // start counting components at zero
else
++m_count;
}
template <class Vertex, class Graph>
void discover_vertex(Vertex u, Graph&) {
put(m_component, u, m_count);
}
protected:
ComponentsMap m_component;
comp_type& m_count;
};
的想法是,一个属性映射被传递到访问者的构造,并稍后用于更新数据。与您的例子中, vertex_visitor
可以通过以下方式进行改写:
The idea is that a property map is passed to the constructor of the visitor, and is later used to update the data. Relating to your example, the vertex_visitor
could be rewritten in the following way:
template <class PropertyMap>
struct vertex_visitor : public boost::dfs_visitor<>
{
PropertyMap m_pmap;
vertex_visitor(PropertyMap pmap) : m_pmap(pmap) {}
template <class Vertex, class Graph>
void discover_vertex(Vertex v, const Graph& g)
{
boost::put(m_pmap, v, 42);
}
};
该游客的实例化是有点令人费解,因为我们需要明确指定属性映射类型:
Instantiation of this visitor is a bit convoluted because we need to specify the property map type explicitly:
typedef boost::property_map<graph_t, int vertex::*>::type NumbersProperty;
vertex_visitor<NumbersProperty> vis(boost::get(&vertex::number, g));
作为每问题的最后部分,图形结构(即增加或顶点和边的缺失)的突变无效interators,所以这会破坏在DFS算法。我认为这是precisely为什么图由常量引用传递的原因。
As per the last part of the question, mutation of graph structure (i.e. addition or deletion of vertices and edges) invalidates interators, so this would break the DFS algorithm. I think this is precisely the reason why the graph is passed by const-reference.
这篇关于不断变化的图形内容在DFS的boost ::图的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!