c++ - 具有非连续存储(即!= vecS)和 add_edge() 的最小 boost adjacency_list

Question

我想为算法创建一个图，该算法需要仅由 adjacency_list 提供的图概念。顶点 ID 本身是随机的 size_t 且不连续，因此使用 vector 作为底层存储是不可能的，但这不会编译:

#include <boost/graph/adjacency_list.hpp>

int main()
{
  using namespace boost;
  using out_edge_storage = setS;
//  using vertex_storage = vecS; // compiles Ok
  using vertex_storage = setS; // error: no matching function for call to 'add_edge'
  using graph = adjacency_list<out_edge_storage, vertex_storage, undirectedS>;
  graph g;
  add_edge(3, 44, g);
  add_edge(1024102400, 3, g); // uses too much space (bad_alloc) with vecS
}

我不需要任何额外的自定义顶点属性，也不需要在创建图形后对其进行修改。通读文档 [1]，我找不到对 add_edge() 的额外要求是什么的原因。

我如何使用集合或散列集合数据类型构建图表，我可以在文档中的哪个位置找到我遗漏的详细信息？

1:http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/using_adjacency_list.html + http://www.boost.org/doc/libs/1_63_0/libs/graph/doc/adjacency_list.html

(关于 adjacency_list+vecS 的其他 stackoverflow 问题(例如 here)远非最小且没有帮助。)

Answer 1

I do not need any extra custom vertex properties nor do I need to modify the graph after creating it.

好吧，也许您不这么认为，但是由于 vector 索引不再“兼作”顶点 ID，您希望在某个地方将这些数字附加到顶点描述符。

这恰好是您要求/渴望属性(property)的理由。 如果您希望算法也自动知道如何使用该数字来识别您的索引，我建议使用内部属性。

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>

using graph = boost::adjacency_list<boost::setS, boost::setS, boost::undirectedS, 
    boost::property<boost::vertex_index_t, size_t> >;

int main() {
    graph g;
    auto A = add_vertex(3, g);
    auto B = add_vertex(44, g);
    auto C = add_vertex(1024102400, g);
    add_edge(A, B, g);
    add_edge(C, A, g);

    print_graph(g);
}

打印:

3 <--> 44 1024102400 
44 <--> 3 
1024102400 <--> 3