]>
git.proxmox.com Git - ceph.git/blob - ceph/src/boost/libs/graph/test/vf2_sub_graph_iso_test_2.cpp
1 //=======================================================================
2 // Boost.Graph library vf2_sub_graph_iso test 2
3 // Test of return value and behaviour with empty graphs
5 // Copyright (C) 2013 Jakob Lykke Andersen, University of Southern Denmark (jlandersen@imada.sdu.dk)
7 // Distributed under the Boost Software License, Version 1.0. (See
8 // accompanying file LICENSE_1_0.txt or copy at
9 // http://www.boost.org/LICENSE_1_0.txt)
10 //=======================================================================
13 #include <boost/test/minimal.hpp>
14 #include <boost/graph/adjacency_list.hpp>
15 #include <boost/graph/vf2_sub_graph_iso.hpp>
17 struct test_callback
{
18 test_callback(bool &got_hit
, bool stop
) : got_hit(got_hit
), stop(stop
) { }
20 template<typename Map1To2
, typename Map2To1
>
21 bool operator()(Map1To2 map1to2
, Map2To1 map2to1
) {
30 struct false_predicate
{
31 template<typename VertexOrEdge1
, typename VertexOrEdge2
>
32 bool operator()(VertexOrEdge1 ve1
, VertexOrEdge2 ve2
) const {
37 void test_empty_graph_cases() {
38 typedef boost::adjacency_list
<boost::vecS
, boost::vecS
, boost::bidirectionalS
> Graph
;
44 test_callback
callback(got_hit
, true);
45 bool exists
= vf2_graph_iso(gEmpty
, gEmpty
, callback
);
47 BOOST_CHECK(got_hit
); // even empty matches are reported
49 { // subgraph isomorphism (induced)
52 test_callback
callback(got_hit
, true);
53 bool exists
= vf2_subgraph_iso(gEmpty
, gEmpty
, callback
);
55 BOOST_CHECK(got_hit
); // even empty matches are reported
57 { // empty vs. non-empty
59 test_callback
callback(got_hit
, true);
60 bool exists
= vf2_subgraph_iso(gEmpty
, gLarge
, callback
);
62 BOOST_CHECK(got_hit
); // even empty matches are reported
65 { // subgraph monomorphism (non-induced subgraph isomorphism)
68 test_callback
callback(got_hit
, true);
69 bool exists
= vf2_subgraph_mono(gEmpty
, gEmpty
, callback
);
71 BOOST_CHECK(got_hit
); // even empty matches are reported
73 { // empty vs. non-empty
75 test_callback
callback(got_hit
, true);
76 bool exists
= vf2_subgraph_mono(gEmpty
, gLarge
, callback
);
78 BOOST_CHECK(got_hit
); // even empty matches are reported
83 void test_return_value() {
84 typedef boost::adjacency_list
<boost::vecS
, boost::vecS
, boost::bidirectionalS
> Graph
;
85 typedef boost::graph_traits
<Graph
>::vertex_descriptor Vertex
;
88 Vertex v1
= add_vertex(gLarge
);
89 Vertex v2
= add_vertex(gLarge
);
90 add_edge(v1
, v2
, gLarge
);
93 { // no morphism due to sizes
95 test_callback
callback(got_hit
, true);
96 bool exists
= vf2_graph_iso(gSmall
, gLarge
, callback
);
98 BOOST_CHECK(!got_hit
);
100 { // no morphism due to vertex mismatches
101 bool got_hit
= false;
102 test_callback
callback(got_hit
, true);
103 false_predicate pred
;
104 bool exists
= vf2_graph_iso(gLarge
, gLarge
, callback
, vertex_order_by_mult(gLarge
),
105 boost::edges_equivalent(pred
).vertices_equivalent(pred
));
106 BOOST_CHECK(!exists
);
107 BOOST_CHECK(!got_hit
);
109 { // morphism, find all
110 bool got_hit
= false;
111 test_callback
callback(got_hit
, false);
112 bool exists
= vf2_graph_iso(gLarge
, gLarge
, callback
);
114 BOOST_CHECK(got_hit
);
116 { // morphism, stop after first hit
117 bool got_hit
= false;
118 test_callback
callback(got_hit
, true);
119 bool exists
= vf2_graph_iso(gLarge
, gLarge
, callback
);
121 BOOST_CHECK(got_hit
);
124 { // subgraph isomorphism (induced)
125 { // no morphism due to sizes
126 bool got_hit
= false;
127 test_callback
callback(got_hit
, true);
128 bool exists
= vf2_subgraph_iso(gLarge
, gSmall
, callback
);
129 BOOST_CHECK(!exists
);
130 BOOST_CHECK(!got_hit
);
132 { // no morphism due to vertex mismatches
133 bool got_hit
= false;
134 test_callback
callback(got_hit
, true);
135 false_predicate pred
;
136 bool exists
= vf2_subgraph_iso(gLarge
, gLarge
, callback
, vertex_order_by_mult(gLarge
),
137 boost::edges_equivalent(pred
).vertices_equivalent(pred
));
138 BOOST_CHECK(!exists
);
139 BOOST_CHECK(!got_hit
);
141 { // morphism, find all
142 bool got_hit
= false;
143 test_callback
callback(got_hit
, false);
144 bool exists
= vf2_subgraph_iso(gLarge
, gLarge
, callback
);
146 BOOST_CHECK(got_hit
);
148 { // morphism, stop after first hit
149 bool got_hit
= false;
150 test_callback
callback(got_hit
, true);
151 bool exists
= vf2_subgraph_iso(gLarge
, gLarge
, callback
);
153 BOOST_CHECK(got_hit
);
156 { // subgraph monomorphism (non-induced subgraph isomorphism)
157 { // no morphism due to sizes
158 bool got_hit
= false;
159 test_callback
callback(got_hit
, true);
160 bool exists
= vf2_subgraph_mono(gLarge
, gSmall
, callback
);
161 BOOST_CHECK(!exists
);
162 BOOST_CHECK(!got_hit
);
164 { // no morphism due to vertex mismatches
165 bool got_hit
= false;
166 test_callback
callback(got_hit
, true);
167 false_predicate pred
;
168 bool exists
= vf2_subgraph_mono(gLarge
, gLarge
, callback
, vertex_order_by_mult(gLarge
),
169 boost::edges_equivalent(pred
).vertices_equivalent(pred
));
170 BOOST_CHECK(!exists
);
171 BOOST_CHECK(!got_hit
);
173 { // morphism, find all
174 bool got_hit
= false;
175 test_callback
callback(got_hit
, false);
176 bool exists
= vf2_subgraph_mono(gLarge
, gLarge
, callback
);
178 BOOST_CHECK(got_hit
);
180 { // morphism, stop after first hit
181 bool got_hit
= false;
182 test_callback
callback(got_hit
, true);
183 bool exists
= vf2_subgraph_mono(gLarge
, gLarge
, callback
);
185 BOOST_CHECK(got_hit
);
190 int test_main(int argc
, char* argv
[]) {
191 test_empty_graph_cases();