1 //=======================================================================
2 // Boost.Graph library vf2_sub_graph_iso test 2
3 // Test of return value and behaviour with empty graphs
4 //
5 // Copyright (C) 2013 Jakob Lykke Andersen, University of Southern Denmark
6 // (jlandersen@imada.sdu.dk)
7 //
8 // Distributed under the Boost Software License, Version 1.0. (See
9 // accompanying file LICENSE_1_0.txt or copy at
10 // http://www.boost.org/LICENSE_1_0.txt)
11 //=======================================================================
12
13 #include <iostream>
14 #include <boost/core/lightweight_test.hpp>
15 #include <boost/graph/adjacency_list.hpp>
16 #include <boost/graph/vf2_sub_graph_iso.hpp>
17
18 struct test_callback
19 {
test_callbacktest_callback20 test_callback(bool& got_hit, bool stop) : got_hit(got_hit), stop(stop) {}
21
22 template < typename Map1To2, typename Map2To1 >
operator ()test_callback23 bool operator()(Map1To2 map1to2, Map2To1 map2to1)
24 {
25 got_hit = true;
26 return stop;
27 }
28
29 bool& got_hit;
30 bool stop;
31 };
32
33 struct false_predicate
34 {
35 template < typename VertexOrEdge1, typename VertexOrEdge2 >
operator ()false_predicate36 bool operator()(VertexOrEdge1 ve1, VertexOrEdge2 ve2) const
37 {
38 return false;
39 }
40 };
41
test_empty_graph_cases()42 void test_empty_graph_cases()
43 {
44 typedef boost::adjacency_list< boost::vecS, boost::vecS,
45 boost::bidirectionalS >
46 Graph;
47 Graph gEmpty, gLarge;
48 add_vertex(gLarge);
49
50 { // isomorphism
51 bool got_hit = false;
52 test_callback callback(got_hit, true);
53 bool exists = vf2_graph_iso(gEmpty, gEmpty, callback);
54 BOOST_TEST(exists);
55 BOOST_TEST(got_hit); // even empty matches are reported
56 }
57 { // subgraph isomorphism (induced)
58 { // empty vs. empty
59 bool got_hit = false;
60 test_callback callback(got_hit, true);
61 bool exists = vf2_subgraph_iso(gEmpty, gEmpty, callback);
62 BOOST_TEST(exists);
63 BOOST_TEST(got_hit); // even empty matches are reported
64 }
65 { // empty vs. non-empty
66 bool got_hit = false;
67 test_callback callback(got_hit, true);
68 bool exists = vf2_subgraph_iso(gEmpty, gLarge, callback);
69 BOOST_TEST(exists);
70 BOOST_TEST(got_hit); // even empty matches are reported
71 }
72 }
73 { // subgraph monomorphism (non-induced subgraph isomorphism)
74 { // empty vs. empty
75 bool got_hit = false;
76 test_callback callback(got_hit, true);
77 bool exists = vf2_subgraph_mono(gEmpty, gEmpty, callback);
78 BOOST_TEST(exists);
79 BOOST_TEST(got_hit); // even empty matches are reported
80 }
81 { // empty vs. non-empty
82 bool got_hit = false;
83 test_callback callback(got_hit, true);
84 bool exists = vf2_subgraph_mono(gEmpty, gLarge, callback);
85 BOOST_TEST(exists);
86 BOOST_TEST(got_hit); // even empty matches are reported
87 }
88 }
89 }
90
test_return_value()91 void test_return_value()
92 {
93 typedef boost::adjacency_list< boost::vecS, boost::vecS,
94 boost::bidirectionalS >
95 Graph;
96 typedef boost::graph_traits< Graph >::vertex_descriptor Vertex;
97 Graph gSmall, gLarge;
98 add_vertex(gSmall);
99 Vertex v1 = add_vertex(gLarge);
100 Vertex v2 = add_vertex(gLarge);
101 add_edge(v1, v2, gLarge);
102
103 { // isomorphism
104 { // no morphism due to sizes
105 bool got_hit = false;
106 test_callback callback(got_hit, true);
107 bool exists = vf2_graph_iso(gSmall, gLarge, callback);
108 BOOST_TEST(!exists);
109 BOOST_TEST(!got_hit);
110 }
111 { // no morphism due to vertex mismatches
112 bool got_hit = false;
113 test_callback callback(got_hit, true);
114 false_predicate pred;
115 bool exists
116 = vf2_graph_iso(gLarge, gLarge, callback, vertex_order_by_mult(gLarge),
117 boost::edges_equivalent(pred).vertices_equivalent(pred));
118 BOOST_TEST(!exists);
119 BOOST_TEST(!got_hit);
120 }
121 { // morphism, find all
122 bool got_hit = false;
123 test_callback callback(got_hit, false);
124 bool exists = vf2_graph_iso(gLarge, gLarge, callback);
125 BOOST_TEST(exists);
126 BOOST_TEST(got_hit);
127 }
128 { // morphism, stop after first hit
129 bool got_hit = false;
130 test_callback callback(got_hit, true);
131 bool exists = vf2_graph_iso(gLarge, gLarge, callback);
132 BOOST_TEST(exists);
133 BOOST_TEST(got_hit);
134 }
135 }
136 { // subgraph isomorphism (induced)
137 { // no morphism due to sizes
138 bool got_hit = false;
139 test_callback callback(got_hit, true);
140 bool exists = vf2_subgraph_iso(gLarge, gSmall, callback);
141 BOOST_TEST(!exists);
142 BOOST_TEST(!got_hit);
143 }
144 { // no morphism due to vertex mismatches
145 bool got_hit = false;
146 test_callback callback(got_hit, true);
147 false_predicate pred;
148 bool exists = vf2_subgraph_iso(gLarge, gLarge, callback,
149 vertex_order_by_mult(gLarge),
150 boost::edges_equivalent(pred).vertices_equivalent(pred));
151 BOOST_TEST(!exists);
152 BOOST_TEST(!got_hit);
153 }
154 { // morphism, find all
155 bool got_hit = false;
156 test_callback callback(got_hit, false);
157 bool exists = vf2_subgraph_iso(gLarge, gLarge, callback);
158 BOOST_TEST(exists);
159 BOOST_TEST(got_hit);
160 }
161 { // morphism, stop after first hit
162 bool got_hit = false;
163 test_callback callback(got_hit, true);
164 bool exists = vf2_subgraph_iso(gLarge, gLarge, callback);
165 BOOST_TEST(exists);
166 BOOST_TEST(got_hit);
167 }
168 }
169 { // subgraph monomorphism (non-induced subgraph isomorphism)
170 { // no morphism due to sizes
171 bool got_hit = false;
172 test_callback callback(got_hit, true);
173 bool exists = vf2_subgraph_mono(gLarge, gSmall, callback);
174 BOOST_TEST(!exists);
175 BOOST_TEST(!got_hit);
176 }
177 { // no morphism due to vertex mismatches
178 bool got_hit = false;
179 test_callback callback(got_hit, true);
180 false_predicate pred;
181 bool exists = vf2_subgraph_mono(gLarge, gLarge, callback,
182 vertex_order_by_mult(gLarge),
183 boost::edges_equivalent(pred).vertices_equivalent(pred));
184 BOOST_TEST(!exists);
185 BOOST_TEST(!got_hit);
186 }
187 { // morphism, find all
188 bool got_hit = false;
189 test_callback callback(got_hit, false);
190 bool exists = vf2_subgraph_mono(gLarge, gLarge, callback);
191 BOOST_TEST(exists);
192 BOOST_TEST(got_hit);
193 }
194 { // morphism, stop after first hit
195 bool got_hit = false;
196 test_callback callback(got_hit, true);
197 bool exists = vf2_subgraph_mono(gLarge, gLarge, callback);
198 BOOST_TEST(exists);
199 BOOST_TEST(got_hit);
200 }
201 }
202 }
203
main(int argc,char * argv[])204 int main(int argc, char* argv[])
205 {
206 test_empty_graph_cases();
207 test_return_value();
208 return boost::report_errors();
209 }
210