如何使用C++ Boost图形库（BGL）来找到同构图？

Question

如何使用C++ Boost图形库（BGL）来找到同构图？

c++boostgraph-theoryboost-graphisomorphism

4

使用C++ Boost Graph Library (BGL)查找同构图

我想获取同构的图形（尊重类型 - A / B）。当然，所有连接数不相同的图形都会在开始时被筛除。

# So the matching structures are the ones in the green box: 
nodes: {A,B,B,B}; bonds: {{0,1},{1,2},{1,3}}
nodes: {B,B,B,A}; bonds: {{3,2},{2,0},{3,1}}
nodes: {B,B,B,A}; bonds: {{0,1},{1,2},{1,3}}

# The structures in the red box are not expected to be the same:
nodes: {B,A,B,B}; bonds: {{0,1},{1,2},{1,3}}
nodes: {B,B,B,B}; bonds: {{0,1},{1,2},{1,3}}
nodes: {A,B,B};   bonds: {{0,1},{1,2}}

// (C) Copyright Jeremy Siek 2001.
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

#include <boost/config.hpp>
#include <iostream>
#include <boost/graph/isomorphism.hpp>
#include <boost/graph/adjacency_list.hpp>

#include <boost/graph/graph_utility.hpp>

/*
  Sample output:
  isomorphic? 1
  f: 9 10 11 0 1 3 2 4 6 8 7 5 
 */

int
main()
{
  using namespace boost;
  
  const int n = 12;

  typedef adjacency_list<vecS, listS, undirectedS,
    property<vertex_index_t, int> > graph_t;
  graph_t g1(n), g2(n);

  std::vector<graph_traits<graph_t>::vertex_descriptor> v1(n), v2(n);

  property_map<graph_t, vertex_index_t>::type 
    v1_index_map = get(vertex_index, g1),
    v2_index_map = get(vertex_index, g2);

  graph_traits<graph_t>::vertex_iterator i, end;
  int id = 0;
  for (tie(i, end) = vertices(g1); i != end; ++i, ++id) {
    put(v1_index_map, *i, id);
    v1[id] = *i;
  }
  id = 0;
  for (tie(i, end) = vertices(g2); i != end; ++i, ++id) {
    put(v2_index_map, *i, id);
    v2[id] = *i;
  }
  add_edge(v1[0], v1[1], g1); add_edge(v1[1], v1[2], g1); 
  add_edge(v1[0], v1[2], g1);
  add_edge(v1[3], v1[4], g1);  add_edge(v1[4], v1[5], g1);
  add_edge(v1[5], v1[6], g1);  add_edge(v1[6], v1[3], g1);
  add_edge(v1[7], v1[8], g1);  add_edge(v1[8], v1[9], g1);
  add_edge(v1[9], v1[10], g1);
  add_edge(v1[10], v1[11], g1);  add_edge(v1[11], v1[7], g1);

  add_edge(v2[9], v2[10], g2);  add_edge(v2[10], v2[11], g2);  
  add_edge(v2[11], v2[9], g2);
  add_edge(v2[0], v2[1], g2);  add_edge(v2[1], v2[3], g2); 
  add_edge(v2[3], v2[2], g2);  add_edge(v2[2], v2[0], g2);
  add_edge(v2[4], v2[5], g2); add_edge(v2[5], v2[7], g2); 
  add_edge(v2[7], v2[8], g2);
  add_edge(v2[8], v2[6], g2); add_edge(v2[6], v2[4], g2);

  std::vector<graph_traits<graph_t>::vertex_descriptor> f(n);

  bool ret = isomorphism
    (g1, g2, isomorphism_map
     (make_iterator_property_map(f.begin(), v1_index_map, f[0])));

  std::cout << "isomorphic? " << ret << std::endl;

  std::cout << "f: ";
  for (std::size_t v = 0; v != f.size(); ++v)
    std::cout << get(get(vertex_index, g2), f[v]) << " ";
  std::cout << std::endl;
  
  return 0;
}

这是我尝试使用Boost的最小示例。如果Boost是正确的库，我会非常感激任何人能向我展示如何实现它？

- michael

这是我尝试让Boost工作的最小示例。看起来你忘记添加实际代码了。 - sehe

这大致是我的起点，我正在尝试扩展它：https://cs.brown.edu/~jwicks/boost/libs/graph/example/isomorphism.cpp。如果您能指点我正确的方向，那就太好了。 - michael

@sehe，当然。我已经更新了原始问题。 - michael

1

这就是手册的作用。 - n. m.

