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
#include
#include
#include
#include
#include
#include
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
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::type
VertexIndexMap;
typedef shared_array_property_map 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_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 >,
property > Graph;
typedef graph_traits<Graph>::vertex_descriptor Vertex;
typedef graph_traits<Graph>::edge_descriptor Edge;
typedef property_map::type VertexNameMap;
typedef property_map::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.
