1 //=======================================================================
2 // Copyright 2009 Trustees of Indiana University.
3 // Authors: Michael Hansen
4 //
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //=======================================================================
9
10 #include <fstream>
11 #include <iostream>
12 #include <string>
13
14 #include <boost/lexical_cast.hpp>
15 #include <boost/graph/adjacency_list.hpp>
16 #include <boost/graph/filtered_graph.hpp>
17 #include <boost/graph/graph_utility.hpp>
18 #include <boost/graph/iteration_macros.hpp>
19 #include <boost/graph/mcgregor_common_subgraphs.hpp>
20 #include <boost/property_map/shared_array_property_map.hpp>
21
22 using namespace boost;
23
24 // Callback that looks for the first common subgraph whose size
25 // matches the user's preference.
26 template < typename Graph > struct example_callback
27 {
28
29 typedef typename graph_traits< Graph >::vertices_size_type VertexSizeFirst;
30
example_callbackexample_callback31 example_callback(const Graph& graph1) : m_graph1(graph1) {}
32
33 template < typename CorrespondenceMapFirstToSecond,
34 typename CorrespondenceMapSecondToFirst >
operator ()example_callback35 bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
36 CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
37 VertexSizeFirst subgraph_size)
38 {
39
40 // Fill membership map for first graph
41 typedef
42 typename property_map< Graph, vertex_index_t >::type VertexIndexMap;
43 typedef shared_array_property_map< bool, VertexIndexMap > MembershipMap;
44
45 MembershipMap membership_map1(
46 num_vertices(m_graph1), get(vertex_index, m_graph1));
47
48 fill_membership_map< Graph >(
49 m_graph1, correspondence_map_1_to_2, membership_map1);
50
51 // Generate filtered graphs using membership map
52 typedef typename membership_filtered_graph_traits< Graph,
53 MembershipMap >::graph_type MembershipFilteredGraph;
54
55 MembershipFilteredGraph subgraph1
56 = make_membership_filtered_graph(m_graph1, membership_map1);
57
58 // Print the graph out to the console
59 std::cout << "Found common subgraph (size " << subgraph_size << ")"
60 << std::endl;
61 print_graph(subgraph1);
62 std::cout << std::endl;
63
64 // Explore the entire space
65 return (true);
66 }
67
68 private:
69 const Graph& m_graph1;
70 VertexSizeFirst m_max_subgraph_size;
71 };
72
main(int argc,char * argv[])73 int main(int argc, char* argv[])
74 {
75
76 // Using a vecS graph here so that we don't have to mess around with
77 // a vertex index map; it will be implicit.
78 typedef adjacency_list< listS, vecS, directedS,
79 property< vertex_name_t, unsigned int,
80 property< vertex_index_t, unsigned int > >,
81 property< edge_name_t, unsigned int > >
82 Graph;
83
84 typedef property_map< Graph, vertex_name_t >::type VertexNameMap;
85
86 // Test maximum and unique variants on known graphs
87 Graph graph_simple1, graph_simple2;
88 example_callback< Graph > user_callback(graph_simple1);
89
90 VertexNameMap vname_map_simple1 = get(vertex_name, graph_simple1);
91 VertexNameMap vname_map_simple2 = get(vertex_name, graph_simple2);
92
93 // Graph that looks like a triangle
94 put(vname_map_simple1, add_vertex(graph_simple1), 1);
95 put(vname_map_simple1, add_vertex(graph_simple1), 2);
96 put(vname_map_simple1, add_vertex(graph_simple1), 3);
97
98 add_edge(0, 1, graph_simple1);
99 add_edge(0, 2, graph_simple1);
100 add_edge(1, 2, graph_simple1);
101
102 std::cout << "First graph:" << std::endl;
103 print_graph(graph_simple1);
104 std::cout << std::endl;
105
106 // Triangle with an extra vertex
107 put(vname_map_simple2, add_vertex(graph_simple2), 1);
108 put(vname_map_simple2, add_vertex(graph_simple2), 2);
109 put(vname_map_simple2, add_vertex(graph_simple2), 3);
110 put(vname_map_simple2, add_vertex(graph_simple2), 4);
111
112 add_edge(0, 1, graph_simple2);
113 add_edge(0, 2, graph_simple2);
114 add_edge(1, 2, graph_simple2);
115 add_edge(1, 3, graph_simple2);
116
117 std::cout << "Second graph:" << std::endl;
118 print_graph(graph_simple2);
119 std::cout << std::endl;
120
121 // All subgraphs
122 std::cout << "mcgregor_common_subgraphs:" << std::endl;
123 mcgregor_common_subgraphs(graph_simple1, graph_simple2, true, user_callback,
124 vertices_equivalent(make_property_map_equivalent(
125 vname_map_simple1, vname_map_simple2)));
126 std::cout << std::endl;
127
128 // Unique subgraphs
129 std::cout << "mcgregor_common_subgraphs_unique:" << std::endl;
130 mcgregor_common_subgraphs_unique(graph_simple1, graph_simple2, true,
131 user_callback,
132 vertices_equivalent(make_property_map_equivalent(
133 vname_map_simple1, vname_map_simple2)));
134 std::cout << std::endl;
135
136 // Maximum subgraphs
137 std::cout << "mcgregor_common_subgraphs_maximum:" << std::endl;
138 mcgregor_common_subgraphs_maximum(graph_simple1, graph_simple2, true,
139 user_callback,
140 vertices_equivalent(make_property_map_equivalent(
141 vname_map_simple1, vname_map_simple2)));
142 std::cout << std::endl;
143
144 // Maximum, unique subgraphs
145 std::cout << "mcgregor_common_subgraphs_maximum_unique:" << std::endl;
146 mcgregor_common_subgraphs_maximum_unique(graph_simple1, graph_simple2, true,
147 user_callback,
148 vertices_equivalent(make_property_map_equivalent(
149 vname_map_simple1, vname_map_simple2)));
150
151 return 0;
152 }
153