graph/test/mcgregor_subgraphs_test.cpp

//=======================================================================
// Copyright 2009 Trustees of Indiana University.
// Authors: Michael Hansen
//
// 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 <cmath>
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>

#include <boost/lexical_cast.hpp>
#include <boost/random.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/isomorphism.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/graph/random.hpp>
#include <boost/graph/mcgregor_common_subgraphs.hpp>
#include <boost/property_map/shared_array_property_map.hpp>
#include <boost/test/minimal.hpp>

bool was_common_subgraph_found = false, output_graphs = false;
std::vector<std::string> simple_subgraph_list;

// Callback that compares incoming graphs to the supplied common
// subgraph.
template <typename Graph>
struct test_callback {

   test_callback(Graph& common_subgraph,
                 const Graph& graph1,
                 const Graph& graph2) :
    m_graph1(graph1),
    m_graph2(graph2),
    m_common_subgraph(common_subgraph) { }

  template <typename CorrespondenceMapFirstToSecond,
            typename CorrespondenceMapSecondToFirst>
  bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
                  CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
                  typename boost::graph_traits<Graph>::vertices_size_type subgraph_size) {

    typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
    typedef typename boost::graph_traits<Graph>::edge_descriptor Edge;
    typedef std::pair<Edge, bool> EdgeInfo;

    typedef typename boost::property_map<Graph, boost::vertex_index_t>::type VertexIndexMap;
    typedef typename boost::property_map<Graph, boost::vertex_name_t>::type VertexNameMap;
    typedef typename boost::property_map<Graph, boost::edge_name_t>::type EdgeNameMap;

    if (subgraph_size != num_vertices(m_common_subgraph)) {
      return (true);
    }

    // Fill membership maps for both graphs
    typedef boost::shared_array_property_map<bool, VertexIndexMap> MembershipMap;

    MembershipMap membership_map1(num_vertices(m_graph1),
                                  get(boost::vertex_index, m_graph1));

    MembershipMap membership_map2(num_vertices(m_graph2),
                                  get(boost::vertex_index, m_graph2));

    boost::fill_membership_map<Graph>(m_graph1, correspondence_map_1_to_2, membership_map1);
    boost::fill_membership_map<Graph>(m_graph2, correspondence_map_2_to_1, membership_map2);

    // Generate filtered graphs using membership maps
    typedef typename boost::membership_filtered_graph_traits<Graph, MembershipMap>::graph_type
      MembershipFilteredGraph;

    MembershipFilteredGraph subgraph1 =
      boost::make_membership_filtered_graph(m_graph1, membership_map1);

    MembershipFilteredGraph subgraph2 =
      boost::make_membership_filtered_graph(m_graph2, membership_map2);

    VertexIndexMap vindex_map1 = get(boost::vertex_index, subgraph1);
    VertexIndexMap vindex_map2 = get(boost::vertex_index, subgraph2);

    VertexNameMap vname_map_common = get(boost::vertex_name, m_common_subgraph);
    VertexNameMap vname_map1 = get(boost::vertex_name, subgraph1);
    VertexNameMap vname_map2 = get(boost::vertex_name, subgraph2);

    EdgeNameMap ename_map_common = get(boost::edge_name, m_common_subgraph);
    EdgeNameMap ename_map1 = get(boost::edge_name, subgraph1);
    EdgeNameMap ename_map2 = get(boost::edge_name, subgraph2);

    // Verify that subgraph1 matches the supplied common subgraph
    BGL_FORALL_VERTICES_T(vertex1, subgraph1, MembershipFilteredGraph) {

      Vertex vertex_common = vertex(get(vindex_map1, vertex1), m_common_subgraph);

      // Match vertex names
      if (get(vname_map_common, vertex_common) != get(vname_map1, vertex1)) {

        // Keep looking
        return (true);

      }

      BGL_FORALL_VERTICES_T(vertex1_2, subgraph1, MembershipFilteredGraph) {

        Vertex vertex_common2 = vertex(get(vindex_map1, vertex1_2), m_common_subgraph);
        EdgeInfo edge_common = edge(vertex_common, vertex_common2, m_common_subgraph);
        EdgeInfo edge1 = edge(vertex1, vertex1_2, subgraph1);

        if ((edge_common.second != edge1.second) ||
            ((edge_common.second && edge1.second) &&
             (get(ename_map_common, edge_common.first) != get(ename_map1, edge1.first)))) {

          // Keep looking
          return (true);

        }
      }

    } // BGL_FORALL_VERTICES_T (subgraph1)

    // Verify that subgraph2 matches the supplied common subgraph
    BGL_FORALL_VERTICES_T(vertex2, subgraph2, MembershipFilteredGraph) {

      Vertex vertex_common = vertex(get(vindex_map2, vertex2), m_common_subgraph);

      // Match vertex names
      if (get(vname_map_common, vertex_common) != get(vname_map2, vertex2)) {

        // Keep looking
        return (true);

      }

      BGL_FORALL_VERTICES_T(vertex2_2, subgraph2, MembershipFilteredGraph) {

        Vertex vertex_common2 = vertex(get(vindex_map2, vertex2_2), m_common_subgraph);
        EdgeInfo edge_common = edge(vertex_common, vertex_common2, m_common_subgraph);
        EdgeInfo edge2 = edge(vertex2, vertex2_2, subgraph2);

        if ((edge_common.second != edge2.second) ||
            ((edge_common.second && edge2.second) &&
             (get(ename_map_common, edge_common.first) != get(ename_map2, edge2.first)))) {

          // Keep looking
          return (true);

        }
      }

    } // BGL_FORALL_VERTICES_T (subgraph2)

    // Check isomorphism just to be thorough
    if (verify_isomorphism(subgraph1, subgraph2, correspondence_map_1_to_2)) {

      was_common_subgraph_found = true;

      if (output_graphs) {

        std::fstream file_subgraph("found_common_subgraph.dot", std::fstream::out);
        write_graphviz(file_subgraph, subgraph1,
                       make_label_writer(get(boost::vertex_name, m_graph1)),
                       make_label_writer(get(boost::edge_name, m_graph1)));

      }

      // Stop iterating
      return (false);

    }

    // Keep looking
    return (true);
  }

