]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | //======================================================================= |
2 | // Boost.Graph library vf2_sub_graph_iso test 2 | |
3 | // Test of return value and behaviour with empty graphs | |
4 | // | |
f67539c2 TL |
5 | // Copyright (C) 2013 Jakob Lykke Andersen, University of Southern Denmark |
6 | // (jlandersen@imada.sdu.dk) | |
7c673cae FG |
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> | |
f67539c2 | 14 | #include <boost/core/lightweight_test.hpp> |
7c673cae FG |
15 | #include <boost/graph/adjacency_list.hpp> |
16 | #include <boost/graph/vf2_sub_graph_iso.hpp> | |
17 | ||
f67539c2 TL |
18 | struct test_callback |
19 | { | |
20 | test_callback(bool& got_hit, bool stop) : got_hit(got_hit), stop(stop) {} | |
7c673cae | 21 | |
f67539c2 TL |
22 | template < typename Map1To2, typename Map2To1 > |
23 | bool operator()(Map1To2 map1to2, Map2To1 map2to1) | |
24 | { | |
25 | got_hit = true; | |
26 | return stop; | |
27 | } | |
7c673cae | 28 | |
f67539c2 TL |
29 | bool& got_hit; |
30 | bool stop; | |
7c673cae FG |
31 | }; |
32 | ||
f67539c2 TL |
33 | struct false_predicate |
34 | { | |
35 | template < typename VertexOrEdge1, typename VertexOrEdge2 > | |
36 | bool operator()(VertexOrEdge1 ve1, VertexOrEdge2 ve2) const | |
37 | { | |
38 | return false; | |
39 | } | |
7c673cae FG |
40 | }; |
41 | ||
f67539c2 TL |
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); | |
7c673cae | 49 | |
f67539c2 TL |
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 | |
7c673cae FG |
66 | bool got_hit = false; |
67 | test_callback callback(got_hit, true); | |
f67539c2 TL |
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) | |
7c673cae | 74 | { // empty vs. empty |
f67539c2 TL |
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 | |
7c673cae FG |
80 | } |
81 | { // empty vs. non-empty | |
f67539c2 TL |
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 | |
7c673cae | 87 | } |
f67539c2 | 88 | } |
7c673cae FG |
89 | } |
90 | ||
f67539c2 TL |
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); | |
7c673cae | 102 | |
f67539c2 TL |
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) | |
7c673cae | 137 | { // no morphism due to sizes |
f67539c2 TL |
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) | |
7c673cae | 170 | { // no morphism due to sizes |
f67539c2 TL |
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); | |
7c673cae FG |
176 | } |
177 | { // no morphism due to vertex mismatches | |
f67539c2 TL |
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); | |
7c673cae FG |
186 | } |
187 | { // morphism, find all | |
f67539c2 TL |
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); | |
7c673cae FG |
193 | } |
194 | { // morphism, stop after first hit | |
f67539c2 TL |
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); | |
7c673cae | 200 | } |
f67539c2 | 201 | } |
7c673cae FG |
202 | } |
203 | ||
f67539c2 TL |
204 | int main(int argc, char* argv[]) |
205 | { | |
206 | test_empty_graph_cases(); | |
207 | test_return_value(); | |
208 | return boost::report_errors(); | |
7c673cae | 209 | } |