具有非连续存储（即！= vecS）和 add_edge() 的最小提升 adjacency_list

Question

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

#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（例如 here）的其他 Whosebug 问题远非最小且没有帮助。）

Answer 1

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

好吧，也许您不这么认为，但是由于向量索引不再 "doubles" 作为顶点 ID，您希望在某处将这些数字附加到顶点描述符。

这 恰好是 你 require/desire 一个属性的原因。我建议使用内部属性如果您希望算法也自动知道如何使用该数字来识别您的索引。

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

具有非连续存储（即！= vecS）和 add_edge() 的最小提升 adjacency_list

Minimal boost adjacency_list with non-contiguous storage (i.e. != vecS) and add_edge()

c++

boost

boost-graph