| //======================================================================= |
| // 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; |
| } |