@n.m. 为了保护OP，这个示例代码实际上是不必要复杂的。我也会从那里开始遇到麻烦。 - sehe

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sehe · Accepted Answer

所以，您发布了来自Boost库的示例。在2019年之前的某个版本。

显然，那不会代表您的图形。首先要现代化：

实时

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/isomorphism.hpp>
#include <iostream>
using boost::make_iterator_range;

int main() {
    constexpr int n = 12;

    using graph_t = boost::adjacency_list<boost::vecS, boost::listS, boost::undirectedS,
                                          boost::property<boost::vertex_index_t, int>>;
    graph_t g1(n), g2(n);
    using V = graph_t::vertex_descriptor;

    std::vector<V> v1(n), v2(n);

    auto v1_index_map = get(boost::vertex_index, g1);
    auto v2_index_map = get(boost::vertex_index, g2);

    for (int id = 0; auto v : make_iterator_range(vertices(g1))) {
        v1_index_map[v] = id;
        v1[id]          = v;
        ++id;
    }
    for (int id = 0; auto v : make_iterator_range(vertices(g2))) {
        v2_index_map[v] = id;
        v2[id]          = v;
        ++id;
    }

    add_edge(v1[0], v1[1], g1);
    add_edge(v1[1], v1[2], g1);
    add_edge(v1[0], v1[2], g1);
    add_edge(v1[3], v1[4], g1);
    add_edge(v1[4], v1[5], g1);
    add_edge(v1[5], v1[6], g1);
    add_edge(v1[6], v1[3], g1);
    add_edge(v1[7], v1[8], g1);
    add_edge(v1[8], v1[9], g1);
    add_edge(v1[9], v1[10], g1);
    add_edge(v1[10], v1[11], g1);
    add_edge(v1[11], v1[7], g1);

    add_edge(v2[9], v2[10], g2);
    add_edge(v2[10], v2[11], g2);
    add_edge(v2[11], v2[9], g2);
    add_edge(v2[0], v2[1], g2);
    add_edge(v2[1], v2[3], g2);
    add_edge(v2[3], v2[2], g2);
    add_edge(v2[2], v2[0], g2);
    add_edge(v2[4], v2[5], g2);
    add_edge(v2[5], v2[7], g2);
    add_edge(v2[7], v2[8], g2);
    add_edge(v2[8], v2[6], g2);
    add_edge(v2[6], v2[4], g2);

    std::vector<V> f(n);

    bool ret = isomorphism(g1, g2, isomorphism_map(make_iterator_property_map(f.begin(), v1_index_map)));

    std::cout << "isomorphic? " << std::boolalpha << ret << std::endl;

    for (std::cout << "f: "; auto el : f)
        std::cout << get(v2_index_map, el) << " ";
    std::cout << std::endl;
}

接下来，简化一下，因为您没有告诉我们不使用vecS提供的内在顶点索引的原因：

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/isomorphism.hpp>
#include <iostream>

int main() {
    using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
    using V = G::vertex_descriptor;

    constexpr int n = 12;
    G g1(n);
    G g2(n);

    for (auto [s, t] : {std::pair{0, 1}, {1, 2}, {0, 2}, {3, 4}, {4, 5}, {5, 6},
                        {6, 3}, {7, 8}, {8, 9}, {9, 10}, {10, 11}, {11, 7}})
    {
        add_edge(s, t, g1);
    }
    for (auto [s, t] : {std::pair{9, 10}, {10, 11}, {11, 9}, {0, 1}, {1, 3}, {3, 2},
                        {2, 0}, {4, 5}, {5, 7}, {7, 8}, {8, 6}, {6, 4}})
    {
        add_edge(s, t, g2);
    }

    std::vector<V> f(n);

    bool ret = isomorphism(g1, g2, boost::isomorphism_map(f.data()));

    std::cout << "isomorphic? " << std::boolalpha << ret << std::endl;

    for (std::cout << "f: "; auto v : f)
        std::cout << v << " ";
    std::cout << std::endl;
}

添加数据

由于您需要类型（A/B），因此让我们将其添加到顶点属性中：

struct Node {
    enum Type {A,B} type;
};
using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Node>;

我们也来创建一下键合图：

using Bond = std::pair<V, V>;

struct Input {
    std::vector<Type> nodes;
    std::vector<Bond> bonds;
};

using Problem = std::vector<Input>;

现在你可以用代码来表述问题：

