Boost Graph Library：与 adjacency_matrix 的子图同构

Question

我正在使用 Boost 1.83 和最新的 Cygwin。我在 Boost 1.66 中也遇到了这个问题。

我正在尝试在 adjacency_matrix 上使用 Boost Graph Library 同构函数：

#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <iostream>

//typedef boost::adjacency_list<boost::vecS,
//                boost::vecS,
//                boost::bidirectionalS> Graph;

typedef boost::adjacency_matrix<boost::bidirectionalS> Graph;

int main(int argc, char* argv[]) {

  Graph g_small(3);

  boost::add_edge(0, 1, g_small);
  boost::add_edge(1, 2, g_small);
  boost::add_edge(2, 0, g_small);

  Graph g_large(5);

  boost::add_edge(0, 1, g_large);
  boost::add_edge(1, 2, g_large);
  boost::add_edge(2, 3, g_large);
  boost::add_edge(3, 4, g_large);
  boost::add_edge(4, 2, g_large);

  auto callback = [&](auto f, auto f_inv) {
    std::cout << "isomorphism" << std::endl;
    return true; // give us more isomorphisms if any
  };
  
  boost::vf2_subgraph_iso(g_small, g_large, callback);

  return 0;
}

代码使用邻接列表进行编译，但使用邻接矩阵时出现以下错误（仅显示前几行）。然后它抱怨一些缺失的函数（我假设那些函数位于双向模型中，而不是定向模型中）。

                 from /usr/local/include/boost/container_hash/hash.hpp:27,
                 from /usr/local/include/boost/functional/hash.hpp:6,
                 from /usr/local/include/boost/unordered/unordered_set.hpp:20,
                 from /usr/local/include/boost/unordered_set.hpp:17,
                 from /usr/local/include/boost/graph/adjacency_list.hpp:20,
                 from mwe.cc:1:
/usr/local/include/boost/graph/adjacency_matrix.hpp: In instantiation of ‘class boost::adjacency_matrix<boost::bidirectionalS>’:
mwe.cc:14:16:   required from here
/usr/local/include/boost/graph/adjacency_matrix.hpp:455:5: error: static assertion failed: !(is_same< Directed, bidirectionalS >::value)
  455 |     BOOST_STATIC_ASSERT(!(is_same< Directed, bidirectionalS >::value));
      |     ^~~~~~~~~~~~~~~~~~~
/usr/local/include/boost/graph/adjacency_matrix.hpp:455:5: note: ‘!(bool)boost::integral_constant<bool, true>::value’ evaluates to false

我以为我理解了说明它应该有效的文档......我错过了什么吗？我不能使用 adjacency_list 因为子图同构在大型邻接列表图上似乎太慢了。

编辑：如果我更改我发布到的最小工作示例中的 typedef

typedef boost::adjacency_matrix<boost::directedS> Graph;

我收到一个错误，似乎表示子图函数期望是双向的，但实际上它是定向的。请参阅下面的摘录。

/usr/local/include/boost/graph/graph_concepts.hpp:118:1:   required from ‘static void boost::concepts::requirement<boost::concepts::failed************ Model::************>::failed() [with Model = boost::concepts::BidirectionalGraphConcept<boost::adjacency_matrix<boost::directedS> >]’
/usr/local/include/boost/graph/vf2_sub_graph_iso.hpp:931:9:   required from ‘bool boost::detail::vf2_subgraph_morphism(const GraphSmall&, const GraphLarge&, SubGraphIsoMapCallback, IndexMapSmall, IndexMapLarge, const VertexOrderSmall&, EdgeEquivalencePredicate, VertexEquivalencePredicate)

Answer 1

因此，在深入研究 Boost Graph Library (BGL) 头文件之后，我想我对正在发生的事情有了更好的了解。

Boost 会阻止你，或者更确切地说，阻止你将 bidirectionS 与 adjacency_matrix 一起使用，显然是因为列表 in_edge、列表 out_edge、in_ Degree 和 out_ Degree 函数违反了 BGL 双向图的恒定时间承诺。这是非常令人恼火的，因为 adjacency_list 图违反了 adjacency_matrix 提供的边缘访问的恒定时间承诺，但这并不妨碍您随时使用 adjacency_list 并接受任何权衡结果。

此外，adjacency_matrix 中的一些函数仍未实现，这对于一个有 20 年历史的库来说是相当令人震惊的。近 20 年来，BGL 的开发人员和维护人员似乎除了修复小错误之外没有做任何事情。考虑到当时对图数据结构和算法的所有研究，以及 C++ 中的所有变化，我想说 BGL 确实已经显示出它的时代了。这太糟糕了，因为我喜欢它的想法，并且我喜欢使用它（当它有效时）。

在我的应用程序中，我不关心内存，只关心速度，并且我的大而密集的图在初始创建后是固定的（顶点或边没有变化），所以我真的很想设置一个新的图类型，它使用邻接矩阵和邻接列表，并选择最快的结构来响应任何查询（例如，在查询两个给定顶点之间是否存在边时使用邻接矩阵，在查询顶点的出边时使用邻接列表）。然而，感觉您需要抽象代数博士学位才能建立新的图类型 BGL。我有点夸张，但最重要的是，我可以比让 BGL 做我想做的事情更快地掌握替代方案。

所以，我的问题的解决方案是使用 LEMON 图形库。