| // Boost.Graph library isomorphism test |
| |
| // Copyright (C) 2001 Douglas Gregor (gregod@cs.rpi.edu) |
| // |
| // 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) |
| |
| // For more information, see http://www.boost.org |
| // |
| // Revision History: |
| // |
| // 29 Nov 2001 Jeremy Siek |
| // Changed to use Boost.Random. |
| // 29 Nov 2001 Doug Gregor |
| // Initial checkin. |
| |
| #define BOOST_INCLUDE_MAIN |
| #include <boost/test/test_tools.hpp> |
| #include <boost/graph/adjacency_list.hpp> |
| #include <boost/graph/isomorphism.hpp> |
| //#include "isomorphism-v3.hpp" |
| #include <boost/property_map/property_map.hpp> |
| #include <iostream> |
| #include <fstream> |
| #include <map> |
| #include <algorithm> |
| #include <cstdlib> |
| #include <ctime> |
| |
| using namespace boost; |
| |
| |
| enum { a, b, c, d, e, f, g, h }; |
| enum { _1, _2, _3, _4, _5, _6, _7, _8 }; |
| |
| void test_isomorphism() |
| { |
| typedef adjacency_list<vecS, vecS, bidirectionalS> GraphA; |
| typedef adjacency_list<vecS, vecS, bidirectionalS> GraphB; |
| |
| char a_names[] = "abcdefgh"; |
| char b_names[] = "12345678"; |
| |
| GraphA Ga(8); |
| add_edge(a, d, Ga); |
| add_edge(a, h, Ga); |
| add_edge(b, c, Ga); |
| add_edge(b, e, Ga); |
| add_edge(c, f, Ga); |
| add_edge(d, a, Ga); |
| add_edge(d, h, Ga); |
| add_edge(e, b, Ga); |
| add_edge(f, b, Ga); |
| add_edge(f, e, Ga); |
| add_edge(g, d, Ga); |
| add_edge(g, f, Ga); |
| add_edge(h, c, Ga); |
| add_edge(h, g, Ga); |
| |
| GraphB Gb(8); |
| add_edge(_1, _6, Gb); |
| add_edge(_2, _1, Gb); |
| add_edge(_2, _5, Gb); |
| add_edge(_3, _2, Gb); |
| add_edge(_3, _4, Gb); |
| add_edge(_4, _2, Gb); |
| add_edge(_4, _3, Gb); |
| add_edge(_5, _4, Gb); |
| add_edge(_5, _6, Gb); |
| add_edge(_6, _7, Gb); |
| add_edge(_6, _8, Gb); |
| add_edge(_7, _8, Gb); |
| add_edge(_8, _1, Gb); |
| add_edge(_8, _7, Gb); |
| |
| |
| std::vector<std::size_t> in_degree_A(num_vertices(Ga)); |
| boost::detail::compute_in_degree(Ga, &in_degree_A[0]); |
| |
| std::vector<std::size_t> in_degree_B(num_vertices(Gb)); |
| boost::detail::compute_in_degree(Gb, &in_degree_B[0]); |
| |
| degree_vertex_invariant<std::size_t*, GraphA> |
| invariantA(&in_degree_A[0], Ga); |
| degree_vertex_invariant<std::size_t*, GraphB> |
| invariantB(&in_degree_B[0], Gb); |
| |
| std::vector<graph_traits<GraphB>::vertex_descriptor> f(num_vertices(Ga)); |
| |
| bool ret = isomorphism(Ga, Gb, &f[0], invariantA, invariantB, |
| (invariantB.max)(), |
| get(vertex_index, Ga), get(vertex_index, Gb)); |
| assert(ret == true); |
| |
| for (std::size_t i = 0; i < num_vertices(Ga); ++i) |
| std::cout << "f(" << a_names[i] << ")=" << b_names[f[i]] << std::endl; |
| |
| BOOST_TEST(verify_isomorphism(Ga, Gb, &f[0])); |
| } |
| |
| int test_main(int, char* []) |
| { |
| test_isomorphism(); |
| return boost::report_errors(); |
| } |