Problem green = {{{A, B, B, B}, {{0, 1}, {1, 2}, {1, 3}}},
                 {{B, B, B, A}, {{3, 2}, {2, 0}, {3, 1}}},
                 {{B, B, B, A}, {{0, 1}, {1, 2}, {1, 3}}}};
Problem red   = {{{B, A, B, B}, {{0, 1}, {1, 2}, {1, 3}}},
                 {{B, B, B, B}, {{0, 1}, {1, 2}, {1, 3}}},
                 {{A, B, B}, {{0, 1}, {1, 2}}}};

Note

Close inspection turns up multiple errors in that representation, so I'll be using my own fixed representation:

Problem green = {{{A, B, B, B}, {{0, 1}, {1, 2}, {1, 3}}},
                 {{B, B, B, A}, {{3, 2}, {2, 0}, {2, 1}}},
                 {{B, B, A, B}, {{0, 1}, {1, 2}, {1, 3}}}};
Problem red   = {{{B, A, B, B}, {{0, 1}, {1, 2}, {1, 3}}},
                 {{B, B, B, B}, {{0, 1}, {1, 2}, {1, 3}}},
                 {{A, B, B}, {{0, 1}, {1, 2}}}};

让我们来实现我们的解决方案：

Graph toGraph(Input const& input);
bool compare(Graph const& a, Graph const& b);
bool solve(Problem const& p);

实际上，toGraph 是一个一对一的辅助方法，用于将输入转换为邻接表:

Graph toGraph(Input const& input) {
    auto  N = input.nodes.size();
    Graph g(begin(input.bonds), end(input.bonds), N);
    for (size_t n = 0; n < N; ++n)
        g[n].type = input.nodes.at(n);
    return g;
}

compare 只是像以前一样包装了对 isomorphism 的调用：

bool compare(Graph const& a, Graph const& b) {
    auto n = num_vertices(a);
    std::vector<V> f(n);

    bool ok =                  //
        (n == num_vertices(b)) //
        && isomorphism(a, b, boost::isomorphism_map(f.data()));

    debug << "isomorphism " << std::boolalpha << ok;

    if (ok)
        for (debug << " f: "; auto v : f)
            debug << v << " ";
    debug << std::endl;
    
    return ok;
}

“我不赞成将输出与逻辑混合在一起，但这可能有助于说明答案，因此我将其留在可以启用的“debug”流下面。”

“现在，解决问题可以通过比较问题中所有图形对来完成：”

bool solve(Problem const& p) {
    std::vector<Graph> gg;
    transform(begin(p), end(p), back_inserter(gg), toGraph);

    assert(gg.size() == 3);
    return compare(gg[0], gg[1]) && compare(gg[1], gg[2]);
}

实际上，我还会添加调试输出来验证图表：

    for (auto& g : gg) {
        auto name = make_transform_value_property_map(
            [&](V v) { return "AB"[g[v].type] + std::to_string(v); }, get(boost::vertex_index, g));
        print_graph(g, name, debug << " --\n");
    }

当然，我们不是没有理由地将问题设置为动态大小的，所以让我们使用算法进行泛化：

bool solve(Problem const& p) {
    std::vector<Graph> gg;
    transform(begin(p), end(p), back_inserter(gg), toGraph);

    for (auto& g : gg) {
        auto name = make_transform_value_property_map(
            [&](V v) { return "AB"[g[v].type] + std::to_string(v); }, get(boost::vertex_index, g));
        print_graph(g, name, debug << " --\n");
    }

    auto mismatch = [](Graph const& a, Graph const& b) { return !compare(a, b); };
    return end(gg) == adjacent_find(begin(gg), end(gg), mismatch);
}

演示时间

在 Coliru 上实时演示

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/isomorphism.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <iostream>

static std::ostream debug(nullptr);

enum Type { A, B };
struct Node {
    Type type;
};

using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Node>;
using V     = Graph::vertex_descriptor;
using Bond  = std::pair<V, V>;

struct Input {
    std::vector<Type> nodes;
    std::vector<Bond> bonds;
};

using Problem = std::vector<Input>;

Graph toGraph(Input const& input) {
    auto N = input.nodes.size();
    Graph    g(begin(input.bonds), end(input.bonds), N);
    for (size_t n = 0; n < N; ++n)
        g[n].type = input.nodes.at(n);
    return g;
}

bool compare(Graph const& a, Graph const& b) {
    auto n = num_vertices(a);
    std::vector<V> f(n);

    bool ok =                  //
        (n == num_vertices(b)) //
        && isomorphism(a, b, boost::isomorphism_map(f.data()));

    debug << "isomorphism " << std::boolalpha << ok;

    if (ok)
        for (debug << " f: "; auto v : f)
            debug << v << " ";
    debug << std::endl;
    
    return ok;
}

