使用boost::strong_components时boost::setS容器编译错误咨询

当VertexList和EdgeList使用boost::setS这类关联容器时，Boost图不会自动生成连续的顶点索引属性（vertex_index）。而strong_components算法依赖这个属性来将顶点映射到整数索引，用于存储每个顶点所属的强连通分量编号——这就是编译失败的核心原因。

对比boost::vecS的情况：它的顶点描述符本身就是连续整数，天然满足vertex_index的需求，所以算法能正常运行。

我们需要手动为顶点创建并传递一个vertex_index映射。下面提供两种可行方案：

方案1：为顶点结构体添加索引属性 #

修改顶点结构体，增加index成员，添加顶点时手动赋值，再通过属性映射传递给算法：

#include "boost/graph/adjacency_list.hpp"
#include "boost/graph/strong_components.hpp"
#include <iostream>
#include <vector>

struct Vinfo
{
   int id;
   int index; // 添加顶点索引成员
};
using Graph = boost::adjacency_list<boost::setS, boost::setS, boost::directedS, Vinfo>;
using vertex_t = boost::graph_traits<Graph>::vertex_descriptor;

using namespace boost;
int main()
{
   Graph mygraph;
   vertex_t a = add_vertex({0, 0}, mygraph);
   vertex_t b = add_vertex({2, 1}, mygraph);
   vertex_t c = add_vertex({8, 2}, mygraph);
   vertex_t d = add_vertex({10, 3}, mygraph);
   
   add_edge(a, b, mygraph);
   add_edge(a, c, mygraph);
   add_edge(a, d, mygraph);
   add_edge(d, a, mygraph);
   add_edge(b, c, mygraph);
   add_edge(c, b, mygraph);

   std::vector<int> component(num_vertices(mygraph));
   int num_scc = strong_components(
       mygraph,
       make_iterator_property_map(component.begin(), get(&Vinfo::index, mygraph))
   );
   std::cout << "there are " << num_scc << " strong components" << '\n';
   
   // 可选：打印每个顶点的组件编号
   for (auto v : make_iterator_range(vertices(mygraph))) {
       std::cout << "Vertex id=" << mygraph[v].id << ", component=" << component[mygraph[v].index] << '\n';
   }
   
   return 0;
}

方案2：使用动态关联属性映射（无需修改顶点结构体） #

如果不想修改顶点结构体，可用std::map存储顶点到索引的映射，再通过associative_property_map包装后传递：

#include "boost/graph/adjacency_list.hpp"
#include "boost/graph/strong_components.hpp"
#include <iostream>
#include <vector>
#include <map>

struct Vinfo
{
   int id;
};
using Graph = boost::adjacency_list<boost::setS, boost::setS, boost::directedS, Vinfo>;
using vertex_t = boost::graph_traits<Graph>::vertex_descriptor;

using namespace boost;
int main()
{
   Graph mygraph;
   vertex_t a = add_vertex({0}, mygraph);
   vertex_t b = add_vertex({2}, mygraph);
   vertex_t c = add_vertex({8}, mygraph);
   vertex_t d = add_vertex({10}, mygraph);
   
   add_edge(a, b, mygraph);
   add_edge(a, c, mygraph);
   add_edge(a, d, mygraph);
   add_edge(d, a, mygraph);
   add_edge(b, c, mygraph);
   add_edge(c, b, mygraph);

   // 创建顶点到索引的映射
   std::map<vertex_t, int> vertex_index_map;
   int idx = 0;
   for (auto v : make_iterator_range(vertices(mygraph))) {
       vertex_index_map[v] = idx++;
   }
   auto index_map = make_assoc_property_map(vertex_index_map);

   std::vector<int> component(num_vertices(mygraph));
   int num_scc = strong_components(
       mygraph,
       make_iterator_property_map(component.begin(), index_map)
   );
   std::cout << "there are " << num_scc << " strong components" << '\n';
   
   // 可选：打印每个顶点的组件编号
   for (auto v : make_iterator_range(vertices(mygraph))) {
       std::cout << "Vertex id=" << mygraph[v].id << ", component=" << component[vertex_index_map[v]] << '\n';
   }
   
   return 0;
}

• strong_components的第二个参数需要可读可写的属性映射，用于存储顶点的组件编号，映射的键必须匹配顶点描述符，值为整数类型。
• 非连续容器（如setS）没有默认的vertex_index属性，必须手动提供映射，算法才能完成顶点到整数索引的转换。

内容的提问来源于stack exchange，提问作者Ge Yan