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
18struct 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
33struct false_predicate
34{
35 template < typename VertexOrEdge1, typename VertexOrEdge2 >
36 bool operator()(VertexOrEdge1 ve1, VertexOrEdge2 ve2) const
37 {
38 return false;
39 }
40};
41
42void 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
91void 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;
139test_callback callback(got_hit, true);
140bool exists = vf2_subgraph_iso(graph_small: gLarge, graph_large: gSmall, user_callback: callback);
141BOOST_TEST(!exists);
142BOOST_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
204int main(int argc, char* argv[])
205{
206 test_empty_graph_cases();
207 test_return_value();
208 return boost::report_errors();
209}
210

source code of boost/libs/graph/test/vf2_sub_graph_iso_test_2.cpp