Subject: [Boost-commit] svn:boost r54315 - in trunk: boost/graph libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-06-24 16:31:51
Author: jewillco
Date: 2009-06-24 16:31:50 EDT (Wed, 24 Jun 2009)
New Revision: 54315
URL: http://svn.boost.org/trac/boost/changeset/54315
Log:
Added McGregor updates from Michael Hansen; refs #3134
Text files modified:
trunk/boost/graph/mcgregor_common_subgraphs.hpp | 299 +++++++++++++++++++++++----------------
trunk/libs/graph/test/mcgregor_subgraphs_test.cpp | 139 ++++++++++++++++++
2 files changed, 313 insertions(+), 125 deletions(-)
Modified: trunk/boost/graph/mcgregor_common_subgraphs.hpp
==============================================================================
--- trunk/boost/graph/mcgregor_common_subgraphs.hpp (original)
+++ trunk/boost/graph/mcgregor_common_subgraphs.hpp 2009-06-24 16:31:50 EDT (Wed, 24 Jun 2009)
@@ -14,13 +14,13 @@
#include <vector>
#include <stack>
+#include <boost/make_shared.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/properties.hpp>
#include <boost/property_map/shared_array_property_map.hpp>
-#include <boost/test/minimal.hpp>
namespace boost {
@@ -37,10 +37,10 @@
typedef typename graph_traits<GraphSecond>::vertex_descriptor vertex_second_type;
typedef shared_array_property_map<vertex_second_type, VertexIndexMapFirst>
- correspondence_map_first_to_second_type;
+ correspondence_map_first_to_second_type;
typedef shared_array_property_map<vertex_first_type, VertexIndexMapSecond>
- correspondence_map_second_to_first_type;
+ correspondence_map_second_to_first_type;
};
} // namespace detail
@@ -119,7 +119,8 @@
typename graph_traits<GraphFirst>::vertex_descriptor new_vertex1,
typename graph_traits<GraphSecond>::vertex_descriptor new_vertex2,
EdgeEquivalencePredicate edges_equivalent,
- VertexEquivalencePredicate vertices_equivalent)
+ VertexEquivalencePredicate vertices_equivalent,
+ bool only_connected_subgraphs)
{
typedef typename graph_traits<GraphFirst>::vertex_descriptor VertexFirst;
typedef typename graph_traits<GraphSecond>::vertex_descriptor VertexSecond;
@@ -239,7 +240,7 @@
} // BGL_FORALL_VERTICES_T
// Make sure new vertices are connected to the existing subgraph
- if (!has_one_edge) {
+ if (only_connected_subgraphs && !has_one_edge) {
return (false);
}
@@ -274,6 +275,7 @@
VertexStackFirst& vertex_stack1,
EdgeEquivalencePredicate edges_equivalent,
VertexEquivalencePredicate vertices_equivalent,
+ bool only_connected_subgraphs,
SubGraphInternalCallback subgraph_callback)
{
typedef typename graph_traits<GraphFirst>::vertex_descriptor VertexFirst;
@@ -315,7 +317,8 @@
correspondence_map_1_to_2, correspondence_map_2_to_1,
(VertexSizeFirst)vertex_stack1.size(),
new_vertex1, new_vertex2,
- edges_equivalent, vertices_equivalent)) {
+ edges_equivalent, vertices_equivalent,
+ only_connected_subgraphs)) {
// Keep track of old graph size for restoring later
VertexSizeFirst old_graph_size = (VertexSizeFirst)vertex_stack1.size(),
@@ -345,7 +348,7 @@
correspondence_map_1_to_2, correspondence_map_2_to_1,
vertex_stack1,
edges_equivalent, vertices_equivalent,
- subgraph_callback);
+ only_connected_subgraphs, subgraph_callback);
if (!continue_iteration) {
return (false);
@@ -366,7 +369,7 @@
graph_traits<GraphFirst>::null_vertex());
vertex_stack1.pop();
- }
+ }
} // if can_extend_graph
@@ -383,8 +386,8 @@
typename GraphSecond,
typename VertexIndexMapFirst,
typename VertexIndexMapSecond,
- typename VertexEquivalencePredicate,
typename EdgeEquivalencePredicate,
+ typename VertexEquivalencePredicate,
typename SubGraphInternalCallback>
inline void mcgregor_common_subgraphs_internal_init
(const GraphFirst& graph1,
@@ -393,6 +396,7 @@
const VertexIndexMapSecond vindex_map2,
EdgeEquivalencePredicate edges_equivalent,
VertexEquivalencePredicate vertices_equivalent,
+ bool only_connected_subgraphs,
SubGraphInternalCallback subgraph_callback)
{
typedef mcgregor_common_subgraph_traits<GraphFirst,
@@ -426,6 +430,7 @@
correspondence_map_1_to_2, correspondence_map_2_to_1,
vertex_stack1,
edges_equivalent, vertices_equivalent,
+ only_connected_subgraphs,
subgraph_callback);
}
@@ -450,6 +455,7 @@
const VertexIndexMapSecond vindex_map2,
EdgeEquivalencePredicate edges_equivalent,
VertexEquivalencePredicate vertices_equivalent,
+ bool only_connected_subgraphs,
SubGraphCallback user_callback)
{
@@ -457,6 +463,7 @@
(graph1, graph2,
vindex_map1, vindex_map2,
edges_equivalent, vertices_equivalent,
+ only_connected_subgraphs,
user_callback);
}
@@ -467,6 +474,7 @@
void mcgregor_common_subgraphs
(const GraphFirst& graph1,
const GraphSecond& graph2,
+ bool only_connected_subgraphs,
SubGraphCallback user_callback)
{
@@ -474,7 +482,7 @@
(graph1, graph2,
get(vertex_index, graph1), get(vertex_index, graph2),
always_equivalent(), always_equivalent(),
- user_callback);
+ only_connected_subgraphs, user_callback);
}
// Named parameter variant of mcgregor_common_subgraphs
@@ -487,6 +495,7 @@
void mcgregor_common_subgraphs
(const GraphFirst& graph1,
const GraphSecond& graph2,
+ bool only_connected_subgraphs,
SubGraphCallback user_callback,
const bgl_named_params<Param, Tag, Rest>& params)
{
@@ -501,7 +510,7 @@
always_equivalent()),
choose_param(get_param(params, vertices_equivalent_t()),
always_equivalent()),
- user_callback);
+ only_connected_subgraphs, user_callback);
}
// ==========================================================================
@@ -519,36 +528,43 @@
typename SubGraphCallback>
struct unique_subgraph_interceptor {
+ typedef typename graph_traits<GraphFirst>::vertices_size_type
+ VertexSizeFirst;
+
typedef mcgregor_common_subgraph_traits<GraphFirst, GraphSecond,
VertexIndexMapFirst, VertexIndexMapSecond> SubGraphTraits;
typedef typename SubGraphTraits::correspondence_map_first_to_second_type
- CorrespondenceMapFirstToSecond;
+ CachedCorrespondenceMapFirstToSecond;
typedef typename SubGraphTraits::correspondence_map_second_to_first_type
- CorrespondenceMapSecondToFirst;
+ CachedCorrespondenceMapSecondToFirst;
- typedef std::pair<std::size_t, std::pair<CorrespondenceMapFirstToSecond,
- CorrespondenceMapSecondToFirst> > SubGraph;
+ typedef std::pair<VertexSizeFirst,
+ std::pair<CachedCorrespondenceMapFirstToSecond,
+ CachedCorrespondenceMapSecondToFirst> > SubGraph;
typedef std::vector<SubGraph> SubGraphList;
unique_subgraph_interceptor(const GraphFirst& graph1,
const GraphSecond& graph2,
- const VertexIndexMapFirst& vindex_map1,
- const VertexIndexMapSecond& vindex_map2,
+ const VertexIndexMapFirst vindex_map1,
+ const VertexIndexMapSecond vindex_map2,
SubGraphCallback user_callback) :
m_graph1(graph1), m_graph2(graph2),
m_vindex_map1(vindex_map1), m_vindex_map2(vindex_map2),
+ m_subgraphs(make_shared<SubGraphList>()),
m_user_callback(user_callback) { }
- bool operator()(CorrespondenceMapFirstToSecond& correspondence_map_1_to_2,
- CorrespondenceMapSecondToFirst& correspondence_map_2_to_1,
- std::size_t subgraph_size) {
+ template <typename CorrespondenceMapFirstToSecond,
+ typename CorrespondenceMapSecondToFirst>
+ bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
+ CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
+ VertexSizeFirst subgraph_size) {
for (typename SubGraphList::const_iterator
- subgraph_iter = m_subgraphs.begin();
- subgraph_iter != m_subgraphs.end();
+ subgraph_iter = m_subgraphs->begin();
+ subgraph_iter != m_subgraphs->end();
++subgraph_iter) {
SubGraph subgraph_cached = *subgraph_iter;
@@ -558,11 +574,8 @@
continue;
}
- CorrespondenceMapFirstToSecond correspondence_map_1_to_2_cached =
- subgraph_cached.second.first;
-
if (!are_property_maps_different(correspondence_map_1_to_2,
- correspondence_map_1_to_2_cached,
+ subgraph_cached.second.first,
m_graph1)) {
// New subgraph is a duplicate
@@ -571,18 +584,25 @@
}
// Subgraph is unique, so make a cached copy
- SubGraph new_subgraph = make_pair(subgraph_size,
- std::make_pair
- (CorrespondenceMapFirstToSecond(num_vertices(m_graph1), m_vindex_map1),
- CorrespondenceMapSecondToFirst(num_vertices(m_graph2), m_vindex_map2)));
-
- copy_vertex_property(correspondence_map_1_to_2,
- new_subgraph.second.first, m_graph1);
+ CachedCorrespondenceMapFirstToSecond
+ new_subgraph_1_to_2 = CachedCorrespondenceMapFirstToSecond
+ (num_vertices(m_graph1), m_vindex_map1);
+
+ CachedCorrespondenceMapSecondToFirst
+ new_subgraph_2_to_1 = CorrespondenceMapSecondToFirst
+ (num_vertices(m_graph2), m_vindex_map2);
- copy_vertex_property(correspondence_map_2_to_1,
- new_subgraph.second.second, m_graph1);
-
- m_subgraphs.push_back(new_subgraph);
+ BGL_FORALL_VERTICES_T(vertex1, m_graph1, GraphFirst) {
+ put(new_subgraph_1_to_2, vertex1, get(correspondence_map_1_to_2, vertex1));
+ }
+
+ BGL_FORALL_VERTICES_T(vertex2, m_graph2, GraphFirst) {
+ put(new_subgraph_2_to_1, vertex2, get(correspondence_map_2_to_1, vertex2));
+ }
+
+ m_subgraphs->push_back(std::make_pair(subgraph_size,
+ std::make_pair(new_subgraph_1_to_2,
+ new_subgraph_2_to_1)));
return (m_user_callback(correspondence_map_1_to_2,
correspondence_map_2_to_1,
@@ -594,7 +614,7 @@
const GraphFirst& m_graph2;
const VertexIndexMapFirst m_vindex_map1;
const VertexIndexMapSecond m_vindex_map2;
- SubGraphList m_subgraphs;
+ shared_ptr<SubGraphList> m_subgraphs;
SubGraphCallback m_user_callback;
};
@@ -617,6 +637,7 @@
const VertexIndexMapSecond vindex_map2,
EdgeEquivalencePredicate edges_equivalent,
VertexEquivalencePredicate vertices_equivalent,
+ bool only_connected_subgraphs,
SubGraphCallback user_callback)
{
detail::unique_subgraph_interceptor<GraphFirst, GraphSecond,
@@ -630,7 +651,7 @@
(graph1, graph2,
vindex_map1, vindex_map2,
edges_equivalent, vertices_equivalent,
- unique_callback);
+ only_connected_subgraphs, unique_callback);
}
// Variant of mcgregor_common_subgraphs_unique with all default
@@ -641,13 +662,14 @@
void mcgregor_common_subgraphs_unique
(const GraphFirst& graph1,
const GraphSecond& graph2,
+ bool only_connected_subgraphs,
SubGraphCallback user_callback)
{
mcgregor_common_subgraphs_unique
(graph1, graph2,
get(vertex_index, graph1), get(vertex_index, graph2),
always_equivalent(), always_equivalent(),
- user_callback);
+ only_connected_subgraphs, user_callback);
}
// Named parameter variant of mcgregor_common_subgraphs_unique
@@ -660,6 +682,7 @@
void mcgregor_common_subgraphs_unique
(const GraphFirst& graph1,
const GraphSecond& graph2,
+ bool only_connected_subgraphs,
SubGraphCallback user_callback,
const bgl_named_params<Param, Tag, Rest>& params)
{
@@ -673,7 +696,7 @@
always_equivalent()),
choose_param(get_param(params, vertices_equivalent_t()),
always_equivalent()),
- user_callback);
+ only_connected_subgraphs, user_callback);
}
// ==========================================================================
@@ -690,63 +713,77 @@
typename SubGraphCallback>
struct maximum_subgraph_interceptor {
+ typedef typename graph_traits<GraphFirst>::vertices_size_type
+ VertexSizeFirst;
+
typedef mcgregor_common_subgraph_traits<GraphFirst, GraphSecond,
VertexIndexMapFirst, VertexIndexMapSecond> SubGraphTraits;
typedef typename SubGraphTraits::correspondence_map_first_to_second_type
- CorrespondenceMapFirstToSecond;
+ CachedCorrespondenceMapFirstToSecond;
typedef typename SubGraphTraits::correspondence_map_second_to_first_type
- CorrespondenceMapSecondToFirst;
+ CachedCorrespondenceMapSecondToFirst;
+
+ typedef std::pair<VertexSizeFirst,
+ std::pair<CachedCorrespondenceMapFirstToSecond,
+ CachedCorrespondenceMapSecondToFirst> > SubGraph;
- typedef std::pair<std::size_t,
- std::pair<CorrespondenceMapFirstToSecond,
- CorrespondenceMapSecondToFirst> > SubGraph;
-
typedef std::vector<SubGraph> SubGraphList;
maximum_subgraph_interceptor(const GraphFirst& graph1,
const GraphSecond& graph2,
const VertexIndexMapFirst vindex_map1,
const VertexIndexMapSecond vindex_map2,
- SubGraphCallback user_callback) :
+ SubGraphCallback user_callback) :
m_graph1(graph1), m_graph2(graph2),
m_vindex_map1(vindex_map1), m_vindex_map2(vindex_map2),
- m_user_callback(user_callback),
- m_largest_size_so_far(0) { }
-
- bool operator()(CorrespondenceMapFirstToSecond& correspondence_map_1_to_2,
- CorrespondenceMapSecondToFirst& correspondence_map_2_to_1,
- std::size_t subgraph_size) {
-
- if (subgraph_size > m_largest_size_so_far) {
- m_subgraphs.clear();
- m_largest_size_so_far = subgraph_size;
+ m_subgraphs(make_shared<SubGraphList>()),
+ m_largest_size_so_far(make_shared<VertexSizeFirst>(0)),
+ m_user_callback(user_callback) { }
+
+ template <typename CorrespondenceMapFirstToSecond,
+ typename CorrespondenceMapSecondToFirst>
+ bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
+ CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
+ VertexSizeFirst subgraph_size) {
+
+ if (subgraph_size > *m_largest_size_so_far) {
+ m_subgraphs->clear();
+ *m_largest_size_so_far = subgraph_size;
}
- if (subgraph_size == m_largest_size_so_far) {
+ if (subgraph_size == *m_largest_size_so_far) {
// Make a cached copy
- SubGraph new_subgraph = make_pair(subgraph_size,
- std::make_pair(CorrespondenceMapFirstToSecond(num_vertices(m_graph1), m_vindex_map1),
- CorrespondenceMapSecondToFirst(num_vertices(m_graph2), m_vindex_map2)));
-
- copy_vertex_property(correspondence_map_1_to_2,
- new_subgraph.second.first, m_graph1);
-
- copy_vertex_property(correspondence_map_2_to_1,
- new_subgraph.second.second, m_graph2);
-
- m_subgraphs.push_back(new_subgraph);
+ CachedCorrespondenceMapFirstToSecond
+ new_subgraph_1_to_2 = CachedCorrespondenceMapFirstToSecond
+ (num_vertices(m_graph1), m_vindex_map1);
+
+ CachedCorrespondenceMapSecondToFirst
+ new_subgraph_2_to_1 = CachedCorrespondenceMapSecondToFirst
+ (num_vertices(m_graph2), m_vindex_map2);
+
+ BGL_FORALL_VERTICES_T(vertex1, m_graph1, GraphFirst) {
+ put(new_subgraph_1_to_2, vertex1, get(correspondence_map_1_to_2, vertex1));
+ }
+
+ BGL_FORALL_VERTICES_T(vertex2, m_graph2, GraphFirst) {
+ put(new_subgraph_2_to_1, vertex2, get(correspondence_map_2_to_1, vertex2));
+ }
+
+ m_subgraphs->push_back(std::make_pair(subgraph_size,
+ std::make_pair(new_subgraph_1_to_2,
+ new_subgraph_2_to_1)));
}
return (true);
}
- void output_cached_subgraphs() {
+ void output_subgraphs() {
for (typename SubGraphList::const_iterator
- subgraph_iter = m_subgraphs.begin();
- subgraph_iter != m_subgraphs.end();
+ subgraph_iter = m_subgraphs->begin();
+ subgraph_iter != m_subgraphs->end();
++subgraph_iter) {
SubGraph subgraph_cached = *subgraph_iter;
@@ -755,15 +792,15 @@
subgraph_cached.first);
}
}
-
+
private:
const GraphFirst& m_graph1;
const GraphFirst& m_graph2;
const VertexIndexMapFirst m_vindex_map1;
const VertexIndexMapSecond m_vindex_map2;
- SubGraphList m_subgraphs;
+ shared_ptr<SubGraphList> m_subgraphs;
+ shared_ptr<VertexSizeFirst> m_largest_size_so_far;
SubGraphCallback m_user_callback;
- typename graph_traits<GraphFirst>::vertices_size_type m_largest_size_so_far;
};
} // namespace detail
@@ -785,6 +822,7 @@
const VertexIndexMapSecond vindex_map2,
EdgeEquivalencePredicate edges_equivalent,
VertexEquivalencePredicate vertices_equivalent,
+ bool only_connected_subgraphs,
SubGraphCallback user_callback)
{
detail::maximum_subgraph_interceptor<GraphFirst, GraphSecond,
@@ -796,10 +834,10 @@
(graph1, graph2,
vindex_map1, vindex_map2,
edges_equivalent, vertices_equivalent,
- max_interceptor);
+ only_connected_subgraphs, max_interceptor);
// Only output the largest subgraphs
- max_interceptor.output_cached_subgraphs();
+ max_interceptor.output_subgraphs();
}
// Variant of mcgregor_common_subgraphs_maximum with all default
@@ -810,13 +848,14 @@
void mcgregor_common_subgraphs_maximum
(const GraphFirst& graph1,
const GraphSecond& graph2,
+ bool only_connected_subgraphs,
SubGraphCallback user_callback)
{
mcgregor_common_subgraphs_maximum
(graph1, graph2,
get(vertex_index, graph1), get(vertex_index, graph2),
always_equivalent(), always_equivalent(),
- user_callback);
+ only_connected_subgraphs, user_callback);
}
// Named parameter variant of mcgregor_common_subgraphs_maximum
@@ -829,6 +868,7 @@
void mcgregor_common_subgraphs_maximum
(const GraphFirst& graph1,
const GraphSecond& graph2,
+ bool only_connected_subgraphs,
SubGraphCallback user_callback,
const bgl_named_params<Param, Tag, Rest>& params)
{
@@ -842,7 +882,7 @@
always_equivalent()),
choose_param(get_param(params, vertices_equivalent_t()),
always_equivalent()),
- user_callback);
+ only_connected_subgraphs, user_callback);
}
// ==========================================================================
@@ -859,19 +899,22 @@
typename SubGraphCallback>
struct unique_maximum_subgraph_interceptor {
+ typedef typename graph_traits<GraphFirst>::vertices_size_type
+ VertexSizeFirst;
+
typedef mcgregor_common_subgraph_traits<GraphFirst, GraphSecond,
VertexIndexMapFirst, VertexIndexMapSecond> SubGraphTraits;
typedef typename SubGraphTraits::correspondence_map_first_to_second_type
- CorrespondenceMapFirstToSecond;
+ CachedCorrespondenceMapFirstToSecond;
typedef typename SubGraphTraits::correspondence_map_second_to_first_type
- CorrespondenceMapSecondToFirst;
+ CachedCorrespondenceMapSecondToFirst;
+
+ typedef std::pair<VertexSizeFirst,
+ std::pair<CachedCorrespondenceMapFirstToSecond,
+ CachedCorrespondenceMapSecondToFirst> > SubGraph;
- typedef std::pair<std::size_t,
- std::pair<CorrespondenceMapFirstToSecond,
- CorrespondenceMapSecondToFirst> > SubGraph;
-
typedef std::vector<SubGraph> SubGraphList;
unique_maximum_subgraph_interceptor(const GraphFirst& graph1,
@@ -881,33 +924,33 @@
SubGraphCallback user_callback) :
m_graph1(graph1), m_graph2(graph2),
m_vindex_map1(vindex_map1), m_vindex_map2(vindex_map2),
- m_user_callback(user_callback),
- m_largest_size_so_far(0) { }
+ m_subgraphs(make_shared<SubGraphList>()),
+ m_largest_size_so_far(make_shared<VertexSizeFirst>(0)),
+ m_user_callback(user_callback) { }
- bool operator()(CorrespondenceMapFirstToSecond& correspondence_map_1_to_2,
- CorrespondenceMapSecondToFirst& correspondence_map_2_to_1,
- std::size_t subgraph_size) {
-
- if (subgraph_size > m_largest_size_so_far) {
- m_subgraphs.clear();
- m_largest_size_so_far = subgraph_size;
+ template <typename CorrespondenceMapFirstToSecond,
+ typename CorrespondenceMapSecondToFirst>
+ bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
+ CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
+ VertexSizeFirst subgraph_size) {
+
+ if (subgraph_size > *m_largest_size_so_far) {
+ m_subgraphs->clear();
+ *m_largest_size_so_far = subgraph_size;
}
- if (subgraph_size == m_largest_size_so_far) {
+ if (subgraph_size == *m_largest_size_so_far) {
// Check if subgraph is unique
for (typename SubGraphList::const_iterator
- subgraph_iter = m_subgraphs.begin();
- subgraph_iter != m_subgraphs.end();
+ subgraph_iter = m_subgraphs->begin();
+ subgraph_iter != m_subgraphs->end();
++subgraph_iter) {
SubGraph subgraph_cached = *subgraph_iter;
- CorrespondenceMapFirstToSecond correspondence_map_1_to_2_cached =
- subgraph_cached.second.first;
-
if (!are_property_maps_different(correspondence_map_1_to_2,
- correspondence_map_1_to_2_cached,
+ subgraph_cached.second.first,
m_graph1)) {
// New subgraph is a duplicate
@@ -916,27 +959,34 @@
}
// Subgraph is unique, so make a cached copy
- SubGraph new_subgraph = std::make_pair(subgraph_size,
- std::make_pair
- (CorrespondenceMapFirstToSecond(num_vertices(m_graph1), m_vindex_map1),
- CorrespondenceMapSecondToFirst(num_vertices(m_graph2), m_vindex_map2)));
-
- copy_vertex_property(correspondence_map_1_to_2,
- new_subgraph.second.first, m_graph1);
-
- copy_vertex_property(correspondence_map_2_to_1,
- new_subgraph.second.second, m_graph2);
-
- m_subgraphs.push_back(new_subgraph);
+ CachedCorrespondenceMapFirstToSecond
+ new_subgraph_1_to_2 = CachedCorrespondenceMapFirstToSecond
+ (num_vertices(m_graph1), m_vindex_map1);
+
+ CachedCorrespondenceMapSecondToFirst
+ new_subgraph_2_to_1 = CachedCorrespondenceMapSecondToFirst
+ (num_vertices(m_graph2), m_vindex_map2);
+
+ BGL_FORALL_VERTICES_T(vertex1, m_graph1, GraphFirst) {
+ put(new_subgraph_1_to_2, vertex1, get(correspondence_map_1_to_2, vertex1));
+ }
+
+ BGL_FORALL_VERTICES_T(vertex2, m_graph2, GraphFirst) {
+ put(new_subgraph_2_to_1, vertex2, get(correspondence_map_2_to_1, vertex2));
+ }
+
+ m_subgraphs->push_back(std::make_pair(subgraph_size,
+ std::make_pair(new_subgraph_1_to_2,
+ new_subgraph_2_to_1)));
}
return (true);
}
- void output_cached_subgraphs() {
+ void output_subgraphs() {
for (typename SubGraphList::const_iterator
- subgraph_iter = m_subgraphs.begin();
- subgraph_iter != m_subgraphs.end();
+ subgraph_iter = m_subgraphs->begin();
+ subgraph_iter != m_subgraphs->end();
++subgraph_iter) {
SubGraph subgraph_cached = *subgraph_iter;
@@ -951,9 +1001,9 @@
const GraphFirst& m_graph2;
const VertexIndexMapFirst m_vindex_map1;
const VertexIndexMapSecond m_vindex_map2;
- SubGraphList m_subgraphs;
+ shared_ptr<SubGraphList> m_subgraphs;
+ shared_ptr<VertexSizeFirst> m_largest_size_so_far;
SubGraphCallback m_user_callback;
- typename graph_traits<GraphFirst>::vertices_size_type m_largest_size_so_far;
};
} // namespace detail
@@ -975,6 +1025,7 @@
const VertexIndexMapSecond vindex_map2,
EdgeEquivalencePredicate edges_equivalent,
VertexEquivalencePredicate vertices_equivalent,
+ bool only_connected_subgraphs,
SubGraphCallback user_callback)
{
detail::unique_maximum_subgraph_interceptor<GraphFirst, GraphSecond,
@@ -986,10 +1037,10 @@
(graph1, graph2,
vindex_map1, vindex_map2,
edges_equivalent, vertices_equivalent,
- unique_max_interceptor);
+ only_connected_subgraphs, unique_max_interceptor);
// Only output the largest, unique subgraphs
- unique_max_interceptor.output_cached_subgraphs();
+ unique_max_interceptor.output_subgraphs();
}
// Variant of mcgregor_common_subgraphs_maximum_unique with all default parameters
@@ -999,6 +1050,7 @@
void mcgregor_common_subgraphs_maximum_unique
(const GraphFirst& graph1,
const GraphSecond& graph2,
+ bool only_connected_subgraphs,
SubGraphCallback user_callback)
{
@@ -1006,7 +1058,7 @@
(graph1, graph2,
get(vertex_index, graph1), get(vertex_index, graph2),
always_equivalent(), always_equivalent(),
- user_callback);
+ only_connected_subgraphs, user_callback);
}
// Named parameter variant of
@@ -1020,6 +1072,7 @@
void mcgregor_common_subgraphs_maximum_unique
(const GraphFirst& graph1,
const GraphSecond& graph2,
+ bool only_connected_subgraphs,
SubGraphCallback user_callback,
const bgl_named_params<Param, Tag, Rest>& params)
{
@@ -1033,7 +1086,7 @@
always_equivalent()),
choose_param(get_param(params, vertices_equivalent_t()),
always_equivalent()),
- user_callback);
+ only_connected_subgraphs, user_callback);
}
// ==========================================================================
Modified: trunk/libs/graph/test/mcgregor_subgraphs_test.cpp
==============================================================================
--- trunk/libs/graph/test/mcgregor_subgraphs_test.cpp (original)
+++ trunk/libs/graph/test/mcgregor_subgraphs_test.cpp 2009-06-24 16:31:50 EDT (Wed, 24 Jun 2009)
@@ -1,7 +1,17 @@
+//=======================================================================
+// 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 <cmath>
#include <iostream>
#include <fstream>
+#include <sstream>
#include <vector>
-#include <cmath>
#include <boost/lexical_cast.hpp>
#include <boost/random.hpp>
@@ -13,10 +23,12 @@
#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>
using namespace boost;
bool was_common_subgraph_found = false, output_graphs = false;
+std::vector<std::string> simple_subgraph_list;
// Callback that compares incoming graphs to the supplied common
// subgraph.
@@ -172,6 +184,46 @@
Graph& m_common_subgraph;
};
+template <typename Graph>
+struct simple_callback {
+
+ simple_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,
+ typename graph_traits<Graph>::vertices_size_type subgraph_size) {
+
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+
+ typedef typename property_map<Graph, vertex_index_t>::type VertexIndexMap;
+ typedef typename property_map<Graph, vertex_name_t>::type VertexNameMap;
+ typedef typename property_map<Graph, edge_name_t>::type EdgeNameMap;
+
+ std::stringstream subgraph_string;
+
+ BGL_FORALL_VERTICES_T(vertex1, m_graph1, Graph) {
+
+ Vertex vertex2 = get(correspondence_map_1_to_2, vertex1);
+
+ if (vertex2 != graph_traits<Graph>::null_vertex()) {
+ subgraph_string << vertex1 << "," << vertex2 << " ";
+ }
+
+ }
+
+ simple_subgraph_list.push_back(subgraph_string.str());
+
+ return (true);
+ }
+
+private:
+ const Graph& m_graph1;
+
+};
+
template <typename Graph,
typename RandomNumberGenerator,
typename VertexNameMap,
@@ -224,6 +276,11 @@
}
}
+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;
@@ -326,11 +383,89 @@
test_callback<Graph> user_callback(common_subgraph, graph1, graph2);
- mcgregor_common_subgraphs(graph1, graph2, user_callback,
+ mcgregor_common_subgraphs(graph1, graph2, true, user_callback,
edges_equivalent(make_property_map_equivalent(ename_map1, ename_map2)).
vertices_equivalent(make_property_map_equivalent(vname_map1, vname_map2)));
BOOST_CHECK(was_common_subgraph_found);
+ // Test maximum and unique variants on known graphs
+ Graph graph_simple1, graph_simple2;
+ simple_callback<Graph> user_callback_simple(graph_simple1);
+
+ VertexNameMap vname_map_simple1 = get(vertex_name, graph_simple1);
+ VertexNameMap vname_map_simple2 = get(vertex_name, graph_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);
+
+ add_edge(0, 1, graph_simple1);
+ add_edge(0, 2, graph_simple1);
+ add_edge(1, 2, graph_simple1);
+
+ 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);
+
+ add_edge(0, 1, graph_simple2);
+ add_edge(0, 2, graph_simple2);
+ add_edge(1, 2, graph_simple2);
+ add_edge(1, 3, graph_simple2);
+
+ // Unique subgraphs
+ std::cout << "Searching for unique subgraphs" << std::endl;
+ mcgregor_common_subgraphs_unique(graph_simple1, graph_simple2,
+ true, user_callback_simple,
+ vertices_equivalent(make_property_map_equivalent(vname_map_simple1, vname_map_simple2)));
+
+ 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 "));
+
+ 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;
+ }
+
+ simple_subgraph_list.clear();
+
+ // Maximum subgraphs
+ std::cout << "Searching for maximum subgraphs" << std::endl;
+ mcgregor_common_subgraphs_maximum(graph_simple1, graph_simple2,
+ true, user_callback_simple,
+ vertices_equivalent(make_property_map_equivalent(vname_map_simple1, vname_map_simple2)));
+
+ 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"));
+
+ std::cout << std::endl;
+ }
+
+ simple_subgraph_list.clear();
+
+ // Maximum, unique subgraphs
+ std::cout << "Searching for maximum unique subgraphs" << std::endl;
+ mcgregor_common_subgraphs_maximum_unique(graph_simple1, graph_simple2,
+ true, user_callback_simple,
+ vertices_equivalent(make_property_map_equivalent(vname_map_simple1, vname_map_simple2)));
+
+ 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"));
+
+ std::cout << std::endl;
+ }
+
return 0;
}