How can I use the C++ Boost Graph Library (BGL) to find isomorphic graphs?

Question

Using C++ Boost Graph Library (BGL) to Find Isomorphic Graphs

See graphs.

I want to get the graphs which are isomorphic (respecting the type - A/B). Of course, all graphs which have not the same number of connections, are sorted out in the beginning.

# 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;
}

This is my attempt to get a minimal example of Boost working. I would be grateful if anybody could show me how to achieve this with Boost, if thats the proper library?

Answer 1

So, you posted the example from the Boost libraries. Some version before 2019.

Obviously, that's not going to represent your graphs. First modernize:

Live

#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;
}

Next, simplify, because you didn't tell us reasons to not have the intrinsic vertex index afforded by using 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;
}

Adding Your Data

Since you need the type (A/B), let's add it to vertex properties:

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

Let's also create the bond graphs:

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

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

using Problem = std::vector<Input>;

Now you can state the problem in code:

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}}}};

Let's implement our solution:

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

Really, toGraph is a 1:1 helper to convert the input to adjacency_list:

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 just wraps up the call to isomorphism like before:

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;
}

I'm not in favour of mixing output with logic, but it may help illustrate the answer, so I left it under the debug stream which can be enabled.

Now, solving it can be done by comparing all pairs of graphs in the problem:

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]);
}

In fact I'll also add debug output to verify the graphs:

    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");
    }

Of course, we didn't make the problem dynamically sized for no reason, so let's generalize using an algorithm:

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);
}

DEMO TIME

Live On 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;
}

Prints

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

Or, with debug disabled just printing:

-> green problem solves true -> red problem solves false

LOOSE ENDS?

I love to note that this final program solves the entire two problems with extensive debug output, in 10 lines of code less than the example you started from.

Note, you mention in your question:

I want to get the graphs which are isomorphic (respecting the type - A/B)_

Now it isn't clear what you mean by that. You seem to expect the green box to match, though it seems obvious that the third graph would not match "respecting the type - A/B"? If you needed that, you'd have to include the corresponding vertex invariant

BONUS: Node Type Invariant

It took some squinting to realize that the "respecting the type" doesn't actually conflict with the expected result. So here goes: an invariant that just looks at the Node types:

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}));

However, to stop there could be a big mistake (especially if your graphs can get bigger). That's because the default invariant matches node degrees, which can be a huge optimization. Combining the heuristic with the type-requirement:

// 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}));

It's not pretty, but it works! Note how I improved the isomorphism mapping debug output so I could even understand the mappings :)

Live On 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;
}

Prints

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