boost_1_45_0/libs/graph/doc/eg1-iso.cpp

// 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();
}