isomorphism.cpp

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

// Boost.Graph library isomorphism test

// Copyright (C) 2001-20044 Douglas Gregor (dgregor at cs dot indiana dot 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.

#include <iostream>
#include <fstream>
#include <map>
#include <algorithm>
#include <cstdlib>
#include <time.h> // clock used without std:: qualifier?
#include <boost/test/minimal.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/isomorphism.hpp>
#include <boost/property_map.hpp>
#include <boost/random/variate_generator.hpp>
#include <boost/random/uniform_real.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/mersenne_twister.hpp>
#include <boost/lexical_cast.hpp>

using namespace boost;

template <typename Generator>
struct random_functor {
  random_functor(Generator& g) : g(g) { }
  std::size_t operator()(std::size_t n) {
    boost::uniform_int<std::size_t> distrib(0, n-1);
    boost::variate_generator<boost::mt19937&, boost::uniform_int<std::size_t> >
      x(g, distrib);
    return x();
  }
  Generator& g;
};

template<typename Graph1, typename Graph2>
void randomly_permute_graph(const Graph1& g1, Graph2& g2)
{
  // Need a clean graph to start with
  BOOST_REQUIRE(num_vertices(g2) == 0);
  BOOST_REQUIRE(num_edges(g2) == 0);

  typedef typename graph_traits<Graph1>::vertex_descriptor vertex1;
  typedef typename graph_traits<Graph2>::vertex_descriptor vertex2;
  typedef typename graph_traits<Graph1>::edge_iterator edge_iterator;

  boost::mt19937 gen;
  random_functor<boost::mt19937> rand_fun(gen);

  // Decide new order
  std::vector<vertex1> orig_vertices;
  std::copy(vertices(g1).first, vertices(g1).second, std::back_inserter(orig_vertices));
  std::random_shuffle(orig_vertices.begin(), orig_vertices.end(), rand_fun);
  std::map<vertex1, vertex2> vertex_map;

  for (std::size_t i = 0; i < num_vertices(g1); ++i) {
    vertex_map[orig_vertices[i]] = add_vertex(g2);
  }

  for (edge_iterator e = edges(g1).first; e != edges(g1).second; ++e) {
    add_edge(vertex_map[source(*e, g1)], vertex_map[target(*e, g1)], g2);
  }
}

template<typename Graph>
void generate_random_digraph(Graph& g, double edge_probability)
{
  typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
  boost::mt19937 random_gen;
  boost::uniform_real<double> distrib(0.0, 1.0);
  boost::variate_generator<boost::mt19937&, boost::uniform_real<double> >
    random_dist(random_gen, distrib);

  for (vertex_iterator u = vertices(g).first; u != vertices(g).second; ++u) {
    vertex_iterator v = u;
    ++v;
    for (; v != vertices(g).second; ++v) {
      if (random_dist() <= edge_probability)
        add_edge(*u, *v, g);
    }
  }
}

void test_isomorphism(int n, double edge_probability)
{
  typedef adjacency_list<vecS, vecS, bidirectionalS> graph1;
  typedef adjacency_list<listS, listS, bidirectionalS,
                         property<vertex_index_t, int> > graph2;

  graph1 g1(n);
  generate_random_digraph(g1, edge_probability);
  graph2 g2;
  randomly_permute_graph(g1, g2);

  int v_idx = 0;
  for (graph2::vertex_iterator v = vertices(g2).first;
       v != vertices(g2).second; ++v) {
    put(vertex_index_t(), g2, *v, v_idx++);
  }

  std::map<graph1::vertex_descriptor, graph2::vertex_descriptor> mapping;

  bool isomorphism_correct;
  clock_t start = clock();
  BOOST_CHECK(isomorphism_correct = isomorphism
               (g1, g2, isomorphism_map(make_assoc_property_map(mapping))));
  clock_t end = clock();

  std::cout << "Elapsed time (clock cycles): " << (end - start) << std::endl;

  bool verify_correct;
  BOOST_CHECK(verify_correct =
             verify_isomorphism(g1, g2, make_assoc_property_map(mapping)));

  if (!isomorphism_correct || !verify_correct) {
    // Output graph 1
    {
      std::ofstream out("isomorphism_failure.bg1");
      out << num_vertices(g1) << std::endl;
      for (graph1::edge_iterator e = edges(g1).first;
           e != edges(g1).second; ++e) {
        out << get(vertex_index_t(), g1, source(*e, g1)) << ' '
            << get(vertex_index_t(), g1, target(*e, g1)) << std::endl;
      }
    }

    // Output graph 2
    {
      std::ofstream out("isomorphism_failure.bg2");
      out << num_vertices(g2) << std::endl;
      for (graph2::edge_iterator e = edges(g2).first;
           e != edges(g2).second; ++e) {
        out << get(vertex_index_t(), g2, source(*e, g2)) << ' '
            << get(vertex_index_t(), g2, target(*e, g2)) << std::endl;
      }
    }
  }
}

int test_main(int argc, char* argv[])
{
  if (argc < 3) {
    test_isomorphism(30, 0.45);
    return 0;
  }

  int n = boost::lexical_cast<int>(argv[1]);
  double edge_prob = boost::lexical_cast<double>(argv[2]);
  test_isomorphism(n, edge_prob);

  return 0;
}