Boost.Graph 2つのグラフが同型かを調べる

Boost.Graphには、boost::isomorphism()(アイソモルフィズムと読む)という、2つのグラフが同型かを調べる関数が用意されています。
以下の2つのグラフが同型かどうかを調べてみます。この2つは、頂点の順番等は異なってますが、同じ形のグラフです。

g1:

g2:

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

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS> Graph;
const int vertex_count = 12;

Graph make_graph1()
{
    const std::vector<std::pair<int, int>> edges = {
        { 0,  1}, { 1, 2},
        { 0,  2},
        { 3,  4}, { 4, 5},
        { 5,  6}, { 6, 3},
        { 7,  8}, { 8, 9},
        { 9, 10},
        {10, 11}, {11, 7}
    };
    return Graph(edges.begin(), edges.end(), vertex_count);
}

Graph make_graph2()
{
    const std::vector<std::pair<int, int>> edges = {
        { 9, 10}, {10, 11},
        {11,  9},
        { 0,  1}, { 1,  3},
        { 3,  2}, { 2,  0},
        { 4,  5}, { 5,  7},
        { 7,  8},
        { 8,  6}, { 6,  4}
    };
    return Graph(edges.begin(), edges.end(), vertex_count);
}

int main()
{
    const Graph g1 = make_graph1();
    const Graph g2 = make_graph2();

    const bool result = boost::isomorphism(g1, g2);
    std::cout << "isomorphic? " << std::boolalpha << result << std::endl;
}

isomorphic? true

trueが返ってきたので、g1とg2が同型であることがわかりました。

参照：
boost::isomorphism() - Boost Graph Library