boost/libs/graph/test/vf2_sub_graph_iso_test_2.cpp

//=======================================================================
// 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@imada.sdu.dk)
//
// 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;
}