| 1 | // (C) Copyright Jeremy Siek 2001. |
|---|
| 2 | // Distributed under the Boost Software License, Version 1.0. (See |
|---|
| 3 | // accompanying file LICENSE_1_0.txt or copy at |
|---|
| 4 | // http://www.boost.org/LICENSE_1_0.txt) |
|---|
| 5 | |
|---|
| 6 | #include <boost/config.hpp> |
|---|
| 7 | #include <iostream> |
|---|
| 8 | #include <boost/graph/isomorphism.hpp> |
|---|
| 9 | #include <boost/graph/adjacency_list.hpp> |
|---|
| 10 | |
|---|
| 11 | #include <boost/graph/graph_utility.hpp> |
|---|
| 12 | |
|---|
| 13 | /* |
|---|
| 14 | Sample output: |
|---|
| 15 | isomorphic? 1 |
|---|
| 16 | f: 9 10 11 0 1 3 2 4 6 8 7 5 |
|---|
| 17 | */ |
|---|
| 18 | |
|---|
| 19 | int main() |
|---|
| 20 | { |
|---|
| 21 | using namespace boost; |
|---|
| 22 | |
|---|
| 23 | const int n = 12; |
|---|
| 24 | |
|---|
| 25 | typedef adjacency_list< vecS, listS, undirectedS, |
|---|
| 26 | property< vertex_index_t, int > > |
|---|
| 27 | graph_t; |
|---|
| 28 | graph_t g1(n), g2(n); |
|---|
| 29 | |
|---|
| 30 | std::vector< graph_traits< graph_t >::vertex_descriptor > v1(n), v2(n); |
|---|
| 31 | |
|---|
| 32 | property_map< graph_t, vertex_index_t >::type v1_index_map |
|---|
| 33 | = get(p: vertex_index, g&: g1), |
|---|
| 34 | v2_index_map = get(p: vertex_index, g&: g2); |
|---|
| 35 | |
|---|
| 36 | graph_traits< graph_t >::vertex_iterator i, end; |
|---|
| 37 | int id = 0; |
|---|
| 38 | for (boost::tie(t0&: i, t1&: end) = vertices(g_: g1); i != end; ++i, ++id) |
|---|
| 39 | { |
|---|
| 40 | put(pa: v1_index_map, k: *i, v: id); |
|---|
| 41 | v1[id] = *i; |
|---|
| 42 | } |
|---|
| 43 | id = 0; |
|---|
| 44 | for (boost::tie(t0&: i, t1&: end) = vertices(g_: g2); i != end; ++i, ++id) |
|---|
| 45 | { |
|---|
| 46 | put(pa: v2_index_map, k: *i, v: id); |
|---|
| 47 | v2[id] = *i; |
|---|
| 48 | } |
|---|
| 49 | add_edge(u: v1[0], v: v1[1], g_&: g1); |
|---|
| 50 | add_edge(u: v1[1], v: v1[2], g_&: g1); |
|---|
| 51 | add_edge(u: v1[0], v: v1[2], g_&: g1); |
|---|
| 52 | add_edge(u: v1[3], v: v1[4], g_&: g1); |
|---|
| 53 | add_edge(u: v1[4], v: v1[5], g_&: g1); |
|---|
| 54 | add_edge(u: v1[5], v: v1[6], g_&: g1); |
|---|
| 55 | add_edge(u: v1[6], v: v1[3], g_&: g1); |
|---|
| 56 | add_edge(u: v1[7], v: v1[8], g_&: g1); |
|---|
| 57 | add_edge(u: v1[8], v: v1[9], g_&: g1); |
|---|
| 58 | add_edge(u: v1[9], v: v1[10], g_&: g1); |
|---|
| 59 | add_edge(u: v1[10], v: v1[11], g_&: g1); |
|---|
| 60 | add_edge(u: v1[11], v: v1[7], g_&: g1); |
|---|
| 61 | |
|---|
| 62 | add_edge(u: v2[9], v: v2[10], g_&: g2); |
|---|
| 63 | add_edge(u: v2[10], v: v2[11], g_&: g2); |
|---|
| 64 | add_edge(u: v2[11], v: v2[9], g_&: g2); |
|---|
| 65 | add_edge(u: v2[0], v: v2[1], g_&: g2); |
|---|
| 66 | add_edge(u: v2[1], v: v2[3], g_&: g2); |
|---|
| 67 | add_edge(u: v2[3], v: v2[2], g_&: g2); |
|---|
| 68 | add_edge(u: v2[2], v: v2[0], g_&: g2); |
|---|
| 69 | add_edge(u: v2[4], v: v2[5], g_&: g2); |
|---|
| 70 | add_edge(u: v2[5], v: v2[7], g_&: g2); |
|---|
| 71 | add_edge(u: v2[7], v: v2[8], g_&: g2); |
|---|
| 72 | add_edge(u: v2[8], v: v2[6], g_&: g2); |
|---|
| 73 | add_edge(u: v2[6], v: v2[4], g_&: g2); |
|---|
| 74 | |
|---|
| 75 | std::vector< graph_traits< graph_t >::vertex_descriptor > f(n); |
|---|
| 76 | |
|---|
| 77 | #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 |
|---|
| 78 | bool ret = isomorphism(g1, g2, |
|---|
| 79 | make_iterator_property_map(f.begin(), v1_index_map, f[0]), |
|---|
| 80 | degree_vertex_invariant(), get(vertex_index, g1), |
|---|
| 81 | get(vertex_index, g2)); |
|---|
| 82 | #else |
|---|
| 83 | bool ret = isomorphism(param0: g1, param1: g2, |
|---|
| 84 | old_style_params: isomorphism_map( |
|---|
| 85 | p: make_iterator_property_map(iter: f.begin(), id: v1_index_map, f[0]))); |
|---|
| 86 | #endif |
|---|
| 87 | std::cout << "isomorphic? " << ret << std::endl; |
|---|
| 88 | |
|---|
| 89 | std::cout << "f: " ; |
|---|
| 90 | for (std::size_t v = 0; v != f.size(); ++v) |
|---|
| 91 | std::cout << get(pa: get(p: vertex_index, g&: g2), k: f[v]) << " " ; |
|---|
| 92 | std::cout << std::endl; |
|---|
| 93 | |
|---|
| 94 | return 0; |
|---|
| 95 | } |
|---|
| 96 | |
|---|
