123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194 |
- //=======================================================================
- // 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;
- }
|