--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/stdcpp/tsrc/Boost_test/graph/src/isomorphism.cpp Fri Jun 04 16:20:51 2010 +0100
@@ -0,0 +1,187 @@
+// 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.
+/*
+ * © Portions copyright (c) 2006-2007 Nokia Corporation. All rights reserved.
+*/
+
+#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>
+#ifdef __SYMBIAN32__
+#include "std_log_result.h"
+#define LOG_FILENAME_LINE __FILE__, __LINE__
+#endif
+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 = true;
+ clock_t start = clock();
+
+ isomorphism_correct = isomorphism(g1, g2, isomorphism_map(make_assoc_property_map(mapping)));
+
+ BOOST_CHECK(isomorphism_correct);
+
+ clock_t end = clock();
+
+ std::cout << "Elapsed time (clock cycles): " << (end - start) << std::endl;
+
+ bool verify_correct = true;
+
+ verify_correct = verify_isomorphism(g1, g2, make_assoc_property_map(mapping));
+
+ BOOST_CHECK(verify_correct);
+
+ 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);
+#ifdef __SYMBIAN32__
+ std_log(LOG_FILENAME_LINE,"[End Test Case ]");
+
+ testResultXml("isomorphism");
+ close_log_file();
+#endif
+ return 0;
+ }
+
+ int n = boost::lexical_cast<int>(argv[1]);
+ double edge_prob = boost::lexical_cast<double>(argv[2]);
+ test_isomorphism(n, edge_prob);
+
+#ifdef __SYMBIAN32__
+std_log(LOG_FILENAME_LINE,"[End Test Case ]");
+
+ testResultXml("isomorphism");
+ close_log_file();
+#endif
+ return 0;
+}