Incorrect result from mcgregor_common_subgraphs. Where can I find more example of this MCS solver?

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/m... 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<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); 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-sub... Sent from the Boost - Users mailing list archive at Nabble.com.

On Mon, 8 Jul 2013, dante0125 wrote:
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/m...
My first question is where can I find more example of this MCS solver?
One place is libs/graph/test/mcgregor_subgraphs_test.cpp in the Boost source tree.
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.
Have you tried using mcgregor_common_subgraphs_maximum or mcgregor_common_subgraphs_maximum_unique? The algorithm only returns a mapping between vertices, so I'm not sure what you mean by the result missing edges. -- Jeremiah Willcock

Thanks for your reply. For the second part, I know there are four functions to compute the common graphs. I use "mcgregor_common_subgraphs_unique" in this example. This function can return all the common subgraphs between two graphs. When I am replying this post, I tried mcgregor_common_subgraphs_maximum_unique. The result if the same size-7 graph. Because, in the example I mentioned above, the answer seems correct. I use this solver for my project then I found that this solver in many cases can not find the maximum common subgraph. The back-tracking method stops at some points it should not. In this example I used in the post, the program supposed to continue to find the adjacent vertices of vertex 8 but it stops. -- View this message in context: http://boost.2283326.n4.nabble.com/Incorrect-result-from-mcgregor-common-sub... Sent from the Boost - Users mailing list archive at Nabble.com.
participants (2)
-
dante0125
-
Jeremiah Willcock