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.