Re: [boost] BGL isomorphism broken

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-11-28 17:14:01

Hi Doug,

Thanks for the test code! I'll look into getting the isomorphism algorithm
fixed (don't expect that to happen in less than a week though).

Cheers,
Jeremy

On Wed, 28 Nov 2001, Douglas Gregor wrote:

gregod> I know it is in a state of flux, but the isomorphism
gregod> algorithm (CVS version)  is broken. I've been generating
gregod> random small digraphs and it's been breaking consistently.
gregod> The test code I've been using follows.
gregod>
gregod> 	Doug
gregod>
gregod> #define BOOST_INCLUDE_MAIN
gregod> #include <boost/test/test_tools.hpp>
gregod> #include <boost/graph/adjacency_list.hpp>
gregod> #include <boost/graph/ddl_isomorphism.hpp>
gregod> #include <boost/graph/isomorphism.hpp>
gregod> #include <boost/property_map.hpp>
gregod> #include <iostream>
gregod> #include <map>
gregod> #include <algorithm>
gregod> #include <cstdlib>
gregod> #include <ctime>
gregod> #include <sys/time.h>
gregod>
gregod> using namespace boost;
gregod>
gregod> template<typename Graph1, typename Graph2>
gregod> void randomly_permute_graph(const Graph1& g1, Graph2& g2)
gregod> {
gregod>   typedef typename graph_traits<Graph1>::vertex_descriptor vertex1;
gregod>   typedef typename graph_traits<Graph2>::vertex_descriptor vertex2;
gregod>   typedef typename graph_traits<Graph1>::edge_iterator edge_iterator;
gregod>
gregod>   // Decide new order
gregod>   std::vector<vertex1> orig_vertices(vertices(g1).first, vertices(g1).second);
gregod>   std::random_shuffle(orig_vertices.begin(), orig_vertices.end());
gregod>   std::map<vertex1, vertex2> vertex_map;
gregod>
gregod>   for (std::size_t i = 0; i < num_vertices(g1); ++i) {
gregod>     vertex_map[orig_vertices[i]] = add_vertex(g2);
gregod>   }
gregod>
gregod>   for (edge_iterator e = edges(g1).first; e != edges(g1).second; ++e) {
gregod>     add_edge(vertex_map[source(*e, g1)], vertex_map[target(*e, g1)], g2);
gregod>   }
gregod> }
gregod>
gregod> template<typename Graph>
gregod> void generate_random_digraph(Graph& g, double edge_probability)
gregod> {
gregod>   typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
gregod>   for (vertex_iterator u = vertices(g).first; u != vertices(g).second; ++u) {
gregod>     vertex_iterator v = u;
gregod>     ++v;
gregod>     for (; v != vertices(g).second; ++v) {
gregod>       if (drand48() <= edge_probability)
gregod>         add_edge(*u, *v, g);
gregod>     }
gregod>   }
gregod> }
gregod>
gregod> void test_isomorphism(int n, double edge_probability) {
gregod>   typedef adjacency_list<vecS, vecS, bidirectionalS> graph;
gregod>   graph g1(n);
gregod>   generate_random_digraph(g1, edge_probability);
gregod>   graph g2;
gregod>   randomly_permute_graph(g1, g2);
gregod>
gregod>   std::map<graph::vertex_descriptor, int> numbering;
gregod>   std::map<graph::vertex_descriptor, graph::vertex_descriptor> mapping;
gregod>   std::map<graph::vertex_descriptor, bool> assigned;
gregod>   timeval ddl_start;
gregod>   timeval ddl_end;
gregod>   timeval bgl_start;
gregod>   timeval bgl_end;
gregod> #if 0
gregod>   gettimeofday(&ddl_start, 0);
gregod>   BOOST_TEST(ddl_isomorphism(g1, g2,
gregod>                              make_assoc_property_map(mapping),
gregod>                              make_assoc_property_map(numbering),
gregod>
gregod>                              make_assoc_property_map(assigned)));
gregod>   gettimeofday(&ddl_end, 0);
gregod>   BOOST_TEST(verify_isomorphism(g1, g2, make_assoc_property_map(mapping)));
gregod>
gregod>   double ddl_elapsed_time = (ddl_end.tv_usec - ddl_start.tv_usec) / 1000000.0
gregod>                           + (ddl_end.tv_sec - ddl_start.tv_sec);
gregod>
gregod>   mapping.clear();
gregod> #endif
gregod>   gettimeofday(&bgl_start, 0);
gregod>   BOOST_TEST(isomorphism(g1, g2,
gregod>                          isomorphism_map(make_assoc_property_map(mapping))));
gregod>   gettimeofday(&bgl_end, 0);
gregod>   BOOST_TEST(verify_isomorphism(g1, g2, make_assoc_property_map(mapping)));
gregod>
gregod>   double bgl_elapsed_time = (bgl_end.tv_usec - bgl_start.tv_usec) / 1000000.0
gregod>                           + (bgl_end.tv_sec - bgl_start.tv_sec);
gregod>
gregod>   //  std::cout << "Elapsed time (DDL): " << ddl_elapsed_time << std::endl;
gregod>   std::cout << "Elapsed time (BGL): " << bgl_elapsed_time << std::endl;
gregod> }
gregod>
gregod> int test_main(int argc, char* argv[])
gregod> {
gregod>   srandom(std::time(0));
gregod>   srand48(std::time(0));
gregod>   typedef adjacency_list<vecS, vecS, bidirectionalS> graph;
gregod>
gregod>   if (argc < 3) {
gregod>     std::cerr
gregod>       << "Usage: ddl_isomorphism <number of vertices> <edge probability>\n";
gregod>     return 0;
gregod>   }
gregod>
gregod>   int n = atoi(argv[1]);
gregod>   double edge_prob = atof(argv[2]);
gregod>   test_isomorphism(n, edge_prob);
gregod>
gregod>   return 0;
gregod> }
gregod>
gregod>
gregod>
gregod> Info: http://www.boost.org  Unsubscribe: <mailto:boost-unsubscribe_at_[hidden]>
gregod>
gregod> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
gregod>
gregod>

----------------------------------------------------------------------
 Jeremy Siek                          http://php.indiana.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------