graph/test/vf2_sub_graph_iso_test.cpp

//=======================================================================
// 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/core/lightweight_test.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_TEST(num_vertices(g1) <= num_vertices(g2));
    BOOST_TEST(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_TEST((0 <= edge_probability) && (edge_probability <= 1));
    BOOST_TEST(
        (0 <= parallel_edge_probability) && (parallel_edge_probability <= 1));
    BOOST_TEST(0 <= max_parallel_edges);
    BOOST_TEST(0 <= max_edge_name);
    BOOST_TEST(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_TEST(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_TEST(vf2_subgraph_iso(g1, g2, callback, vertex_order_by_mult(g1),
        edges_equivalent(edge_comp).vertices_equivalent(vertex_comp)));
    BOOST_TEST(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_TEST(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 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 boost::report_errors();
}