BGL isomorphism broken

From: Douglas Gregor (gregod_at_[hidden])
Date: 2001-11-28 12:28:26

I know it is in a state of flux, but the isomorphism algorithm (CVS version) 
is broken. I've been generating random small digraphs and it's been breaking 
consistently. The test code I've been using follows.

        Doug

#define BOOST_INCLUDE_MAIN
#include <boost/test/test_tools.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/ddl_isomorphism.hpp>
#include <boost/graph/isomorphism.hpp>
#include <boost/property_map.hpp>
#include <iostream>
#include <map>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <sys/time.h>

using namespace boost;

template<typename Graph1, typename Graph2>
void randomly_permute_graph(const Graph1& g1, Graph2& g2)
{
  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;

  // Decide new order
  std::vector<vertex1> orig_vertices(vertices(g1).first, vertices(g1).second);
  std::random_shuffle(orig_vertices.begin(), orig_vertices.end());
  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;
  for (vertex_iterator u = vertices(g).first; u != vertices(g).second; ++u) {
    vertex_iterator v = u;
    ++v;
    for (; v != vertices(g).second; ++v) {
      if (drand48() <= edge_probability)
        add_edge(*u, *v, g);
    }
  }
}

void test_isomorphism(int n, double edge_probability) {
  typedef adjacency_list<vecS, vecS, bidirectionalS> graph;
  graph g1(n);
  generate_random_digraph(g1, edge_probability);
  graph g2;
  randomly_permute_graph(g1, g2);

  std::map<graph::vertex_descriptor, int> numbering;
  std::map<graph::vertex_descriptor, graph::vertex_descriptor> mapping;
  std::map<graph::vertex_descriptor, bool> assigned;
  timeval ddl_start;
  timeval ddl_end;
  timeval bgl_start;
  timeval bgl_end;
#if 0
  gettimeofday(&ddl_start, 0);
  BOOST_TEST(ddl_isomorphism(g1, g2, 
                             make_assoc_property_map(mapping),
                             make_assoc_property_map(numbering),

                             make_assoc_property_map(assigned)));
  gettimeofday(&ddl_end, 0);
  BOOST_TEST(verify_isomorphism(g1, g2, make_assoc_property_map(mapping)));

  double ddl_elapsed_time = (ddl_end.tv_usec - ddl_start.tv_usec) / 1000000.0
                          + (ddl_end.tv_sec - ddl_start.tv_sec);

  mapping.clear();
#endif
  gettimeofday(&bgl_start, 0);
  BOOST_TEST(isomorphism(g1, g2, 
                         isomorphism_map(make_assoc_property_map(mapping))));
  gettimeofday(&bgl_end, 0);
  BOOST_TEST(verify_isomorphism(g1, g2, make_assoc_property_map(mapping)));

  double bgl_elapsed_time = (bgl_end.tv_usec - bgl_start.tv_usec) / 1000000.0
                          + (bgl_end.tv_sec - bgl_start.tv_sec);

  //  std::cout << "Elapsed time (DDL): " << ddl_elapsed_time << std::endl;
  std::cout << "Elapsed time (BGL): " << bgl_elapsed_time << std::endl;
}

int test_main(int argc, char* argv[])
{
  srandom(std::time(0));
  srand48(std::time(0));
  typedef adjacency_list<vecS, vecS, bidirectionalS> graph;

  if (argc < 3) {
    std::cerr
      << "Usage: ddl_isomorphism <number of vertices> <edge probability>\n";
    return 0;
  }

  int n = atoi(argv[1]);
  double edge_prob = atof(argv[2]);
  test_isomorphism(n, edge_prob);

  return 0;
}