boost_1_45_0/libs/graph/example/mcgregor_subgraphs_example.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 <fstream>
#include <iostream>
#include <string>

#include <boost/lexical_cast.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/graph/mcgregor_common_subgraphs.hpp>
#include <boost/property_map/shared_array_property_map.hpp>

using namespace boost;

// Callback that looks for the first common subgraph whose size
// matches the user's preference.
template <typename Graph>
struct example_callback {

  typedef typename graph_traits<Graph>::vertices_size_type VertexSizeFirst;

  example_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,
                  VertexSizeFirst subgraph_size) {

    // Fill membership map for first graph
    typedef typename property_map<Graph, vertex_index_t>::type VertexIndexMap;
    typedef shared_array_property_map<bool, VertexIndexMap> MembershipMap;
      
    MembershipMap membership_map1(num_vertices(m_graph1),
                                  get(vertex_index, m_graph1));

    fill_membership_map<Graph>(m_graph1, correspondence_map_1_to_2, membership_map1);

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

    MembershipFilteredGraph subgraph1 =
      make_membership_filtered_graph(m_graph1, membership_map1);

    // Print the graph out to the console
    std::cout << "Found common subgraph (size " << subgraph_size << ")" << std::endl;
    print_graph(subgraph1);
    std::cout << std::endl;

    // Explore the entire space
    return (true);
  }

private:
  const Graph& m_graph1;
  VertexSizeFirst m_max_subgraph_size;
};

int main (int argc, char *argv[]) {

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

  typedef graph_traits<Graph>::vertex_descriptor Vertex;
  typedef graph_traits<Graph>::edge_descriptor Edge;

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

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

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

  // Graph that looks like a triangle
  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);

  std::cout << "First graph:" << std::endl;
  print_graph(graph_simple1);
  std::cout << std::endl;

  // Triangle with an extra vertex
  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);

  std::cout << "Second graph:" << std::endl;
  print_graph(graph_simple2);
  std::cout << std::endl;

  // All subgraphs
  std::cout << "mcgregor_common_subgraphs:" << std::endl;
  mcgregor_common_subgraphs
    (graph_simple1, graph_simple2, true, user_callback,
     vertices_equivalent(make_property_map_equivalent(vname_map_simple1, vname_map_simple2))); 
  std::cout << std::endl;

  // Unique subgraphs
  std::cout << "mcgregor_common_subgraphs_unique:" << std::endl;
  mcgregor_common_subgraphs_unique
    (graph_simple1, graph_simple2, true, user_callback,
     vertices_equivalent(make_property_map_equivalent(vname_map_simple1, vname_map_simple2))); 
  std::cout << std::endl;

  // Maximum subgraphs
  std::cout << "mcgregor_common_subgraphs_maximum:" << std::endl;
  mcgregor_common_subgraphs_maximum
    (graph_simple1, graph_simple2, true, user_callback,
     vertices_equivalent(make_property_map_equivalent(vname_map_simple1, vname_map_simple2))); 
  std::cout << std::endl;

  // Maximum, unique subgraphs
  std::cout << "mcgregor_common_subgraphs_maximum_unique:" << std::endl;
  mcgregor_common_subgraphs_maximum_unique
    (graph_simple1, graph_simple2, true, user_callback,
     vertices_equivalent(make_property_map_equivalent(vname_map_simple1, vname_map_simple2))); 

  return 0;
}