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 | { |
20 | test_callback(bool& got_hit, bool stop) : got_hit(got_hit), stop(stop) {} |
21 | |
22 | template < typename Map1To2, typename Map2To1 > |
23 | 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 > |
36 | bool operator()(VertexOrEdge1 ve1, VertexOrEdge2 ve2) const |
37 | { |
38 | return false; |
39 | } |
40 | }; |
41 | |
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(g_&: gLarge); |
49 | |
50 | { // isomorphism |
51 | bool got_hit = false; |
52 | test_callback callback(got_hit, true); |
53 | bool exists = vf2_graph_iso(graph1: gEmpty, graph2: gEmpty, user_callback: 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(graph_small: gEmpty, graph_large: gEmpty, user_callback: 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(graph_small: gEmpty, graph_large: gLarge, user_callback: 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(graph_small: gEmpty, graph_large: gEmpty, user_callback: 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(graph_small: gEmpty, graph_large: gLarge, user_callback: callback); |
85 | BOOST_TEST(exists); |
86 | BOOST_TEST(got_hit); // even empty matches are reported |
87 | } |
88 | } |
89 | } |
90 | |
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(g_&: gSmall); |
99 | Vertex v1 = add_vertex(g_&: gLarge); |
100 | Vertex v2 = add_vertex(g_&: gLarge); |
101 | add_edge(u: v1, v: v2, g_&: 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(graph1: gSmall, graph2: gLarge, user_callback: 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(graph1: gLarge, graph2: gLarge, user_callback: callback, vertex_order1: vertex_order_by_mult(graph: gLarge), |
117 | params: boost::edges_equivalent(p: pred).vertices_equivalent(p: 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(graph1: gLarge, graph2: gLarge, user_callback: 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(graph1: gLarge, graph2: gLarge, user_callback: 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(graph_small: gLarge, graph_large: gSmall, user_callback: 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(graph_small: gLarge, graph_large: gLarge, user_callback: callback, |
149 | vertex_order_small: vertex_order_by_mult(graph: gLarge), |
150 | params: boost::edges_equivalent(p: pred).vertices_equivalent(p: 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(graph_small: gLarge, graph_large: gLarge, user_callback: 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(graph_small: gLarge, graph_large: gLarge, user_callback: 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(graph_small: gLarge, graph_large: gSmall, user_callback: 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(graph_small: gLarge, graph_large: gLarge, user_callback: callback, |
182 | vertex_order_small: vertex_order_by_mult(graph: gLarge), |
183 | params: boost::edges_equivalent(p: pred).vertices_equivalent(p: 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(graph_small: gLarge, graph_large: gLarge, user_callback: 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(graph_small: gLarge, graph_large: gLarge, user_callback: callback); |
198 | BOOST_TEST(exists); |
199 | BOOST_TEST(got_hit); |
200 | } |
201 | } |
202 | } |
203 | |
204 | int main(int argc, char* argv[]) |
205 | { |
206 | test_empty_graph_cases(); |
207 | test_return_value(); |
208 | return boost::report_errors(); |
209 | } |
210 | |