//=======================================================================
// 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)
//=======================================================================

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
using namespace boost;

int main()
{
    typedef property< edge_name_t, char > edge_property;
    typedef property< vertex_name_t, char, property< vertex_index_t, int > >
        vertex_property;

    // Using a vecS graphs => the index maps are implicit.
    typedef adjacency_list< vecS, vecS, bidirectionalS, vertex_property,
        edge_property >
        graph_type;

    // Build graph1
    graph_type graph1;

    add_vertex(vertex_property('a'), graph1);
    add_vertex(vertex_property('a'), graph1);
    add_vertex(vertex_property('a'), graph1);

    add_edge(0, 1, edge_property('b'), graph1);
    add_edge(0, 1, edge_property('b'), graph1);
    add_edge(0, 1, edge_property('d'), graph1);

    add_edge(1, 2, edge_property('s'), graph1);

    add_edge(2, 2, edge_property('l'), graph1);
    add_edge(2, 2, edge_property('l'), graph1);

    // Build graph2
    graph_type graph2;

    add_vertex(vertex_property('a'), graph2);
    add_vertex(vertex_property('a'), graph2);
    add_vertex(vertex_property('a'), graph2);
    add_vertex(vertex_property('a'), graph2);
    add_vertex(vertex_property('a'), graph2);
    add_vertex(vertex_property('a'), graph2);

    add_edge(0, 1, edge_property('a'), graph2);
    add_edge(0, 1, edge_property('a'), graph2);
    add_edge(0, 1, edge_property('b'), graph2);

    add_edge(1, 2, edge_property('s'), graph2);

    add_edge(2, 3, edge_property('b'), graph2);
    add_edge(2, 3, edge_property('d'), graph2);
    add_edge(2, 3, edge_property('b'), graph2);

    add_edge(3, 4, edge_property('s'), graph2);

    add_edge(4, 4, edge_property('l'), graph2);
    add_edge(4, 4, edge_property('l'), graph2);

    add_edge(4, 5, edge_property('c'), graph2);
    add_edge(4, 5, edge_property('c'), graph2);
    add_edge(4, 5, edge_property('c'), graph2);

    add_edge(5, 0, edge_property('s'), graph2);

    // create predicates
    typedef property_map< graph_type, vertex_name_t >::type vertex_name_map_t;
    typedef property_map_equivalent< vertex_name_map_t, vertex_name_map_t >
        vertex_comp_t;
    vertex_comp_t vertex_comp = make_property_map_equivalent(
        get(vertex_name, graph1), get(vertex_name, graph2));

    typedef property_map< graph_type, edge_name_t >::type edge_name_map_t;
    typedef property_map_equivalent< edge_name_map_t, edge_name_map_t >
        edge_comp_t;
    edge_comp_t edge_comp = make_property_map_equivalent(
        get(edge_name, graph1), get(edge_name, graph2));

    // Create callback
    vf2_print_callback< graph_type, graph_type > callback(graph1, graph2);

    // Print out all subgraph isomorphism mappings between graph1 and graph2.
    // Function vertex_order_by_mult is used to compute the order of
    // vertices of graph1. This is the order in which the vertices are examined
    // during the matching process.
    vf2_subgraph_iso(graph1, graph2, callback, vertex_order_by_mult(graph1),
        edges_equivalent(edge_comp).vertices_equivalent(vertex_comp));

    return 0;
}