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