private:
  const Graph& m_graph1, m_graph2;
  Graph& m_common_subgraph;
};

template <typename Graph>
struct simple_callback {

  simple_callback(const Graph& graph1) :
    m_graph1(graph1) { }

  template <typename CorrespondenceMapFirstToSecond,
            typename CorrespondenceMapSecondToFirst>
  bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
                  CorrespondenceMapSecondToFirst /*correspondence_map_2_to_1*/,
                  typename boost::graph_traits<Graph>::vertices_size_type /*subgraph_size*/) {

    typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;

    std::stringstream subgraph_string;

    BGL_FORALL_VERTICES_T(vertex1, m_graph1, Graph) {

      Vertex vertex2 = get(correspondence_map_1_to_2, vertex1);

      if (vertex2 != boost::graph_traits<Graph>::null_vertex()) {
        subgraph_string << vertex1 << "," << vertex2 << " ";
      }

    }

    simple_subgraph_list.push_back(subgraph_string.str());

    return (true);
  }

private:
  const Graph& m_graph1;

};

template <typename Graph,
          typename RandomNumberGenerator,
          typename VertexNameMap,
          typename EdgeNameMap>
void add_random_vertices(Graph& graph, RandomNumberGenerator& generator,
                         int vertices_to_create, int max_edges_per_vertex,
                         VertexNameMap vname_map, EdgeNameMap ename_map) {

  typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
  typedef std::vector<Vertex> VertexList;

  VertexList new_vertices;

  for (int v_index = 0; v_index < vertices_to_create; ++v_index) {

    Vertex new_vertex = add_vertex(graph);
    put(vname_map, new_vertex, generator());
    new_vertices.push_back(new_vertex);

  }

  // Add edges for every new vertex. Care is taken to avoid parallel
  // edges.
  for (typename VertexList::const_iterator v_iter = new_vertices.begin();
       v_iter != new_vertices.end(); ++v_iter) {

    Vertex source_vertex = *v_iter;
    int edges_for_vertex = (std::min)((int)(generator() % max_edges_per_vertex) + 1,
                                      (int)num_vertices(graph));

    while (edges_for_vertex > 0) {

      Vertex target_vertex = random_vertex(graph, generator);

      if (source_vertex == target_vertex) {
        continue;
      }

      BGL_FORALL_OUTEDGES_T(source_vertex, edge, graph, Graph) {
        if (target(edge, graph) == target_vertex) {
          continue;
        }
      }

      put(ename_map, add_edge(source_vertex, target_vertex, graph).first,
          generator());

      edges_for_vertex--;
    }
  }
}

