107 lines
2.7 KiB
C++
107 lines
2.7 KiB
C++
// 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();
|
|
}
|