1 //=======================================================================
2 // Copyright (C) 2012 Flavio De Lorenzi (fdlorenzi@gmail.com)
3 //
4 // Distributed under the Boost Software License, Version 1.0. (See
5 // accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 //=======================================================================
8
9 #include <boost/graph/adjacency_list.hpp>
10 #include <boost/graph/vf2_sub_graph_iso.hpp>
11 using namespace boost;
12
main()13 int main()
14 {
15 typedef property< edge_name_t, char > edge_property;
16 typedef property< vertex_name_t, char, property< vertex_index_t, int > >
17 vertex_property;
18
19 // Using a vecS graphs => the index maps are implicit.
20 typedef adjacency_list< vecS, vecS, bidirectionalS, vertex_property,
21 edge_property >
22 graph_type;
23
24 // Build graph1
25 graph_type graph1;
26
27 add_vertex(vertex_property('a'), graph1);
28 add_vertex(vertex_property('a'), graph1);
29 add_vertex(vertex_property('a'), graph1);
30
31 add_edge(0, 1, edge_property('b'), graph1);
32 add_edge(0, 1, edge_property('b'), graph1);
33 add_edge(0, 1, edge_property('d'), graph1);
34
35 add_edge(1, 2, edge_property('s'), graph1);
36
37 add_edge(2, 2, edge_property('l'), graph1);
38 add_edge(2, 2, edge_property('l'), graph1);
39
40 // Build graph2
41 graph_type graph2;
42
43 add_vertex(vertex_property('a'), graph2);
44 add_vertex(vertex_property('a'), graph2);
45 add_vertex(vertex_property('a'), graph2);
46 add_vertex(vertex_property('a'), graph2);
47 add_vertex(vertex_property('a'), graph2);
48 add_vertex(vertex_property('a'), graph2);
49
50 add_edge(0, 1, edge_property('a'), graph2);
51 add_edge(0, 1, edge_property('a'), graph2);
52 add_edge(0, 1, edge_property('b'), graph2);
53
54 add_edge(1, 2, edge_property('s'), graph2);
55
56 add_edge(2, 3, edge_property('b'), graph2);
57 add_edge(2, 3, edge_property('d'), graph2);
58 add_edge(2, 3, edge_property('b'), graph2);
59
60 add_edge(3, 4, edge_property('s'), graph2);
61
62 add_edge(4, 4, edge_property('l'), graph2);
63 add_edge(4, 4, edge_property('l'), graph2);
64
65 add_edge(4, 5, edge_property('c'), graph2);
66 add_edge(4, 5, edge_property('c'), graph2);
67 add_edge(4, 5, edge_property('c'), graph2);
68
69 add_edge(5, 0, edge_property('s'), graph2);
70
71 // create predicates
72 typedef property_map< graph_type, vertex_name_t >::type vertex_name_map_t;
73 typedef property_map_equivalent< vertex_name_map_t, vertex_name_map_t >
74 vertex_comp_t;
75 vertex_comp_t vertex_comp = make_property_map_equivalent(
76 get(vertex_name, graph1), get(vertex_name, graph2));
77
78 typedef property_map< graph_type, edge_name_t >::type edge_name_map_t;
79 typedef property_map_equivalent< edge_name_map_t, edge_name_map_t >
80 edge_comp_t;
81 edge_comp_t edge_comp = make_property_map_equivalent(
82 get(edge_name, graph1), get(edge_name, graph2));
83
84 // Create callback
85 vf2_print_callback< graph_type, graph_type > callback(graph1, graph2);
86
87 // Print out all subgraph isomorphism mappings between graph1 and graph2.
88 // Function vertex_order_by_mult is used to compute the order of
89 // vertices of graph1. This is the order in which the vertices are examined
90 // during the matching process.
91 vf2_subgraph_iso(graph1, graph2, callback, vertex_order_by_mult(graph1),
92 edges_equivalent(edge_comp).vertices_equivalent(vertex_comp));
93
94 return 0;
95 }
96