我想为算法创建一个图,该算法需要仅由 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)远非最小且没有帮助。)
最佳答案
I do not need any extra custom vertex properties nor do I need to modify the graph after creating it.
好吧,也许您不这么认为,但是由于 vector 索引不再“兼作”顶点 ID,您希望在某个地方将这些数字附加到顶点描述符。
这恰好是您要求/渴望属性(property)的理由。 如果您希望算法也自动知道如何使用该数字来识别您的索引,我建议使用内部属性。
#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
关于c++ - 具有非连续存储(即!= vecS)和 add_edge() 的最小 boost adjacency_list,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43473029/