bool solve(Problem const& p) {
    std::vector<Graph> gg;
    transform(begin(p), end(p), back_inserter(gg), toGraph);

    for (auto& g : gg) {
        auto name = make_transform_value_property_map(
            [&](V v) { return "AB"[g[v].type] + std::to_string(v); }, get(boost::vertex_index, g));
        print_graph(g, name, debug << " --\n");
    }

    auto mismatch = [](Graph const& a, Graph const& b) { return !compare(a, b); };
    return end(gg) == adjacent_find(begin(gg), end(gg), mismatch);
}

int main() {
    debug.rdbuf(std::cout.rdbuf()); // verbose

    debug << "green ---\n";
    bool ok = solve({{{A, B, B, B}, {{0, 1}, {1, 2}, {1, 3}}},
                     {{B, B, B, A}, {{3, 2}, {2, 0}, {2, 1}}},
                     {{B, B, A, B}, {{0, 1}, {1, 2}, {1, 3}}}});
    std::cout << " -> green problem solves " << std::boolalpha << ok << std::endl;

    debug << "red ---\n";
    ok = solve({{{B, A, B, B}, {{0, 1}, {1, 2}, {1, 3}}},
                {{B, B, B, B}, {{0, 1}, {1, 2}, {1, 3}}},
                {{A, B, B}, {{0, 1}, {1, 2}}}});
    std::cout << " -> red problem solves " << std::boolalpha << ok << std::endl;
}

打印

green ---
 --
A0 <--> B1 
B1 <--> A0 B2 B3 
B2 <--> B1 
B3 <--> B1 
 --
B0 <--> B2 
B1 <--> B2 
B2 <--> A3 B0 B1 
A3 <--> B2 
 --
B0 <--> B1 
B1 <--> B0 A2 B3 
A2 <--> B1 
B3 <--> B1 
isomorphism true f: 3 2 0 1 
isomorphism true f: 2 3 1 0 
 -> green problem solves true
red ---
 --
B0 <--> A1 
A1 <--> B0 B2 B3 
B2 <--> A1 
B3 <--> A1 
 --
B0 <--> B1 
B1 <--> B0 B2 B3 
B2 <--> B1 
B3 <--> B1 
 --
A0 <--> B1 
B1 <--> A0 B2 
B2 <--> B1 
isomorphism true f: 0 1 2 3 
isomorphism false
 -> red problem solves false

或者，禁用调试只需打印：

-> 绿色问题解决为真 -> 红色问题解决为假

还有什么疑问吗？

我很高兴指出，这个最终程序通过广泛的调试输出解决了整个两个问题，在比你开始的示例少 10行代码 的情况下。

请注意，你在问题中提到：

我想要获取同构的图形（尊重类型 - A/B）_

现在不清楚你的意思。你似乎期望绿色框匹配，但很明显第三个图形不会与“尊重类型-A/B”匹配吧？如果你需要这个，你需要包含相应的顶点不变量

奖励：节点类型不变量

需要仔细观察才能意识到“尊重类型”实际上并不与预期结果冲突。因此，这里有一个只关注节点类型的不变量：

struct Invariant {
    Graph const& g;
    using result_type   = int; // ugh 1998 wants their unary_function back
    using argument_type = V;
    static int max() { return 2; } // 2 types [0,1]
    Type operator()(V v) const { return g[v].type; };
};

bool ok = (n == num_vertices(b)) &&
    isomorphism(a, b,
                boost::isomorphism_map(f.data())
                    .vertex_max_invariant(2)         // 2 types
                    .vertex_invariant1(Invariant{a}) //
                    .vertex_invariant2(Invariant{b}));

然而，停留在那里可能是一个很大的错误（特别是如果你的图可以变得更大）。这是因为默认的不变量匹配节点度数，这可以是一个巨大的优化。将启发式与类型要求相结合：

// invariant space Type x degree
size_t max_inv = 2 * num_vertices(a) * num_vertices(b);

struct Invariant {
    Graph const& g;
    size_t const max_;
    using argument_type = V; // ugh 1998 wants their unary_function back
    using result_type   = size_t;

    result_type max() const { return max_; }
    result_type operator()(argument_type v) const { return static_cast<int>(g[v].type) * degree(v, g); }
};

