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: (812) 855-3608
----------------------------------------------------------------------