bool has_subgraph_string(std::string set_string) {
  return (std::find(simple_subgraph_list.begin(), simple_subgraph_list.end(),
                    set_string) != simple_subgraph_list.end());
}

int test_main (int argc, char *argv[]) {
  int vertices_to_create = 10;
  int max_edges_per_vertex = 2;
  std::size_t random_seed = time(0);

  if (argc > 1) {
    vertices_to_create = boost::lexical_cast<int>(argv[1]);
  }

  if (argc > 2) {
    max_edges_per_vertex = boost::lexical_cast<int>(argv[2]);
  }

  if (argc > 3) {
    output_graphs = boost::lexical_cast<bool>(argv[3]);
  }

  if (argc > 4) {
    random_seed = boost::lexical_cast<std::size_t>(argv[4]);
  }

  boost::minstd_rand generator(random_seed);

  // Using a vecS graph here so that we don't have to mess around with
  // a vertex index map; it will be implicit.
  typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS,
    boost::property<boost::vertex_name_t, unsigned int,
    boost::property<boost::vertex_index_t, unsigned int> >,
    boost::property<boost::edge_name_t, unsigned int> > Graph;

  typedef boost::property_map<Graph, boost::vertex_name_t>::type VertexNameMap;
  typedef boost::property_map<Graph, boost::edge_name_t>::type EdgeNameMap;

  // Generate a random common subgraph and then add random vertices
  // and edges to the two parent graphs.
  Graph common_subgraph, graph1, graph2;

  VertexNameMap vname_map_common = get(boost::vertex_name, common_subgraph);
  VertexNameMap vname_map1 = get(boost::vertex_name, graph1);
  VertexNameMap vname_map2 = get(boost::vertex_name, graph2);

  EdgeNameMap ename_map_common = get(boost::edge_name, common_subgraph);
  EdgeNameMap ename_map1 = get(boost::edge_name, graph1);
  EdgeNameMap ename_map2 = get(boost::edge_name, graph2);

  for (int vindex = 0; vindex < vertices_to_create; ++vindex) {
    put(vname_map_common, add_vertex(common_subgraph), generator());
  }

  BGL_FORALL_VERTICES(source_vertex, common_subgraph, Graph) {

    BGL_FORALL_VERTICES(target_vertex, common_subgraph, Graph) {

      if (source_vertex != target_vertex) {
        put(ename_map_common,
            add_edge(source_vertex, target_vertex, common_subgraph).first,
            generator());
      }
    }
  }

  boost::randomize_property<boost::vertex_name_t>(common_subgraph, generator);
  boost::randomize_property<boost::edge_name_t>(common_subgraph, generator);

  boost::copy_graph(common_subgraph, graph1);
  boost::copy_graph(common_subgraph, graph2);

  // Randomly add vertices and edges to graph1 and graph2.
  add_random_vertices(graph1, generator, vertices_to_create,
                      max_edges_per_vertex, vname_map1, ename_map1);

  add_random_vertices(graph2, generator, vertices_to_create,
                      max_edges_per_vertex, vname_map2, ename_map2);

  if (output_graphs) {

    std::fstream file_graph1("graph1.dot", std::fstream::out),
      file_graph2("graph2.dot", std::fstream::out),
      file_common_subgraph("expected_common_subgraph.dot", std::fstream::out);

    write_graphviz(file_graph1, graph1,
                   make_label_writer(vname_map1),
                   make_label_writer(ename_map1));

    write_graphviz(file_graph2, graph2,
                   make_label_writer(vname_map2),
                   make_label_writer(ename_map2));

    write_graphviz(file_common_subgraph, common_subgraph,
                   make_label_writer(get(boost::vertex_name, common_subgraph)),
                   make_label_writer(get(boost::edge_name, common_subgraph)));

  }

  std::cout << "Searching for common subgraph of size " <<
    num_vertices(common_subgraph) << std::endl;

  test_callback<Graph> user_callback(common_subgraph, graph1, graph2);

  boost::mcgregor_common_subgraphs(graph1, graph2, true, user_callback,
    boost::edges_equivalent(boost::make_property_map_equivalent(ename_map1, ename_map2)).
    vertices_equivalent(boost::make_property_map_equivalent(vname_map1, vname_map2)));

  BOOST_CHECK(was_common_subgraph_found);

  // Test maximum and unique variants on known graphs
  Graph graph_simple1, graph_simple2;
  simple_callback<Graph> user_callback_simple(graph_simple1);

  VertexNameMap vname_map_simple1 = get(boost::vertex_name, graph_simple1);
  VertexNameMap vname_map_simple2 = get(boost::vertex_name, graph_simple2);

  put(vname_map_simple1, add_vertex(graph_simple1), 1);
  put(vname_map_simple1, add_vertex(graph_simple1), 2);
  put(vname_map_simple1, add_vertex(graph_simple1), 3);

  add_edge(0, 1, graph_simple1);
  add_edge(0, 2, graph_simple1);
  add_edge(1, 2, graph_simple1);

  put(vname_map_simple2, add_vertex(graph_simple2), 1);
  put(vname_map_simple2, add_vertex(graph_simple2), 2);
  put(vname_map_simple2, add_vertex(graph_simple2), 3);
  put(vname_map_simple2, add_vertex(graph_simple2), 4);

  add_edge(0, 1, graph_simple2);
  add_edge(0, 2, graph_simple2);
  add_edge(1, 2, graph_simple2);
  add_edge(1, 3, graph_simple2);

  // Unique subgraphs
  std::cout << "Searching for unique subgraphs" << std::endl;
  boost::mcgregor_common_subgraphs_unique(graph_simple1, graph_simple2,
    true, user_callback_simple,
    boost::vertices_equivalent(boost::make_property_map_equivalent(vname_map_simple1, vname_map_simple2)));

  BOOST_CHECK(has_subgraph_string("0,0 1,1 "));
  BOOST_CHECK(has_subgraph_string("0,0 1,1 2,2 "));
  BOOST_CHECK(has_subgraph_string("0,0 2,2 "));
  BOOST_CHECK(has_subgraph_string("1,1 2,2 "));

  if (output_graphs) {
    std::copy(simple_subgraph_list.begin(), simple_subgraph_list.end(),
              std::ostream_iterator<std::string>(std::cout, "\n"));

    std::cout << std::endl;
  }

  simple_subgraph_list.clear();

  // Maximum subgraphs
  std::cout << "Searching for maximum subgraphs" << std::endl;
  boost::mcgregor_common_subgraphs_maximum(graph_simple1, graph_simple2,
    true, user_callback_simple,
    boost::vertices_equivalent(boost::make_property_map_equivalent(vname_map_simple1, vname_map_simple2)));

  BOOST_CHECK(has_subgraph_string("0,0 1,1 2,2 "));

  if (output_graphs) {
    std::copy(simple_subgraph_list.begin(), simple_subgraph_list.end(),
              std::ostream_iterator<std::string>(std::cout, "\n"));

    std::cout << std::endl;
  }

  simple_subgraph_list.clear();

  // Maximum, unique subgraphs
  std::cout << "Searching for maximum unique subgraphs" << std::endl;
  boost::mcgregor_common_subgraphs_maximum_unique(graph_simple1, graph_simple2,
    true, user_callback_simple,
    boost::vertices_equivalent(boost::make_property_map_equivalent(vname_map_simple1, vname_map_simple2)));

  BOOST_CHECK(simple_subgraph_list.size() == 1);
  BOOST_CHECK(has_subgraph_string("0,0 1,1 2,2 "));

  if (output_graphs) {
    std::copy(simple_subgraph_list.begin(), simple_subgraph_list.end(),
              std::ostream_iterator<std::string>(std::cout, "\n"));

    std::cout << std::endl;
  }

  return 0;
}