|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r56116 - in trunk: boost/graph boost/graph/detail boost/graph/distributed libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-09-08 18:55:06
Author: jewillco
Date: 2009-09-08 18:55:05 EDT (Tue, 08 Sep 2009)
New Revision: 56116
URL: http://svn.boost.org/trac/boost/changeset/56116
Log:
Refactored CSR graph code to get ready for bidirectional support
Added:
trunk/boost/graph/detail/compressed_sparse_row_struct.hpp (contents, props changed)
trunk/boost/graph/detail/histogram_sort.hpp (contents, props changed)
Text files modified:
trunk/boost/graph/compressed_sparse_row_graph.hpp | 751 ++++++++-------------------------------
trunk/boost/graph/distributed/compressed_sparse_row_graph.hpp | 105 +++--
trunk/libs/graph/test/csr_graph_test.cpp | 12
3 files changed, 233 insertions(+), 635 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-09-08 18:55:05 EDT (Tue, 08 Sep 2009)
@@ -26,6 +26,7 @@
#include <boost/graph/properties.hpp>
#include <boost/graph/filtered_graph.hpp> // For keep_all
#include <boost/graph/detail/indexed_properties.hpp>
+#include <boost/graph/detail/compressed_sparse_row_struct.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/iterator/counting_iterator.hpp>
#include <boost/iterator/reverse_iterator.hpp>
@@ -133,41 +134,8 @@
compressed_sparse_row_graph<Directed, VertexProperty, EdgeProperty, \
GraphProperty, Vertex, EdgeIndex>
-// Forward declaration of CSR edge descriptor type, needed to pass to
-// indexed_edge_properties.
-template<typename Vertex, typename EdgeIndex>
-class csr_edge_descriptor;
-
-namespace detail {
- template<typename InputIterator>
- size_t
- reserve_count_for_single_pass_helper(InputIterator, InputIterator,
- std::input_iterator_tag)
- {
- // Do nothing: we have no idea how much storage to reserve.
- return 0;
- }
-
- template<typename InputIterator>
- size_t
- reserve_count_for_single_pass_helper(InputIterator first, InputIterator last,
- std::random_access_iterator_tag)
- {
- using std::distance;
- typename std::iterator_traits<InputIterator>::difference_type n =
- distance(first, last);
- return (size_t)n;
- }
-
- template<typename InputIterator>
- size_t
- reserve_count_for_single_pass(InputIterator first, InputIterator last) {
- typedef typename std::iterator_traits<InputIterator>::iterator_category
- category;
- return reserve_count_for_single_pass_helper(first, last, category());
- }
-
#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+namespace detail {
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;
@@ -198,8 +166,8 @@
return t.template get<N>();
}
};
-#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
}
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
/** Compressed sparse row graph.
*
@@ -214,10 +182,7 @@
typename EdgeIndex = Vertex>
class compressed_sparse_row_graph
: public detail::indexed_vertex_properties<BOOST_CSR_GRAPH_TYPE, VertexProperty,
- Vertex>,
- public detail::indexed_edge_properties<BOOST_CSR_GRAPH_TYPE, EdgeProperty,
- csr_edge_descriptor<Vertex,
- EdgeIndex> >
+ Vertex>
{
public:
@@ -225,34 +190,11 @@
VertexProperty, Vertex>
inherited_vertex_properties;
- typedef detail::indexed_edge_properties<BOOST_CSR_GRAPH_TYPE, EdgeProperty,
- csr_edge_descriptor<Vertex, EdgeIndex> >
- inherited_edge_properties;
-
public:
// For Property Graph
typedef GraphProperty graph_property_type;
- protected:
- template<typename InputIterator>
- void
- maybe_reserve_edge_list_storage(InputIterator, InputIterator,
- std::input_iterator_tag)
- {
- // Do nothing: we have no idea how much storage to reserve.
- }
-
- template<typename InputIterator>
- void
- maybe_reserve_edge_list_storage(InputIterator first, InputIterator last,
- std::forward_iterator_tag)
- {
- using std::distance;
- typename std::iterator_traits<InputIterator>::difference_type n =
- distance(first, last);
- m_column.reserve(n);
- inherited_edge_properties::reserve(n);
- }
+ typedef detail::compressed_sparse_row_structure<EdgeProperty, Vertex, EdgeIndex> forward_type;
public:
/* At this time, the compressed sparse row graph can only be used to
@@ -298,108 +240,44 @@
// For internal use
typedef csr_graph_tag graph_tag;
+ typedef typename forward_type::inherited_edge_properties::edge_bundled edge_bundled;
+ typedef typename forward_type::inherited_edge_properties::edge_push_back_type edge_push_back_type;
+ typedef typename forward_type::inherited_edge_properties::edge_property_type edge_property_type;
+
// Constructors
// Default constructor: an empty graph.
- compressed_sparse_row_graph()
- : m_rowstart(1, EdgeIndex(0)), m_column(0), m_property()
-#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- , m_last_source(0)
-#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- {}
+ compressed_sparse_row_graph(): m_property() {}
// With numverts vertices
compressed_sparse_row_graph(vertices_size_type numverts)
- : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
- m_column(0)
-#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- , m_last_source(numverts)
-#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- {
- for (Vertex v = 0; v < numverts + 1; ++v)
- m_rowstart[v] = 0;
- }
+ : inherited_vertex_properties(numverts), m_forward(numverts) {}
#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// Rebuild graph from number of vertices and multi-pass unsorted list of
- // edges (filtered using edge_pred and mapped using global_to_local)
- template <typename MultiPassInputIterator, typename GlobalToLocal, typename EdgePred>
+ // edges (filtered using source_pred and mapped using global_to_local)
+ template <typename MultiPassInputIterator, typename GlobalToLocal, typename SourcePred>
void
assign_unsorted_multi_pass_edges(MultiPassInputIterator edge_begin,
MultiPassInputIterator edge_end,
vertices_size_type numlocalverts,
const GlobalToLocal& global_to_local,
- const EdgePred& edge_pred) {
- m_rowstart.clear();
- 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[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 <= numlocalverts; ++i) {
- start_of_this_row += m_rowstart[i];
- m_rowstart[i] = start_of_this_row;
- }
- m_column.resize(m_rowstart.back());
-
- // Histogram sort the edges by their source vertices, putting the targets
- // 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() + numlocalverts);
- for (; edge_begin != edge_end; ++edge_begin)
- if (edge_pred(*edge_begin))
- m_column[current_insert_positions[get(global_to_local, edge_begin->first)]++] = edge_begin->second;
+ const SourcePred& source_pred) {
+ m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numlocalverts, global_to_local, source_pred);
}
// Rebuild graph from number of vertices and multi-pass unsorted list of
- // edges and their properties (filtered using edge_pred and mapped using
+ // edges and their properties (filtered using source_pred and mapped using
// global_to_local)
- template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename EdgePred>
+ template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred>
void
assign_unsorted_multi_pass_edges(MultiPassInputIterator edge_begin,
MultiPassInputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numlocalverts,
const GlobalToLocal& global_to_local,
- const EdgePred& edge_pred) {
- m_rowstart.clear();
- 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[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 <= numlocalverts; ++i) {
- start_of_this_row += m_rowstart[i];
- m_rowstart[i] = start_of_this_row;
- }
- m_column.resize(m_rowstart.back());
- inherited_edge_properties::resize(m_rowstart.back());
-
- // Histogram sort the edges by their source vertices, putting the targets
- // 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() + numlocalverts);
- for (; edge_begin != edge_end; ++edge_begin, ++ep_iter) {
- if (edge_pred(*edge_begin)) {
- 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;
- inherited_edge_properties::write_by_index(insert_pos, *ep_iter);
- }
- }
+ const SourcePred& source_pred) {
+ m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numlocalverts, global_to_local, source_pred);
}
// From number of vertices and unsorted list of edges
@@ -409,13 +287,9 @@
MultiPassInputIterator edge_end,
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numverts), m_rowstart(),
- m_column(0), m_property(prop)
+ : inherited_vertex_properties(numverts), m_property(prop)
{
- 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());
+ m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numverts, identity_property_map(), keep_all());
}
// From number of vertices and unsorted list of edges, plus edge properties
@@ -426,114 +300,66 @@
EdgePropertyIterator ep_iter,
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numverts), m_rowstart(),
- m_column(0), m_property(prop)
+ : inherited_vertex_properties(numverts), m_forward(), m_property(prop)
{
- assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numverts, identity_property_map(), keep_all());
+ m_forward.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 and
// global-to-local map
- template <typename MultiPassInputIterator, typename GlobalToLocal, typename EdgePred>
+ template <typename MultiPassInputIterator, typename GlobalToLocal, typename SourcePred>
compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
MultiPassInputIterator edge_begin,
MultiPassInputIterator edge_end,
vertices_size_type numlocalverts,
const GlobalToLocal& global_to_local,
- const EdgePred& edge_pred,
+ const SourcePred& source_pred,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numlocalverts), m_rowstart(),
- m_column(0), m_property(prop)
+ : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop)
{
- 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());
+ m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numlocalverts, global_to_local, source_pred);
}
// 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>
+ template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred>
compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
MultiPassInputIterator edge_begin,
MultiPassInputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numlocalverts,
const GlobalToLocal& global_to_local,
- const EdgePred& edge_pred,
+ const SourcePred& source_pred,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numlocalverts), m_rowstart(),
- m_column(0), m_property(prop)
+ : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop)
{
- assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numlocalverts, global_to_local, edge_pred);
+ m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numlocalverts, global_to_local, source_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>
+ template<typename InputIterator, typename GlobalToLocal, typename SourcePred>
void assign_from_sorted_edges(
InputIterator edge_begin, InputIterator edge_end,
const GlobalToLocal& global_to_local,
- const EdgePred& edge_pred,
+ const SourcePred& source_pred,
vertices_size_type numlocalverts,
edges_size_type numedges_or_zero) {
- m_column.clear();
- m_column.reserve(numedges_or_zero);
+ m_forward.assign_from_sorted_edges(edge_begin, edge_end, global_to_local, source_pred, numlocalverts, 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>
+ template<typename InputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred>
void assign_from_sorted_edges(
InputIterator edge_begin, InputIterator edge_end,
EdgePropertyIterator ep_iter,
const GlobalToLocal& global_to_local,
- const EdgePred& edge_pred,
+ const SourcePred& source_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);
+ m_forward.assign_from_sorted_edges(edge_begin, edge_end, ep_iter, global_to_local, source_pred, numlocalverts, 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
@@ -545,17 +371,10 @@
vertices_size_type numverts,
edges_size_type numedges = 0,
const GraphProperty& prop = GraphProperty())
- : m_property(prop), m_last_source(numverts)
+ : m_property(prop)
{
- // Reserving storage in advance can save us lots of time and
- // memory, but it can only be done if we have forward iterators or
- // the user has supplied the number of edges.
- if (numedges == 0) {
- typedef typename std::iterator_traits<InputIterator>::iterator_category
- category;
- numedges = detail::reserve_count_for_single_pass(edge_begin, edge_end);
- }
- assign_from_sorted_edges(edge_begin, edge_end, identity_property_map(), keep_all(), numverts, numedges);
+ m_forward.assign_from_sorted_edges(edge_begin, edge_end, identity_property_map(), keep_all(), numverts, numedges);
+ inherited_vertex_properties::resize(numlocalverts);
}
// From number of vertices and sorted list of edges (deprecated
@@ -566,17 +385,10 @@
vertices_size_type numverts,
edges_size_type numedges = 0,
const GraphProperty& prop = GraphProperty())
- : m_property(prop), m_last_source(numverts)
+ : m_property(prop)
{
- // Reserving storage in advance can save us lots of time and
- // memory, but it can only be done if we have forward iterators or
- // the user has supplied the number of edges.
- if (numedges == 0) {
- typedef typename std::iterator_traits<InputIterator>::iterator_category
- category;
- 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);
+ m_forward.assign_from_sorted_edges(edge_begin, edge_end, ep_iter, identity_property_map(), keep_all(), numverts, numedges);
+ inherited_vertex_properties::resize(numlocalverts);
}
#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
@@ -589,19 +401,9 @@
edges_size_type numedges = 0,
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
{
- // Reserving storage in advance can save us lots of time and
- // memory, but it can only be done if we have forward iterators or
- // the user has supplied the number of edges.
- if (numedges == 0) {
- typedef typename std::iterator_traits<InputIterator>::iterator_category
- category;
- numedges = detail::reserve_count_for_single_pass(edge_begin, edge_end);
- }
- assign_from_sorted_edges(edge_begin, edge_end, identity_property_map(), keep_all(), numverts, numedges);
+ m_forward.assign_from_sorted_edges(edge_begin, edge_end, identity_property_map(), keep_all(), numverts, numedges);
+ inherited_vertex_properties::resize(numverts);
}
// From number of vertices and sorted list of edges (new interface)
@@ -613,53 +415,39 @@
edges_size_type numedges = 0,
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
{
- // Reserving storage in advance can save us lots of time and
- // memory, but it can only be done if we have forward iterators or
- // the user has supplied the number of edges.
- if (numedges == 0) {
- typedef typename std::iterator_traits<InputIterator>::iterator_category
- category;
- 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);
+ m_forward.assign_from_sorted_edges(edge_begin, edge_end, ep_iter, identity_property_map(), keep_all(), numverts, numedges);
+ inherited_vertex_properties::resize(numverts);
}
#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>
+ template<typename InputIterator, typename GlobalToLocal, typename SourcePred>
compressed_sparse_row_graph(edges_are_sorted_global_t,
InputIterator edge_begin, InputIterator edge_end,
const GlobalToLocal& global_to_local,
- const EdgePred& edge_pred,
+ const SourcePred& source_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);
+ m_forward.assign_from_sorted_edges(edge_begin, edge_end, global_to_local, source_pred, numverts, 0);
+ inherited_vertex_properties::resize(numverts);
}
// From number of vertices and sorted list of edges (new interface)
- template<typename InputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename EdgePred>
+ template<typename InputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred>
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,
+ const SourcePred& source_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);
+ m_forward.assign_from_sorted_edges(edge_begin, edge_end, ep_iter, global_to_local, source_pred, numverts, 0);
+ inherited_vertex_properties::resize(numverts);
}
// From number of vertices and mutable vectors of sources and targets;
@@ -670,10 +458,9 @@
std::vector<vertex_descriptor>& targets,
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numverts), m_rowstart(),
- m_column(), m_property(prop)
+ : inherited_vertex_properties(numverts), m_property(prop)
{
- assign_sources_and_targets_global(sources, targets, numverts, boost::identity_property_map());
+ m_forward.assign_sources_and_targets_global(sources, targets, numverts, boost::identity_property_map());
}
// From number of vertices and mutable vectors of sources and targets,
@@ -688,10 +475,9 @@
vertices_size_type numlocalverts,
GlobalToLocal global_to_local,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numlocalverts), m_rowstart(),
- m_column(), m_property(prop)
+ : inherited_vertex_properties(numlocalverts), m_property(prop)
{
- assign_sources_and_targets_global(sources, targets, numlocalverts, global_to_local);
+ m_forward.assign_sources_and_targets_global(sources, targets, numlocalverts, global_to_local);
}
// From number of vertices and mutable vectors of sources, targets, and edge
@@ -700,13 +486,12 @@
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_bundled>& edge_props,
+ std::vector<typename forward_type::inherited_edge_properties::edge_bundled>& edge_props,
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numverts), m_rowstart(),
- m_column(), m_property(prop)
+ : inherited_vertex_properties(numverts), m_property(prop)
{
- assign_sources_and_targets_global(sources, targets, edge_props, numverts, boost::identity_property_map());
+ m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numverts, boost::identity_property_map());
}
// From number of vertices and mutable vectors of sources and targets and
@@ -718,14 +503,13 @@
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_bundled>& edge_props,
+ std::vector<typename forward_type::inherited_edge_properties::edge_bundled>& edge_props,
vertices_size_type numlocalverts,
GlobalToLocal global_to_local,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numlocalverts), m_rowstart(),
- m_column(), m_property(prop)
+ : inherited_vertex_properties(numlocalverts), m_property(prop)
{
- assign_sources_and_targets_global(sources, targets, edge_props, numlocalverts, global_to_local);
+ m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numlocalverts, global_to_local);
}
// From number of vertices and single-pass range of unsorted edges. Data is
@@ -735,18 +519,11 @@
InputIterator edge_begin, InputIterator edge_end,
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numverts), m_rowstart(),
- m_column(), m_property(prop)
+ : inherited_vertex_properties(numverts), m_property(prop)
{
std::vector<vertex_descriptor> sources, targets;
- size_t reserve_size
- = detail::reserve_count_for_single_pass(edge_begin, edge_end);
- sources.reserve(reserve_size);
- targets.reserve(reserve_size);
- for (; edge_begin != edge_end; ++edge_begin) {
- sources.push_back(edge_begin->first);
- targets.push_back(edge_begin->second);
- }
+ boost::graph::detail::split_into_separate_coords
+ (edge_begin, edge_end, sources, targets);
assign_sources_and_targets_global(sources, targets, numverts, boost::identity_property_map());
}
@@ -759,45 +536,35 @@
EdgePropertyIterator ep_iter,
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numverts), m_rowstart(),
- m_column(), m_property(prop)
+ : inherited_vertex_properties(numverts), m_property(prop)
{
std::vector<vertex_descriptor> sources, targets;
- 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);
- targets.reserve(reserve_size);
- edge_props.reserve(reserve_size);
- for (; edge_begin != edge_end; ++edge_begin, ++ep_iter) {
- sources.push_back(edge_begin->first);
- targets.push_back(edge_begin->second);
- edge_props.push_back(*ep_iter);
+ boost::graph::detail::split_into_separate_coords
+ (edge_begin, edge_end, sources, targets);
+ size_t numedges = sources.size();
+ std::vector<typename forward_type::inherited_edge_properties::edge_bundled> edge_props(numedges);
+ for (size_t i = 0; i < numedges; ++i) {
+ edge_props[i] = *ep_iter++;
}
- assign_sources_and_targets_global(sources, targets, edge_props, numverts, boost::identity_property_map());
+ m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numverts, boost::identity_property_map());
}
// From number of vertices and single-pass range of unsorted edges. Data is
// 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>
+ template<typename InputIterator, typename GlobalToLocal, typename SourcePred>
compressed_sparse_row_graph(edges_are_unsorted_global_t,
InputIterator edge_begin, InputIterator edge_end,
vertices_size_type numlocalverts,
GlobalToLocal global_to_local,
- const EdgePred& edge_pred,
+ const SourcePred& source_pred,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numlocalverts), m_rowstart(),
- m_column(), m_property(prop)
+ : inherited_vertex_properties(numlocalverts), m_property(prop)
{
std::vector<vertex_descriptor> sources, targets;
- for (; edge_begin != edge_end; ++edge_begin) {
- if (edge_pred(*edge_begin)) {
- sources.push_back(edge_begin->first);
- targets.push_back(edge_begin->second);
- }
- }
- assign_sources_and_targets_global(sources, targets, numlocalverts, global_to_local);
+ boost::graph::detail::split_into_separate_coords_filtered
+ (edge_begin, edge_end, sources, targets, source_pred);
+ m_forward.assign_sources_and_targets_global(sources, targets, numlocalverts, global_to_local);
}
// From number of vertices and single-pass range of unsorted edges and
@@ -805,27 +572,21 @@
// before creating the actual graph. Edges are filtered and transformed for
// use in a distributed graph.
template<typename InputIterator, typename EdgePropertyIterator,
- typename GlobalToLocal, typename EdgePred>
+ typename GlobalToLocal, typename SourcePred>
compressed_sparse_row_graph(edges_are_unsorted_global_t,
InputIterator edge_begin, InputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numlocalverts,
GlobalToLocal global_to_local,
- const EdgePred& edge_pred,
+ const SourcePred& source_pred,
const GraphProperty& prop = GraphProperty())
- : inherited_vertex_properties(numlocalverts), m_rowstart(),
- m_column(), m_property(prop)
+ : inherited_vertex_properties(numlocalverts), m_property(prop)
{
std::vector<vertex_descriptor> sources, targets;
- 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);
- targets.push_back(edge_begin->second);
- edge_props.push_back(*ep_iter);
- }
- }
- assign_sources_and_targets_global(sources, targets, edge_props, numlocalverts, global_to_local);
+ std::vector<edge_bundled> edge_props;
+ boost::graph::detail::split_into_separate_coords_filtered
+ (edge_begin, edge_end, ep_iter, sources, targets, edge_props, source_pred);
+ m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numlocalverts, global_to_local);
}
// Replace graph with sources and targets given, sorting them in-place, and
@@ -836,55 +597,7 @@
std::vector<vertex_descriptor>& targets,
vertices_size_type numverts,
GlobalToLocal global_to_local) {
- assert (sources.size() == targets.size());
- typedef typename std::vector<vertex_descriptor>::iterator vertex_vec_iter;
- EdgeIndex numedges = sources.size();
-#if 0
- std::cerr << "Edges before:";
- for (size_t i = 0; i < numedges; ++i) {
- std::cerr << " (" << sources[i] << " -> " << targets[i] << ")";
- }
- std::cerr << std::endl;
-#endif
- // Do an in-place histogram sort (at least that's what I think it is) to
- // sort sources and targets
- // 1. Count degrees; degree of vertex v is in m_rowstart[v + 1]
- 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
- for (size_t i = 0; i < numverts; ++i) {
- m_rowstart[i + 1] += m_rowstart[i];
- }
- // 3. Copy m_rowstart (except last element) to get insert positions
- std::vector<EdgeIndex> insert_positions(m_rowstart.begin(), boost::prior(m_rowstart.end()));
- // 4. Swap the sources and targets into place
- for (size_t i = 0; i < numedges; ++i) {
- // While edge i is not in the right bucket:
- while (!(i >= m_rowstart[get(global_to_local, sources[i])] && i < insert_positions[get(global_to_local, sources[i])])) {
- // Add a slot in the right bucket
- size_t target_pos = insert_positions[get(global_to_local, sources[i])]++;
- assert (target_pos < m_rowstart[get(global_to_local, sources[i]) + 1]);
- if (target_pos == i) continue;
- // Swap this edge into place
- using std::swap;
- swap(sources[i], sources[target_pos]);
- swap(targets[i], targets[target_pos]);
- }
- }
-#if 0
- std::cerr << "Edges after:";
- for (size_t i = 0; i < sources.size(); ++i) {
- std::cerr << " (" << sources[i] << " -> " << targets[i] << ")";
- }
- std::cerr << std::endl;
-#endif
- // Now targets is the correct vector (properly sorted by source) for
- // m_column
- m_column.swap(targets);
+ m_forward.assign_sources_and_targets_global(sources, targets, numverts, global_to_local);
}
// Replace graph with sources and targets and edge properties given, sorting
@@ -893,59 +606,10 @@
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_bundled>& edge_props,
+ std::vector<edge_bundled>& edge_props,
vertices_size_type numverts,
GlobalToLocal global_to_local) {
- assert (sources.size() == targets.size());
- assert (sources.size() == edge_props.size());
- EdgeIndex numedges = sources.size();
-#if 0
- std::cerr << "Edges before:";
- for (size_t i = 0; i < numedges; ++i) {
- std::cerr << " (" << sources[i] << " -> " << targets[i] << ")";
- }
- std::cerr << std::endl;
-#endif
- // Do an in-place histogram sort (at least that's what I think it is) to
- // sort sources and targets
- // 1. Count degrees; degree of vertex v is in m_rowstart[v + 1]
- m_rowstart.clear();
- m_rowstart.resize(numverts + 1);
- for (size_t i = 0; i < numedges; ++i) {
- ++m_rowstart[get(global_to_local, sources[i]) + 1];
- }
- // 2. Do a prefix sum on those to get starting positions of each row
- for (size_t i = 0; i < numverts; ++i) {
- m_rowstart[i + 1] += m_rowstart[i];
- }
- // 3. Copy m_rowstart (except last element) to get insert positions
- std::vector<EdgeIndex> insert_positions(m_rowstart.begin(), boost::prior(m_rowstart.end()));
- // 4. Swap the sources and targets into place
- for (size_t i = 0; i < numedges; ++i) {
- // While edge i is not in the right bucket:
- while (!(i >= m_rowstart[get(global_to_local, sources[i])] && i < insert_positions[get(global_to_local, sources[i])])) {
- // Add a slot in the right bucket
- size_t target_pos = insert_positions[get(global_to_local, sources[i])]++;
- assert (target_pos < m_rowstart[get(global_to_local, sources[i]) + 1]);
- if (target_pos == i) continue;
- // Swap this edge into place
- using std::swap;
- swap(sources[i], sources[target_pos]);
- swap(targets[i], targets[target_pos]);
- swap(edge_props[i], edge_props[target_pos]);
- }
- }
-#if 0
- std::cerr << "Edges after:";
- for (size_t i = 0; i < sources.size(); ++i) {
- std::cerr << " (" << sources[i] << " -> " << targets[i] << ")";
- }
- std::cerr << std::endl;
-#endif
- // Now targets is the correct vector (properly sorted by source) for
- // m_column, and edge_props for m_edge_properties
- m_column.swap(targets);
- this->m_edge_properties.swap(edge_props);
+ m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numverts, global_to_local);
}
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
@@ -959,6 +623,7 @@
: m_property()
{
assign(g, vi, numverts, numedges);
+ inherited_vertex_properties::resize(numverts);
}
// Requires VertexListGraph and EdgeListGraph
@@ -970,7 +635,9 @@
if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
numedges *= 2; // Double each edge (actual doubling done by out_edges function)
}
- assign(g, vi, num_vertices(g), numedges);
+ vertices_size_type numverts = num_vertices(g);
+ assign(g, vi, numverts, numedges);
+ inherited_vertex_properties::resize(numverts);
}
// Requires vertex index map plus requirements of previous constructor
@@ -994,40 +661,8 @@
assign(const Graph& g, const VertexIndexMap& vi,
vertices_size_type numverts, edges_size_type numedges)
{
+ m_forward.assign(g, vi, numverts, numedges);
inherited_vertex_properties::resize(numverts);
- m_rowstart.resize(numverts + 1);
- m_column.resize(numedges);
- EdgeIndex current_edge = 0;
- typedef typename boost::graph_traits<Graph>::vertex_descriptor g_vertex;
- typedef typename boost::graph_traits<Graph>::edge_descriptor g_edge;
- typedef typename boost::graph_traits<Graph>::out_edge_iterator
- g_out_edge_iter;
-
- std::vector<g_vertex> ordered_verts_of_g(numverts);
- BGL_FORALL_VERTICES_T(v, g, Graph) {
- ordered_verts_of_g[get(vertex_index, g, v)] = v;
- }
- for (Vertex i = 0; i != numverts; ++i) {
- m_rowstart[i] = current_edge;
- g_vertex v = ordered_verts_of_g[i];
-#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- // Out edges in a single vertex are only sorted for the old interface
- EdgeIndex num_edges_before_this_vertex = current_edge;
-#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- g_out_edge_iter ei, ei_end;
- for (tie(ei, ei_end) = out_edges(v, g); ei != ei_end; ++ei) {
- m_column[current_edge++] = get(vi, target(*ei, g));
- }
-#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- // Out edges in a single vertex are only sorted for the old interface
- std::sort(m_column.begin() + num_edges_before_this_vertex,
- m_column.begin() + current_edge);
-#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- }
- m_rowstart[numverts] = current_edge;
-#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- m_last_source = numverts;
-#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
}
// Requires the above, plus VertexListGraph and EdgeListGraph
@@ -1038,7 +673,9 @@
if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
numedges *= 2; // Double each edge (actual doubling done by out_edges function)
}
- assign(g, vi, num_vertices(g), numedges);
+ vertices_size_type numverts = num_vertices(g);
+ m_forward.assign(g, vi, numverts, numedges);
+ inherited_vertex_properties::resize(numverts);
}
// Requires the above, plus a vertex_index map.
@@ -1049,7 +686,9 @@
if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
numedges *= 2; // Double each edge (actual doubling done by out_edges function)
}
- assign(g, get(vertex_index, g), num_vertices(g), numedges);
+ vertices_size_type numverts = num_vertices(g);
+ m_forward.assign(g, get(vertex_index, g), numverts, numedges);
+ inherited_vertex_properties::resize(numverts);
}
#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
@@ -1063,66 +702,7 @@
BidirectionalIteratorOrig last_sorted,
EPIterOrig ep_iter_sorted,
const GlobalToLocal& global_to_local) {
- 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 (get(global_to_local, 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;
- --temp_prop;
- 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)
- }
+ m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, global_to_local);
}
template <typename BidirectionalIteratorOrig, typename EPIterOrig>
@@ -1131,8 +711,7 @@
BidirectionalIteratorOrig first_sorted,
BidirectionalIteratorOrig last_sorted,
EPIterOrig ep_iter_sorted) {
- add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted,
- identity_property_map());
+ m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, identity_property_map());
}
// Add edges from a sorted (smallest sources first) range of pairs
@@ -1141,7 +720,7 @@
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>());
+ m_forward.add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<edge_bundled>());
}
template <typename BidirectionalIteratorOrig, typename GlobalToLocal>
@@ -1150,8 +729,7 @@
BidirectionalIteratorOrig first_sorted,
BidirectionalIteratorOrig last_sorted,
const GlobalToLocal& global_to_local) {
- add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<typename inherited_edge_properties::edge_bundled>(),
- global_to_local);
+ m_forward.add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<edge_bundled>(), global_to_local);
}
template <typename BidirectionalIteratorOrig, typename EPIterOrig,
@@ -1162,8 +740,7 @@
BidirectionalIteratorOrig last_sorted,
EPIterOrig ep_iter_sorted,
const GlobalToLocal& global_to_local) {
- add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted,
- global_to_local);
+ m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, global_to_local);
}
// Add edges from a range of (source, target) pairs that are unsorted
@@ -1179,13 +756,13 @@
edge_vector_t new_edges(first, last);
if (new_edges.empty()) return;
std::sort(new_edges.begin(), new_edges.end());
- add_edges_sorted_internal_global(new_edges.begin(), new_edges.end(), global_to_local);
+ this->add_edges_sorted_internal_global(new_edges.begin(), new_edges.end(), global_to_local);
}
template <typename InputIterator>
inline void
add_edges_internal(InputIterator first, InputIterator last) {
- add_edges_internal(first, last, identity_property_map());
+ this->add_edges_internal(first, last, identity_property_map());
}
// Add edges from a range of (source, target) pairs and edge properties that
@@ -1202,7 +779,7 @@
typedef std::pair<vertex_t, vertex_t> vertex_pair;
typedef std::vector<
boost::tuple<vertex_pair,
- typename inherited_edge_properties::edge_bundled> >
+ edge_bundled> >
edge_vector_t;
edge_vector_t new_edges
(boost::make_zip_iterator(boost::make_tuple(first, ep_iter)),
@@ -1211,7 +788,7 @@
std::sort(new_edges.begin(), new_edges.end(),
boost::detail::compare_first<
std::less<vertex_pair> >());
- add_edges_sorted_internal
+ m_forward.add_edges_sorted_internal
(boost::make_transform_iterator(
new_edges.begin(),
boost::detail::my_tuple_get_class<0, vertex_pair>()),
@@ -1221,7 +798,7 @@
boost::make_transform_iterator(
new_edges.begin(),
boost::detail::my_tuple_get_class
- <1, typename inherited_edge_properties::edge_bundled>()),
+ <1, edge_bundled>()),
global_to_local);
}
@@ -1231,27 +808,27 @@
inline void
add_edges_internal(InputIterator first, InputIterator last,
EPIterator ep_iter, EPIterator ep_iter_end) {
- add_edges_internal(first, last, ep_iter, ep_iter_end, identity_property_map());
+ this->add_edges_internal(first, last, ep_iter, ep_iter_end, identity_property_map());
}
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
using inherited_vertex_properties::operator[];
- using inherited_edge_properties::operator[];
+
+ // Directly access a edge or edge bundle
+ edge_push_back_type& operator[](const edge_descriptor& v)
+ { return m_forward.m_edge_properties[get(edge_index, *this, v)]; }
+
+ const edge_push_back_type& operator[](const edge_descriptor& v) const
+ { return m_forward.m_edge_properties[get(edge_index, *this, v)]; }
// private: non-portable, requires friend templates
inherited_vertex_properties& vertex_properties() {return *this;}
const inherited_vertex_properties& vertex_properties() const {return *this;}
- inherited_edge_properties& edge_properties() { return *this; }
- const inherited_edge_properties& edge_properties() const { return *this; }
+ typename forward_type::inherited_edge_properties& edge_properties() { return m_forward; }
+ const typename forward_type::inherited_edge_properties& edge_properties() const { return m_forward; }
- std::vector<EdgeIndex> m_rowstart;
- std::vector<Vertex> m_column;
+ forward_type m_forward;
GraphProperty m_property;
-#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- // This member is only needed to support add_edge(), which is not provided by
- // the new interface
- Vertex m_last_source; // Last source of added edge, plus one
-#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
};
template<typename Vertex, typename EdgeIndex>
@@ -1293,9 +870,9 @@
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
inline Vertex
add_vertex(BOOST_CSR_GRAPH_TYPE& g) {
- Vertex old_num_verts_plus_one = g.m_rowstart.size();
- EdgeIndex numedges = g.m_rowstart.back();
- g.m_rowstart.push_back(numedges);
+ Vertex old_num_verts_plus_one = g.m_forward.m_rowstart.size();
+ EdgeIndex numedges = g.m_forward.m_rowstart.back();
+ g.m_forward.m_rowstart.push_back(numedges);
g.vertex_properties().resize(num_vertices(g));
return old_num_verts_plus_one - 1;
}
@@ -1304,8 +881,8 @@
inline Vertex
add_vertex(BOOST_CSR_GRAPH_TYPE& g,
typename BOOST_CSR_GRAPH_TYPE::vertex_bundled const& p) {
- Vertex old_num_verts_plus_one = g.m_rowstart.size();
- g.m_rowstart.push_back(EdgeIndex(0));
+ Vertex old_num_verts_plus_one = g.m_forward.m_rowstart.size();
+ g.m_forward.m_rowstart.push_back(EdgeIndex(0));
g.vertex_properties().push_back(p);
return old_num_verts_plus_one - 1;
}
@@ -1313,9 +890,9 @@
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
inline Vertex
add_vertices(typename BOOST_CSR_GRAPH_TYPE::vertices_size_type count, BOOST_CSR_GRAPH_TYPE& g) {
- Vertex old_num_verts_plus_one = g.m_rowstart.size();
- EdgeIndex numedges = g.m_rowstart.back();
- g.m_rowstart.resize(old_num_verts_plus_one + count, numedges);
+ Vertex old_num_verts_plus_one = g.m_forward.m_rowstart.size();
+ EdgeIndex numedges = g.m_forward.m_rowstart.back();
+ g.m_forward.m_rowstart.resize(old_num_verts_plus_one + count, numedges);
g.vertex_properties().resize(num_vertices(g));
return old_num_verts_plus_one - 1;
}
@@ -1328,11 +905,11 @@
add_edge(Vertex src, Vertex tgt, BOOST_CSR_GRAPH_TYPE& g) {
assert ((g.m_last_source == 0 || src >= g.m_last_source - 1) &&
src < num_vertices(g));
- EdgeIndex num_edges_orig = g.m_column.size();
+ EdgeIndex num_edges_orig = g.m_forward.m_column.size();
for (; g.m_last_source <= src; ++g.m_last_source)
- g.m_rowstart[g.m_last_source] = num_edges_orig;
- g.m_rowstart[src + 1] = num_edges_orig + 1;
- g.m_column.push_back(tgt);
+ g.m_forward.m_rowstart[g.m_last_source] = num_edges_orig;
+ g.m_forward.m_rowstart[src + 1] = num_edges_orig + 1;
+ g.m_forward.m_column.push_back(tgt);
typedef typename BOOST_CSR_GRAPH_TYPE::edge_push_back_type push_back_type;
g.edge_properties().push_back(push_back_type());
return typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(src, num_edges_orig);
@@ -1347,11 +924,11 @@
BOOST_CSR_GRAPH_TYPE& g) {
assert ((g.m_last_source == 0 || src >= g.m_last_source - 1) &&
src < num_vertices(g));
- EdgeIndex num_edges_orig = g.m_column.size();
+ EdgeIndex num_edges_orig = g.m_forward.m_column.size();
for (; g.m_last_source <= src; ++g.m_last_source)
- g.m_rowstart[g.m_last_source] = num_edges_orig;
- g.m_rowstart[src + 1] = num_edges_orig + 1;
- g.m_column.push_back(tgt);
+ g.m_forward.m_rowstart[g.m_last_source] = num_edges_orig;
+ g.m_forward.m_rowstart[src + 1] = num_edges_orig + 1;
+ g.m_forward.m_column.push_back(tgt);
g.edge_properties().push_back(p);
return typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(src, num_edges_orig);
}
@@ -1448,7 +1025,7 @@
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
inline Vertex
num_vertices(const BOOST_CSR_GRAPH_TYPE& g) {
- return g.m_rowstart.size() - 1;
+ return g.m_forward.m_rowstart.size() - 1;
}
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
@@ -1506,7 +1083,7 @@
target(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e,
const BOOST_CSR_GRAPH_TYPE& g)
{
- return g.m_column[e.idx];
+ return g.m_forward.m_column[e.idx];
}
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
@@ -1516,8 +1093,8 @@
{
typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor ed;
typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator it;
- EdgeIndex v_row_start = g.m_rowstart[v];
- EdgeIndex next_row_start = g.m_rowstart[v + 1];
+ EdgeIndex v_row_start = g.m_forward.m_rowstart[v];
+ EdgeIndex next_row_start = g.m_forward.m_rowstart[v + 1];
#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
return std::make_pair(it(ed(v, v_row_start)),
it(ed(v, next_row_start)));
@@ -1532,8 +1109,8 @@
inline EdgeIndex
out_degree(Vertex v, const BOOST_CSR_GRAPH_TYPE& g)
{
- EdgeIndex v_row_start = g.m_rowstart[v];
- EdgeIndex next_row_start = g.m_rowstart[v + 1];
+ EdgeIndex v_row_start = g.m_forward.m_rowstart[v];
+ EdgeIndex next_row_start = g.m_forward.m_rowstart[v + 1];
#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
return next_row_start - v_row_start;
#else
@@ -1548,15 +1125,15 @@
typename BOOST_CSR_GRAPH_TYPE::adjacency_iterator>
adjacent_vertices(Vertex v, const BOOST_CSR_GRAPH_TYPE& g)
{
- EdgeIndex v_row_start = g.m_rowstart[v];
- EdgeIndex next_row_start = g.m_rowstart[v + 1];
+ EdgeIndex v_row_start = g.m_forward.m_rowstart[v];
+ EdgeIndex next_row_start = g.m_forward.m_rowstart[v + 1];
#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
- return std::make_pair(g.m_column.begin() + v_row_start,
- g.m_column.begin() + next_row_start);
+ return std::make_pair(g.m_forward.m_column.begin() + v_row_start,
+ g.m_forward.m_column.begin() + next_row_start);
#else
// Special case to allow incremental construction
- return std::make_pair(g.m_column.begin() + v_row_start,
- g.m_column.begin() +
+ return std::make_pair(g.m_forward.m_column.begin() + v_row_start,
+ g.m_forward.m_column.begin() +
(std::max)(v_row_start, next_row_start));
#endif
}
@@ -1587,8 +1164,8 @@
std::pair<adj_iter, adj_iter> raw_adjacencies = adjacent_vertices(i, g);
std::pair<adj_iter, adj_iter> adjacencies =
std::equal_range(raw_adjacencies.first, raw_adjacencies.second, j);
- EdgeIndex idx_begin = adjacencies.first - g.m_column.begin();
- EdgeIndex idx_end = adjacencies.second - g.m_column.begin();
+ EdgeIndex idx_begin = adjacencies.first - g.m_forward.m_column.begin();
+ EdgeIndex idx_end = adjacencies.second - g.m_forward.m_column.begin();
return std::make_pair(out_edge_iter(edge_desc(i, idx_begin)),
out_edge_iter(edge_desc(i, idx_end)));
}
@@ -1633,19 +1210,19 @@
typedef typename std::vector<EdgeIndex>::const_iterator row_start_iter;
assert (idx < num_edges(g));
row_start_iter src_plus_1 =
- std::upper_bound(g.m_rowstart.begin(),
+ std::upper_bound(g.m_forward.m_rowstart.begin(),
#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
// This handles the case where there are some vertices
// with rowstart 0 after the last provided vertex; this
// case does not happen with the new interface
- g.m_rowstart.begin() + g.m_last_source + 1,
+ g.m_forward.m_rowstart.begin() + g.m_last_source + 1,
#else // !BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- g.m_rowstart.end(),
+ g.m_forward.m_rowstart.end(),
#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
idx);
// Get last source whose rowstart is at most idx
// upper_bound returns this position plus 1
- Vertex src = (src_plus_1 - g.m_rowstart.begin()) - 1;
+ Vertex src = (src_plus_1 - g.m_forward.m_rowstart.begin()) - 1;
return typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(src, idx);
}
@@ -1667,7 +1244,7 @@
edge_iterator(const compressed_sparse_row_graph& graph,
edge_descriptor current_edge,
EdgeIndex end_of_this_vertex)
- : rowstart_array(&graph.m_rowstart[0]), current_edge(current_edge),
+ : rowstart_array(&graph.m_forward.m_rowstart[0]), current_edge(current_edge),
end_of_this_vertex(end_of_this_vertex) {}
// From InputIterator
@@ -1706,7 +1283,7 @@
inline EdgeIndex
num_edges(const BOOST_CSR_GRAPH_TYPE& g)
{
- return g.m_column.size();
+ return g.m_forward.m_column.size();
}
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
@@ -1716,14 +1293,14 @@
{
typedef typename BOOST_CSR_GRAPH_TYPE::edge_iterator ei;
typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor edgedesc;
- if (g.m_rowstart.size() == 1 || g.m_column.empty()) {
+ if (g.m_forward.m_rowstart.size() == 1 || g.m_forward.m_column.empty()) {
return std::make_pair(ei(), ei());
} else {
// Find the first vertex that has outgoing edges
Vertex src = 0;
- while (g.m_rowstart[src + 1] == 0) ++src;
- return std::make_pair(ei(g, edgedesc(src, 0), g.m_rowstart[src + 1]),
- ei(g, edgedesc(num_vertices(g), g.m_column.size()), 0));
+ while (g.m_forward.m_rowstart[src + 1] == 0) ++src;
+ return std::make_pair(ei(g, edgedesc(src, 0), g.m_forward.m_rowstart[src + 1]),
+ ei(g, edgedesc(num_vertices(g), g.m_forward.m_column.size()), 0));
}
}
Added: trunk/boost/graph/detail/compressed_sparse_row_struct.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/detail/compressed_sparse_row_struct.hpp 2009-09-08 18:55:05 EDT (Tue, 08 Sep 2009)
@@ -0,0 +1,409 @@
+// Copyright 2005-2009 The Trustees of Indiana University.
+
+// 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)
+
+// Authors: Jeremiah Willcock
+// Douglas Gregor
+// Andrew Lumsdaine
+
+// Compressed sparse row graph type internal structure
+
+#ifndef BOOST_GRAPH_COMPRESSED_SPARSE_ROW_STRUCT_HPP
+#define BOOST_GRAPH_COMPRESSED_SPARSE_ROW_STRUCT_HPP
+
+#ifndef BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP
+#error This file should only be included from boost/graph/compressed_sparse_row_graph.hpp
+#endif
+
+#include <vector>
+#include <utility>
+#include <algorithm>
+#include <climits>
+#include <cassert>
+#include <iterator>
+#if 0
+#include <iostream> // For some debugging code below
+#endif
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/properties.hpp>
+#include <boost/graph/filtered_graph.hpp> // For keep_all
+#include <boost/graph/detail/indexed_properties.hpp>
+#include <boost/graph/detail/histogram_sort.hpp>
+#include <boost/graph/iteration_macros.hpp>
+#include <boost/iterator/counting_iterator.hpp>
+#include <boost/iterator/reverse_iterator.hpp>
+#include <boost/iterator/zip_iterator.hpp>
+#include <boost/iterator/transform_iterator.hpp>
+#include <boost/tuple/tuple.hpp>
+#include <boost/property_map/property_map.hpp>
+#include <boost/integer.hpp>
+#include <boost/iterator/iterator_facade.hpp>
+#include <boost/mpl/if.hpp>
+#include <boost/graph/graph_selectors.hpp>
+#include <boost/static_assert.hpp>
+#include <boost/functional/hash.hpp>
+#include <boost/utility.hpp>
+
+namespace boost {
+
+// Forward declaration of CSR edge descriptor type, needed to pass to
+// indexed_edge_properties.
+template<typename Vertex, typename EdgeIndex>
+class csr_edge_descriptor;
+
+namespace detail {
+ /** Compressed sparse row graph internal structure.
+ *
+ * Vertex and EdgeIndex should be unsigned integral types and should
+ * specialize numeric_limits.
+ */
+ template <typename EdgeProperty,
+ typename Vertex = std::size_t, typename EdgeIndex = Vertex>
+ class compressed_sparse_row_structure :
+ public detail::indexed_edge_properties<
+ compressed_sparse_row_structure<EdgeProperty, Vertex, EdgeIndex>,
+ EdgeProperty,
+ csr_edge_descriptor<Vertex, EdgeIndex> > {
+ public:
+ typedef detail::indexed_edge_properties<
+ compressed_sparse_row_structure<EdgeProperty, Vertex, EdgeIndex>,
+ EdgeProperty,
+ csr_edge_descriptor<Vertex, EdgeIndex> >
+ inherited_edge_properties;
+
+ typedef Vertex vertices_size_type;
+ typedef Vertex vertex_descriptor;
+ typedef EdgeIndex edges_size_type;
+
+ static vertex_descriptor null_vertex() { return vertex_descriptor(-1); }
+
+ std::vector<EdgeIndex> m_rowstart;
+ std::vector<Vertex> m_column;
+#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+ // This member is only needed to support add_edge(), which is not provided by
+ // the new interface
+ Vertex m_last_source; // Last source of added edge, plus one
+#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+
+ compressed_sparse_row_structure(Vertex numverts = 0)
+ : m_rowstart(numverts + 1, EdgeIndex(0)), m_column()
+#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+ , m_last_source(numverts)
+#endif
+ {}
+
+ // Rebuild graph from number of vertices and multi-pass unsorted list of
+ // edges (filtered using source_pred and mapped using global_to_local)
+ template <typename MultiPassInputIterator, typename GlobalToLocal, typename SourcePred>
+ void
+ assign_unsorted_multi_pass_edges(MultiPassInputIterator edge_begin,
+ MultiPassInputIterator edge_end,
+ vertices_size_type numlocalverts,
+ const GlobalToLocal& global_to_local,
+ const SourcePred& source_pred) {
+ m_rowstart.clear();
+ m_rowstart.resize(numlocalverts + 1, 0);
+ typedef std::pair<vertices_size_type, vertices_size_type> edge_type;
+ typedef boost::transform_iterator<boost::graph::detail::project1st<edge_type>, MultiPassInputIterator> source_iterator;
+ typedef boost::transform_iterator<boost::graph::detail::project2nd<edge_type>, MultiPassInputIterator> target_iterator;
+ source_iterator sources_begin(edge_begin, boost::graph::detail::project1st<edge_type>());
+ source_iterator sources_end(edge_end, boost::graph::detail::project1st<edge_type>());
+ target_iterator targets_begin(edge_begin, boost::graph::detail::project2nd<edge_type>());
+ target_iterator targets_end(edge_end, boost::graph::detail::project2nd<edge_type>());
+
+ boost::graph::detail::count_starts
+ (sources_begin, sources_end, m_rowstart.begin(), numlocalverts,
+ source_pred, make_property_map_function(global_to_local));
+
+ m_column.resize(m_rowstart.back());
+
+ boost::graph::detail::histogram_sort
+ (sources_begin, sources_end, m_rowstart.begin(), numlocalverts,
+ targets_begin, m_column.begin(),
+ source_pred, make_property_map_function(global_to_local));
+ }
+
+ // Rebuild graph from number of vertices and multi-pass unsorted list of
+ // edges and their properties (filtered using source_pred and mapped using
+ // global_to_local)
+ template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred>
+ void
+ assign_unsorted_multi_pass_edges(MultiPassInputIterator edge_begin,
+ MultiPassInputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numlocalverts,
+ const GlobalToLocal& global_to_local,
+ const SourcePred& source_pred) {
+ m_rowstart.clear();
+ m_rowstart.resize(numlocalverts + 1, 0);
+ typedef std::pair<vertices_size_type, vertices_size_type> edge_type;
+ typedef boost::transform_iterator<boost::graph::detail::project1st<edge_type>, MultiPassInputIterator> source_iterator;
+ typedef boost::transform_iterator<boost::graph::detail::project2nd<edge_type>, MultiPassInputIterator> target_iterator;
+ source_iterator sources_begin(edge_begin, boost::graph::detail::project1st<edge_type>());
+ source_iterator sources_end(edge_end, boost::graph::detail::project1st<edge_type>());
+ target_iterator targets_begin(edge_begin, boost::graph::detail::project2nd<edge_type>());
+ target_iterator targets_end(edge_end, boost::graph::detail::project2nd<edge_type>());
+
+ boost::graph::detail::count_starts
+ (sources_begin, sources_end, m_rowstart.begin(), numlocalverts,
+ source_pred, make_property_map_function(global_to_local));
+
+ m_column.resize(m_rowstart.back());
+ inherited_edge_properties::resize(m_rowstart.back());
+
+ boost::graph::detail::histogram_sort
+ (sources_begin, sources_end, m_rowstart.begin(), numlocalverts,
+ targets_begin, m_column.begin(),
+ ep_iter, inherited_edge_properties::begin(),
+ source_pred, make_property_map_function(global_to_local));
+ }
+
+ // Assign from number of vertices and sorted list of edges
+ template<typename InputIterator, typename GlobalToLocal, typename SourcePred>
+ void assign_from_sorted_edges(
+ InputIterator edge_begin, InputIterator edge_end,
+ const GlobalToLocal& global_to_local,
+ const SourcePred& source_pred,
+ vertices_size_type numlocalverts,
+ edges_size_type numedges_or_zero) {
+ m_column.clear();
+ m_column.reserve(numedges_or_zero);
+ 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 (!source_pred(ei->first)) 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 SourcePred>
+ void assign_from_sorted_edges(
+ InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ const GlobalToLocal& global_to_local,
+ const SourcePred& source_pred,
+ vertices_size_type numlocalverts,
+ edges_size_type numedges_or_zero) {
+ // Reserving storage in advance can save us lots of time and
+ // memory, but it can only be done if we have forward iterators or
+ // the user has supplied the number of edges.
+ edges_size_type numedges = numedges_or_zero;
+ if (numedges == 0) {
+ typedef typename std::iterator_traits<InputIterator>::iterator_category
+ category;
+ numedges = boost::graph::detail::reserve_count_for_single_pass(edge_begin, edge_end);
+ }
+ m_column.clear();
+ m_column.reserve(numedges_or_zero);
+ inherited_edge_properties::clear();
+ inherited_edge_properties::reserve(numedges_or_zero);
+ 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 (!source_pred(ei->first)) 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;
+ }
+
+ // Replace graph with sources and targets given, sorting them in-place, and
+ // using the given global-to-local property map to get local indices from
+ // global ones in the two arrays.
+ template <typename GlobalToLocal>
+ void assign_sources_and_targets_global(std::vector<vertex_descriptor>& sources,
+ std::vector<vertex_descriptor>& targets,
+ vertices_size_type numverts,
+ GlobalToLocal global_to_local) {
+ assert (sources.size() == targets.size());
+ // Do an in-place histogram sort (at least that's what I think it is) to
+ // sort sources and targets
+ m_rowstart.clear();
+ m_rowstart.resize(numverts + 1);
+ boost::graph::detail::count_starts
+ (sources.begin(), sources.end(), m_rowstart.begin(), numverts,
+ keep_all(), make_property_map_function(global_to_local));
+ boost::graph::detail::histogram_sort_inplace
+ (sources.begin(), sources.end(), m_rowstart.begin(), numverts,
+ targets.begin(), make_property_map_function(global_to_local));
+ // Now targets is the correct vector (properly sorted by source) for
+ // m_column
+ m_column.swap(targets);
+ }
+
+ // Replace graph with sources and targets and edge properties given, sorting
+ // them in-place, and using the given global-to-local property map to get
+ // local indices from global ones in the two arrays.
+ 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_bundled>& edge_props,
+ vertices_size_type numverts,
+ GlobalToLocal global_to_local) {
+ assert (sources.size() == targets.size());
+ assert (sources.size() == edge_props.size());
+ // Do an in-place histogram sort (at least that's what I think it is) to
+ // sort sources and targets
+ m_rowstart.clear();
+ m_rowstart.resize(numverts + 1);
+ boost::graph::detail::count_starts
+ (sources.begin(), sources.end(), m_rowstart.begin(), numverts,
+ keep_all(), make_property_map_function(global_to_local));
+ boost::graph::detail::histogram_sort_inplace
+ (sources.begin(), sources.end(), m_rowstart.begin(), numverts,
+ targets.begin(), edge_props.begin(),
+ make_property_map_function(global_to_local));
+ // Now targets is the correct vector (properly sorted by source) for
+ // m_column, and edge_props for m_edge_properties
+ m_column.swap(targets);
+ this->m_edge_properties.swap(edge_props);
+ }
+
+ // From any graph (slow and uses a lot of memory)
+ // Requires IncidenceGraph and a vertex index map
+ // Internal helper function
+ // Note that numedges must be doubled for undirected source graphs
+ template<typename Graph, typename VertexIndexMap>
+ void
+ assign(const Graph& g, const VertexIndexMap& vi,
+ vertices_size_type numverts, edges_size_type numedges)
+ {
+ m_rowstart.resize(numverts + 1);
+ m_column.resize(numedges);
+ EdgeIndex current_edge = 0;
+ typedef typename boost::graph_traits<Graph>::vertex_descriptor g_vertex;
+ typedef typename boost::graph_traits<Graph>::edge_descriptor g_edge;
+ typedef typename boost::graph_traits<Graph>::out_edge_iterator
+ g_out_edge_iter;
+
+ std::vector<g_vertex> ordered_verts_of_g(numverts);
+ BGL_FORALL_VERTICES_T(v, g, Graph) {
+ ordered_verts_of_g[get(vertex_index, g, v)] = v;
+ }
+ for (Vertex i = 0; i != numverts; ++i) {
+ m_rowstart[i] = current_edge;
+ g_vertex v = ordered_verts_of_g[i];
+#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+ // Out edges in a single vertex are only sorted for the old interface
+ EdgeIndex num_edges_before_this_vertex = current_edge;
+#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+ g_out_edge_iter ei, ei_end;
+ for (tie(ei, ei_end) = out_edges(v, g); ei != ei_end; ++ei) {
+ m_column[current_edge++] = get(vi, target(*ei, g));
+ }
+#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+ // Out edges in a single vertex are only sorted for the old interface
+ std::sort(m_column.begin() + num_edges_before_this_vertex,
+ m_column.begin() + current_edge);
+#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+ }
+ m_rowstart[numverts] = current_edge;
+#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+ m_last_source = numverts;
+#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+ }
+
+ // Add edges from a sorted (smallest sources first) range of pairs and edge
+ // properties
+ template <typename BidirectionalIteratorOrig, typename EPIterOrig,
+ typename GlobalToLocal>
+ void
+ add_edges_sorted_internal(
+ BidirectionalIteratorOrig first_sorted,
+ BidirectionalIteratorOrig last_sorted,
+ EPIterOrig ep_iter_sorted,
+ const GlobalToLocal& global_to_local) {
+ typedef boost::reverse_iterator<BidirectionalIteratorOrig> BidirectionalIterator;
+ typedef boost::reverse_iterator<EPIterOrig> EPIter;
+ // Flip sequence
+ BidirectionalIterator first(last_sorted);
+ BidirectionalIterator last(first_sorted);
+ typedef Vertex vertex_t;
+ typedef Vertex vertex_num;
+ typedef EdgeIndex 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 = m_rowstart.size() - 1; 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 (get(global_to_local, 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;
+ --temp_prop;
+ 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)
+ }
+ }
+
+ };
+
+} // namespace detail
+} // namespace boost
+
+#endif // BOOST_GRAPH_COMPRESSED_SPARSE_ROW_STRUCT_HPP
Added: trunk/boost/graph/detail/histogram_sort.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/detail/histogram_sort.hpp 2009-09-08 18:55:05 EDT (Tue, 08 Sep 2009)
@@ -0,0 +1,286 @@
+// Copyright 2009 The Trustees of Indiana University.
+
+// 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)
+
+// Authors: Jeremiah Willcock
+// Andrew Lumsdaine
+
+#ifndef BOOST_GRAPH_DETAIL_HISTOGRAM_SORT_HPP
+#define BOOST_GRAPH_DETAIL_HISTOGRAM_SORT_HPP
+
+namespace boost {
+ namespace graph {
+ namespace detail {
+
+template<typename InputIterator>
+size_t
+reserve_count_for_single_pass_helper(InputIterator, InputIterator,
+ std::input_iterator_tag)
+{
+ // Do nothing: we have no idea how much storage to reserve.
+ return 0;
+}
+
+template<typename InputIterator>
+size_t
+reserve_count_for_single_pass_helper(InputIterator first, InputIterator last,
+ std::random_access_iterator_tag)
+{
+ using std::distance;
+ typename std::iterator_traits<InputIterator>::difference_type n =
+ distance(first, last);
+ return (size_t)n;
+}
+
+template<typename InputIterator>
+size_t
+reserve_count_for_single_pass(InputIterator first, InputIterator last) {
+ typedef typename std::iterator_traits<InputIterator>::iterator_category
+ category;
+ return reserve_count_for_single_pass_helper(first, last, category());
+}
+
+template <typename KeyIterator, typename RowstartIterator,
+ typename VerticesSize, typename KeyFilter, typename KeyTransform>
+void
+count_starts
+ (KeyIterator begin, KeyIterator end,
+ RowstartIterator starts, // Must support numverts + 1 elements
+ VerticesSize numkeys,
+ KeyFilter key_filter,
+ KeyTransform key_transform) {
+
+ typedef VerticesSize vertices_size_type;
+ typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;
+
+ // Put the degree of each vertex v into m_rowstart[v + 1]
+ for (KeyIterator i = begin; i != end; ++i) {
+ if (key_filter(*i)) {
+ ++starts[key_transform(*i) + 1];
+ }
+ }
+
+ // Compute the partial sum of the degrees to get the actual values of
+ // m_rowstart
+ EdgeIndex start_of_this_row = 0;
+ starts[0] = start_of_this_row;
+ for (vertices_size_type i = 1; i <= numkeys; ++i) {
+ start_of_this_row += starts[i];
+ starts[i] = start_of_this_row;
+ }
+}
+
+template <typename KeyIterator, typename RowstartIterator,
+ typename NumKeys,
+ typename Value1InputIter,
+ typename Value1OutputIter, typename KeyFilter, typename KeyTransform>
+void
+histogram_sort(KeyIterator key_begin, KeyIterator key_end,
+ RowstartIterator rowstart, // Must support numkeys + 1 elements and be precomputed
+ NumKeys numkeys,
+ Value1InputIter values1_begin,
+ Value1OutputIter values1_out,
+ KeyFilter key_filter,
+ KeyTransform key_transform) {
+
+ typedef NumKeys vertices_size_type;
+ typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;
+
+ // Histogram sort the edges by their source vertices, putting the targets
+ // 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(rowstart, rowstart + numkeys);
+ Value1InputIter v1i = values1_begin;
+ for (KeyIterator i = key_begin; i != key_end; ++i, ++v1i) {
+ if (key_filter(*i)) {
+ vertices_size_type source = key_transform(*i);
+ EdgeIndex insert_pos = current_insert_positions[source];
+ ++current_insert_positions[source];
+ values1_out[insert_pos] = *v1i;
+ }
+ }
+}
+
+template <typename KeyIterator, typename RowstartIterator,
+ typename NumKeys,
+ typename Value1InputIter,
+ typename Value1OutputIter,
+ typename Value2InputIter,
+ typename Value2OutputIter,
+ typename KeyFilter, typename KeyTransform>
+void
+histogram_sort(KeyIterator key_begin, KeyIterator key_end,
+ RowstartIterator rowstart, // Must support numkeys + 1 elements and be precomputed
+ NumKeys numkeys,
+ Value1InputIter values1_begin,
+ Value1OutputIter values1_out,
+ Value2InputIter values2_begin,
+ Value2OutputIter values2_out,
+ KeyFilter key_filter,
+ KeyTransform key_transform) {
+
+ typedef NumKeys vertices_size_type;
+ typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;
+
+ // Histogram sort the edges by their source vertices, putting the targets
+ // 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(rowstart, rowstart + numkeys);
+ Value1InputIter v1i = values1_begin;
+ Value2InputIter v2i = values2_begin;
+ for (KeyIterator i = key_begin; i != key_end; ++i, ++v1i, ++v2i) {
+ if (key_filter(*i)) {
+ vertices_size_type source = key_transform(*i);
+ EdgeIndex insert_pos = current_insert_positions[source];
+ ++current_insert_positions[source];
+ values1_out[insert_pos] = *v1i;
+ values2_out[insert_pos] = *v2i;
+ }
+ }
+}
+
+template <typename KeyIterator, typename RowstartIterator,
+ typename NumKeys,
+ typename Value1Iter,
+ typename KeyTransform>
+void
+histogram_sort_inplace(KeyIterator key_begin, KeyIterator key_end,
+ RowstartIterator rowstart, // Must support numkeys + 1 elements and be precomputed
+ NumKeys numkeys,
+ Value1Iter values1,
+ KeyTransform key_transform) {
+
+ typedef NumKeys vertices_size_type;
+ typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;
+
+ // 1. Copy m_rowstart (except last element) to get insert positions
+ std::vector<EdgeIndex> insert_positions(rowstart, rowstart + numkeys);
+ // 2. Swap the sources and targets into place
+ for (size_t i = 0; i < rowstart[numkeys]; ++i) {
+ // While edge i is not in the right bucket:
+ while (!(i >= rowstart[key_transform(key_begin[i])] && i < insert_positions[key_transform(key_begin[i])])) {
+ // Add a slot in the right bucket
+ size_t target_pos = insert_positions[key_transform(key_begin[i])]++;
+ assert (target_pos < rowstart[key_transform(key_begin[i]) + 1]);
+ if (target_pos == i) continue;
+ // Swap this edge into place
+ using std::swap;
+ swap(key_begin[i], key_begin[target_pos]);
+ swap(values1[i], values1[target_pos]);
+ }
+ }
+}
+
+template <typename KeyIterator, typename RowstartIterator,
+ typename NumKeys,
+ typename Value1Iter,
+ typename Value2Iter,
+ typename KeyTransform>
+void
+histogram_sort_inplace(KeyIterator key_begin, KeyIterator key_end,
+ RowstartIterator rowstart, // Must support numkeys + 1 elements and be precomputed
+ NumKeys numkeys,
+ Value1Iter values1,
+ Value2Iter values2,
+ KeyTransform key_transform) {
+
+ typedef NumKeys vertices_size_type;
+ typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;
+
+ // 1. Copy m_rowstart (except last element) to get insert positions
+ std::vector<EdgeIndex> insert_positions(rowstart, rowstart + numkeys);
+ // 2. Swap the sources and targets into place
+ for (size_t i = 0; i < rowstart[numkeys]; ++i) {
+ // While edge i is not in the right bucket:
+ while (!(i >= rowstart[key_transform(key_begin[i])] && i < insert_positions[key_transform(key_begin[i])])) {
+ // Add a slot in the right bucket
+ size_t target_pos = insert_positions[key_transform(key_begin[i])]++;
+ assert (target_pos < rowstart[key_transform(key_begin[i]) + 1]);
+ if (target_pos == i) continue;
+ // Swap this edge into place
+ using std::swap;
+ swap(key_begin[i], key_begin[target_pos]);
+ swap(values1[i], values1[target_pos]);
+ swap(values2[i], values2[target_pos]);
+ }
+ }
+}
+
+template <typename InputIterator, typename VerticesSize>
+void split_into_separate_coords(InputIterator begin, InputIterator end,
+ std::vector<VerticesSize>& firsts,
+ std::vector<VerticesSize>& seconds) {
+ firsts.clear();
+ seconds.clear();
+ size_t reserve_size
+ = detail::reserve_count_for_single_pass(begin, end);
+ firsts.reserve(reserve_size);
+ seconds.reserve(reserve_size);
+ for (; begin != end; ++begin) {
+ std::pair<VerticesSize, VerticesSize> edge = *begin;
+ firsts.push_back(edge.first);
+ seconds.push_back(edge.second);
+ }
+}
+
+template <typename InputIterator, typename VerticesSize, typename SourceFilter>
+void split_into_separate_coords_filtered
+ (InputIterator begin, InputIterator end,
+ std::vector<VerticesSize>& firsts,
+ std::vector<VerticesSize>& seconds,
+ const SourceFilter& filter) {
+ firsts.clear();
+ seconds.clear();
+ for (; begin != end; ++begin) {
+ std::pair<VerticesSize, VerticesSize> edge = *begin;
+ if (filter(edge.first)) {
+ firsts.push_back(edge.first);
+ seconds.push_back(edge.second);
+ }
+ }
+}
+
+template <typename InputIterator, typename PropInputIterator,
+ typename VerticesSize, typename PropType, typename SourceFilter>
+void split_into_separate_coords_filtered
+ (InputIterator begin, InputIterator end,
+ PropInputIterator props,
+ std::vector<VerticesSize>& firsts,
+ std::vector<VerticesSize>& seconds,
+ std::vector<PropType>& props_out,
+ const SourceFilter& filter) {
+ firsts.clear();
+ seconds.clear();
+ props_out.clear();
+ for (; begin != end; ++begin) {
+ std::pair<VerticesSize, VerticesSize> edge = *begin;
+ if (filter(edge.first)) {
+ firsts.push_back(edge.first);
+ seconds.push_back(edge.second);
+ props_out.push_back(*props);
+ }
+ ++props;
+ }
+}
+
+template <typename Pair>
+struct project1st {
+ typedef typename Pair::first_type result_type;
+ const result_type& operator()(const Pair& p) const {return p.first;}
+};
+
+template <typename Pair>
+struct project2nd {
+ typedef typename Pair::second_type result_type;
+ const result_type& operator()(const Pair& p) const {return p.second;}
+};
+
+ }
+ }
+}
+
+#endif // BOOST_GRAPH_DETAIL_HISTOGRAM_SORT_HPP
Modified: trunk/boost/graph/distributed/compressed_sparse_row_graph.hpp
==============================================================================
--- trunk/boost/graph/distributed/compressed_sparse_row_graph.hpp (original)
+++ trunk/boost/graph/distributed/compressed_sparse_row_graph.hpp 2009-09-08 18:55:05 EDT (Tue, 08 Sep 2009)
@@ -525,8 +525,8 @@
typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor ed;
typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator it;
edges_size_type u_local = get(vertex_local, g, u);
- edges_size_type u_row_start = g.base().m_rowstart[u_local];
- edges_size_type next_row_start = g.base().m_rowstart[u_local + 1];
+ edges_size_type u_row_start = g.base().m_forward.m_rowstart[u_local];
+ edges_size_type next_row_start = g.base().m_forward.m_rowstart[u_local + 1];
return std::make_pair(it(ed(u, u_row_start)),
it(ed(u, (std::max)(u_row_start, next_row_start))));
}
@@ -658,7 +658,7 @@
while (current_edge.idx == end_of_this_vertex && local_src < num_vertices(*graph)-1) {
++local_src;
current_edge.src = graph->local_to_global_vertex(local_src);
- end_of_this_vertex = graph->base().m_rowstart[local_src + 1];
+ end_of_this_vertex = graph->base().m_forward.m_rowstart[local_src + 1];
}
return *this;
}
@@ -680,7 +680,7 @@
inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type
num_edges(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{
- return g.base().m_column.size();
+ return g.base().m_forward.m_column.size();
}
template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
@@ -691,14 +691,15 @@
typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor Vertex;
typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_iterator ei;
typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor edgedesc;
- if (g.base().m_rowstart.size() == 1 || g.base().m_column.empty()) {
+ if (g.base().m_forward.m_rowstart.size() == 1 ||
+ g.base().m_forward.m_column.empty()) {
return std::make_pair(ei(), ei());
} else {
// Find the first vertex that has outgoing edges
Vertex src = 0;
- while (g.base().m_rowstart[src + 1] == 0) ++src;
- return std::make_pair(ei(g, edgedesc(src, 0), g.base().m_rowstart[src + 1]),
- ei(g, edgedesc(num_vertices(g), g.base().m_column.size()), 0));
+ while (g.base().m_forward.m_rowstart[src + 1] == 0) ++src;
+ return std::make_pair(ei(g, edgedesc(src, 0), g.base().m_forward.m_rowstart[src + 1]),
+ ei(g, edgedesc(num_vertices(g), g.base().m_forward.m_column.size()), 0));
}
}
@@ -708,6 +709,26 @@
#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// Returns true if a vertex belongs to a process according to a distribution
template <typename OwnerMap, typename ProcessId>
+struct local_vertex {
+
+ local_vertex(OwnerMap owner, ProcessId id)
+ : owner(owner), id(id) {}
+
+ template <typename Vertex>
+ bool operator()(Vertex x)
+ { return get(owner, x) == id; }
+
+ template <typename Vertex>
+ bool operator()(Vertex x) const
+ { return get(owner, x) == id; }
+
+private:
+ OwnerMap owner;
+ ProcessId id;
+};
+
+// Returns true if a vertex belongs to a process according to a distribution
+template <typename OwnerMap, typename ProcessId>
struct local_edge {
local_edge(OwnerMap owner, ProcessId id)
@@ -827,8 +848,8 @@
index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{ }
@@ -848,8 +869,8 @@
index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{ }
@@ -870,8 +891,8 @@
ep_iter,
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{ }
@@ -894,8 +915,8 @@
ep_iter,
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{ }
@@ -914,8 +935,8 @@
index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
m_distribution.block_size(process_id(m_process_group), numverts),
prop)
{ }
@@ -935,8 +956,8 @@
index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
m_distribution.block_size(process_id(m_process_group), numverts),
prop)
{ }
@@ -958,8 +979,8 @@
index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
ep_iter,
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
m_distribution.block_size(process_id(m_process_group), numverts),
prop)
{ }
@@ -982,8 +1003,8 @@
index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
ep_iter,
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
m_distribution.block_size(process_id(m_process_group), numverts),
prop)
{ }
@@ -1004,8 +1025,8 @@
make_index_to_vertex_iterator(edge_end, parallel::block(m_process_group, numverts), *this),
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{ }
@@ -1026,8 +1047,8 @@
make_index_to_vertex_iterator(edge_end, parallel::block(m_process_group, numverts), *this),
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{ }
@@ -1050,8 +1071,8 @@
ep_iter,
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{ }
@@ -1075,8 +1096,8 @@
ep_iter,
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
{ }
@@ -1216,8 +1237,8 @@
index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
#endif
@@ -1263,8 +1284,8 @@
ep_iter,
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
#endif
{
@@ -1308,8 +1329,8 @@
index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
#endif
{
@@ -1354,8 +1375,8 @@
index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
m_distribution.block_size(process_id(m_process_group), numverts),
get(vertex_local, *this),
- local_edge<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
- process_id_type> (get(vertex_owner, *this), process_id(pg)),
+ local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
+ process_id_type> (get(vertex_owner, *this), process_id(pg)),
prop)
#endif
{
@@ -1494,8 +1515,8 @@
std::pair<adj_iter, adj_iter> raw_adjacencies = adjacent_vertices(i, g);
std::pair<adj_iter, adj_iter> adjacencies =
std::equal_range(raw_adjacencies.first, raw_adjacencies.second, j);
- EdgeIndex idx_begin = adjacencies.first - g.base().m_column.begin();
- EdgeIndex idx_end = adjacencies.second - g.base().m_column.begin();
+ EdgeIndex idx_begin = adjacencies.first - g.base().m_forward.m_column.begin();
+ EdgeIndex idx_end = adjacencies.second - g.base().m_forward.m_column.begin();
return std::make_pair(out_edge_iter(edge_desc(i, idx_begin)),
out_edge_iter(edge_desc(i, idx_end)));
}
Modified: trunk/libs/graph/test/csr_graph_test.cpp
==============================================================================
--- trunk/libs/graph/test/csr_graph_test.cpp (original)
+++ trunk/libs/graph/test/csr_graph_test.cpp 2009-09-08 18:55:05 EDT (Tue, 08 Sep 2009)
@@ -167,7 +167,7 @@
#endif // !BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// Check that m_rowstart entries are valid, and that entries after
// m_last_source + 1 are all zero
- BOOST_CHECK(g.m_rowstart[0] == 0);
+ BOOST_CHECK(g.m_forward.m_rowstart[0] == 0);
for (CSRGraphT::vertices_size_type i = 0;
#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
i < num_vertices(g);
@@ -175,18 +175,18 @@
i < g.m_last_source;
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
++i) {
- BOOST_CHECK(g.m_rowstart[i + 1] >= g.m_rowstart[i]);
- BOOST_CHECK(g.m_rowstart[i + 1] <= num_edges(g));
+ BOOST_CHECK(g.m_forward.m_rowstart[i + 1] >= g.m_forward.m_rowstart[i]);
+ BOOST_CHECK(g.m_forward.m_rowstart[i + 1] <= num_edges(g));
}
#ifndef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
for (CSRGraphT::vertices_size_type i = g.m_last_source + 1;
- i < g.m_rowstart.size(); ++i) {
- BOOST_CHECK(g.m_rowstart[i] == 0);
+ i < g.m_forward.m_rowstart.size(); ++i) {
+ BOOST_CHECK(g.m_forward.m_rowstart[i] == 0);
}
#endif // !BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// Check that m_column entries are within range
for (CSRGraphT::edges_size_type i = 0; i < num_edges(g); ++i) {
- BOOST_CHECK(g.m_column[i] < num_vertices(g));
+ BOOST_CHECK(g.m_forward.m_column[i] < num_vertices(g));
}
}
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk