具有非连续存储的最小boost adjacency_list（即！= vecS）和add

我想为算法创建一个图形，该图形需要仅由 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() 的额外要求是什么原因 .

如何使用set或hash set数据类型构建图形，在文档中的哪个位置可以找到我错过的详细信息？

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）远非极小，并没有帮助 . ）

1 回答

我不需要任何额外的自定义顶点属性，也不需要在创建后修改图形 .

好吧，也许不在你的脑海中，但由于矢量索引不再“加倍”作为顶点id，你想要某处将这些数字附加到顶点描述符 .

这恰好是您要求/渴望 property 的理由 . 我建议一个内部属性 if 你希望算法也自动知道如何使用这个数字来识别你的索引 .

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

回复于 2024-05-05T23:06:29+08:00

具有非连续存储的最小boost adjacency_list（即！= vecS）和add_edge（）

1 回答

相关问题