[Boost-users] Incorrect result from mcgregor_common_subgraphs. Where can I find more example of this MCS solver?

Subject: [Boost-users] Incorrect result from mcgregor_common_subgraphs. Where can I find more example of this MCS solver?
From: dante0125 (gh11c_at_[hidden])
Date: 2013-07-08 14:04:32

Hi, I am a beginner with BGL. Currently I am using mcgregor_common_subgraphs
solver to find all the common subgraphs between two graphs.  The following
link is the only one example showing how to use the library that I can find
from the Internet.
http://svn.kulitorum.com/RepSnapper/Libraries/Boost1.40/libs/graph/example/mcgregor_subgraphs_example.cpp 

My first question is where can I find more example of this MCS solver?
My second question is why some times it can not find maximum common
subgraph. By maximum I mean a common subgraph with largest number of
vertices which is implemented in the code. 
Here I provide an example. This code is modified from
mcgregor_subgraphs_example, I change the graph to undirected graph and add
some vetices and edges. It is obvious that the correct answer should be of
size 9. The answer return by the code missing edge 8-5 and 8-3.

//=======================================================================
// 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, undirectedS,
    property&lt;vertex_name_t, unsigned int,
    property&lt;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);
  put(vname_map_simple1, add_vertex(graph_simple1), 4);
  put(vname_map_simple1, add_vertex(graph_simple1), 5);
  put(vname_map_simple1, add_vertex(graph_simple1), 6);
  put(vname_map_simple1, add_vertex(graph_simple1), 7);
  put(vname_map_simple1, add_vertex(graph_simple1), 8);
  put(vname_map_simple1, add_vertex(graph_simple1), 9);

  add_edge(0, 1, graph_simple1);
  add_edge(0, 2, graph_simple1);
  add_edge(0, 4, graph_simple1);
  add_edge(1, 2, graph_simple1);
  add_edge(1, 3, graph_simple1);
  add_edge(1, 6, graph_simple1);
  add_edge(2, 3, graph_simple1);
  add_edge(2, 4, graph_simple1);
  add_edge(3, 5, graph_simple1);
  add_edge(4, 5, graph_simple1);
  add_edge(5, 6, graph_simple1);
  add_edge(7, 8, graph_simple1);
  add_edge(6, 7, graph_simple1);
  add_edge(8, 5, graph_simple1);
  add_edge(8, 3, 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);
  put(vname_map_simple2, add_vertex(graph_simple2), 5);
  put(vname_map_simple2, add_vertex(graph_simple2), 6);
  put(vname_map_simple2, add_vertex(graph_simple2), 7);
  put(vname_map_simple2, add_vertex(graph_simple2), 8);
  put(vname_map_simple2, add_vertex(graph_simple2), 9);

  add_edge(0, 1, graph_simple2);
  add_edge(0, 2, graph_simple2);
  add_edge(0, 4, graph_simple2);
  add_edge(1, 2, graph_simple2);
  add_edge(1, 5, graph_simple2);
  add_edge(2, 4, graph_simple2);
  add_edge(3, 5, graph_simple2);
  add_edge(3, 6, graph_simple2);
  add_edge(7, 8, graph_simple2);
  add_edge(1, 6, graph_simple2);
  add_edge(6, 7, graph_simple2);
  add_edge(8, 5, graph_simple2);
  add_edge(8, 3, graph_simple2);

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

  // Maximum subgraphs

  // Maximum, 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::cin.get();

  return 0;
}

--
View this message in context: http://boost.2283326.n4.nabble.com/Incorrect-result-from-mcgregor-common-subgraphs-Where-can-I-find-more-example-of-this-MCS-solver-tp4649521.html
Sent from the Boost - Users mailing list archive at Nabble.com.