使用Boost adjacency_list执行connected_components，其中VertexList = listS [英] Perform connected_components with Boost adjacency_list where VertexList=listS

问题描述

我在项目中使用Boost图表库，它被声明为：

I use Boost Graph Library in a project and it is declared as:

typedef adjacency_list <listS, listS, undirectedS, TrackInformation, LinkInformation> TracksConnectionGraph;

事情进行得很顺利，直到我在图表上调用connected_components。

Things are going fine until I have to call connected_components on my graph.

typedef std::map<TracksConnectionGraph::vertex_descriptor, TracksConnectionGraph::vertices_size_type> component_type;
component_type component;
boost::associative_property_map< component_type > component_map(component);

int num_components = connected_components(tracks_connection_graph_, component_map);

问题似乎是，如果VertexList = listS，我没有vertex_index作为属性我的顶点。这使得connected_components给我这样的错误：

The problem seems to be that if the VertexList=listS, I do not have vertex_index as a property of my vertex. This makes connected_components give me errors like theses:

/usr/local/include/boost-1_39/boost/property_map.hpp：
在成员函数'R
boost :: iterator_property_map :: operator []（typename
boost :: property_traits :: key_type）
const [With RandomAccessIterator =
__gnu_cxx :: __normal_iterator
，IndexMap = boost :: adj_list_vertex_property_map，
boost :: detail :: error_property_not_found，
const
boost :: detail :: error_property_not_found&，
boost :: vertex_index_t>，T =
boost :: default_color_type，R =
boost :: default_color_type&]'：

/usr/local/include/boost-1_39/boost/property_map.hpp: In member function 'R boost::iterator_property_map::operator[](typename boost::property_traits::key_type) const [with RandomAccessIterator = __gnu_cxx::__normal_iterator , IndexMap = boost::adj_list_vertex_property_map, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t>, T = boost::default_color_type, R = boost::default_color_type&]':

所以问题是：如何添加vertex_index作为我的顶点的属性？

So the question is: how do I add vertex_index as a property of my vertices?

如果我添加它，这意味着每当我调用add_vertex，remove_vertex等，我必须为每个顶点更新此信息？

If I add it, does it mean that whenever I call add_vertex, remove_vertex and such, I have to update this information for each vertex?

推荐答案

您可以添加 vertex_index 属性定义你的图类型（在 adjacency_list 的顶点属性模板参数中，更改 TrackInformation 到 property< vertex_index_t，size_t，TrackInformation> ）。在调用算法之前，您需要使用一个循环来填充属性映射，例如：

You can add a vertex_index property to the definition of your graph type (in the vertex property template argument to adjacency_list, change TrackInformation to property<vertex_index_t, size_t, TrackInformation>). Before calling the algorithm, you will need to fill in the property map using a loop such as:

size_t index = 0;
BGL_FORALL_VERTICES(v, tracks_connection_graph_, TracksConnectionGraph) {
  put(vertex_index, g, v, index++);
}

这篇关于使用Boost adjacency_list执行connected_components，其中VertexList = listS的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！