1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/stdcpp/tsrc/Boost_test/graph/src/isomorphism.cpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,187 @@
1.4 +// Boost.Graph library isomorphism test
1.5 +
1.6 +// Copyright (C) 2001-20044 Douglas Gregor (dgregor at cs dot indiana dot edu)
1.7 +//
1.8 +// Distributed under the Boost Software License, Version 1.0. (See
1.9 +// accompanying file LICENSE_1_0.txt or copy at
1.10 +// http://www.boost.org/LICENSE_1_0.txt)
1.11 +
1.12 +// For more information, see http://www.boost.org
1.13 +//
1.14 +// Revision History:
1.15 +//
1.16 +// 29 Nov 2001 Jeremy Siek
1.17 +// Changed to use Boost.Random.
1.18 +// 29 Nov 2001 Doug Gregor
1.19 +// Initial checkin.
1.20 +/*
1.21 + * © Portions copyright (c) 2006-2007 Nokia Corporation. All rights reserved.
1.22 +*/
1.23 +
1.24 +#include <iostream>
1.25 +#include <fstream>
1.26 +#include <map>
1.27 +#include <algorithm>
1.28 +#include <cstdlib>
1.29 +#include <time.h> // clock used without std:: qualifier?
1.30 +#include <boost/test/minimal.hpp>
1.31 +#include <boost/graph/adjacency_list.hpp>
1.32 +#include <boost/graph/isomorphism.hpp>
1.33 +#include <boost/property_map.hpp>
1.34 +#include <boost/random/variate_generator.hpp>
1.35 +#include <boost/random/uniform_real.hpp>
1.36 +#include <boost/random/uniform_int.hpp>
1.37 +#include <boost/random/mersenne_twister.hpp>
1.38 +#include <boost/lexical_cast.hpp>
1.39 +#ifdef __SYMBIAN32__
1.40 +#include "std_log_result.h"
1.41 +#define LOG_FILENAME_LINE __FILE__, __LINE__
1.42 +#endif
1.43 +using namespace boost;
1.44 +
1.45 +template <typename Generator>
1.46 +struct random_functor {
1.47 + random_functor(Generator& g) : g(g) { }
1.48 + std::size_t operator()(std::size_t n) {
1.49 + boost::uniform_int<std::size_t> distrib(0, n-1);
1.50 + boost::variate_generator<boost::mt19937&, boost::uniform_int<std::size_t> >
1.51 + x(g, distrib);
1.52 + return x();
1.53 + }
1.54 + Generator& g;
1.55 +};
1.56 +
1.57 +template<typename Graph1, typename Graph2>
1.58 +void randomly_permute_graph(const Graph1& g1, Graph2& g2)
1.59 +{
1.60 + // Need a clean graph to start with
1.61 + BOOST_REQUIRE(num_vertices(g2) == 0);
1.62 + BOOST_REQUIRE(num_edges(g2) == 0);
1.63 +
1.64 + typedef typename graph_traits<Graph1>::vertex_descriptor vertex1;
1.65 + typedef typename graph_traits<Graph2>::vertex_descriptor vertex2;
1.66 + typedef typename graph_traits<Graph1>::edge_iterator edge_iterator;
1.67 +
1.68 + boost::mt19937 gen;
1.69 + random_functor<boost::mt19937> rand_fun(gen);
1.70 +
1.71 + // Decide new order
1.72 + std::vector<vertex1> orig_vertices;
1.73 + std::copy(vertices(g1).first, vertices(g1).second, std::back_inserter(orig_vertices));
1.74 + std::random_shuffle(orig_vertices.begin(), orig_vertices.end(), rand_fun);
1.75 + std::map<vertex1, vertex2> vertex_map;
1.76 +
1.77 + for (std::size_t i = 0; i < num_vertices(g1); ++i) {
1.78 + vertex_map[orig_vertices[i]] = add_vertex(g2);
1.79 + }
1.80 +
1.81 + for (edge_iterator e = edges(g1).first; e != edges(g1).second; ++e) {
1.82 + add_edge(vertex_map[source(*e, g1)], vertex_map[target(*e, g1)], g2);
1.83 + }
1.84 +}
1.85 +
1.86 +template<typename Graph>
1.87 +void generate_random_digraph(Graph& g, double edge_probability)
1.88 +{
1.89 + typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
1.90 + boost::mt19937 random_gen;
1.91 + boost::uniform_real<double> distrib(0.0, 1.0);
1.92 + boost::variate_generator<boost::mt19937&, boost::uniform_real<double> >
1.93 + random_dist(random_gen, distrib);
1.94 +
1.95 + for (vertex_iterator u = vertices(g).first; u != vertices(g).second; ++u) {
1.96 + vertex_iterator v = u;
1.97 + ++v;
1.98 + for (; v != vertices(g).second; ++v) {
1.99 + if (random_dist() <= edge_probability)
1.100 + add_edge(*u, *v, g);
1.101 + }
1.102 + }
1.103 +}
1.104 +
1.105 +void test_isomorphism(int n, double edge_probability)
1.106 +{
1.107 + typedef adjacency_list<vecS, vecS, bidirectionalS> graph1;
1.108 + typedef adjacency_list<listS, listS, bidirectionalS,
1.109 + property<vertex_index_t, int> > graph2;
1.110 +
1.111 + graph1 g1(n);
1.112 + generate_random_digraph(g1, edge_probability);
1.113 + graph2 g2;
1.114 + randomly_permute_graph(g1, g2);
1.115 +
1.116 + int v_idx = 0;
1.117 + for (graph2::vertex_iterator v = vertices(g2).first;
1.118 + v != vertices(g2).second; ++v) {
1.119 + put(vertex_index_t(), g2, *v, v_idx++);
1.120 + }
1.121 +
1.122 + std::map<graph1::vertex_descriptor, graph2::vertex_descriptor> mapping;
1.123 +
1.124 + bool isomorphism_correct = true;
1.125 + clock_t start = clock();
1.126 +
1.127 + isomorphism_correct = isomorphism(g1, g2, isomorphism_map(make_assoc_property_map(mapping)));
1.128 +
1.129 + BOOST_CHECK(isomorphism_correct);
1.130 +
1.131 + clock_t end = clock();
1.132 +
1.133 + std::cout << "Elapsed time (clock cycles): " << (end - start) << std::endl;
1.134 +
1.135 + bool verify_correct = true;
1.136 +
1.137 + verify_correct = verify_isomorphism(g1, g2, make_assoc_property_map(mapping));
1.138 +
1.139 + BOOST_CHECK(verify_correct);
1.140 +
1.141 + if (!isomorphism_correct || !verify_correct) {
1.142 + // Output graph 1
1.143 + {
1.144 + std::ofstream out("isomorphism_failure.bg1");
1.145 + out << num_vertices(g1) << std::endl;
1.146 + for (graph1::edge_iterator e = edges(g1).first;
1.147 + e != edges(g1).second; ++e) {
1.148 + out << get(vertex_index_t(), g1, source(*e, g1)) << ' '
1.149 + << get(vertex_index_t(), g1, target(*e, g1)) << std::endl;
1.150 + }
1.151 + }
1.152 +
1.153 + // Output graph 2
1.154 + {
1.155 + std::ofstream out("isomorphism_failure.bg2");
1.156 + out << num_vertices(g2) << std::endl;
1.157 + for (graph2::edge_iterator e = edges(g2).first;
1.158 + e != edges(g2).second; ++e) {
1.159 + out << get(vertex_index_t(), g2, source(*e, g2)) << ' '
1.160 + << get(vertex_index_t(), g2, target(*e, g2)) << std::endl;
1.161 + }
1.162 + }
1.163 + }
1.164 +}
1.165 +
1.166 +int test_main(int argc, char* argv[])
1.167 +{
1.168 + if (argc < 3) {
1.169 + test_isomorphism(30, 0.45);
1.170 +#ifdef __SYMBIAN32__
1.171 + std_log(LOG_FILENAME_LINE,"[End Test Case ]");
1.172 +
1.173 + testResultXml("isomorphism");
1.174 + close_log_file();
1.175 +#endif
1.176 + return 0;
1.177 + }
1.178 +
1.179 + int n = boost::lexical_cast<int>(argv[1]);
1.180 + double edge_prob = boost::lexical_cast<double>(argv[2]);
1.181 + test_isomorphism(n, edge_prob);
1.182 +
1.183 +#ifdef __SYMBIAN32__
1.184 +std_log(LOG_FILENAME_LINE,"[End Test Case ]");
1.185 +
1.186 + testResultXml("isomorphism");
1.187 + close_log_file();
1.188 +#endif
1.189 + return 0;
1.190 +}