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
   4 //
   5 // Copyright (C) 2013 Jakob Lykke Andersen, University of Southern Denmark (jlandersen@imada.sdu.dk)
   6 //
   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 //=======================================================================
  11
  12 #include <iostream>
  13 #include <boost/test/minimal.hpp>
  14 #include <boost/graph/adjacency_list.hpp>
  15 #include <boost/graph/vf2_sub_graph_iso.hpp>
  16
  17 struct test_callback {
  18   test_callback(bool &got_hit, bool stop) : got_hit(got_hit), stop(stop) { }
  19
  20   template<typename Map1To2, typename Map2To1>
  21   bool operator()(Map1To2 map1to2, Map2To1 map2to1) {
  22     got_hit = true;
  23     return stop;
  24   }
  25
  26   bool &got_hit;
  27   bool stop;
  28 };
  29
  30 struct false_predicate {
  31   template<typename VertexOrEdge1, typename VertexOrEdge2>
  32   bool operator()(VertexOrEdge1 ve1, VertexOrEdge2 ve2) const {
  33     return false;
  34   }
  35 };
  36
  37 void test_empty_graph_cases() {
  38   typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS> Graph;
  39   Graph gEmpty, gLarge;
  40   add_vertex(gLarge);
  41
  42   { // isomorphism
  43     bool got_hit = false;
  44     test_callback callback(got_hit, true);
  45     bool exists = vf2_graph_iso(gEmpty, gEmpty, callback);
  46     BOOST_CHECK(exists);
  47     BOOST_CHECK(got_hit); // even empty matches are reported
  48   }
  49   { // subgraph isomorphism (induced)
  50     { // empty vs. empty
  51       bool got_hit = false;
  52       test_callback callback(got_hit, true);
  53       bool exists = vf2_subgraph_iso(gEmpty, gEmpty, callback);
  54       BOOST_CHECK(exists);
  55       BOOST_CHECK(got_hit); // even empty matches are reported
  56     }
  57     { // empty vs. non-empty
  58       bool got_hit = false;
  59       test_callback callback(got_hit, true);
  60       bool exists = vf2_subgraph_iso(gEmpty, gLarge, callback);
  61       BOOST_CHECK(exists);
  62       BOOST_CHECK(got_hit); // even empty matches are reported
  63     }
  64   }
  65   { // subgraph monomorphism (non-induced subgraph isomorphism)
  66     { // empty vs. empty
  67       bool got_hit = false;
  68       test_callback callback(got_hit, true);
  69       bool exists = vf2_subgraph_mono(gEmpty, gEmpty, callback);
  70       BOOST_CHECK(exists);
  71       BOOST_CHECK(got_hit); // even empty matches are reported
  72     }
  73     { // empty vs. non-empty
  74       bool got_hit = false;
  75       test_callback callback(got_hit, true);
  76       bool exists = vf2_subgraph_mono(gEmpty, gLarge, callback);
  77       BOOST_CHECK(exists);
  78       BOOST_CHECK(got_hit); // even empty matches are reported
  79     }
  80   }
  81 }
  82
  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;
  86   Graph gSmall, gLarge;
  87   add_vertex(gSmall);
  88   Vertex v1 = add_vertex(gLarge);
  89   Vertex v2 = add_vertex(gLarge);
  90   add_edge(v1, v2, gLarge);
  91
  92   { // isomorphism
  93     { // no morphism due to sizes
  94       bool got_hit = false;
  95       test_callback callback(got_hit, true);
  96       bool exists = vf2_graph_iso(gSmall, gLarge, callback);
  97       BOOST_CHECK(!exists);
  98       BOOST_CHECK(!got_hit);
  99     }
 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);
 108     }
 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);
 113       BOOST_CHECK(exists);
 114       BOOST_CHECK(got_hit);
 115     }
 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);
 120       BOOST_CHECK(exists);
 121       BOOST_CHECK(got_hit);
 122     }
 123   }
 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);
 131     }
 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);
 140     }
 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);
 145       BOOST_CHECK(exists);
 146       BOOST_CHECK(got_hit);
 147     }
 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);
 152       BOOST_CHECK(exists);
 153       BOOST_CHECK(got_hit);
 154     }
 155   }
 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);
 163     }
 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);
 172     }
 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);
 177       BOOST_CHECK(exists);
 178       BOOST_CHECK(got_hit);
 179     }
 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);
 184       BOOST_CHECK(exists);
 185       BOOST_CHECK(got_hit);
 186     }
 187   }
 188 }
 189
 190 int test_main(int argc, char* argv[]) {
 191   test_empty_graph_cases();
 192   test_return_value();
 193   return 0;
 194 }