c++ - Boost Graph Library undirected_graph：如何指定顶点类型（如int）？

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

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

消息来源告诉我它接受通用图（就像 BGL 一样）：

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

文档很难找到（可能是快速手册定义中的错误？），但这里有：

要求：类型Graph必须是AdjacencyMatrix、 IncidenceGraph概念和VertexIndexGraph 概念的模型。[¹ 任何Graph实现该edge() 函数的类型都将满足 的表达式要求 AdjacencyMatrix，但由于非恒定的时间复杂度可能会产生额外的开销。]。

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

我看到可能的“缺失环节”是 VertexIndexGraph 概念。您可以通过添加vertex_index_t 内部属性来实现此目的