Subject: [Boost-commit] svn:boost r54540 - in branches/release: boost/graph boost/graph/detail boost/property_map libs/graph/doc libs/graph/example libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-06-30 13:08:51
Author: jewillco
Date: 2009-06-30 13:08:49 EDT (Tue, 30 Jun 2009)
New Revision: 54540
URL: http://svn.boost.org/trac/boost/changeset/54540
Log:
Merged patches mentioned in comments 34-53 from ticket 3134 into release branch; refs #3134
Added:
branches/release/boost/graph/mcgregor_common_subgraphs.hpp
- copied, changed from r54069, /trunk/boost/graph/mcgregor_common_subgraphs.hpp
branches/release/libs/graph/doc/mcgregor_common_subgraphs.html
- copied unchanged from r54344, /trunk/libs/graph/doc/mcgregor_common_subgraphs.html
branches/release/libs/graph/example/mcgregor_subgraphs_example.cpp
- copied unchanged from r54344, /trunk/libs/graph/example/mcgregor_subgraphs_example.cpp
branches/release/libs/graph/test/mcgregor_subgraphs_test.cpp
- copied, changed from r54216, /trunk/libs/graph/test/mcgregor_subgraphs_test.cpp
Text files modified:
branches/release/boost/graph/compressed_sparse_row_graph.hpp | 514 ++++++++++++++++++++++++---------------
branches/release/boost/graph/detail/indexed_properties.hpp | 32 ++
branches/release/boost/graph/filtered_graph.hpp | 17 +
branches/release/boost/graph/graph_utility.hpp | 37 ++
branches/release/boost/graph/mcgregor_common_subgraphs.hpp | 434 ++++++++++++++++++---------------
branches/release/boost/property_map/shared_array_property_map.hpp | 2
branches/release/libs/graph/doc/compressed_sparse_row.html | 51 +++
branches/release/libs/graph/doc/table_of_contents.html | 1
branches/release/libs/graph/example/Jamfile.v2 | 1
branches/release/libs/graph/test/CMakeLists.txt | 1
branches/release/libs/graph/test/Jamfile.v2 | 1
branches/release/libs/graph/test/mcgregor_subgraphs_test.cpp | 148 ++++++++++
12 files changed, 836 insertions(+), 403 deletions(-)
Modified: branches/release/boost/graph/compressed_sparse_row_graph.hpp
==============================================================================
--- branches/release/boost/graph/compressed_sparse_row_graph.hpp (original)
+++ branches/release/boost/graph/compressed_sparse_row_graph.hpp 2009-06-30 13:08:49 EDT (Tue, 30 Jun 2009)
@@ -27,6 +27,7 @@
#include <boost/graph/filtered_graph.hpp> // For keep_all
#include <boost/graph/detail/indexed_properties.hpp>
#include <boost/iterator/counting_iterator.hpp>
+#include <boost/iterator/reverse_iterator.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/integer.hpp>
#include <boost/iterator/iterator_facade.hpp>
@@ -64,6 +65,11 @@
enum edges_are_sorted_t {edges_are_sorted};
#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+// A type (edges_are_sorted_global_t) and a value (edges_are_sorted_global)
+// used to indicate that the edge list passed into the CSR graph is already
+// sorted by source vertex.
+enum edges_are_sorted_global_t {edges_are_sorted_global};
+
// A type (edges_are_unsorted_t) and a value (edges_are_unsorted) used to
// indicate that the edge list passed into the CSR graph is not sorted by
// source vertex. This version caches the edge information in memory, and thus
@@ -76,13 +82,13 @@
// memory but requires multi-pass capability on the iterators.
enum edges_are_unsorted_multi_pass_t {edges_are_unsorted_multi_pass};
-// A type (edges_are_unsorted_multi_pass_filtered_t) and a value
-// (edges_are_unsorted_multi_pass_filtered) used to indicate that the edge list
+// A type (edges_are_unsorted_multi_pass_global_t) and a value
+// (edges_are_unsorted_multi_pass_global) used to indicate that the edge list
// passed into the CSR graph is not sorted by source vertex. This version uses
// less memory but requires multi-pass capability on the iterators. The
-// filtering is done here because it is often faster and it greatly simplifies
-// handling of edge properties.
-enum edges_are_unsorted_multi_pass_filtered_t {edges_are_unsorted_multi_pass_filtered};
+// global mapping and filtering is done here because it is often faster and it
+// greatly simplifies handling of edge properties.
+enum edges_are_unsorted_multi_pass_global_t {edges_are_unsorted_multi_pass_global};
// A type (construct_inplace_from_sources_and_targets_t) and a value
// (construct_inplace_from_sources_and_targets) used to indicate that mutable
@@ -102,14 +108,14 @@
// (sequential and distributed).
enum construct_inplace_from_sources_and_targets_global_t {construct_inplace_from_sources_and_targets_global};
-// A type (edges_are_unsorted_for_distributed_graph_t) and a value
-// (edges_are_unsorted_for_distributed_graph) used to indicate that the edge
-// list passed into the CSR graph is not sorted by source vertex. The data is
-// also stored using global vertex indices, and must be filtered to choose only
-// local vertices. This constructor caches the edge information in memory, and
-// thus requires only a single pass over the input data. This constructor is
-// intended for internal use by the distributed CSR constructors.
-enum edges_are_unsorted_for_distributed_graph_t {edges_are_unsorted_for_distributed_graph};
+// A type (edges_are_unsorted_global_t) and a value (edges_are_unsorted_global)
+// used to indicate that the edge list passed into the CSR graph is not sorted
+// by source vertex. The data is also stored using global vertex indices, and
+// must be filtered to choose only local vertices. This constructor caches the
+// edge information in memory, and thus requires only a single pass over the
+// input data. This constructor is intended for internal use by the
+// distributed CSR constructors.
+enum edges_are_unsorted_global_t {edges_are_unsorted_global};
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
@@ -128,7 +134,6 @@
template<typename Vertex, typename EdgeIndex>
class csr_edge_descriptor;
-#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
namespace detail {
template<typename InputIterator>
size_t
@@ -157,8 +162,21 @@
category;
return reserve_count_for_single_pass_helper(first, last, category());
}
-}
+
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+ template <typename T>
+ struct default_construct_iterator: public boost::iterator_facade<default_construct_iterator<T>, T, boost::random_access_traversal_tag, const T&> {
+ typedef boost::iterator_facade<default_construct_iterator<T>, T, std::random_access_iterator_tag, const T&> base_type;
+ T saved_value;
+ const T& dereference() const {return saved_value;}
+ bool equal(default_construct_iterator i) const {return true;}
+ void increment() {}
+ void decrement() {}
+ void advance(typename base_type::difference_type) {}
+ typename base_type::difference_type distance_to(default_construct_iterator) const {return 0;}
+ };
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+}
/** Compressed sparse row graph.
*
@@ -166,8 +184,8 @@
* specialize numeric_limits.
*/
template<typename Directed = directedS,
- typename VertexProperty = void,
- typename EdgeProperty = void,
+ typename VertexProperty = no_property,
+ typename EdgeProperty = no_property,
typename GraphProperty = no_property,
typename Vertex = std::size_t,
typename EdgeIndex = Vertex>
@@ -179,6 +197,7 @@
EdgeIndex> >
{
+ public:
typedef detail::indexed_vertex_properties<compressed_sparse_row_graph,
VertexProperty, Vertex>
inherited_vertex_properties;
@@ -280,25 +299,26 @@
#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// Rebuild graph from number of vertices and multi-pass unsorted list of
- // edges (filtered using edge_pred)
- template <typename MultiPassInputIterator, typename EdgePred>
+ // edges (filtered using edge_pred and mapped using global_to_local)
+ template <typename MultiPassInputIterator, typename GlobalToLocal, typename EdgePred>
void
assign_unsorted_multi_pass_edges(MultiPassInputIterator edge_begin,
MultiPassInputIterator edge_end,
- vertices_size_type numverts,
+ vertices_size_type numlocalverts,
+ const GlobalToLocal& global_to_local,
const EdgePred& edge_pred) {
m_rowstart.clear();
- m_rowstart.resize(numverts + 1, 0);
+ m_rowstart.resize(numlocalverts + 1, 0);
// Put the degree of each vertex v into m_rowstart[v + 1]
for (MultiPassInputIterator i = edge_begin; i != edge_end; ++i)
if (edge_pred(*i))
- ++m_rowstart[i->first + 1];
+ ++m_rowstart[get(global_to_local, i->first) + 1];
// Compute the partial sum of the degrees to get the actual values of
// m_rowstart
EdgeIndex start_of_this_row = 0;
m_rowstart[0] = start_of_this_row;
- for (vertices_size_type i = 1; i <= numverts; ++i) {
+ for (vertices_size_type i = 1; i <= numlocalverts; ++i) {
start_of_this_row += m_rowstart[i];
m_rowstart[i] = start_of_this_row;
}
@@ -308,33 +328,35 @@
// into m_column. The index current_insert_positions[v] contains the next
// location to insert out edges for vertex v.
std::vector<EdgeIndex>
- current_insert_positions(m_rowstart.begin(), m_rowstart.begin() + numverts);
+ current_insert_positions(m_rowstart.begin(), m_rowstart.begin() + numlocalverts);
for (; edge_begin != edge_end; ++edge_begin)
if (edge_pred(*edge_begin))
- m_column[current_insert_positions[edge_begin->first]++] = edge_begin->second;
+ m_column[current_insert_positions[get(global_to_local, edge_begin->first)]++] = edge_begin->second;
}
// Rebuild graph from number of vertices and multi-pass unsorted list of
- // edges and their properties (filtered using edge_pred)
- template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename EdgePred>
+ // edges and their properties (filtered using edge_pred and mapped using
+ // global_to_local)
+ template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename EdgePred>
void
assign_unsorted_multi_pass_edges(MultiPassInputIterator edge_begin,
MultiPassInputIterator edge_end,
EdgePropertyIterator ep_iter,
- vertices_size_type numverts,
+ vertices_size_type numlocalverts,
+ const GlobalToLocal& global_to_local,
const EdgePred& edge_pred) {
m_rowstart.clear();
- m_rowstart.resize(numverts + 1, 0);
+ m_rowstart.resize(numlocalverts + 1, 0);
// Put the degree of each vertex v into m_rowstart[v + 1]
for (MultiPassInputIterator i = edge_begin; i != edge_end; ++i)
if (edge_pred(*i))
- ++m_rowstart[i->first + 1];
+ ++m_rowstart[get(global_to_local, i->first) + 1];
// Compute the partial sum of the degrees to get the actual values of
// m_rowstart
EdgeIndex start_of_this_row = 0;
m_rowstart[0] = start_of_this_row;
- for (vertices_size_type i = 1; i <= numverts; ++i) {
+ for (vertices_size_type i = 1; i <= numlocalverts; ++i) {
start_of_this_row += m_rowstart[i];
m_rowstart[i] = start_of_this_row;
}
@@ -345,10 +367,10 @@
// into m_column. The index current_insert_positions[v] contains the next
// location to insert out edges for vertex v.
std::vector<EdgeIndex>
- current_insert_positions(m_rowstart.begin(), m_rowstart.begin() + numverts);
+ current_insert_positions(m_rowstart.begin(), m_rowstart.begin() + numlocalverts);
for (; edge_begin != edge_end; ++edge_begin, ++ep_iter) {
if (edge_pred(*edge_begin)) {
- vertices_size_type source = edge_begin->first;
+ vertices_size_type source = get(global_to_local, edge_begin->first);
EdgeIndex insert_pos = current_insert_positions[source];
++current_insert_positions[source];
m_column[insert_pos] = edge_begin->second;
@@ -367,7 +389,7 @@
: inherited_vertex_properties(numverts), m_rowstart(),
m_column(0), m_property(prop)
{
- assign_unsorted_multi_pass_edges(edge_begin, edge_end, numverts, keep_all());
+ assign_unsorted_multi_pass_edges(edge_begin, edge_end, numverts, identity_property_map(), keep_all());
// Default-construct properties for edges
inherited_edge_properties::resize(m_column.size());
@@ -384,42 +406,113 @@
: inherited_vertex_properties(numverts), m_rowstart(),
m_column(0), m_property(prop)
{
- assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numverts, keep_all());
+ assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numverts, identity_property_map(), keep_all());
}
- // From number of vertices and unsorted list of edges, with filter
- template <typename MultiPassInputIterator, typename EdgePred>
- compressed_sparse_row_graph(edges_are_unsorted_multi_pass_filtered_t,
+ // From number of vertices and unsorted list of edges, with filter and
+ // global-to-local map
+ template <typename MultiPassInputIterator, typename GlobalToLocal, typename EdgePred>
+ compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
MultiPassInputIterator edge_begin,
MultiPassInputIterator edge_end,
- vertices_size_type numverts,
+ vertices_size_type numlocalverts,
+ const GlobalToLocal& global_to_local,
const EdgePred& edge_pred,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numverts), m_rowstart(),
+ : inherited_vertex_properties(numlocalverts), m_rowstart(),
m_column(0), m_property(prop)
{
- assign_unsorted_multi_pass_edges(edge_begin, edge_end, numverts, edge_pred);
+ assign_unsorted_multi_pass_edges(edge_begin, edge_end, numlocalverts, global_to_local, edge_pred);
// Default-construct properties for edges
inherited_edge_properties::resize(m_column.size());
}
- // From number of vertices and unsorted list of edges, plus edge properties, with filter
- template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename EdgePred>
- compressed_sparse_row_graph(edges_are_unsorted_multi_pass_filtered_t,
+ // From number of vertices and unsorted list of edges, plus edge properties,
+ // with filter and global-to-local map
+ template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename EdgePred>
+ compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
MultiPassInputIterator edge_begin,
MultiPassInputIterator edge_end,
EdgePropertyIterator ep_iter,
- vertices_size_type numverts,
+ vertices_size_type numlocalverts,
+ const GlobalToLocal& global_to_local,
const EdgePred& edge_pred,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numverts), m_rowstart(),
+ : inherited_vertex_properties(numlocalverts), m_rowstart(),
m_column(0), m_property(prop)
{
- assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numverts, edge_pred);
+ assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numlocalverts, global_to_local, edge_pred);
}
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+ // Assign from number of vertices and sorted list of edges
+ template<typename InputIterator, typename GlobalToLocal, typename EdgePred>
+ void assign_from_sorted_edges(
+ InputIterator edge_begin, InputIterator edge_end,
+ const GlobalToLocal& global_to_local,
+ const EdgePred& edge_pred,
+ vertices_size_type numlocalverts,
+ edges_size_type numedges_or_zero) {
+ m_column.clear();
+ m_column.reserve(numedges_or_zero);
+ inherited_vertex_properties::resize(numlocalverts);
+ m_rowstart.resize(numlocalverts + 1);
+ EdgeIndex current_edge = 0;
+ Vertex current_vertex_plus_one = 1;
+ m_rowstart[0] = 0;
+ for (InputIterator ei = edge_begin; ei != edge_end; ++ei) {
+ if (!edge_pred(*ei)) continue;
+ Vertex src = get(global_to_local, ei->first);
+ Vertex tgt = ei->second;
+ for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)
+ m_rowstart[current_vertex_plus_one] = current_edge;
+ m_column.push_back(tgt);
+ ++current_edge;
+ }
+
+ // The remaining vertices have no edges
+ for (; current_vertex_plus_one != numlocalverts + 1; ++current_vertex_plus_one)
+ m_rowstart[current_vertex_plus_one] = current_edge;
+
+ // Default-construct properties for edges
+ inherited_edge_properties::resize(m_column.size());
+ }
+
+ // Assign from number of vertices and sorted list of edges
+ template<typename InputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename EdgePred>
+ void assign_from_sorted_edges(
+ InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ const GlobalToLocal& global_to_local,
+ const EdgePred& edge_pred,
+ vertices_size_type numlocalverts,
+ edges_size_type numedges_or_zero) {
+ m_column.clear();
+ m_column.reserve(numedges_or_zero);
+ inherited_edge_properties::clear();
+ inherited_edge_properties::reserve(numedges_or_zero);
+ inherited_vertex_properties::resize(numlocalverts);
+ m_rowstart.resize(numlocalverts + 1);
+ EdgeIndex current_edge = 0;
+ Vertex current_vertex_plus_one = 1;
+ m_rowstart[0] = 0;
+ for (InputIterator ei = edge_begin; ei != edge_end; ++ei, ++ep_iter) {
+ if (!edge_pred(*ei)) continue;
+ Vertex src = get(global_to_local, ei->first);
+ Vertex tgt = ei->second;
+ for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)
+ m_rowstart[current_vertex_plus_one] = current_edge;
+ m_column.push_back(tgt);
+ inherited_edge_properties::push_back(*ep_iter);
+ ++current_edge;
+ }
+
+ // The remaining vertices have no edges
+ for (; current_vertex_plus_one != numlocalverts + 1; ++current_vertex_plus_one)
+ m_rowstart[current_vertex_plus_one] = current_edge;
+ }
+
#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
// From number of vertices and sorted list of edges (deprecated
@@ -429,8 +522,7 @@
vertices_size_type numverts,
edges_size_type numedges = 0,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
- m_column(0), m_property(prop), m_last_source(numverts)
+ : m_property(prop), m_last_source(numverts)
{
// Reserving storage in advance can save us lots of time and
// memory, but it can only be done if we have forward iterators or
@@ -438,29 +530,9 @@
if (numedges == 0) {
typedef typename std::iterator_traits<InputIterator>::iterator_category
category;
- maybe_reserve_edge_list_storage(edge_begin, edge_end, category());
- } else {
- m_column.reserve(numedges);
- }
-
- EdgeIndex current_edge = 0;
- Vertex current_vertex_plus_one = 1;
- m_rowstart[0] = 0;
- for (InputIterator ei = edge_begin; ei != edge_end; ++ei) {
- Vertex src = ei->first;
- Vertex tgt = ei->second;
- for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)
- m_rowstart[current_vertex_plus_one] = current_edge;
- m_column.push_back(tgt);
- ++current_edge;
+ numedges = detail::reserve_count_for_single_pass(edge_begin, edge_end);
}
-
- // The remaining vertices have no edges
- for (; current_vertex_plus_one != numverts + 1; ++current_vertex_plus_one)
- m_rowstart[current_vertex_plus_one] = current_edge;
-
- // Default-construct properties for edges
- inherited_edge_properties::resize(m_column.size());
+ assign_from_sorted_edges(edge_begin, edge_end, identity_property_map(), keep_all(), numverts, numedges);
}
// From number of vertices and sorted list of edges (deprecated
@@ -471,8 +543,7 @@
vertices_size_type numverts,
edges_size_type numedges = 0,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
- m_column(0), m_property(prop), m_last_source(numverts)
+ : m_property(prop), m_last_source(numverts)
{
// Reserving storage in advance can save us lots of time and
// memory, but it can only be done if we have forward iterators or
@@ -480,27 +551,9 @@
if (numedges == 0) {
typedef typename std::iterator_traits<InputIterator>::iterator_category
category;
- maybe_reserve_edge_list_storage(edge_begin, edge_end, category());
- } else {
- m_column.reserve(numedges);
- }
-
- EdgeIndex current_edge = 0;
- Vertex current_vertex_plus_one = 1;
- m_rowstart[0] = 0;
- for (InputIterator ei = edge_begin; ei != edge_end; ++ei, ++ep_iter) {
- Vertex src = ei->first;
- Vertex tgt = ei->second;
- for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)
- m_rowstart[current_vertex_plus_one] = current_edge;
- m_column.push_back(tgt);
- inherited_edge_properties::push_back(*ep_iter);
- ++current_edge;
+ numedges = detail::reserve_count_for_single_pass(edge_begin, edge_end);
}
-
- // The remaining vertices have no edges
- for (; current_vertex_plus_one != numverts + 1; ++current_vertex_plus_one)
- m_rowstart[current_vertex_plus_one] = current_edge;
+ assign_from_sorted_edges(edge_begin, edge_end, ep_iter, identity_property_map(), keep_all(), numverts, numedges);
}
#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
@@ -512,8 +565,7 @@
vertices_size_type numverts,
edges_size_type numedges = 0,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
- m_column(0), m_property(prop)
+ : m_property(prop)
#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
, m_last_source(numverts)
#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
@@ -524,29 +576,9 @@
if (numedges == 0) {
typedef typename std::iterator_traits<InputIterator>::iterator_category
category;
- maybe_reserve_edge_list_storage(edge_begin, edge_end, category());
- } else {
- m_column.reserve(numedges);
- }
-
- EdgeIndex current_edge = 0;
- Vertex current_vertex_plus_one = 1;
- m_rowstart[0] = 0;
- for (InputIterator ei = edge_begin; ei != edge_end; ++ei) {
- Vertex src = ei->first;
- Vertex tgt = ei->second;
- for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)
- m_rowstart[current_vertex_plus_one] = current_edge;
- m_column.push_back(tgt);
- ++current_edge;
+ numedges = detail::reserve_count_for_single_pass(edge_begin, edge_end);
}
-
- // The remaining vertices have no edges
- for (; current_vertex_plus_one != numverts + 1; ++current_vertex_plus_one)
- m_rowstart[current_vertex_plus_one] = current_edge;
-
- // Default-construct properties for edges
- inherited_edge_properties::resize(m_column.size());
+ assign_from_sorted_edges(edge_begin, edge_end, identity_property_map(), keep_all(), numverts, numedges);
}
// From number of vertices and sorted list of edges (new interface)
@@ -557,8 +589,7 @@
vertices_size_type numverts,
edges_size_type numedges = 0,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
- m_column(0), m_property(prop)
+ : m_property(prop)
#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
, m_last_source(numverts)
#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
@@ -569,30 +600,45 @@
if (numedges == 0) {
typedef typename std::iterator_traits<InputIterator>::iterator_category
category;
- maybe_reserve_edge_list_storage(edge_begin, edge_end, category());
- } else {
- m_column.reserve(numedges);
+ numedges = detail::reserve_count_for_single_pass(edge_begin, edge_end);
}
+ assign_from_sorted_edges(edge_begin, edge_end, ep_iter, identity_property_map(), keep_all(), numverts, numedges);
+ }
- EdgeIndex current_edge = 0;
- Vertex current_vertex_plus_one = 1;
- m_rowstart[0] = 0;
- for (InputIterator ei = edge_begin; ei != edge_end; ++ei, ++ep_iter) {
- Vertex src = ei->first;
- Vertex tgt = ei->second;
- for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)
- m_rowstart[current_vertex_plus_one] = current_edge;
- m_column.push_back(tgt);
- inherited_edge_properties::push_back(*ep_iter);
- ++current_edge;
- }
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+ // From number of vertices and sorted list of edges, filtered and global (new interface)
+ template<typename InputIterator, typename GlobalToLocal, typename EdgePred>
+ compressed_sparse_row_graph(edges_are_sorted_global_t,
+ InputIterator edge_begin, InputIterator edge_end,
+ const GlobalToLocal& global_to_local,
+ const EdgePred& edge_pred,
+ vertices_size_type numverts,
+ const GraphProperty& prop = GraphProperty())
+ : m_property(prop)
+#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+ , m_last_source(numverts)
+#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+ {
+ assign_from_sorted_edges(edge_begin, edge_end, global_to_local, edge_pred, numverts, 0);
+ }
- // The remaining vertices have no edges
- for (; current_vertex_plus_one != numverts + 1; ++current_vertex_plus_one)
- m_rowstart[current_vertex_plus_one] = current_edge;
+ // From number of vertices and sorted list of edges (new interface)
+ template<typename InputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename EdgePred>
+ compressed_sparse_row_graph(edges_are_sorted_global_t,
+ InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ const GlobalToLocal& global_to_local,
+ const EdgePred& edge_pred,
+ vertices_size_type numverts,
+ const GraphProperty& prop = GraphProperty())
+ : m_property(prop)
+#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+ , m_last_source(numverts)
+#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+ {
+ assign_from_sorted_edges(edge_begin, edge_end, ep_iter, global_to_local, edge_pred, numverts, 0);
}
-#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// From number of vertices and mutable vectors of sources and targets;
// vectors are returned with unspecified contents but are guaranteed not to
// share storage with the constructed graph.
@@ -631,7 +677,7 @@
compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t,
std::vector<vertex_descriptor>& sources,
std::vector<vertex_descriptor>& targets,
- std::vector<typename inherited_edge_properties::edge_property_type>& edge_props,
+ std::vector<typename inherited_edge_properties::edge_bundled>& edge_props,
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty())
: inherited_vertex_properties(numverts), m_rowstart(),
@@ -649,7 +695,7 @@
compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_global_t,
std::vector<vertex_descriptor>& sources,
std::vector<vertex_descriptor>& targets,
- std::vector<typename inherited_edge_properties::edge_property_type>& edge_props,
+ std::vector<typename inherited_edge_properties::edge_bundled>& edge_props,
vertices_size_type numlocalverts,
GlobalToLocal global_to_local,
const GraphProperty& prop = GraphProperty())
@@ -694,7 +740,7 @@
m_column(), m_property(prop)
{
std::vector<vertex_descriptor> sources, targets;
- std::vector<typename inherited_edge_properties::edge_property_type> edge_props;
+ std::vector<typename inherited_edge_properties::edge_bundled> edge_props;
size_t reserve_size
= detail::reserve_count_for_single_pass(edge_begin, edge_end);
sources.reserve(reserve_size);
@@ -712,7 +758,7 @@
// cached in coordinate form before creating the actual graph. Edges are
// filtered and transformed for use in a distributed graph.
template<typename InputIterator, typename GlobalToLocal, typename EdgePred>
- compressed_sparse_row_graph(edges_are_unsorted_for_distributed_graph_t,
+ compressed_sparse_row_graph(edges_are_unsorted_global_t,
InputIterator edge_begin, InputIterator edge_end,
vertices_size_type numlocalverts,
GlobalToLocal global_to_local,
@@ -737,7 +783,7 @@
// use in a distributed graph.
template<typename InputIterator, typename EdgePropertyIterator,
typename GlobalToLocal, typename EdgePred>
- compressed_sparse_row_graph(edges_are_unsorted_for_distributed_graph_t,
+ compressed_sparse_row_graph(edges_are_unsorted_global_t,
InputIterator edge_begin, InputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numlocalverts,
@@ -748,7 +794,7 @@
m_column(), m_property(prop)
{
std::vector<vertex_descriptor> sources, targets;
- std::vector<typename inherited_edge_properties::edge_property_type> edge_props;
+ std::vector<typename inherited_edge_properties::edge_bundled> edge_props;
for (; edge_begin != edge_end; ++edge_begin, ++ep_iter) {
if (edge_pred(*edge_begin)) {
sources.push_back(edge_begin->first);
@@ -776,6 +822,7 @@
m_rowstart.clear();
m_rowstart.resize(numverts + 1);
for (size_t i = 0; i < numedges; ++i) {
+ assert(get(global_to_local, sources[i]) < numverts);
++m_rowstart[get(global_to_local, sources[i]) + 1];
}
// 2. Do a prefix sum on those to get starting positions of each row
@@ -809,7 +856,7 @@
template <typename GlobalToLocal>
void assign_sources_and_targets_global(std::vector<vertex_descriptor>& sources,
std::vector<vertex_descriptor>& targets,
- std::vector<typename inherited_edge_properties::edge_property_type>& edge_props,
+ std::vector<typename inherited_edge_properties::edge_bundled>& edge_props,
vertices_size_type numverts,
GlobalToLocal global_to_local) {
assert (sources.size() == targets.size());
@@ -933,6 +980,100 @@
assign(g, get(vertex_index, g), num_vertices(g), num_edges(g));
}
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+ // Add edges from a sorted (smallest sources first) range of pairs and edge
+ // properties
+ template <typename BidirectionalIteratorOrig, typename EPIterOrig>
+ void
+ add_edges_sorted_internal(
+ BidirectionalIteratorOrig first_sorted,
+ BidirectionalIteratorOrig last_sorted,
+ EPIterOrig ep_iter_sorted) {
+ typedef boost::reverse_iterator<BidirectionalIteratorOrig> BidirectionalIterator;
+ typedef boost::reverse_iterator<EPIterOrig> EPIter;
+ // Flip sequence
+ BidirectionalIterator first(last_sorted);
+ BidirectionalIterator last(first_sorted);
+ typedef compressed_sparse_row_graph Graph;
+ typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
+ typedef typename boost::graph_traits<Graph>::vertices_size_type vertex_num;
+ typedef typename boost::graph_traits<Graph>::edges_size_type edge_num;
+ edge_num new_edge_count = std::distance(first, last);
+ EPIter ep_iter(ep_iter_sorted);
+ std::advance(ep_iter, -(std::ptrdiff_t)new_edge_count);
+ edge_num edges_added_before_i = new_edge_count; // Count increment to add to rowstarts
+ m_column.resize(m_column.size() + new_edge_count);
+ inherited_edge_properties::resize(inherited_edge_properties::size() + new_edge_count);
+ BidirectionalIterator current_new_edge = first, prev_new_edge = first;
+ EPIter current_new_edge_prop = ep_iter;
+ for (vertex_num i_plus_1 = num_vertices(*this); i_plus_1 > 0; --i_plus_1) {
+ vertex_num i = i_plus_1 - 1;
+ prev_new_edge = current_new_edge;
+ // edges_added_to_this_vertex = #mbrs of new_edges with first == i
+ edge_num edges_added_to_this_vertex = 0;
+ while (current_new_edge != last) {
+ if (current_new_edge->first != i) break;
+ ++current_new_edge;
+ ++current_new_edge_prop;
+ ++edges_added_to_this_vertex;
+ }
+ edges_added_before_i -= edges_added_to_this_vertex;
+ // Invariant: edges_added_before_i = #mbrs of new_edges with first < i
+ edge_num old_rowstart = m_rowstart[i];
+ edge_num new_rowstart = m_rowstart[i] + edges_added_before_i;
+ edge_num old_degree = m_rowstart[i + 1] - m_rowstart[i];
+ edge_num new_degree = old_degree + edges_added_to_this_vertex;
+ // Move old edges forward (by #new_edges before this i) to make room
+ // new_rowstart > old_rowstart, so use copy_backwards
+ if (old_rowstart != new_rowstart) {
+ std::copy_backward(m_column.begin() + old_rowstart,
+ m_column.begin() + old_rowstart + old_degree,
+ m_column.begin() + new_rowstart + old_degree);
+ inherited_edge_properties::move_range(old_rowstart, old_rowstart + old_degree, new_rowstart);
+ }
+ // Add new edges (reversed because current_new_edge is a
+ // const_reverse_iterator)
+ BidirectionalIterator temp = current_new_edge;
+ EPIter temp_prop = current_new_edge_prop;
+ for (; temp != prev_new_edge; ++old_degree) {
+ --temp;
+ m_column[new_rowstart + old_degree] = temp->second;
+ inherited_edge_properties::write_by_index(new_rowstart + old_degree, *temp_prop);
+ }
+ m_rowstart[i + 1] = new_rowstart + new_degree;
+ if (edges_added_before_i == 0) break; // No more edges inserted before this point
+ // m_rowstart[i] will be fixed up on the next iteration (to avoid
+ // changing the degree of vertex i - 1); the last iteration never changes
+ // it (either because of the condition of the break or because
+ // m_rowstart[0] is always 0)
+ }
+ }
+
+ // Add edges from a sorted (smallest sources first) range of pairs
+ template <typename BidirectionalIteratorOrig>
+ void
+ add_edges_sorted_internal(
+ BidirectionalIteratorOrig first_sorted,
+ BidirectionalIteratorOrig last_sorted) {
+ add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<typename inherited_edge_properties::edge_bundled>());
+ }
+
+ // Add edges from a range of (source, target) pairs that are unsorted
+ template <typename InputIterator>
+ inline void
+ add_edges_internal(InputIterator first, InputIterator last) {
+ typedef compressed_sparse_row_graph Graph;
+ typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
+ typedef typename boost::graph_traits<Graph>::vertices_size_type vertex_num;
+ typedef typename boost::graph_traits<Graph>::edges_size_type edge_num;
+ typedef std::vector<std::pair<vertex_t, vertex_t> > edge_vector_t;
+ edge_vector_t new_edges(first, last);
+ if (new_edges.empty()) return;
+ std::sort(new_edges.begin(), new_edges.end());
+ add_edges_sorted_internal(new_edges.begin(), new_edges.end());
+ }
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+
using inherited_vertex_properties::operator[];
using inherited_edge_properties::operator[];
@@ -1044,62 +1185,35 @@
#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
-// Add edges from a range of (source, target) pairs that are unsorted
-template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator>
-inline void
-add_edges(InputIterator first, InputIterator last, BOOST_CSR_GRAPH_TYPE& g) {
- typedef BOOST_CSR_GRAPH_TYPE Graph;
- typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
- typedef typename boost::graph_traits<Graph>::vertices_size_type vertex_num;
- typedef typename boost::graph_traits<Graph>::edges_size_type edge_num;
- typedef std::vector<std::pair<vertex_t, vertex_t> > edge_vector_t;
- edge_vector_t new_edges(first, last);
- if (new_edges.empty()) return;
- std::sort(new_edges.begin(), new_edges.end());
- edge_num edges_added_before_i = new_edges.size(); // Count increment to add to rowstarts
- g.m_column.resize(g.m_column.size() + new_edges.size());
- typename edge_vector_t::const_reverse_iterator
- current_new_edge = new_edges.rbegin(),
- prev_new_edge = new_edges.rbegin();
- for (vertex_num i_plus_1 = num_vertices(g); i_plus_1 > 0; --i_plus_1) {
- vertex_num i = i_plus_1 - 1;
- prev_new_edge = current_new_edge;
- // edges_added_to_this_vertex = #mbrs of new_edges with first == i
- edge_num edges_added_to_this_vertex = 0;
- while (current_new_edge !=
- (typename edge_vector_t::const_reverse_iterator)new_edges.rend()) {
- if (current_new_edge->first != i) break;
- ++current_new_edge;
- ++edges_added_to_this_vertex;
- }
- edges_added_before_i -= edges_added_to_this_vertex;
- // Invariant: edges_added_before_i = #mbrs of new_edges with first < i
- edge_num old_rowstart = g.m_rowstart[i];
- edge_num new_rowstart = g.m_rowstart[i] + edges_added_before_i;
- edge_num old_degree = g.m_rowstart[i + 1] - g.m_rowstart[i];
- edge_num new_degree = old_degree + edges_added_to_this_vertex;
- // Move old edges forward (by #new_edges before this i) to make room
- // new_rowstart > old_rowstart, so use copy_backwards
- if (old_rowstart != new_rowstart) {
- std::copy_backward(g.m_column.begin() + old_rowstart,
- g.m_column.begin() + old_rowstart + old_degree,
- g.m_column.begin() + new_rowstart + old_degree);
- }
- // Add new edges (reversed because current_new_edge is a
- // const_reverse_iterator)
- typename edge_vector_t::const_reverse_iterator temp = current_new_edge;
- for (; temp != prev_new_edge; ++old_degree) {
- --temp;
- g.m_column[new_rowstart + old_degree] = temp->second;
- }
- g.m_rowstart[i + 1] = new_rowstart + new_degree;
- if (edges_added_before_i == 0) break; // No more edges inserted before this point
- // g.m_rowstart[i] will be fixed up on the next iteration (to avoid
- // changing the degree of vertex i - 1); the last iteration never changes
- // it (either because of the condition of the break or because
- // g.m_rowstart[0] is always 0)
+ // Add edges from a sorted (smallest sources first) range of pairs and edge
+ // properties
+ template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig,
+ typename EPIterOrig>
+ void
+ add_edges_sorted(
+ BidirectionalIteratorOrig first_sorted,
+ BidirectionalIteratorOrig last_sorted,
+ EPIterOrig ep_iter_sorted,
+ BOOST_CSR_GRAPH_TYPE& g) {
+ g.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted);
+ }
+
+ // Add edges from a sorted (smallest sources first) range of pairs
+ template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig>
+ void
+ add_edges_sorted(
+ BidirectionalIteratorOrig first_sorted,
+ BidirectionalIteratorOrig last_sorted,
+ BOOST_CSR_GRAPH_TYPE& g) {
+ g.add_edges_sorted_internal(first_sorted, last_sorted);
+ }
+
+ // Add edges from a range of (source, target) pairs that are unsorted
+ template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator>
+ inline void
+ add_edges(InputIterator first, InputIterator last, BOOST_CSR_GRAPH_TYPE& g) {
+ g.add_edges_internal(first, last);
}
-}
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// From VertexListGraph
Modified: branches/release/boost/graph/detail/indexed_properties.hpp
==============================================================================
--- branches/release/boost/graph/detail/indexed_properties.hpp (original)
+++ branches/release/boost/graph/detail/indexed_properties.hpp 2009-06-30 13:08:49 EDT (Tue, 30 Jun 2009)
@@ -50,6 +50,12 @@
indexed_vertex_properties(std::size_t n) : m_vertex_properties(n) { }
public:
+ // Clear the properties vector
+ void clear()
+ {
+ m_vertex_properties.clear();
+ }
+
// Resize the properties vector
void resize(std::size_t n)
{
@@ -101,6 +107,7 @@
indexed_vertex_properties(std::size_t) { }
public:
+ void clear() { }
void resize(std::size_t) { }
void reserve(std::size_t) { }
};
@@ -127,6 +134,18 @@
// Initialize with n default-constructed property values
indexed_edge_properties(std::size_t n) : m_edge_properties(n) { }
+ // Get the size of the properties vector
+ std::size_t size() const
+ {
+ return m_edge_properties.size();
+ }
+
+ // Clear the properties vector
+ void clear()
+ {
+ m_edge_properties.clear();
+ }
+
// Resize the properties vector
void resize(std::size_t n)
{
@@ -152,6 +171,14 @@
m_edge_properties.push_back(prop);
}
+ // Move range of properties backwards
+ void move_range(std::size_t src_begin, std::size_t src_end, std::size_t dest_begin) {
+ std::copy_backward(
+ m_edge_properties.begin() + src_begin,
+ m_edge_properties.begin() + src_end,
+ m_edge_properties.begin() + dest_begin + (src_end - src_begin));
+ }
+
private:
// Access to the derived object
Derived& derived() { return *static_cast<Derived*>(this); }
@@ -174,16 +201,21 @@
typedef void* edge_push_back_type;
secret operator[](secret) { return secret(); }
+ void write_by_index(std::size_t idx, const no_property& prop) {}
protected:
// All operations do nothing.
indexed_edge_properties() { }
indexed_edge_properties(std::size_t) { }
+ std::size_t size() const {return 0;}
+ void clear() { }
void resize(std::size_t) { }
void reserve(std::size_t) { }
public:
void push_back(const edge_push_back_type&) { }
+ void move_range(std::size_t src_begin, std::size_t src_end, std::size_t dest_begin) {}
+
};
}
Modified: branches/release/boost/graph/filtered_graph.hpp
==============================================================================
--- branches/release/boost/graph/filtered_graph.hpp (original)
+++ branches/release/boost/graph/filtered_graph.hpp 2009-06-30 13:08:49 EDT (Tue, 30 Jun 2009)
@@ -500,6 +500,23 @@
return Filter(g, keep_all(), p);
}
+ // Filter that uses a property map whose value_type is a boolean
+ template <typename PropertyMap>
+ struct property_map_filter {
+
+ property_map_filter() { }
+
+ property_map_filter(const PropertyMap& property_map) :
+ m_property_map(property_map) { }
+
+ template <typename Key>
+ bool operator()(const Key& key) const {
+ return (get(m_property_map, key));
+ }
+
+ private :
+ PropertyMap m_property_map;
+ };
} // namespace boost
Modified: branches/release/boost/graph/graph_utility.hpp
==============================================================================
--- branches/release/boost/graph/graph_utility.hpp (original)
+++ branches/release/boost/graph/graph_utility.hpp 2009-06-30 13:08:49 EDT (Tue, 30 Jun 2009)
@@ -468,6 +468,43 @@
} // namespace graph
+ #include <boost/graph/iteration_macros.hpp>
+
+ template <class PropertyIn, class PropertyOut, class Graph>
+ void copy_vertex_property(PropertyIn p_in, PropertyOut p_out, Graph& g)
+ {
+ BGL_FORALL_VERTICES_T(u, g, Graph)
+ put(p_out, u, get(p_in, g));
+ }
+
+ template <class PropertyIn, class PropertyOut, class Graph>
+ void copy_edge_property(PropertyIn p_in, PropertyOut p_out, Graph& g)
+ {
+ BGL_FORALL_EDGES_T(e, g, Graph)
+ put(p_out, e, get(p_in, g));
+ }
+
+ // Return true if property_map1 and property_map2 differ
+ // for any of the vertices in graph.
+ template <typename PropertyMapFirst,
+ typename PropertyMapSecond,
+ typename Graph>
+ bool are_property_maps_different
+ (const PropertyMapFirst property_map1,
+ const PropertyMapSecond property_map2,
+ const Graph& graph) {
+
+ BGL_FORALL_VERTICES_T(vertex, graph, Graph) {
+ if (get(property_map1, vertex) !=
+ get(property_map2, vertex)) {
+
+ return (true);
+ }
+ }
+
+ return (false);
+ }
+
} /* namespace boost */
#endif /* BOOST_GRAPH_UTILITY_HPP*/
Copied: branches/release/boost/graph/mcgregor_common_subgraphs.hpp (from r54069, /trunk/boost/graph/mcgregor_common_subgraphs.hpp)
==============================================================================
--- /trunk/boost/graph/mcgregor_common_subgraphs.hpp (original)
+++ branches/release/boost/graph/mcgregor_common_subgraphs.hpp 2009-06-30 13:08:49 EDT (Tue, 30 Jun 2009)
@@ -11,12 +11,10 @@
#define BOOST_GRAPH_MCGREGOR_COMMON_SUBGRAPHS_HPP
#include <algorithm>
-#include <map>
-#include <stack>
-#include <set>
#include <vector>
+#include <stack>
-#include <boost/bind.hpp>
+#include <boost/make_shared.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/graph_utility.hpp>
@@ -28,8 +26,8 @@
namespace detail {
- // Traits associated with common subgraphs, used mainly to
- // keep a consistent type for the correspondence maps.
+ // Traits associated with common subgraphs, used mainly to keep a
+ // consistent type for the correspondence maps.
template <typename GraphFirst,
typename GraphSecond,
typename VertexIndexMapFirst,
@@ -39,18 +37,18 @@
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
// ==========================================================================
- // Binary function object that returns true if the values for
- // vertex1 in property_map1 and vertex2 in property_map2 are equivalent.
+ // Binary function object that returns true if the values for item1
+ // in property_map1 and item2 in property_map2 are equivalent.
template <typename PropertyMapFirst,
typename PropertyMapSecond>
struct property_map_equivalent {
@@ -60,10 +58,10 @@
m_property_map1(property_map1),
m_property_map2(property_map2) { }
- template <typename VertexFirst,
- typename VertexSecond>
- bool operator()(const VertexFirst vertex1, const VertexSecond vertex2) {
- return (get(m_property_map1, vertex1) == get(m_property_map2, vertex2));
+ template <typename ItemFirst,
+ typename ItemSecond>
+ bool operator()(const ItemFirst item1, const ItemSecond item2) {
+ return (get(m_property_map1, item1) == get(m_property_map2, item2));
}
private:
@@ -85,8 +83,8 @@
(property_map1, property_map2));
}
- // Binary function object that always returns true. Used when vertices
- // or edges are always equivalent (i.e. have no labels).
+ // Binary function object that always returns true. Used when
+ // vertices or edges are always equivalent (i.e. have no labels).
struct always_equivalent {
template <typename ItemFirst,
@@ -100,10 +98,11 @@
namespace detail {
- // Return true if new_vertex1 and new_vertex2 can extend the subgraph
- // represented by correspondence_map_1_to_2 and correspondence_map_2_to_1.
- // The vertices_equivalent and edges_equivalent predicates are used to
- // test vertex and edge equivalency between the two graphs.
+ // Return true if new_vertex1 and new_vertex2 can extend the
+ // subgraph represented by correspondence_map_1_to_2 and
+ // correspondence_map_2_to_1. The vertices_equivalent and
+ // edges_equivalent predicates are used to test vertex and edge
+ // equivalency between the two graphs.
template <typename GraphFirst,
typename GraphSecond,
typename CorrespondenceMapFirstToSecond,
@@ -119,7 +118,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;
@@ -149,8 +149,8 @@
continue;
}
- // NOTE: This will not work with parallel edges, since the first
- // matching edge is always chosen.
+ // NOTE: This will not work with parallel edges, since the
+ // first matching edge is always chosen.
EdgeFirst edge_to_new1, edge_from_new1;
bool edge_to_new_exists1 = false, edge_from_new_exists1 = false;
@@ -239,7 +239,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);
}
@@ -248,11 +248,12 @@
// Recursive method that does a depth-first search in the space of
// potential subgraphs. At each level, every new vertex pair from
- // both graphs is tested to see if it can extend the current subgraph.
- // If so, the subgraph is output to subgraph_callback in the form
- // of two correspondence maps (one for each graph).
- // Returning false from subgraph_callback will terminate the search.
- // Function returns true if the entire search space was explored.
+ // both graphs is tested to see if it can extend the current
+ // subgraph. If so, the subgraph is output to subgraph_callback
+ // in the form of two correspondence maps (one for each graph).
+ // Returning false from subgraph_callback will terminate the
+ // search. Function returns true if the entire search space was
+ // explored.
template <typename GraphFirst,
typename GraphSecond,
typename VertexIndexMapFirst,
@@ -273,6 +274,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;
@@ -314,7 +316,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(),
@@ -344,7 +347,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);
@@ -365,7 +368,7 @@
graph_traits<GraphFirst>::null_vertex());
vertex_stack1.pop();
- }
+ }
} // if can_extend_graph
@@ -382,8 +385,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,
@@ -392,6 +395,7 @@
const VertexIndexMapSecond vindex_map2,
EdgeEquivalencePredicate edges_equivalent,
VertexEquivalencePredicate vertices_equivalent,
+ bool only_connected_subgraphs,
SubGraphInternalCallback subgraph_callback)
{
typedef mcgregor_common_subgraph_traits<GraphFirst,
@@ -425,6 +429,7 @@
correspondence_map_1_to_2, correspondence_map_2_to_1,
vertex_stack1,
edges_equivalent, vertices_equivalent,
+ only_connected_subgraphs,
subgraph_callback);
}
@@ -449,6 +454,7 @@
const VertexIndexMapSecond vindex_map2,
EdgeEquivalencePredicate edges_equivalent,
VertexEquivalencePredicate vertices_equivalent,
+ bool only_connected_subgraphs,
SubGraphCallback user_callback)
{
@@ -456,6 +462,7 @@
(graph1, graph2,
vindex_map1, vindex_map2,
edges_equivalent, vertices_equivalent,
+ only_connected_subgraphs,
user_callback);
}
@@ -466,6 +473,7 @@
void mcgregor_common_subgraphs
(const GraphFirst& graph1,
const GraphSecond& graph2,
+ bool only_connected_subgraphs,
SubGraphCallback user_callback)
{
@@ -473,7 +481,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
@@ -486,6 +494,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)
{
@@ -500,7 +509,7 @@
always_equivalent()),
choose_param(get_param(params, vertices_equivalent_t()),
always_equivalent()),
- user_callback);
+ only_connected_subgraphs, user_callback);
}
// ==========================================================================
@@ -508,9 +517,9 @@
namespace detail {
// Binary function object that intercepts subgraphs from
- // mcgregor_common_subgraphs_internal and maintains a cache
- // of unique subgraphs. The user callback is invoked for
- // each unique subgraph.
+ // mcgregor_common_subgraphs_internal and maintains a cache of
+ // unique subgraphs. The user callback is invoked for each unique
+ // subgraph.
template <typename GraphFirst,
typename GraphSecond,
typename VertexIndexMapFirst,
@@ -518,36 +527,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;
@@ -557,11 +573,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
@@ -570,18 +583,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,
@@ -593,7 +613,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;
};
@@ -616,6 +636,7 @@
const VertexIndexMapSecond vindex_map2,
EdgeEquivalencePredicate edges_equivalent,
VertexEquivalencePredicate vertices_equivalent,
+ bool only_connected_subgraphs,
SubGraphCallback user_callback)
{
detail::unique_subgraph_interceptor<GraphFirst, GraphSecond,
@@ -629,23 +650,25 @@
(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 parameters
+ // Variant of mcgregor_common_subgraphs_unique with all default
+ // parameters.
template <typename GraphFirst,
typename GraphSecond,
typename SubGraphCallback>
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
@@ -658,6 +681,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)
{
@@ -671,7 +695,7 @@
always_equivalent()),
choose_param(get_param(params, vertices_equivalent_t()),
always_equivalent()),
- user_callback);
+ only_connected_subgraphs, user_callback);
}
// ==========================================================================
@@ -679,8 +703,8 @@
namespace detail {
// Binary function object that intercepts subgraphs from
- // mcgregor_common_subgraphs_internal and maintains a cache
- // of the largest subgraphs.
+ // mcgregor_common_subgraphs_internal and maintains a cache of the
+ // largest subgraphs.
template <typename GraphFirst,
typename GraphSecond,
typename VertexIndexMapFirst,
@@ -688,63 +712,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;
@@ -753,15 +791,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
@@ -776,13 +814,14 @@
typename EdgeEquivalencePredicate,
typename VertexEquivalencePredicate,
typename SubGraphCallback>
- void mcgregor_maximum_common_subgraphs
+ void mcgregor_common_subgraphs_maximum
(const GraphFirst& graph1,
const GraphSecond& graph2,
const VertexIndexMapFirst vindex_map1,
const VertexIndexMapSecond vindex_map2,
EdgeEquivalencePredicate edges_equivalent,
VertexEquivalencePredicate vertices_equivalent,
+ bool only_connected_subgraphs,
SubGraphCallback user_callback)
{
detail::maximum_subgraph_interceptor<GraphFirst, GraphSecond,
@@ -794,42 +833,45 @@
(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_maximum_common_subgraphs with all default parameters
+ // Variant of mcgregor_common_subgraphs_maximum with all default
+ // parameters.
template <typename GraphFirst,
typename GraphSecond,
typename SubGraphCallback>
- void mcgregor_maximum_common_subgraphs
+ void mcgregor_common_subgraphs_maximum
(const GraphFirst& graph1,
const GraphSecond& graph2,
+ bool only_connected_subgraphs,
SubGraphCallback user_callback)
{
- mcgregor_maximum_common_subgraphs
+ 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_maximum_common_subgraphs
+ // Named parameter variant of mcgregor_common_subgraphs_maximum
template <typename GraphFirst,
typename GraphSecond,
typename SubGraphCallback,
typename Param,
typename Tag,
typename Rest>
- void mcgregor_maximum_common_subgraphs
+ 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)
{
- mcgregor_maximum_common_subgraphs
+ mcgregor_common_subgraphs_maximum
(graph1, graph2,
choose_const_pmap(get_param(params, vertex_index1),
graph1, vertex_index),
@@ -839,7 +881,7 @@
always_equivalent()),
choose_param(get_param(params, vertices_equivalent_t()),
always_equivalent()),
- user_callback);
+ only_connected_subgraphs, user_callback);
}
// ==========================================================================
@@ -847,8 +889,8 @@
namespace detail {
// Binary function object that intercepts subgraphs from
- // mcgregor_common_subgraphs_internal and maintains a cache
- // of the largest, unique subgraphs.
+ // mcgregor_common_subgraphs_internal and maintains a cache of the
+ // largest, unique subgraphs.
template <typename GraphFirst,
typename GraphSecond,
typename VertexIndexMapFirst,
@@ -856,19 +898,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,
@@ -878,33 +923,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
@@ -913,27 +958,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;
@@ -948,16 +1000,16 @@
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
- // Enumerates the largest, unique common subgraphs found between graph1
- // and graph2. Note that the ENTIRE search space is explored before
- // user_callback is actually invoked.
+ // Enumerates the largest, unique common subgraphs found between
+ // graph1 and graph2. Note that the ENTIRE search space is explored
+ // before user_callback is actually invoked.
template <typename GraphFirst,
typename GraphSecond,
typename VertexIndexMapFirst,
@@ -965,13 +1017,14 @@
typename EdgeEquivalencePredicate,
typename VertexEquivalencePredicate,
typename SubGraphCallback>
- void mcgregor_maximum_common_subgraphs_unique
+ void mcgregor_common_subgraphs_maximum_unique
(const GraphFirst& graph1,
const GraphSecond& graph2,
const VertexIndexMapFirst vindex_map1,
const VertexIndexMapSecond vindex_map2,
EdgeEquivalencePredicate edges_equivalent,
VertexEquivalencePredicate vertices_equivalent,
+ bool only_connected_subgraphs,
SubGraphCallback user_callback)
{
detail::unique_maximum_subgraph_interceptor<GraphFirst, GraphSecond,
@@ -983,43 +1036,46 @@
(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_maximum_common_subgraphs_unique with all default parameters
+ // Variant of mcgregor_common_subgraphs_maximum_unique with all default parameters
template <typename GraphFirst,
typename GraphSecond,
typename SubGraphCallback>
- void mcgregor_maximum_common_subgraphs_unique
+ void mcgregor_common_subgraphs_maximum_unique
(const GraphFirst& graph1,
const GraphSecond& graph2,
+ bool only_connected_subgraphs,
SubGraphCallback user_callback)
{
- mcgregor_maximum_common_subgraphs_unique
+ mcgregor_common_subgraphs_maximum_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_maximum_common_subgraphs_unique
+ // Named parameter variant of
+ // mcgregor_common_subgraphs_maximum_unique
template <typename GraphFirst,
typename GraphSecond,
typename SubGraphCallback,
typename Param,
typename Tag,
typename Rest>
- void mcgregor_maximum_common_subgraphs_unique
+ 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)
{
- mcgregor_maximum_common_subgraphs_unique
+ mcgregor_common_subgraphs_maximum_unique
(graph1, graph2,
choose_const_pmap(get_param(params, vertex_index1),
graph1, vertex_index),
@@ -1029,45 +1085,33 @@
always_equivalent()),
choose_param(get_param(params, vertices_equivalent_t()),
always_equivalent()),
- user_callback);
+ only_connected_subgraphs, user_callback);
}
// ==========================================================================
- // Fills two membership maps (vertex -> bool) using the information present
- // in correspondence_map_1_to_2 and correspondence_map_2_to_1. Every vertex in a
- // membership map will have a true value only if it is not associated with
- // a null vertex in its respective correspondence map.
- template <typename GraphFirst,
- typename GraphSecond,
+ // Fills a membership map (vertex -> bool) using the information
+ // present in correspondence_map_1_to_2. Every vertex in a
+ // membership map will have a true value only if it is not
+ // associated with a null vertex in the correspondence map.
+ template <typename GraphSecond,
+ typename GraphFirst,
typename CorrespondenceMapFirstToSecond,
- typename CorrespondenceMapSecondToFirst,
- typename MembershipMapFirst,
- typename MembershipMapSecond>
- void fill_membership_maps
+ typename MembershipMapFirst>
+ void fill_membership_map
(const GraphFirst& graph1,
- const GraphSecond& graph2,
const CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
- const CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
- MembershipMapFirst membership_map1,
- MembershipMapSecond membership_map2) {
-
- typedef typename graph_traits<GraphSecond>::vertex_descriptor
- VertexSecond;
+ MembershipMapFirst membership_map1) {
BGL_FORALL_VERTICES_T(vertex1, graph1, GraphFirst) {
put(membership_map1, vertex1,
get(correspondence_map_1_to_2, vertex1) != graph_traits<GraphSecond>::null_vertex());
}
- BGL_FORALL_VERTICES_T(vertex2, graph2, GraphSecond) {
- put(membership_map2, vertex2,
- get(correspondence_map_2_to_1, vertex2) != graph_traits<GraphFirst>::null_vertex());
- }
}
- // Traits associated with a membership map filtered graph. Provided for
- // convenience to access graph and vertex filter types.
+ // Traits associated with a membership map filtered graph. Provided
+ // for convenience to access graph and vertex filter types.
template <typename Graph,
typename MembershipMap>
struct membership_filtered_graph_traits {
Modified: branches/release/boost/property_map/shared_array_property_map.hpp
==============================================================================
--- branches/release/boost/property_map/shared_array_property_map.hpp (original)
+++ branches/release/boost/property_map/shared_array_property_map.hpp 2009-06-30 13:08:49 EDT (Tue, 30 Jun 2009)
@@ -25,6 +25,8 @@
typedef T& reference;
typedef boost::lvalue_property_map_tag category;
+ inline shared_array_property_map(): data(), index() {}
+
explicit inline shared_array_property_map(
size_t n,
const IndexMap& _id = IndexMap())
Modified: branches/release/libs/graph/doc/compressed_sparse_row.html
==============================================================================
--- branches/release/libs/graph/doc/compressed_sparse_row.html (original)
+++ branches/release/libs/graph/doc/compressed_sparse_row.html 2009-06-30 13:08:49 EDT (Tue, 30 Jun 2009)
@@ -294,6 +294,14 @@
template<typename InputIterator, typename Graph>
void add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph& g);
+<b>(new interface only)</b>
+template<typename BidirectionalIterator, typename Graph>
+void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, compressed_sparse_row_graph& g);
+
+<b>(new interface only)</b>
+template<typename BidirectionalIterator, typename EPIter, typename Graph>
+void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, EPIter ep_iter, compressed_sparse_row_graph& g);
+
} <i>// end namespace boost</i>
</pre>
@@ -918,7 +926,7 @@
<pre><a name="add_edges"></a>
template<typename InputIterator>
-edge_descriptor add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph& g)
+void add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph& g)
</pre>
<p class="indent">
@@ -932,6 +940,47 @@
</p>
<hr></hr>
+
+ <pre><a name="add_edges_sorted"></a>
+template<typename BidirectionalIterator>
+void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, compressed_sparse_row_graph& g)
+ </pre>
+
+ <p class="indent">
+ Add a range of edges (from <tt>first</tt> to <tt>last</tt>) to the graph.
+ The <tt>BidirectionalIterator</tt> must be a model of <a
+ href="http://www.sgi.com/tech/stl/BidirectionalIterator.html">BidirectionalIterator</a>
+ whose <code>value_type</code> is an <code>std::pair</code> of integer
+ values. These integer values are the source and target vertices of the
+ new edges. The edges must be sorted in increasing order by source vertex
+ index.
+ <b>(This function is only provided by the new interface.)</b>
+ </p>
+
+ <hr></hr>
+
+ <pre><a name="add_edges_sorted_prop"></a>
+template<typename BidirectionalIterator, typename EPIter>
+void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, EPIter ep_iter, compressed_sparse_row_graph& g)
+ </pre>
+
+ <p class="indent">
+ Add a range of edges (from <tt>first</tt> to <tt>last</tt>) to the graph.
+ The <tt>BidirectionalIterator</tt> and <tt>EPIter</tt> must be models of
+ <a
+ href="http://www.sgi.com/tech/stl/BidirectionalIterator.html">BidirectionalIterator</a>.
+ The <code>value_type</code> of the <tt>BidirectionalIterator</tt> must be
+ an <code>std::pair</code> of integer
+ values. These integer values are the source and target vertices of the
+ new edges.
+ The <code>value_type</code> of the <tt>EPIter</tt> must be the edge
+ property type of the graph.
+ The edges must be sorted in increasing order by source vertex
+ index.
+ <b>(This function is only provided by the new interface.)</b>
+ </p>
+
+ <hr></hr>
<a name="example"></a><h2>Example</h2>
<br>[<a
Modified: branches/release/libs/graph/doc/table_of_contents.html
==============================================================================
--- branches/release/libs/graph/doc/table_of_contents.html (original)
+++ branches/release/libs/graph/doc/table_of_contents.html 2009-06-30 13:08:49 EDT (Tue, 30 Jun 2009)
@@ -245,6 +245,7 @@
<tt>make_maximal_planar</tt></a>
</ol>
<li>lengauer_tarjan_dominator_tree</li>
+ <li>mcgregor_common_subgraphs</li>
</OL>
</OL>
Modified: branches/release/libs/graph/example/Jamfile.v2
==============================================================================
--- branches/release/libs/graph/example/Jamfile.v2 (original)
+++ branches/release/libs/graph/example/Jamfile.v2 2009-06-30 13:08:49 EDT (Tue, 30 Jun 2009)
@@ -18,3 +18,4 @@
exe tiernan_girth_circumference : tiernan_girth_circumference.cpp ;
exe bron_kerbosch_print_cliques : bron_kerbosch_print_cliques.cpp ;
exe bron_kerbosch_clique_number : bron_kerbosch_clique_number.cpp ;
+exe mcgregor_subgraphs_example : mcgregor_subgraphs_example.cpp ;
Modified: branches/release/libs/graph/test/CMakeLists.txt
==============================================================================
--- branches/release/libs/graph/test/CMakeLists.txt (original)
+++ branches/release/libs/graph/test/CMakeLists.txt 2009-06-30 13:08:49 EDT (Tue, 30 Jun 2009)
@@ -47,6 +47,7 @@
boost_test_run(cuthill_mckee_ordering)
boost_test_run(king_ordering)
boost_test_run(matching_test)
+boost_test_run(mcgregor_subgraphs_test)
# boost_test_run(max_flow_test)
# boost_test_run(kolmogorov_max_flow_test) TODO: Boost 1.34.x only
Modified: branches/release/libs/graph/test/Jamfile.v2
==============================================================================
--- branches/release/libs/graph/test/Jamfile.v2 (original)
+++ branches/release/libs/graph/test/Jamfile.v2 2009-06-30 13:08:49 EDT (Tue, 30 Jun 2009)
@@ -118,6 +118,7 @@
[ run clustering_coefficient.cpp ]
[ run core_numbers_test.cpp ]
[ run read_propmap.cpp ]
+ [ run mcgregor_subgraphs_test.cpp ]
$(optional_tests)
;
Copied: branches/release/libs/graph/test/mcgregor_subgraphs_test.cpp (from r54216, /trunk/libs/graph/test/mcgregor_subgraphs_test.cpp)
==============================================================================
--- /trunk/libs/graph/test/mcgregor_subgraphs_test.cpp (original)
+++ branches/release/libs/graph/test/mcgregor_subgraphs_test.cpp 2009-06-30 13:08:49 EDT (Tue, 30 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.
@@ -57,9 +69,8 @@
MembershipMap membership_map2(num_vertices(m_graph2),
get(vertex_index, m_graph2));
- fill_membership_maps(m_graph1, m_graph2,
- correspondence_map_1_to_2, correspondence_map_2_to_1,
- membership_map1, membership_map2);
+ fill_membership_map<Graph>(m_graph1, correspondence_map_1_to_2, membership_map1);
+ fill_membership_map<Graph>(m_graph2, correspondence_map_2_to_1, membership_map2);
// Generate filtered graphs using membership maps
typedef typename membership_filtered_graph_traits<Graph, MembershipMap>::graph_type
@@ -172,6 +183,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,
@@ -199,8 +250,8 @@
v_iter != new_vertices.end(); ++v_iter) {
Vertex source_vertex = *v_iter;
- int edges_for_vertex = std::min((generator() % max_edges_per_vertex) + 1,
- (int)num_vertices(graph));
+ int edges_for_vertex = (std::min)((int)(generator() % max_edges_per_vertex) + 1,
+ (int)num_vertices(graph));
while (edges_for_vertex > 0) {
@@ -224,6 +275,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 +382,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;
}