Subject: [Boost-commit] svn:boost r86336 - in trunk: boost/graph libs/graph/test
From: jewillco_at_[hidden]
Date: 2013-10-16 22:51:15
Author: jewillco
Date: 2013-10-16 22:51:14 EDT (Wed, 16 Oct 2013)
New Revision: 86336
URL: http://svn.boost.org/trac/boost/changeset/86336
Log:
Made some of changes from #9246: added new test case (modifying tests on callback usage to match current documentation); removed special-casing of empty graphs; added patch from #9246 for correct return values; did not make change to documentation suggested there since I chose to have the callback called even for empty graphs; fixes #9246
Added:
trunk/libs/graph/test/vf2_sub_graph_iso_test_2.cpp (contents, props changed)
Text files modified:
trunk/boost/graph/vf2_sub_graph_iso.hpp | 12 -
trunk/libs/graph/test/Jamfile.v2 | 1
trunk/libs/graph/test/vf2_sub_graph_iso_test_2.cpp | 194 ++++++++++++++++++++++++++++++++++++++++
3 files changed, 199 insertions(+), 8 deletions(-)
Modified: trunk/boost/graph/vf2_sub_graph_iso.hpp
==============================================================================
--- trunk/boost/graph/vf2_sub_graph_iso.hpp Wed Oct 16 13:49:10 2013 (r86335)
+++ trunk/boost/graph/vf2_sub_graph_iso.hpp 2013-10-16 22:51:14 EDT (Wed, 16 Oct 2013) (r86336)
@@ -690,11 +690,13 @@
typedef vf2_match_continuation<Graph1, Graph2, VertexOrder1> match_continuation_type;
std::vector<match_continuation_type> k;
+ bool found_match = false;
recur:
if (s.success()) {
if (!s.call_back(user_callback))
- return false;
+ return true;
+ found_match = true;
goto back_track;
}
@@ -726,7 +728,7 @@
back_track:
if (k.empty())
- return true;
+ return found_match;
const match_continuation_type kk = k.back();
graph1_verts_iter = kk.graph1_verts_iter;
@@ -887,9 +889,6 @@
if (num_edges_small > num_edges_large)
return false;
- if ((num_vertices(graph_small) == 0) && (num_vertices(graph_large) == 0))
- return true;
-
detail::state<GraphSmall, GraphLarge, IndexMapSmall, IndexMapLarge,
EdgeEquivalencePredicate, VertexEquivalencePredicate,
SubGraphIsoMapCallback, problem_selection>
@@ -1123,9 +1122,6 @@
if (num_edges1 != num_edges2)
return false;
- if ((num_vertices(graph1) == 0) && (num_vertices(graph2) == 0))
- return true;
-
detail::state<Graph1, Graph2, IndexMap1, IndexMap2,
EdgeEquivalencePredicate, VertexEquivalencePredicate,
GraphIsoMapCallback, detail::isomorphism>
Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2 Wed Oct 16 13:49:10 2013 (r86335)
+++ trunk/libs/graph/test/Jamfile.v2 2013-10-16 22:51:14 EDT (Wed, 16 Oct 2013) (r86336)
@@ -128,6 +128,7 @@
[ run stoer_wagner_test.cpp ../../test/build//boost_unit_test_framework/<link>static : $(TEST_DIR) ]
[ compile filtered_graph_properties_dijkstra.cpp ]
[ run vf2_sub_graph_iso_test.cpp ]
+ [ run vf2_sub_graph_iso_test_2.cpp ]
[ run hawick_circuits.cpp ]
[ run successive_shortest_path_nonnegative_weights_test.cpp ../../test/build//boost_unit_test_framework/<link>static ]
[ run cycle_canceling_test.cpp ../../test/build//boost_unit_test_framework/<link>static ]
Added: trunk/libs/graph/test/vf2_sub_graph_iso_test_2.cpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/libs/graph/test/vf2_sub_graph_iso_test_2.cpp 2013-10-16 22:51:14 EDT (Wed, 16 Oct 2013) (r86336)
@@ -0,0 +1,194 @@
+//=======================================================================
+// Boost.Graph library vf2_sub_graph_iso test 2
+// Test of return value and behaviour with empty graphs
+//
+// Copyright (C) 2013 Jakob Lykke Andersen, University of Southern Denmark (jlandersen_at_[hidden])
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//=======================================================================
+
+#include <iostream>
+#include <boost/test/minimal.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/vf2_sub_graph_iso.hpp>
+
+struct test_callback {
+ test_callback(bool &got_hit, bool stop) : got_hit(got_hit), stop(stop) { }
+
+ template<typename Map1To2, typename Map2To1>
+ bool operator()(Map1To2 map1to2, Map2To1 map2to1) {
+ got_hit = true;
+ return stop;
+ }
+
+ bool &got_hit;
+ bool stop;
+};
+
+struct false_predicate {
+ template<typename VertexOrEdge1, typename VertexOrEdge2>
+ bool operator()(VertexOrEdge1 ve1, VertexOrEdge2 ve2) const {
+ return false;
+ }
+};
+
+void test_empty_graph_cases() {
+ typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS> Graph;
+ Graph gEmpty, gLarge;
+ add_vertex(gLarge);
+
+ { // isomorphism
+ bool got_hit = false;
+ test_callback callback(got_hit, true);
+ bool exists = vf2_graph_iso(gEmpty, gEmpty, callback);
+ BOOST_CHECK(exists);
+ BOOST_CHECK(got_hit); // even empty matches are reported
+ }
+ { // subgraph isomorphism (induced)
+ { // empty vs. empty
+ bool got_hit = false;
+ test_callback callback(got_hit, true);
+ bool exists = vf2_subgraph_iso(gEmpty, gEmpty, callback);
+ BOOST_CHECK(exists);
+ BOOST_CHECK(got_hit); // even empty matches are reported
+ }
+ { // empty vs. non-empty
+ bool got_hit = false;
+ test_callback callback(got_hit, true);
+ bool exists = vf2_subgraph_iso(gEmpty, gLarge, callback);
+ BOOST_CHECK(exists);
+ BOOST_CHECK(got_hit); // even empty matches are reported
+ }
+ }
+ { // subgraph monomorphism (non-induced subgraph isomorphism)
+ { // empty vs. empty
+ bool got_hit = false;
+ test_callback callback(got_hit, true);
+ bool exists = vf2_subgraph_mono(gEmpty, gEmpty, callback);
+ BOOST_CHECK(exists);
+ BOOST_CHECK(got_hit); // even empty matches are reported
+ }
+ { // empty vs. non-empty
+ bool got_hit = false;
+ test_callback callback(got_hit, true);
+ bool exists = vf2_subgraph_mono(gEmpty, gLarge, callback);
+ BOOST_CHECK(exists);
+ BOOST_CHECK(got_hit); // even empty matches are reported
+ }
+ }
+}
+
+void test_return_value() {
+ typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS> Graph;
+ typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
+ Graph gSmall, gLarge;
+ add_vertex(gSmall);
+ Vertex v1 = add_vertex(gLarge);
+ Vertex v2 = add_vertex(gLarge);
+ add_edge(v1, v2, gLarge);
+
+ { // isomorphism
+ { // no morphism due to sizes
+ bool got_hit = false;
+ test_callback callback(got_hit, true);
+ bool exists = vf2_graph_iso(gSmall, gLarge, callback);
+ BOOST_CHECK(!exists);
+ BOOST_CHECK(!got_hit);
+ }
+ { // no morphism due to vertex mismatches
+ bool got_hit = false;
+ test_callback callback(got_hit, true);
+ false_predicate pred;
+ bool exists = vf2_graph_iso(gLarge, gLarge, callback, vertex_order_by_mult(gLarge),
+ boost::edges_equivalent(pred).vertices_equivalent(pred));
+ BOOST_CHECK(!exists);
+ BOOST_CHECK(!got_hit);
+ }
+ { // morphism, find all
+ bool got_hit = false;
+ test_callback callback(got_hit, false);
+ bool exists = vf2_graph_iso(gLarge, gLarge, callback);
+ BOOST_CHECK(exists);
+ BOOST_CHECK(got_hit);
+ }
+ { // morphism, stop after first hit
+ bool got_hit = false;
+ test_callback callback(got_hit, true);
+ bool exists = vf2_graph_iso(gLarge, gLarge, callback);
+ BOOST_CHECK(exists);
+ BOOST_CHECK(got_hit);
+ }
+ }
+ { // subgraph isomorphism (induced)
+ { // no morphism due to sizes
+ bool got_hit = false;
+ test_callback callback(got_hit, true);
+ bool exists = vf2_subgraph_iso(gLarge, gSmall, callback);
+ BOOST_CHECK(!exists);
+ BOOST_CHECK(!got_hit);
+ }
+ { // no morphism due to vertex mismatches
+ bool got_hit = false;
+ test_callback callback(got_hit, true);
+ false_predicate pred;
+ bool exists = vf2_subgraph_iso(gLarge, gLarge, callback, vertex_order_by_mult(gLarge),
+ boost::edges_equivalent(pred).vertices_equivalent(pred));
+ BOOST_CHECK(!exists);
+ BOOST_CHECK(!got_hit);
+ }
+ { // morphism, find all
+ bool got_hit = false;
+ test_callback callback(got_hit, false);
+ bool exists = vf2_subgraph_iso(gLarge, gLarge, callback);
+ BOOST_CHECK(exists);
+ BOOST_CHECK(got_hit);
+ }
+ { // morphism, stop after first hit
+ bool got_hit = false;
+ test_callback callback(got_hit, true);
+ bool exists = vf2_subgraph_iso(gLarge, gLarge, callback);
+ BOOST_CHECK(exists);
+ BOOST_CHECK(got_hit);
+ }
+ }
+ { // subgraph monomorphism (non-induced subgraph isomorphism)
+ { // no morphism due to sizes
+ bool got_hit = false;
+ test_callback callback(got_hit, true);
+ bool exists = vf2_subgraph_mono(gLarge, gSmall, callback);
+ BOOST_CHECK(!exists);
+ BOOST_CHECK(!got_hit);
+ }
+ { // no morphism due to vertex mismatches
+ bool got_hit = false;
+ test_callback callback(got_hit, true);
+ false_predicate pred;
+ bool exists = vf2_subgraph_mono(gLarge, gLarge, callback, vertex_order_by_mult(gLarge),
+ boost::edges_equivalent(pred).vertices_equivalent(pred));
+ BOOST_CHECK(!exists);
+ BOOST_CHECK(!got_hit);
+ }
+ { // morphism, find all
+ bool got_hit = false;
+ test_callback callback(got_hit, false);
+ bool exists = vf2_subgraph_mono(gLarge, gLarge, callback);
+ BOOST_CHECK(exists);
+ BOOST_CHECK(got_hit);
+ }
+ { // morphism, stop after first hit
+ bool got_hit = false;
+ test_callback callback(got_hit, true);
+ bool exists = vf2_subgraph_mono(gLarge, gLarge, callback);
+ BOOST_CHECK(exists);
+ BOOST_CHECK(got_hit);
+ }
+ }
+}
+
+int test_main(int argc, char* argv[]) {
+ test_empty_graph_cases();
+ test_return_value();
+ return 0;
+}