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
main()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(vertex_index, g1),
34 v2_index_map = get(vertex_index, g2);
35
36 graph_traits< graph_t >::vertex_iterator i, end;
37 int id = 0;
38 for (boost::tie(i, end) = vertices(g1); i != end; ++i, ++id)
39 {
40 put(v1_index_map, *i, id);
41 v1[id] = *i;
42 }
43 id = 0;
44 for (boost::tie(i, end) = vertices(g2); i != end; ++i, ++id)
45 {
46 put(v2_index_map, *i, id);
47 v2[id] = *i;
48 }
49 add_edge(v1[0], v1[1], g1);
50 add_edge(v1[1], v1[2], g1);
51 add_edge(v1[0], v1[2], g1);
52 add_edge(v1[3], v1[4], g1);
53 add_edge(v1[4], v1[5], g1);
54 add_edge(v1[5], v1[6], g1);
55 add_edge(v1[6], v1[3], g1);
56 add_edge(v1[7], v1[8], g1);
57 add_edge(v1[8], v1[9], g1);
58 add_edge(v1[9], v1[10], g1);
59 add_edge(v1[10], v1[11], g1);
60 add_edge(v1[11], v1[7], g1);
61
62 add_edge(v2[9], v2[10], g2);
63 add_edge(v2[10], v2[11], g2);
64 add_edge(v2[11], v2[9], g2);
65 add_edge(v2[0], v2[1], g2);
66 add_edge(v2[1], v2[3], g2);
67 add_edge(v2[3], v2[2], g2);
68 add_edge(v2[2], v2[0], g2);
69 add_edge(v2[4], v2[5], g2);
70 add_edge(v2[5], v2[7], g2);
71 add_edge(v2[7], v2[8], g2);
72 add_edge(v2[8], v2[6], g2);
73 add_edge(v2[6], v2[4], 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(g1, g2,
84 isomorphism_map(
85 make_iterator_property_map(f.begin(), 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(get(vertex_index, g2), f[v]) << " ";
92 std::cout << std::endl;
93
94 return 0;
95 }
96