bool ok = (n == num_vertices(b)) &&
    isomorphism(a, b,
                boost::isomorphism_map(f.data())
                    .vertex_invariant1(Invariant{a, max_inv}) //
                    .vertex_invariant2(Invariant{b, max_inv}));

虽然不太美观，但它能正常工作！注意我如何改进同构映射的调试输出，以便我甚至能理解这些映射 :)

在 Coliru 上实时运行

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/isomorphism.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <iostream>
using boost::make_iterator_range;

static std::ostream debug(nullptr);

enum Type   { A, B       };
struct Node { Type type; };
using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Node>;
using V     = Graph::vertex_descriptor;
using Bond  = std::pair<V, V>;

struct Input {
    std::vector<Type> nodes;
    std::vector<Bond> bonds;
};

using Problem = std::vector<Input>;

Graph toGraph(Input const& input) {
    auto  N = input.nodes.size();
    Graph g(begin(input.bonds), end(input.bonds), N);
    for (size_t n = 0; n < N; ++n)
        g[n].type = input.nodes.at(n);
    return g;
}

static auto names(Graph const& g) {
    return make_transform_value_property_map([&](V v) { return "AB"[g[v].type] + std::to_string(v); },
                                             get(boost::vertex_index, g));
}

bool compare(Graph const& a, Graph const& b) {
    auto n = num_vertices(a);
    std::vector<V> f(n);

    // invariant space Type x degree
    size_t max_inv = 2 * num_vertices(a) * num_vertices(b);

    struct Invariant {
        Graph const& g;
        size_t const max_;
        using argument_type = V; // ugh 1998 wants their unary_function back
        using result_type   = size_t;

        result_type max() const { return max_; }
        result_type operator()(argument_type v) const { return static_cast<int>(g[v].type) * degree(v, g); }
    };

    bool ok = (n == num_vertices(b)) &&
        isomorphism(a, b,
                    boost::isomorphism_map(f.data())
                        .vertex_invariant1(Invariant{a, max_inv}) //
                        .vertex_invariant2(Invariant{b, max_inv}));

    debug << "isomorphism " << std::boolalpha << ok;

    if (auto an = names(a), bn = names(b); ok)
        for (debug << " f: "; V v : make_iterator_range(vertices(a)))
            debug << an[v] << "->" << bn[f[v]] << " ";
    debug << std::endl;
    
    return ok;
}

bool solve(Problem const& p) {
    std::vector<Graph> gg;
    transform(begin(p), end(p), back_inserter(gg), toGraph);

    for (auto& g : gg)
        print_graph(g, names(g), debug << " --\n");

    auto mismatch = [](Graph const& a, Graph const& b) { return !compare(a, b); };
    return end(gg) == adjacent_find(begin(gg), end(gg), mismatch);
}

int main() {
    debug.rdbuf(std::cout.rdbuf()); // verbose

    debug << "green ---\n";
    bool ok = solve({{{A, B, B, B}, {{0, 1}, {1, 2}, {1, 3}}},
                     {{B, B, B, A}, {{3, 2}, {2, 0}, {2, 1}}},
                     {{B, B, A, B}, {{0, 1}, {1, 2}, {1, 3}}}});
    std::cout << " -> green problem solves " << std::boolalpha << ok << std::endl;

    debug << "red ---\n";
    ok = solve({{{B, A, B, B}, {{0, 1}, {1, 2}, {1, 3}}},
                {{B, B, B, B}, {{0, 1}, {1, 2}, {1, 3}}},
                {{A, B, B}, {{0, 1}, {1, 2}}}});
    std::cout << " -> red problem solves " << std::boolalpha << ok << std::endl;
}

打印

green ---
 --
A0 <--> B1 
B1 <--> A0 B2 B3 
B2 <--> B1 
B3 <--> B1 
 --
B0 <--> B2 
B1 <--> B2 
B2 <--> A3 B0 B1 
A3 <--> B2 
 --
B0 <--> B1 
B1 <--> B0 A2 B3 
A2 <--> B1 
B3 <--> B1 
isomorphism true f: A0->A3 B1->B2 B2->B0 B3->B1 
isomorphism true f: B0->B0 B1->B3 B2->B1 A3->A2 
 -> green problem solves true
red ---
 --
B0 <--> A1 
A1 <--> B0 B2 B3 
B2 <--> A1 
B3 <--> A1 
 --
B0 <--> B1 
B1 <--> B0 B2 B3 
B2 <--> B1 
B3 <--> B1 
 --
A0 <--> B1 
B1 <--> A0 B2 
B2 <--> B1 
isomorphism false
 -> red problem solves false