[Boost-commit] svn:boost r86336 - in trunk: boost/graph libs/graph/test

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;
+}