c++ - Boost 图形库 undirected_graph : how to specify the vertex type (e. g。作为整数)？

Question

是否可以修复 boost::undirected_graph 中的顶点类型例如，'int'？

“int”顶点类型似乎是 boost::adjacency_list 的默认值，并且以下代码有效:

boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS> g;
boost::add_edge(0 , 1 , g);

但因 undirected_graph 而失败。我应该执行哪些额外步骤才能使用相同的语法将顶点添加到 undirected_graph？

我需要使用 bron_kerbosch_all_cliques只接受 undirected_graph 作为输入的算法。

谢谢

Answer 1

I need to use a bron_kerbosch_all_cliques algorithm which only accepts undirected_graph as input.

消息来源告诉我它接受通用图形(就像 BGL 所做的那样):

• http://www.boost.org/doc/libs/1_57_0/boost/graph/bron_kerbosch_all_cliques.hpp

文档很难找到(可能是 quickbook 定义中的错误？)，但这里有:

Requirements: The Graph type must be a model of the AdjacencyMatrix, IncidenceGraph concept and the VertexIndexGraph concepts. [¹ Any Graph type that implements the edge() function will satisfy the expression requirements for the AdjacencyMatrix, but may incur additional overhead due non-constant time complexity.].

前往 BGL 文档中的概念页面，查看符合要求的图表类型。

我看到可能的“缺失链接”是 VertexIndexGraph 概念。您可能可以通过添加 vertex_index_t Interior Property 来实现此目的