254 lines
7.8 KiB
C++
254 lines
7.8 KiB
C++
// 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.
|
|
|
|
#include <iostream>
|
|
#include <fstream>
|
|
#include <map>
|
|
#include <algorithm>
|
|
#include <cstdlib>
|
|
#include <time.h> // clock used without std:: qualifier?
|
|
#include <boost/core/lightweight_test.hpp>
|
|
#include <boost/graph/adjacency_list.hpp>
|
|
#include <boost/graph/isomorphism.hpp>
|
|
#include <boost/property_map/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>
|
|
|
|
#ifndef BOOST_NO_CXX11_HDR_RANDOM
|
|
#include <random>
|
|
typedef std::mt19937 random_generator_type;
|
|
#else
|
|
typedef boost::mt19937 random_generator_type;
|
|
#endif
|
|
|
|
using namespace boost;
|
|
|
|
#ifndef BOOST_NO_CXX98_RANDOM_SHUFFLE
|
|
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< random_generator_type&,
|
|
boost::uniform_int< std::size_t > >
|
|
x(g, distrib);
|
|
return x();
|
|
}
|
|
Generator& g;
|
|
};
|
|
#endif
|
|
|
|
template < typename Graph1, typename Graph2 >
|
|
void randomly_permute_graph(const Graph1& g1, Graph2& g2)
|
|
{
|
|
// Need a clean graph to start with
|
|
BOOST_TEST(num_vertices(g2) == 0);
|
|
BOOST_TEST(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;
|
|
|
|
random_generator_type gen;
|
|
|
|
#ifndef BOOST_NO_CXX98_RANDOM_SHUFFLE
|
|
random_functor< random_generator_type > rand_fun(gen);
|
|
#endif
|
|
|
|
// Decide new order
|
|
std::vector< vertex1 > orig_vertices;
|
|
std::copy(vertices(g1).first, vertices(g1).second,
|
|
std::back_inserter(orig_vertices));
|
|
#ifndef BOOST_NO_CXX98_RANDOM_SHUFFLE
|
|
std::random_shuffle(orig_vertices.begin(), orig_vertices.end(), rand_fun);
|
|
#else
|
|
std::shuffle(orig_vertices.begin(), orig_vertices.end(), gen);
|
|
#endif
|
|
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;
|
|
random_generator_type random_gen;
|
|
boost::uniform_real< double > distrib(0.0, 1.0);
|
|
boost::variate_generator< random_generator_type&,
|
|
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_isomorphism2()
|
|
{
|
|
using namespace boost::graph::keywords;
|
|
typedef adjacency_list< vecS, vecS, bidirectionalS > graph1;
|
|
typedef adjacency_list< listS, listS, bidirectionalS,
|
|
property< vertex_index_t, int > >
|
|
graph2;
|
|
|
|
graph1 g1(2);
|
|
add_edge(vertex(0, g1), vertex(1, g1), g1);
|
|
add_edge(vertex(1, g1), vertex(1, g1), g1);
|
|
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;
|
|
clock_t start = clock();
|
|
BOOST_TEST(isomorphism_correct = boost::graph::isomorphism(g1, g2,
|
|
_vertex_index1_map = get(vertex_index, g1),
|
|
_isomorphism_map = make_assoc_property_map(mapping)));
|
|
clock_t end = clock();
|
|
|
|
std::cout << "Elapsed time (clock cycles): " << (end - start) << std::endl;
|
|
|
|
bool verify_correct;
|
|
BOOST_TEST(verify_correct
|
|
= verify_isomorphism(g1, g2, make_assoc_property_map(mapping)));
|
|
|
|
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;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
void test_isomorphism(int n, double edge_probability)
|
|
{
|
|
using namespace boost::graph::keywords;
|
|
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;
|
|
clock_t start = clock();
|
|
BOOST_TEST(isomorphism_correct = boost::graph::isomorphism(g1, g2,
|
|
_isomorphism_map = make_assoc_property_map(mapping)));
|
|
clock_t end = clock();
|
|
|
|
std::cout << "Elapsed time (clock cycles): " << (end - start) << std::endl;
|
|
|
|
bool verify_correct;
|
|
BOOST_TEST(verify_correct
|
|
= verify_isomorphism(g1, g2, make_assoc_property_map(mapping)));
|
|
|
|
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 main(int argc, char* argv[])
|
|
{
|
|
int n = argc < 3 ? 30 : boost::lexical_cast< int >(argv[1]);
|
|
double edge_prob = argc < 3 ? 0.45 : boost::lexical_cast< double >(argv[2]);
|
|
test_isomorphism(n, edge_prob);
|
|
|
|
return boost::report_errors();
|
|
}
|