mirror of
https://github.com/boostorg/graph.git
synced 2025-05-09 23:14:00 +00:00
125 lines
2.8 KiB
C++
125 lines
2.8 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();
|
|
}
|