c++ - 每个组件 boost 库中的顶点数

Question

我是新的 boost 库(windows 7\visual studio 2010)。我遵循了这个示例代码:

#include <boost/config.hpp>
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>


using namespace std;

int main(int , char* []) 
{
  using namespace boost;
  {
    typedef adjacency_list <vecS, vecS, undirectedS> Graph;

    Graph G;
    add_edge(0, 1, G);
    add_edge(1, 4, G);
    add_edge(4, 0, G);
    add_edge(2, 5, G);
    
    std::vector<int> component(num_vertices(G));

    int num = connected_components(G, &component[0]);
    
    std::vector<int>::size_type i;
    cout << "Total number of components: " << num << endl;
    for (i = 0; i != component.size(); ++i)
      cout << "Vertex " << i <<" is in component " << component[i] << endl;
    cout << endl;
  }
  return 0;
}

代码构建图形并通过 for 循环打印哪个顶点属于哪个组件。

是否有一个获取图形并返回\存储哪个顶点属于哪个组件的函数示例 - 以有组织的方式(某种数据结构)？而不是 for 循环？

我试图搜索 here ，希望我没有错过。

谢谢。

编辑:目标是对每个组件进行测量(例如节点数、直径、一个组件中每个节点的邻居数..)

Answer 1

我建议使用关联属性映射:

std::map<Graph::vertex_descriptor, Graph::vertices_size_type> map;

auto const num = connected_components(G, make_assoc_property_map(map));
std::cout << "Total number of components: " << num << std::endl;

for (auto& e : map)
    std::cout << "Vertex " << e.first << " is in component " << e.second << std::endl;

当然，现在的谜底是，如何有效的得到反向图呢？

---

^{(同时，生活发生了......)}

---

抱歉写这篇文章时没劲了。这里有一个指向早期文章的链接，希望它可以作为获取双向关联 可写 属性映射的灵感(在另一个 BGL 调用的上下文中，但您可以想象这种连接)。

• Cut set of a graph, Boost Graph Library

稍微相关的示例:

• Using boost::associative property map with boost::BIMAP interface
• Insert into boost::BIMAP using BOOST::associative property map ... failed