123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331 |
- //=======================================================================
- // Boost.Graph library vf2_sub_graph_iso test
- // Adapted from isomorphism.cpp and mcgregor_subgraphs_test.cpp
- //
- // Copyright (C) 2012 Flavio De Lorenzi (fdlorenzi@gmail.com)
- //
- // 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)
- //=======================================================================
- // Revision History:
- // 8 April 2013: Fixed a typo in random_functor. (Flavio De Lorenzi)
- #include <iostream>
- #include <fstream>
- #include <map>
- #include <algorithm>
- #include <cstdlib>
- #include <time.h>
- #include <boost/test/minimal.hpp>
- #include <boost/graph/adjacency_list.hpp>
- #include <boost/graph/vf2_sub_graph_iso.hpp>
- #include <boost/graph/random.hpp>
- #include <boost/property_map/property_map.hpp>
- #include <boost/random.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>
- #include <boost/graph/graphviz.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<Generator&, boost::uniform_int<std::size_t> >
- x(g, distrib);
- return x();
- }
- Generator& g;
- };
- #endif
- template<typename Graph1, typename Graph2>
- void randomly_permute_graph(Graph1& g1, const Graph2& g2) {
- BOOST_REQUIRE(num_vertices(g1) <= num_vertices(g2));
- BOOST_REQUIRE(num_edges(g1) == 0);
-
- typedef typename graph_traits<Graph1>::vertex_descriptor vertex1;
- typedef typename graph_traits<Graph2>::vertex_descriptor vertex2;
- typedef typename graph_traits<Graph1>::vertex_iterator vertex_iterator;
- typedef typename graph_traits<Graph2>::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<vertex2> orig_vertices;
- std::copy(vertices(g2).first, vertices(g2).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<vertex2, vertex1> vertex_map;
-
- std::size_t i = 0;
- for (vertex_iterator vi = vertices(g1).first;
- vi != vertices(g1).second; ++i, ++vi) {
- vertex_map[orig_vertices[i]] = *vi;
- put(vertex_name_t(), g1, *vi, get(vertex_name_t(), g2, orig_vertices[i]));
- }
- for (edge_iterator ei = edges(g2).first; ei != edges(g2).second; ++ei) {
- typename std::map<vertex2, vertex1>::iterator si = vertex_map.find(source(*ei, g2)),
- ti = vertex_map.find(target(*ei, g2));
- if ((si != vertex_map.end()) && (ti != vertex_map.end()))
- add_edge(si->second, ti->second, get(edge_name_t(), g2, *ei), g1);
- }
- }
- template<typename Graph>
- void generate_random_digraph(Graph& g, double edge_probability,
- int max_parallel_edges, double parallel_edge_probability,
- int max_edge_name, int max_vertex_name) {
- BOOST_REQUIRE((0 <= edge_probability) && (edge_probability <= 1));
- BOOST_REQUIRE((0 <= parallel_edge_probability) && (parallel_edge_probability <= 1));
- BOOST_REQUIRE(0 <= max_parallel_edges);
- BOOST_REQUIRE(0 <= max_edge_name);
- BOOST_REQUIRE(0 <= max_vertex_name);
- typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
- random_generator_type random_gen;
- boost::uniform_real<double> dist_real(0.0, 1.0);
- boost::variate_generator<random_generator_type&, boost::uniform_real<double> >
- random_real_dist(random_gen, dist_real);
- for (vertex_iterator u = vertices(g).first; u != vertices(g).second; ++u) {
- for (vertex_iterator v = vertices(g).first; v != vertices(g).second; ++v) {
- if (random_real_dist() <= edge_probability) {
- add_edge(*u, *v, g);
- for (int i = 0; i < max_parallel_edges; ++i) {
- if (random_real_dist() <= parallel_edge_probability)
- add_edge(*u, *v, g);
- }
- }
- }
- }
-
- {
- boost::uniform_int<int> dist_int(0, max_edge_name);
- boost::variate_generator<random_generator_type&, boost::uniform_int<int> >
- random_int_dist(random_gen, dist_int);
- randomize_property<vertex_name_t>(g, random_int_dist);
- }
- {
- boost::uniform_int<int> dist_int(0, max_vertex_name);
- boost::variate_generator<random_generator_type&, boost::uniform_int<int> >
- random_int_dist(random_gen, dist_int);
-
- randomize_property<edge_name_t>(g, random_int_dist);
- }
- }
- template <typename Graph1,
- typename Graph2,
- typename EdgeEquivalencePredicate,
- typename VertexEquivalencePredicate>
- struct test_callback {
-
- test_callback(const Graph1& graph1, const Graph2& graph2,
- EdgeEquivalencePredicate edge_comp,
- VertexEquivalencePredicate vertex_comp, bool output)
- : graph1_(graph1), graph2_(graph2), edge_comp_(edge_comp), vertex_comp_(vertex_comp),
- output_(output) {}
-
- template <typename CorrespondenceMap1To2,
- typename CorrespondenceMap2To1>
- bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1) {
-
- bool verified;
- BOOST_CHECK(verified = verify_vf2_subgraph_iso(graph1_, graph2_, f, edge_comp_, vertex_comp_));
-
- // Output (sub)graph isomorphism map
- if (!verified || output_) {
- std::cout << "Verfied: " << std::boolalpha << verified << std::endl;
- std::cout << "Num vertices: " << num_vertices(graph1_) << ' ' << num_vertices(graph2_) << std::endl;
- BGL_FORALL_VERTICES_T(v, graph1_, Graph1)
- std::cout << '(' << get(vertex_index_t(), graph1_, v) << ", "
- << get(vertex_index_t(), graph2_, get(f, v)) << ") ";
-
- std::cout << std::endl;
- }
-
- return true;
- }
-
- private:
- const Graph1& graph1_;
- const Graph2& graph2_;
- EdgeEquivalencePredicate edge_comp_;
- VertexEquivalencePredicate vertex_comp_;
- bool output_;
- };
- // we pretend this is something more complicated which calculates indices somehow
- template<typename G>
- struct IndirectIndexMap {
- typedef std::size_t value_type;
- typedef value_type reference;
- typedef typename boost::graph_traits<G>::vertex_descriptor key_type;
- typedef boost::readable_property_map_tag category;
- explicit IndirectIndexMap(const G &g) : g(g) {}
- public:
- const G &g;
- };
- template<typename G>
- std::size_t get(const IndirectIndexMap<G> &map, typename boost::graph_traits<G>::vertex_descriptor v) {
- // we pretend this is something more complicated which calculates indices somehow
- return get(vertex_index_t(), map.g, v);
- }
- void test_vf2_sub_graph_iso(int n1, int n2, double edge_probability,
- int max_parallel_edges, double parallel_edge_probability,
- int max_edge_name, int max_vertex_name, bool output) {
- typedef property<edge_name_t, int> edge_property;
- typedef property<vertex_name_t, int, property<vertex_index_t, int> > vertex_property;
-
- typedef adjacency_list<listS, listS, bidirectionalS, vertex_property, edge_property> graph1;
- typedef adjacency_list<vecS, vecS, bidirectionalS, vertex_property, edge_property> graph2;
-
- graph1 g1(n1);
- graph2 g2(n2);
- generate_random_digraph(g2, edge_probability, max_parallel_edges, parallel_edge_probability,
- max_edge_name, max_vertex_name);
- randomly_permute_graph(g1, g2);
- int v_idx = 0;
- for (graph_traits<graph1>::vertex_iterator vi = vertices(g1).first;
- vi != vertices(g1).second; ++vi) {
- put(vertex_index_t(), g1, *vi, v_idx++);
- }
- // Create vertex and edge predicates
- typedef property_map<graph1, vertex_name_t>::type vertex_name_map1;
- typedef property_map<graph2, vertex_name_t>::type vertex_name_map2;
-
- typedef property_map_equivalent<vertex_name_map1, vertex_name_map2> vertex_predicate;
- vertex_predicate vertex_comp =
- make_property_map_equivalent(get(vertex_name, g1), get(vertex_name, g2));
-
- typedef property_map<graph1, edge_name_t>::type edge_name_map1;
- typedef property_map<graph2, edge_name_t>::type edge_name_map2;
-
- typedef property_map_equivalent<edge_name_map1, edge_name_map2> edge_predicate;
- edge_predicate edge_comp =
- make_property_map_equivalent(get(edge_name, g1), get(edge_name, g2));
-
-
- std::clock_t start = std::clock();
-
- // Create callback
- test_callback<graph1, graph2, edge_predicate, vertex_predicate>
- callback(g1, g2, edge_comp, vertex_comp, output);
- std::cout << std::endl;
- BOOST_CHECK(vf2_subgraph_iso(g1, g2, callback, vertex_order_by_mult(g1),
- edges_equivalent(edge_comp).vertices_equivalent(vertex_comp)));
- BOOST_CHECK(vf2_subgraph_iso(g1, g2, callback,
- IndirectIndexMap<graph1>(g1),
- IndirectIndexMap<graph2>(g2),
- vertex_order_by_mult(g1),
- edge_comp, vertex_comp));
- std::clock_t end1 = std::clock();
- std::cout << "vf2_subgraph_iso: elapsed time (clock cycles): " << (end1 - start) << std::endl;
- if (num_vertices(g1) == num_vertices(g2)) {
- std::cout << std::endl;
- BOOST_CHECK(vf2_graph_iso(g1, g2, callback, vertex_order_by_mult(g1),
- edges_equivalent(edge_comp).vertices_equivalent(vertex_comp)));
-
- std::clock_t end2 = std::clock();
- std::cout << "vf2_graph_iso: elapsed time (clock cycles): " << (end2 - end1) << std::endl;
- }
-
- if (output) {
- std::fstream file_graph1("graph1.dot", std::fstream::out);
- write_graphviz(file_graph1, g1,
- make_label_writer(get(boost::vertex_name, g1)),
- make_label_writer(get(boost::edge_name, g1)));
-
- std::fstream file_graph2("graph2.dot", std::fstream::out);
- write_graphviz(file_graph2, g2,
- make_label_writer(get(boost::vertex_name, g2)),
- make_label_writer(get(boost::edge_name, g2)));
- }
- }
- int test_main(int argc, char* argv[]) {
- int num_vertices_g1 = 10;
- int num_vertices_g2 = 20;
- double edge_probability = 0.4;
- int max_parallel_edges = 2;
- double parallel_edge_probability = 0.4;
- int max_edge_name = 5;
- int max_vertex_name = 5;
- bool output = false;
-
- if (argc > 1) {
- num_vertices_g1 = boost::lexical_cast<int>(argv[1]);
- }
-
- if (argc > 2) {
- num_vertices_g2 = boost::lexical_cast<int>(argv[2]);
- }
-
- if (argc > 3) {
- edge_probability = boost::lexical_cast<double>(argv[3]);
- }
-
- if (argc > 4) {
- max_parallel_edges = boost::lexical_cast<int>(argv[4]);
- }
-
- if (argc > 5) {
- parallel_edge_probability = boost::lexical_cast<double>(argv[5]);
- }
-
- if (argc > 6) {
- max_edge_name = boost::lexical_cast<int>(argv[6]);
- }
-
- if (argc > 7) {
- max_vertex_name = boost::lexical_cast<int>(argv[7]);
- }
-
- if (argc > 8) {
- output = boost::lexical_cast<bool>(argv[8]);
- }
- test_vf2_sub_graph_iso(num_vertices_g1, num_vertices_g2, edge_probability,
- max_parallel_edges, parallel_edge_probability,
- max_edge_name, max_vertex_name, output);
-
- return 0;
- }
|