#include <boost/graph/random.hpp>
#include <boost/graph/mcgregor_common_subgraphs.hpp>
#include <boost/property_map/shared_array_property_map.hpp>
-#include <boost/test/minimal.hpp>
+#include <boost/core/lightweight_test.hpp>
bool was_common_subgraph_found = false, output_graphs = false;
-std::vector<std::string> simple_subgraph_list;
+std::vector< std::string > simple_subgraph_list;
// Callback that compares incoming graphs to the supplied common
// subgraph.
-template <typename Graph>
-struct test_callback {
-
- test_callback(Graph& common_subgraph,
- const Graph& graph1,
- const Graph& graph2) :
- m_graph1(graph1),
- m_graph2(graph2),
- m_common_subgraph(common_subgraph) { }
-
- template <typename CorrespondenceMapFirstToSecond,
- typename CorrespondenceMapSecondToFirst>
- bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
- CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
- typename boost::graph_traits<Graph>::vertices_size_type subgraph_size) {
-
- typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename boost::graph_traits<Graph>::edge_descriptor Edge;
- typedef std::pair<Edge, bool> EdgeInfo;
-
- typedef typename boost::property_map<Graph, boost::vertex_index_t>::type VertexIndexMap;
- typedef typename boost::property_map<Graph, boost::vertex_name_t>::type VertexNameMap;
- typedef typename boost::property_map<Graph, boost::edge_name_t>::type EdgeNameMap;
-
- if (subgraph_size != num_vertices(m_common_subgraph)) {
- return (true);
+template < typename Graph > struct test_callback
+{
+
+ test_callback(
+ Graph& common_subgraph, const Graph& graph1, const Graph& graph2)
+ : m_graph1(graph1), m_graph2(graph2), m_common_subgraph(common_subgraph)
+ {
}
- // Fill membership maps for both graphs
- typedef boost::shared_array_property_map<bool, VertexIndexMap> MembershipMap;
-
- MembershipMap membership_map1(num_vertices(m_graph1),
- get(boost::vertex_index, m_graph1));
+ template < typename CorrespondenceMapFirstToSecond,
+ typename CorrespondenceMapSecondToFirst >
+ bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
+ CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
+ typename boost::graph_traits< Graph >::vertices_size_type subgraph_size)
+ {
+
+ typedef typename boost::graph_traits< Graph >::vertex_descriptor Vertex;
+ typedef typename boost::graph_traits< Graph >::edge_descriptor Edge;
+ typedef std::pair< Edge, bool > EdgeInfo;
+
+ typedef
+ typename boost::property_map< Graph, boost::vertex_index_t >::type
+ VertexIndexMap;
+ typedef
+ typename boost::property_map< Graph, boost::vertex_name_t >::type
+ VertexNameMap;
+ typedef typename boost::property_map< Graph, boost::edge_name_t >::type
+ EdgeNameMap;
+
+ if (subgraph_size != num_vertices(m_common_subgraph))
+ {
+ return (true);
+ }
- MembershipMap membership_map2(num_vertices(m_graph2),
- get(boost::vertex_index, m_graph2));
+ // Fill membership maps for both graphs
+ typedef boost::shared_array_property_map< bool, VertexIndexMap >
+ MembershipMap;
- boost::fill_membership_map<Graph>(m_graph1, correspondence_map_1_to_2, membership_map1);
- boost::fill_membership_map<Graph>(m_graph2, correspondence_map_2_to_1, membership_map2);
+ MembershipMap membership_map1(
+ num_vertices(m_graph1), get(boost::vertex_index, m_graph1));
- // Generate filtered graphs using membership maps
- typedef typename boost::membership_filtered_graph_traits<Graph, MembershipMap>::graph_type
- MembershipFilteredGraph;
+ MembershipMap membership_map2(
+ num_vertices(m_graph2), get(boost::vertex_index, m_graph2));
- MembershipFilteredGraph subgraph1 =
- boost::make_membership_filtered_graph(m_graph1, membership_map1);
+ boost::fill_membership_map< Graph >(
+ m_graph1, correspondence_map_1_to_2, membership_map1);
+ boost::fill_membership_map< Graph >(
+ m_graph2, correspondence_map_2_to_1, membership_map2);
- MembershipFilteredGraph subgraph2 =
- boost::make_membership_filtered_graph(m_graph2, membership_map2);
+ // Generate filtered graphs using membership maps
+ typedef typename boost::membership_filtered_graph_traits< Graph,
+ MembershipMap >::graph_type MembershipFilteredGraph;
- VertexIndexMap vindex_map1 = get(boost::vertex_index, subgraph1);
- VertexIndexMap vindex_map2 = get(boost::vertex_index, subgraph2);
+ MembershipFilteredGraph subgraph1
+ = boost::make_membership_filtered_graph(m_graph1, membership_map1);
- VertexNameMap vname_map_common = get(boost::vertex_name, m_common_subgraph);
- VertexNameMap vname_map1 = get(boost::vertex_name, subgraph1);
- VertexNameMap vname_map2 = get(boost::vertex_name, subgraph2);
+ MembershipFilteredGraph subgraph2
+ = boost::make_membership_filtered_graph(m_graph2, membership_map2);
- EdgeNameMap ename_map_common = get(boost::edge_name, m_common_subgraph);
- EdgeNameMap ename_map1 = get(boost::edge_name, subgraph1);
- EdgeNameMap ename_map2 = get(boost::edge_name, subgraph2);
+ VertexIndexMap vindex_map1 = get(boost::vertex_index, subgraph1);
+ VertexIndexMap vindex_map2 = get(boost::vertex_index, subgraph2);
- // Verify that subgraph1 matches the supplied common subgraph
- BGL_FORALL_VERTICES_T(vertex1, subgraph1, MembershipFilteredGraph) {
-
- Vertex vertex_common = vertex(get(vindex_map1, vertex1), m_common_subgraph);
+ VertexNameMap vname_map_common
+ = get(boost::vertex_name, m_common_subgraph);
+ VertexNameMap vname_map1 = get(boost::vertex_name, subgraph1);
+ VertexNameMap vname_map2 = get(boost::vertex_name, subgraph2);
- // Match vertex names
- if (get(vname_map_common, vertex_common) != get(vname_map1, vertex1)) {
+ EdgeNameMap ename_map_common = get(boost::edge_name, m_common_subgraph);
+ EdgeNameMap ename_map1 = get(boost::edge_name, subgraph1);
+ EdgeNameMap ename_map2 = get(boost::edge_name, subgraph2);
- // Keep looking
- return (true);
+ // Verify that subgraph1 matches the supplied common subgraph
+ BGL_FORALL_VERTICES_T(vertex1, subgraph1, MembershipFilteredGraph)
+ {
- }
+ Vertex vertex_common
+ = vertex(get(vindex_map1, vertex1), m_common_subgraph);
- BGL_FORALL_VERTICES_T(vertex1_2, subgraph1, MembershipFilteredGraph) {
+ // Match vertex names
+ if (get(vname_map_common, vertex_common)
+ != get(vname_map1, vertex1))
+ {
- Vertex vertex_common2 = vertex(get(vindex_map1, vertex1_2), m_common_subgraph);
- EdgeInfo edge_common = edge(vertex_common, vertex_common2, m_common_subgraph);
- EdgeInfo edge1 = edge(vertex1, vertex1_2, subgraph1);
+ // Keep looking
+ return (true);
+ }
- if ((edge_common.second != edge1.second) ||
- ((edge_common.second && edge1.second) &&
- (get(ename_map_common, edge_common.first) != get(ename_map1, edge1.first)))) {
+ BGL_FORALL_VERTICES_T(vertex1_2, subgraph1, MembershipFilteredGraph)
+ {
- // Keep looking
- return (true);
+ Vertex vertex_common2
+ = vertex(get(vindex_map1, vertex1_2), m_common_subgraph);
+ EdgeInfo edge_common
+ = edge(vertex_common, vertex_common2, m_common_subgraph);
+ EdgeInfo edge1 = edge(vertex1, vertex1_2, subgraph1);
- }
- }
-
- } // BGL_FORALL_VERTICES_T (subgraph1)
+ if ((edge_common.second != edge1.second)
+ || ((edge_common.second && edge1.second)
+ && (get(ename_map_common, edge_common.first)
+ != get(ename_map1, edge1.first))))
+ {
- // Verify that subgraph2 matches the supplied common subgraph
- BGL_FORALL_VERTICES_T(vertex2, subgraph2, MembershipFilteredGraph) {
-
- Vertex vertex_common = vertex(get(vindex_map2, vertex2), m_common_subgraph);
+ // Keep looking
+ return (true);
+ }
+ }
- // Match vertex names
- if (get(vname_map_common, vertex_common) != get(vname_map2, vertex2)) {
+ } // BGL_FORALL_VERTICES_T (subgraph1)
- // Keep looking
- return (true);
+ // Verify that subgraph2 matches the supplied common subgraph
+ BGL_FORALL_VERTICES_T(vertex2, subgraph2, MembershipFilteredGraph)
+ {
- }
+ Vertex vertex_common
+ = vertex(get(vindex_map2, vertex2), m_common_subgraph);
- BGL_FORALL_VERTICES_T(vertex2_2, subgraph2, MembershipFilteredGraph) {
+ // Match vertex names
+ if (get(vname_map_common, vertex_common)
+ != get(vname_map2, vertex2))
+ {
- Vertex vertex_common2 = vertex(get(vindex_map2, vertex2_2), m_common_subgraph);
- EdgeInfo edge_common = edge(vertex_common, vertex_common2, m_common_subgraph);
- EdgeInfo edge2 = edge(vertex2, vertex2_2, subgraph2);
+ // Keep looking
+ return (true);
+ }
- if ((edge_common.second != edge2.second) ||
- ((edge_common.second && edge2.second) &&
- (get(ename_map_common, edge_common.first) != get(ename_map2, edge2.first)))) {
+ BGL_FORALL_VERTICES_T(vertex2_2, subgraph2, MembershipFilteredGraph)
+ {
- // Keep looking
- return (true);
+ Vertex vertex_common2
+ = vertex(get(vindex_map2, vertex2_2), m_common_subgraph);
+ EdgeInfo edge_common
+ = edge(vertex_common, vertex_common2, m_common_subgraph);
+ EdgeInfo edge2 = edge(vertex2, vertex2_2, subgraph2);
- }
- }
-
- } // BGL_FORALL_VERTICES_T (subgraph2)
-
- // Check isomorphism just to be thorough
- if (verify_isomorphism(subgraph1, subgraph2, correspondence_map_1_to_2)) {
+ if ((edge_common.second != edge2.second)
+ || ((edge_common.second && edge2.second)
+ && (get(ename_map_common, edge_common.first)
+ != get(ename_map2, edge2.first))))
+ {
- was_common_subgraph_found = true;
+ // Keep looking
+ return (true);
+ }
+ }
+
+ } // BGL_FORALL_VERTICES_T (subgraph2)
- if (output_graphs) {
+ // Check isomorphism just to be thorough
+ if (verify_isomorphism(subgraph1, subgraph2, correspondence_map_1_to_2))
+ {
- std::fstream file_subgraph("found_common_subgraph.dot", std::fstream::out);
- write_graphviz(file_subgraph, subgraph1,
- make_label_writer(get(boost::vertex_name, m_graph1)),
- make_label_writer(get(boost::edge_name, m_graph1)));
+ was_common_subgraph_found = true;
- }
+ if (output_graphs)
+ {
- // Stop iterating
- return (false);
+ std::fstream file_subgraph(
+ "found_common_subgraph.dot", std::fstream::out);
+ write_graphviz(file_subgraph, subgraph1,
+ make_label_writer(get(boost::vertex_name, m_graph1)),
+ make_label_writer(get(boost::edge_name, m_graph1)));
+ }
+
+ // Stop iterating
+ return (false);
+ }
+ // Keep looking
+ return (true);
}
-
- // Keep looking
- return (true);
- }
private:
- const Graph& m_graph1, m_graph2;
- Graph& m_common_subgraph;
+ const Graph &m_graph1, m_graph2;
+ Graph& m_common_subgraph;
};
-template <typename Graph>
-struct simple_callback {
-
- simple_callback(const Graph& graph1) :
- m_graph1(graph1) { }
+template < typename Graph > struct simple_callback
+{
- template <typename CorrespondenceMapFirstToSecond,
- typename CorrespondenceMapSecondToFirst>
- bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
- CorrespondenceMapSecondToFirst /*correspondence_map_2_to_1*/,
- typename boost::graph_traits<Graph>::vertices_size_type /*subgraph_size*/) {
+ simple_callback(const Graph& graph1) : m_graph1(graph1) {}
- typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
+ template < typename CorrespondenceMapFirstToSecond,
+ typename CorrespondenceMapSecondToFirst >
+ bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
+ CorrespondenceMapSecondToFirst /*correspondence_map_2_to_1*/,
+ typename boost::graph_traits<
+ Graph >::vertices_size_type /*subgraph_size*/)
+ {
- std::stringstream subgraph_string;
+ typedef typename boost::graph_traits< Graph >::vertex_descriptor Vertex;
- BGL_FORALL_VERTICES_T(vertex1, m_graph1, Graph) {
+ std::stringstream subgraph_string;
- Vertex vertex2 = get(correspondence_map_1_to_2, vertex1);
+ BGL_FORALL_VERTICES_T(vertex1, m_graph1, Graph)
+ {
- if (vertex2 != boost::graph_traits<Graph>::null_vertex()) {
- subgraph_string << vertex1 << "," << vertex2 << " ";
- }
+ Vertex vertex2 = get(correspondence_map_1_to_2, vertex1);
- }
+ if (vertex2 != boost::graph_traits< Graph >::null_vertex())
+ {
+ subgraph_string << vertex1 << "," << vertex2 << " ";
+ }
+ }
- simple_subgraph_list.push_back(subgraph_string.str());
+ simple_subgraph_list.push_back(subgraph_string.str());
- return (true);
- }
+ return (true);
+ }
private:
- const Graph& m_graph1;
-
+ const Graph& m_graph1;
};
-template <typename Graph,
- typename RandomNumberGenerator,
- typename VertexNameMap,
- typename EdgeNameMap>
+template < typename Graph, typename RandomNumberGenerator,
+ typename VertexNameMap, typename EdgeNameMap >
void add_random_vertices(Graph& graph, RandomNumberGenerator& generator,
- int vertices_to_create, int max_edges_per_vertex,
- VertexNameMap vname_map, EdgeNameMap ename_map) {
-
- typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
- typedef std::vector<Vertex> VertexList;
+ int vertices_to_create, int max_edges_per_vertex, VertexNameMap vname_map,
+ EdgeNameMap ename_map)
+{
- VertexList new_vertices;
+ typedef typename boost::graph_traits< Graph >::vertex_descriptor Vertex;
+ typedef std::vector< Vertex > VertexList;
- for (int v_index = 0; v_index < vertices_to_create; ++v_index) {
+ VertexList new_vertices;
- Vertex new_vertex = add_vertex(graph);
- put(vname_map, new_vertex, generator());
- new_vertices.push_back(new_vertex);
+ for (int v_index = 0; v_index < vertices_to_create; ++v_index)
+ {
- }
+ Vertex new_vertex = add_vertex(graph);
+ put(vname_map, new_vertex, generator());
+ new_vertices.push_back(new_vertex);
+ }
- // Add edges for every new vertex. Care is taken to avoid parallel
- // edges.
- for (typename VertexList::const_iterator v_iter = new_vertices.begin();
- v_iter != new_vertices.end(); ++v_iter) {
+ // Add edges for every new vertex. Care is taken to avoid parallel
+ // edges.
+ for (typename VertexList::const_iterator v_iter = new_vertices.begin();
+ v_iter != new_vertices.end(); ++v_iter)
+ {
- Vertex source_vertex = *v_iter;
- int edges_for_vertex = (std::min)((int)(generator() % max_edges_per_vertex) + 1,
- (int)num_vertices(graph));
+ Vertex source_vertex = *v_iter;
+ int edges_for_vertex
+ = (std::min)((int)(generator() % max_edges_per_vertex) + 1,
+ (int)num_vertices(graph));
- while (edges_for_vertex > 0) {
+ while (edges_for_vertex > 0)
+ {
- Vertex target_vertex = random_vertex(graph, generator);
+ Vertex target_vertex = random_vertex(graph, generator);
- if (source_vertex == target_vertex) {
- continue;
- }
+ if (source_vertex == target_vertex)
+ {
+ continue;
+ }
- BGL_FORALL_OUTEDGES_T(source_vertex, edge, graph, Graph) {
- if (target(edge, graph) == target_vertex) {
- continue;
- }
- }
+ BGL_FORALL_OUTEDGES_T(source_vertex, edge, graph, Graph)
+ {
+ if (target(edge, graph) == target_vertex)
+ {
+ continue;
+ }
+ }
- put(ename_map, add_edge(source_vertex, target_vertex, graph).first,
- generator());
+ put(ename_map, add_edge(source_vertex, target_vertex, graph).first,
+ generator());
- edges_for_vertex--;
+ edges_for_vertex--;
+ }
}
- }
}
-bool has_subgraph_string(std::string set_string) {
- return (std::find(simple_subgraph_list.begin(), simple_subgraph_list.end(),
- set_string) != simple_subgraph_list.end());
+bool has_subgraph_string(std::string set_string)
+{
+ return (std::find(simple_subgraph_list.begin(), simple_subgraph_list.end(),
+ set_string)
+ != simple_subgraph_list.end());
}
-int test_main (int argc, char *argv[]) {
- int vertices_to_create = 10;
- int max_edges_per_vertex = 2;
- std::size_t random_seed = time(0);
-
- if (argc > 1) {
- vertices_to_create = boost::lexical_cast<int>(argv[1]);
- }
-
- if (argc > 2) {
- max_edges_per_vertex = boost::lexical_cast<int>(argv[2]);
- }
-
- if (argc > 3) {
- output_graphs = boost::lexical_cast<bool>(argv[3]);
- }
-
- if (argc > 4) {
- random_seed = boost::lexical_cast<std::size_t>(argv[4]);
- }
-
- boost::minstd_rand generator(random_seed);
-
- // Using a vecS graph here so that we don't have to mess around with
- // a vertex index map; it will be implicit.
- typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS,
- boost::property<boost::vertex_name_t, unsigned int,
- boost::property<boost::vertex_index_t, unsigned int> >,
- boost::property<boost::edge_name_t, unsigned int> > Graph;
-
- typedef boost::property_map<Graph, boost::vertex_name_t>::type VertexNameMap;
- typedef boost::property_map<Graph, boost::edge_name_t>::type EdgeNameMap;
-
- // Generate a random common subgraph and then add random vertices
- // and edges to the two parent graphs.
- Graph common_subgraph, graph1, graph2;
-
- VertexNameMap vname_map_common = get(boost::vertex_name, common_subgraph);
- VertexNameMap vname_map1 = get(boost::vertex_name, graph1);
- VertexNameMap vname_map2 = get(boost::vertex_name, graph2);
-
- EdgeNameMap ename_map_common = get(boost::edge_name, common_subgraph);
- EdgeNameMap ename_map1 = get(boost::edge_name, graph1);
- EdgeNameMap ename_map2 = get(boost::edge_name, graph2);
-
- for (int vindex = 0; vindex < vertices_to_create; ++vindex) {
- put(vname_map_common, add_vertex(common_subgraph), generator());
- }
-
- BGL_FORALL_VERTICES(source_vertex, common_subgraph, Graph) {
-
- BGL_FORALL_VERTICES(target_vertex, common_subgraph, Graph) {
-
- if (source_vertex != target_vertex) {
- put(ename_map_common,
- add_edge(source_vertex, target_vertex, common_subgraph).first,
- generator());
- }
+int main(int argc, char* argv[])
+{
+ int vertices_to_create = 10;
+ int max_edges_per_vertex = 2;
+ std::size_t random_seed = time(0);
+
+ if (argc > 1)
+ {
+ vertices_to_create = boost::lexical_cast< int >(argv[1]);
}
- }
- boost::randomize_property<boost::vertex_name_t>(common_subgraph, generator);
- boost::randomize_property<boost::edge_name_t>(common_subgraph, generator);
+ if (argc > 2)
+ {
+ max_edges_per_vertex = boost::lexical_cast< int >(argv[2]);
+ }
- boost::copy_graph(common_subgraph, graph1);
- boost::copy_graph(common_subgraph, graph2);
+ if (argc > 3)
+ {
+ output_graphs = boost::lexical_cast< bool >(argv[3]);
+ }
+
+ if (argc > 4)
+ {
+ random_seed = boost::lexical_cast< std::size_t >(argv[4]);
+ }
+
+ boost::minstd_rand generator(random_seed);
+
+ // Using a vecS graph here so that we don't have to mess around with
+ // a vertex index map; it will be implicit.
+ typedef boost::adjacency_list< boost::listS, boost::vecS, boost::directedS,
+ boost::property< boost::vertex_name_t, unsigned int,
+ boost::property< boost::vertex_index_t, unsigned int > >,
+ boost::property< boost::edge_name_t, unsigned int > >
+ Graph;
+
+ typedef boost::property_map< Graph, boost::vertex_name_t >::type
+ VertexNameMap;
+ typedef boost::property_map< Graph, boost::edge_name_t >::type EdgeNameMap;
+
+ // Generate a random common subgraph and then add random vertices
+ // and edges to the two parent graphs.
+ Graph common_subgraph, graph1, graph2;
+
+ VertexNameMap vname_map_common = get(boost::vertex_name, common_subgraph);
+ VertexNameMap vname_map1 = get(boost::vertex_name, graph1);
+ VertexNameMap vname_map2 = get(boost::vertex_name, graph2);
+
+ EdgeNameMap ename_map_common = get(boost::edge_name, common_subgraph);
+ EdgeNameMap ename_map1 = get(boost::edge_name, graph1);
+ EdgeNameMap ename_map2 = get(boost::edge_name, graph2);
+
+ for (int vindex = 0; vindex < vertices_to_create; ++vindex)
+ {
+ put(vname_map_common, add_vertex(common_subgraph), generator());
+ }
- // Randomly add vertices and edges to graph1 and graph2.
- add_random_vertices(graph1, generator, vertices_to_create,
- max_edges_per_vertex, vname_map1, ename_map1);
+ BGL_FORALL_VERTICES(source_vertex, common_subgraph, Graph)
+ {
- add_random_vertices(graph2, generator, vertices_to_create,
- max_edges_per_vertex, vname_map2, ename_map2);
+ BGL_FORALL_VERTICES(target_vertex, common_subgraph, Graph)
+ {
- if (output_graphs) {
+ if (source_vertex != target_vertex)
+ {
+ put(ename_map_common,
+ add_edge(source_vertex, target_vertex, common_subgraph)
+ .first,
+ generator());
+ }
+ }
+ }
+
+ boost::randomize_property< boost::vertex_name_t >(
+ common_subgraph, generator);
+ boost::randomize_property< boost::edge_name_t >(common_subgraph, generator);
- std::fstream file_graph1("graph1.dot", std::fstream::out),
- file_graph2("graph2.dot", std::fstream::out),
- file_common_subgraph("expected_common_subgraph.dot", std::fstream::out);
-
- write_graphviz(file_graph1, graph1,
- make_label_writer(vname_map1),
- make_label_writer(ename_map1));
+ boost::copy_graph(common_subgraph, graph1);
+ boost::copy_graph(common_subgraph, graph2);
- write_graphviz(file_graph2, graph2,
- make_label_writer(vname_map2),
- make_label_writer(ename_map2));
+ // Randomly add vertices and edges to graph1 and graph2.
+ add_random_vertices(graph1, generator, vertices_to_create,
+ max_edges_per_vertex, vname_map1, ename_map1);
- write_graphviz(file_common_subgraph, common_subgraph,
- make_label_writer(get(boost::vertex_name, common_subgraph)),
- make_label_writer(get(boost::edge_name, common_subgraph)));
+ add_random_vertices(graph2, generator, vertices_to_create,
+ max_edges_per_vertex, vname_map2, ename_map2);
- }
+ if (output_graphs)
+ {
- std::cout << "Searching for common subgraph of size " <<
- num_vertices(common_subgraph) << std::endl;
+ std::fstream file_graph1("graph1.dot", std::fstream::out),
+ file_graph2("graph2.dot", std::fstream::out),
+ file_common_subgraph(
+ "expected_common_subgraph.dot", std::fstream::out);
- test_callback<Graph> user_callback(common_subgraph, graph1, graph2);
+ write_graphviz(file_graph1, graph1, make_label_writer(vname_map1),
+ make_label_writer(ename_map1));
- boost::mcgregor_common_subgraphs(graph1, graph2, true, user_callback,
- boost::edges_equivalent(boost::make_property_map_equivalent(ename_map1, ename_map2)).
- vertices_equivalent(boost::make_property_map_equivalent(vname_map1, vname_map2)));
+ write_graphviz(file_graph2, graph2, make_label_writer(vname_map2),
+ make_label_writer(ename_map2));
- BOOST_CHECK(was_common_subgraph_found);
+ write_graphviz(file_common_subgraph, common_subgraph,
+ make_label_writer(get(boost::vertex_name, common_subgraph)),
+ make_label_writer(get(boost::edge_name, common_subgraph)));
+ }
- // Test maximum and unique variants on known graphs
- Graph graph_simple1, graph_simple2;
- simple_callback<Graph> user_callback_simple(graph_simple1);
+ std::cout << "Searching for common subgraph of size "
+ << num_vertices(common_subgraph) << std::endl;
- VertexNameMap vname_map_simple1 = get(boost::vertex_name, graph_simple1);
- VertexNameMap vname_map_simple2 = get(boost::vertex_name, graph_simple2);
+ test_callback< Graph > user_callback(common_subgraph, graph1, graph2);
- 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);
+ boost::mcgregor_common_subgraphs(graph1, graph2, true, user_callback,
+ boost::edges_equivalent(
+ boost::make_property_map_equivalent(ename_map1, ename_map2))
+ .vertices_equivalent(
+ boost::make_property_map_equivalent(vname_map1, vname_map2)));
- add_edge(0, 1, graph_simple1);
- add_edge(0, 2, graph_simple1);
- add_edge(1, 2, graph_simple1);
+ BOOST_TEST(was_common_subgraph_found);
- 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);
+ // Test maximum and unique variants on known graphs
+ Graph graph_simple1, graph_simple2;
+ simple_callback< Graph > user_callback_simple(graph_simple1);
- add_edge(0, 1, graph_simple2);
- add_edge(0, 2, graph_simple2);
- add_edge(1, 2, graph_simple2);
- add_edge(1, 3, graph_simple2);
+ VertexNameMap vname_map_simple1 = get(boost::vertex_name, graph_simple1);
+ VertexNameMap vname_map_simple2 = get(boost::vertex_name, graph_simple2);
- // Unique subgraphs
- std::cout << "Searching for unique subgraphs" << std::endl;
- boost::mcgregor_common_subgraphs_unique(graph_simple1, graph_simple2,
- true, user_callback_simple,
- boost::vertices_equivalent(boost::make_property_map_equivalent(vname_map_simple1, vname_map_simple2)));
+ 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);
- BOOST_CHECK(has_subgraph_string("0,0 1,1 "));
- BOOST_CHECK(has_subgraph_string("0,0 1,1 2,2 "));
- BOOST_CHECK(has_subgraph_string("0,0 2,2 "));
- BOOST_CHECK(has_subgraph_string("1,1 2,2 "));
+ add_edge(0, 1, graph_simple1);
+ add_edge(0, 2, graph_simple1);
+ add_edge(1, 2, graph_simple1);
- if (output_graphs) {
- std::copy(simple_subgraph_list.begin(), simple_subgraph_list.end(),
- std::ostream_iterator<std::string>(std::cout, "\n"));
+ 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);
- std::cout << std::endl;
- }
+ add_edge(0, 1, graph_simple2);
+ add_edge(0, 2, graph_simple2);
+ add_edge(1, 2, graph_simple2);
+ add_edge(1, 3, graph_simple2);
- simple_subgraph_list.clear();
+ // Unique subgraphs
+ std::cout << "Searching for unique subgraphs" << std::endl;
+ boost::mcgregor_common_subgraphs_unique(graph_simple1, graph_simple2, true,
+ user_callback_simple,
+ boost::vertices_equivalent(boost::make_property_map_equivalent(
+ vname_map_simple1, vname_map_simple2)));
- // Maximum subgraphs
- std::cout << "Searching for maximum subgraphs" << std::endl;
- boost::mcgregor_common_subgraphs_maximum(graph_simple1, graph_simple2,
- true, user_callback_simple,
- boost::vertices_equivalent(boost::make_property_map_equivalent(vname_map_simple1, vname_map_simple2)));
+ BOOST_TEST(has_subgraph_string("0,0 1,1 "));
+ BOOST_TEST(has_subgraph_string("0,0 1,1 2,2 "));
+ BOOST_TEST(has_subgraph_string("0,0 2,2 "));
+ BOOST_TEST(has_subgraph_string("1,1 2,2 "));
- BOOST_CHECK(has_subgraph_string("0,0 1,1 2,2 "));
+ if (output_graphs)
+ {
+ std::copy(simple_subgraph_list.begin(), simple_subgraph_list.end(),
+ std::ostream_iterator< std::string >(std::cout, "\n"));
- if (output_graphs) {
- std::copy(simple_subgraph_list.begin(), simple_subgraph_list.end(),
- std::ostream_iterator<std::string>(std::cout, "\n"));
+ std::cout << std::endl;
+ }
- std::cout << std::endl;
- }
+ simple_subgraph_list.clear();
- simple_subgraph_list.clear();
+ // Maximum subgraphs
+ std::cout << "Searching for maximum subgraphs" << std::endl;
+ boost::mcgregor_common_subgraphs_maximum(graph_simple1, graph_simple2, true,
+ user_callback_simple,
+ boost::vertices_equivalent(boost::make_property_map_equivalent(
+ vname_map_simple1, vname_map_simple2)));
- // Maximum, unique subgraphs
- std::cout << "Searching for maximum unique subgraphs" << std::endl;
- boost::mcgregor_common_subgraphs_maximum_unique(graph_simple1, graph_simple2,
- true, user_callback_simple,
- boost::vertices_equivalent(boost::make_property_map_equivalent(vname_map_simple1, vname_map_simple2)));
+ BOOST_TEST(has_subgraph_string("0,0 1,1 2,2 "));
- BOOST_CHECK(simple_subgraph_list.size() == 1);
- BOOST_CHECK(has_subgraph_string("0,0 1,1 2,2 "));
+ if (output_graphs)
+ {
+ std::copy(simple_subgraph_list.begin(), simple_subgraph_list.end(),
+ std::ostream_iterator< std::string >(std::cout, "\n"));
- if (output_graphs) {
- std::copy(simple_subgraph_list.begin(), simple_subgraph_list.end(),
- std::ostream_iterator<std::string>(std::cout, "\n"));
+ std::cout << std::endl;
+ }
- std::cout << std::endl;
- }
+ simple_subgraph_list.clear();
+
+ // Maximum, unique subgraphs
+ std::cout << "Searching for maximum unique subgraphs" << std::endl;
+ boost::mcgregor_common_subgraphs_maximum_unique(graph_simple1,
+ graph_simple2, true, user_callback_simple,
+ boost::vertices_equivalent(boost::make_property_map_equivalent(
+ vname_map_simple1, vname_map_simple2)));
+
+ BOOST_TEST(simple_subgraph_list.size() == 1);
+ BOOST_TEST(has_subgraph_string("0,0 1,1 2,2 "));
+
+ if (output_graphs)
+ {
+ std::copy(simple_subgraph_list.begin(), simple_subgraph_list.end(),
+ std::ostream_iterator< std::string >(std::cout, "\n"));
+
+ std::cout << std::endl;
+ }
- return 0;
+ return boost::report_errors();
}
projects / ceph.git / blobdiff