Boost Graph Library：具有 adjacency_matrix 的子图同构

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

Boost 不鼓励你，或者更确切地说，阻止你将双向 S 与 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 图形库。

我同意这种“清教徒”的限制，即您不得将 AdjacencyMatrix 用作（穷人的）BidirectionalGraph，即使只是为了玩弄/比较。

事实证明，说服图书馆“相信我，我知道我在做什么”是很容易的。您需要一种独特的图形类型，可以将特征专用于：

struct Graph : boost::adjacency_matrix<boost::directedS> {
    using Impl = boost::adjacency_matrix<boost::directedS>;
};

现在你有一个可以撒谎的类型：

namespace boost {
    template <> struct graph_traits<Graph> : graph_traits<Graph::Impl> {
        struct traversal_category
            : boost::bidirectional_graph_tag
            , Graph::Impl::traversal_category {};
    };

    // O(2N)
    auto degree(Graph::vertex_descriptor u, Graph const& g) {
        return size(out_edges(u, g)) + size(in_edges(u, g));
    }
}; // namespace boost

就这样：

在 Coliru 上直播

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

struct Graph : boost::adjacency_matrix<boost::directedS> {
    using Impl = boost::adjacency_matrix<boost::directedS>;
    // using Impl::Impl;
    // using Impl::operator=;
};

namespace boost {
    template <> struct graph_traits<Graph> : graph_traits<Graph::Impl> {
        struct traversal_category
            : boost::bidirectional_graph_tag
            , Graph::Impl::traversal_category {};
    };

    // O(2N)
    auto degree(Graph::vertex_descriptor u, Graph const& g) {
        return size(out_edges(u, g)) + size(in_edges(u, g));
    }
}; // namespace boost

int main() {
    Graph g_small(3);

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

    Graph g_large(5);

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

    auto callback = [&](auto f, auto /*f_inv*/) {
        std::cout << "isomorphism";
        for (auto v : boost::make_iterator_range(vertices(g_small))) {
            std::cout << " " << v << "->" << f[v];
        }
        std::cout << std::endl;
        return true; // give us more isomorphisms if any
    };

    vf2_subgraph_iso(g_small, g_large, callback);
}

打印输出

isomorphism 0->2 1->3 2->4
isomorphism 0->3 1->4 2->2
isomorphism 0->4 1->2 2->3

结束语

YMMV：当然，性能不会是最佳的，但正如你所说，大多数其他型号也不会。如果你能够预先计算/缓存每个顶点的度数，你可能会有你的蛋糕并吃掉它。根据您的域逻辑，这可能很容易添加。