Subject: [Boost-commit] svn:boost r54386 - in trunk/boost/graph: . detail
From: jewillco_at_[hidden]
Date: 2009-06-26 19:06:39
Author: jewillco
Date: 2009-06-26 19:06:38 EDT (Fri, 26 Jun 2009)
New Revision: 54386
URL: http://svn.boost.org/trac/boost/changeset/54386
Log:
Added global, filtered CSR constructors from sorted edge sets
Text files modified:
trunk/boost/graph/compressed_sparse_row_graph.hpp | 207 ++++++++++++++++++++++-----------------
trunk/boost/graph/detail/indexed_properties.hpp | 14 ++
2 files changed, 130 insertions(+), 91 deletions(-)
Modified: trunk/boost/graph/compressed_sparse_row_graph.hpp
==============================================================================
--- trunk/boost/graph/compressed_sparse_row_graph.hpp (original)
+++ trunk/boost/graph/compressed_sparse_row_graph.hpp 2009-06-26 19:06:38 EDT (Fri, 26 Jun 2009)
@@ -65,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
@@ -434,6 +439,73 @@
}
#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
@@ -443,8 +515,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
@@ -452,29 +523,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
@@ -485,8 +536,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
@@ -494,27 +544,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);
+ numedges = detail::reserve_count_for_single_pass(edge_begin, edge_end);
}
-
- 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;
- }
-
- // 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
@@ -526,8 +558,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
@@ -538,29 +569,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)
@@ -571,8 +582,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
@@ -583,30 +593,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.
Modified: trunk/boost/graph/detail/indexed_properties.hpp
==============================================================================
--- trunk/boost/graph/detail/indexed_properties.hpp (original)
+++ trunk/boost/graph/detail/indexed_properties.hpp 2009-06-26 19:06:38 EDT (Fri, 26 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) { }
};
@@ -133,6 +140,12 @@
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)
{
@@ -195,6 +208,7 @@
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) { }