|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r56128 - in trunk: boost/graph boost/graph/detail boost/graph/distributed libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-09-09 17:29:18
Author: jewillco
Date: 2009-09-09 17:29:17 EDT (Wed, 09 Sep 2009)
New Revision: 56128
URL: http://svn.boost.org/trac/boost/changeset/56128
Log:
Refactored and added bidirectional CSR support; fixes #3386
Text files modified:
trunk/boost/graph/compressed_sparse_row_graph.hpp | 549 ++++++++++++++++++++++++++++++---------
trunk/boost/graph/detail/compressed_sparse_row_struct.hpp | 204 ++++++++++++--
trunk/boost/graph/detail/indexed_properties.hpp | 19 +
trunk/boost/graph/distributed/compressed_sparse_row_graph.hpp | 10
trunk/libs/graph/test/csr_graph_test.cpp | 125 ++++----
5 files changed, 687 insertions(+), 220 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-09 17:29:17 EDT (Wed, 09 Sep 2009)
@@ -216,7 +216,7 @@
public:
/* At this time, the compressed sparse row graph can only be used to
- * create a directed graph. In the future, bidirectional and
+ * create directed and bidirectional graphs. In the future,
* undirected CSR graphs will also be supported.
*/
// BOOST_STATIC_ASSERT((is_same<Directed, directedS>::value));
@@ -224,7 +224,7 @@
// Concept requirements:
// For Graph
typedef Vertex vertex_descriptor;
- typedef csr_edge_descriptor<Vertex, EdgeIndex> edge_descriptor;
+ typedef detail::csr_edge_descriptor<Vertex, EdgeIndex> edge_descriptor;
typedef directed_tag directed_category;
typedef allow_parallel_edge_tag edge_parallel_category;
@@ -272,32 +272,6 @@
: 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 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_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 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_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
template <typename MultiPassInputIterator>
compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
@@ -355,31 +329,6 @@
}
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
- // 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_forward.assign_from_sorted_edges(edge_begin, edge_end, global_to_local, source_pred, numlocalverts, numedges_or_zero);
- inherited_vertex_properties::resize(numlocalverts);
- }
-
- // 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) {
- 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);
- }
-
#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
// From number of vertices and sorted list of edges (deprecated
@@ -542,7 +491,7 @@
std::vector<vertex_descriptor> sources, targets;
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());
+ m_forward.assign_sources_and_targets_global(sources, targets, numverts, boost::identity_property_map());
}
// From number of vertices and single-pass range of unsorted edges and
@@ -607,29 +556,6 @@
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
- // 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) {
- m_forward.assign_sources_and_targets_global(sources, targets, numverts, global_to_local);
- }
-
- // 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<edge_bundled>& edge_props,
- vertices_size_type numverts,
- GlobalToLocal global_to_local) {
- m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numverts, global_to_local);
- }
-
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
@@ -849,50 +775,383 @@
GraphProperty m_property;
};
-template<typename Vertex, typename EdgeIndex>
-class csr_edge_descriptor
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+// Bidir is only supported in this mode
+template<typename VertexProperty,
+ typename EdgeProperty,
+ typename GraphProperty,
+ typename Vertex,
+ typename EdgeIndex>
+class compressed_sparse_row_graph<bidirectionalS, VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex>
+ : public detail::indexed_vertex_properties<BOOST_BIDIR_CSR_GRAPH_TYPE,
+ VertexProperty, Vertex>
{
public:
- Vertex src;
- EdgeIndex idx;
+ typedef detail::indexed_vertex_properties<compressed_sparse_row_graph,
+ VertexProperty, Vertex>
+ inherited_vertex_properties;
+
+ public:
+ // For Property Graph
+ typedef GraphProperty graph_property_type;
+
+ typedef detail::compressed_sparse_row_structure<EdgeProperty, Vertex, EdgeIndex> forward_type;
+ typedef EdgeIndex /* typename boost::mpl::if_c<boost::is_same<EdgeProperty, boost::no_property>, boost::no_property, EdgeIndex> */ backward_edge_property;
+ typedef detail::compressed_sparse_row_structure<backward_edge_property, Vertex, EdgeIndex> backward_type;
+
+ public:
+ // Concept requirements:
+ // For Graph
+ typedef Vertex vertex_descriptor;
+ typedef detail::csr_edge_descriptor<Vertex, EdgeIndex> edge_descriptor;
+ typedef bidirectional_tag directed_category;
+ typedef allow_parallel_edge_tag edge_parallel_category;
+
+ class traversal_category: public incidence_graph_tag,
+ public bidirectional_graph_tag,
+ public adjacency_graph_tag,
+ public vertex_list_graph_tag,
+ public edge_list_graph_tag {};
+
+ static vertex_descriptor null_vertex() { return vertex_descriptor(-1); }
+
+ // For VertexListGraph
+ typedef counting_iterator<Vertex> vertex_iterator;
+ typedef Vertex vertices_size_type;
+
+ // For EdgeListGraph
+ typedef EdgeIndex edges_size_type;
- csr_edge_descriptor(Vertex src, EdgeIndex idx): src(src), idx(idx) {}
- csr_edge_descriptor(): src(0), idx(0) {}
+ // For IncidenceGraph
+ typedef detail::csr_out_edge_iterator<compressed_sparse_row_graph> out_edge_iterator;
+ typedef EdgeIndex degree_size_type;
- bool operator==(const csr_edge_descriptor& e) const {return idx == e.idx;}
- bool operator!=(const csr_edge_descriptor& e) const {return idx != e.idx;}
- bool operator<(const csr_edge_descriptor& e) const {return idx < e.idx;}
- bool operator>(const csr_edge_descriptor& e) const {return idx > e.idx;}
- bool operator<=(const csr_edge_descriptor& e) const {return idx <= e.idx;}
- bool operator>=(const csr_edge_descriptor& e) const {return idx >= e.idx;}
+ // For AdjacencyGraph
+ typedef typename std::vector<Vertex>::const_iterator adjacency_iterator;
+
+ // For EdgeListGraph
+ typedef detail::csr_edge_iterator<compressed_sparse_row_graph> edge_iterator;
+
+ // For BidirectionalGraph (not implemented)
+ typedef detail::csr_in_edge_iterator<compressed_sparse_row_graph> in_edge_iterator;
+
+ // 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_property() {}
+
+ // With numverts vertices
+ compressed_sparse_row_graph(vertices_size_type numverts)
+ : inherited_vertex_properties(numverts),
+ m_forward(numverts), m_backward(numverts) {}
- template<typename Archiver>
- void serialize(Archiver& ar, const unsigned int /*version*/)
+ private:
+
+ void set_up_backward_property_links() {
+ std::pair<edge_iterator, edge_iterator> e = edges(*this);
+ m_backward.assign_unsorted_multi_pass_edges
+ (detail::transpose_edges(
+ detail::make_edge_to_index_pair_iter
+ (*this, get(vertex_index, *this), e.first)),
+ detail::transpose_edges(
+ detail::make_edge_to_index_pair_iter
+ (*this, get(vertex_index, *this), e.second)),
+ boost::counting_iterator<EdgeIndex>(0),
+ m_forward.m_rowstart.size() - 1,
+ identity_property_map(),
+ keep_all());
+ }
+
+ public:
+
+ // From number of vertices and unsorted list of edges
+ template <typename MultiPassInputIterator>
+ compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
+ MultiPassInputIterator edge_begin,
+ MultiPassInputIterator edge_end,
+ vertices_size_type numverts,
+ const GraphProperty& prop = GraphProperty())
+ : inherited_vertex_properties(numverts), m_property(prop)
{
- ar & src & idx;
+ m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numverts, identity_property_map(), keep_all());
+ set_up_backward_property_links();
}
-};
-template<typename Vertex, typename EdgeIndex>
-struct hash<csr_edge_descriptor<Vertex, EdgeIndex> >
-{
- std::size_t operator()(csr_edge_descriptor<Vertex, EdgeIndex> const& x) const
+ // From number of vertices and unsorted list of edges, plus edge properties
+ template <typename MultiPassInputIterator, typename EdgePropertyIterator>
+ compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
+ MultiPassInputIterator edge_begin,
+ MultiPassInputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ const GraphProperty& prop = GraphProperty())
+ : inherited_vertex_properties(numverts), m_forward(), m_property(prop)
{
- std::size_t hash = hash_value(x.src);
- hash_combine(hash, x.idx);
- return hash;
+ m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numverts, identity_property_map(), keep_all());
+ set_up_backward_property_links();
}
+
+ // From number of vertices and unsorted list of edges, with filter and
+ // global-to-local map
+ 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 SourcePred& source_pred,
+ const GraphProperty& prop = GraphProperty())
+ : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop)
+ {
+ m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numlocalverts, global_to_local, source_pred);
+ set_up_backward_property_links();
+ }
+
+ // 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 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 SourcePred& source_pred,
+ const GraphProperty& prop = GraphProperty())
+ : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop)
+ {
+ m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numlocalverts, global_to_local, source_pred);
+ set_up_backward_property_links();
+ }
+
+ // Requires IncidenceGraph and a vertex index map
+ template<typename Graph, typename VertexIndexMap>
+ compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi,
+ vertices_size_type numverts,
+ edges_size_type numedges)
+ : m_property()
+ {
+ assign(g, vi, numverts, numedges);
+ inherited_vertex_properties::resize(numverts);
+ }
+
+ // Requires VertexListGraph and EdgeListGraph
+ template<typename Graph, typename VertexIndexMap>
+ compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi)
+ : m_property()
+ {
+ typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
+ if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
+ numedges *= 2; // Double each edge (actual doubling done by out_edges function)
+ }
+ 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
+ template<typename Graph>
+ explicit compressed_sparse_row_graph(const Graph& g)
+ : m_property()
+ {
+ typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
+ 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);
+ }
+
+ // 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_forward.assign(g, vi, numverts, numedges);
+ inherited_vertex_properties::resize(numverts);
+ }
+
+ // Requires the above, plus VertexListGraph and EdgeListGraph
+ template<typename Graph, typename VertexIndexMap>
+ void assign(const Graph& g, const VertexIndexMap& vi)
+ {
+ typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
+ if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
+ numedges *= 2; // Double each edge (actual doubling done by out_edges function)
+ }
+ 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.
+ template<typename Graph>
+ void assign(const Graph& g)
+ {
+ typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
+ if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
+ numedges *= 2; // Double each edge (actual doubling done by out_edges function)
+ }
+ vertices_size_type numverts = num_vertices(g);
+ m_forward.assign(g, get(vertex_index, g), numverts, numedges);
+ inherited_vertex_properties::resize(numverts);
+ }
+
+ // 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) {
+ m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, global_to_local);
+ }
+
+ template <typename BidirectionalIteratorOrig, typename EPIterOrig>
+ void
+ add_edges_sorted_internal(
+ BidirectionalIteratorOrig first_sorted,
+ BidirectionalIteratorOrig last_sorted,
+ EPIterOrig ep_iter_sorted) {
+ 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
+ template <typename BidirectionalIteratorOrig>
+ void
+ add_edges_sorted_internal(
+ BidirectionalIteratorOrig first_sorted,
+ BidirectionalIteratorOrig last_sorted) {
+ m_forward.add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<edge_bundled>());
+ }
+
+ template <typename BidirectionalIteratorOrig, typename GlobalToLocal>
+ void
+ add_edges_sorted_internal_global(
+ BidirectionalIteratorOrig first_sorted,
+ BidirectionalIteratorOrig last_sorted,
+ const GlobalToLocal& 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,
+ typename GlobalToLocal>
+ void
+ add_edges_sorted_internal_global(
+ BidirectionalIteratorOrig first_sorted,
+ BidirectionalIteratorOrig last_sorted,
+ EPIterOrig ep_iter_sorted,
+ const GlobalToLocal& 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
+ template <typename InputIterator, typename GlobalToLocal>
+ inline void
+ add_edges_internal(InputIterator first, InputIterator last,
+ const GlobalToLocal& global_to_local) {
+ typedef compressed_sparse_row_graph Graph;
+ typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
+ typedef typename boost::graph_traits<Graph>::vertices_size_type vertex_num;
+ typedef typename boost::graph_traits<Graph>::edges_size_type edge_num;
+ typedef std::vector<std::pair<vertex_t, vertex_t> > edge_vector_t;
+ edge_vector_t new_edges(first, last);
+ if (new_edges.empty()) return;
+ std::sort(new_edges.begin(), new_edges.end());
+ 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) {
+ this->add_edges_internal(first, last, identity_property_map());
+ }
+
+ // Add edges from a range of (source, target) pairs and edge properties that
+ // are unsorted
+ template <typename InputIterator, typename EPIterator, typename GlobalToLocal>
+ inline void
+ add_edges_internal(InputIterator first, InputIterator last,
+ EPIterator ep_iter, EPIterator ep_iter_end,
+ const GlobalToLocal& global_to_local) {
+ typedef compressed_sparse_row_graph Graph;
+ typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
+ typedef typename boost::graph_traits<Graph>::vertices_size_type vertex_num;
+ typedef typename boost::graph_traits<Graph>::edges_size_type edge_num;
+ typedef std::pair<vertex_t, vertex_t> vertex_pair;
+ typedef std::vector<
+ boost::tuple<vertex_pair,
+ edge_bundled> >
+ edge_vector_t;
+ edge_vector_t new_edges
+ (boost::make_zip_iterator(boost::make_tuple(first, ep_iter)),
+ boost::make_zip_iterator(boost::make_tuple(last, ep_iter_end)));
+ if (new_edges.empty()) return;
+ std::sort(new_edges.begin(), new_edges.end(),
+ boost::detail::compare_first<
+ std::less<vertex_pair> >());
+ m_forward.add_edges_sorted_internal
+ (boost::make_transform_iterator(
+ new_edges.begin(),
+ boost::detail::my_tuple_get_class<0, vertex_pair>()),
+ boost::make_transform_iterator(
+ new_edges.end(),
+ boost::detail::my_tuple_get_class<0, vertex_pair>()),
+ boost::make_transform_iterator(
+ new_edges.begin(),
+ boost::detail::my_tuple_get_class
+ <1, edge_bundled>()),
+ global_to_local);
+ }
+
+ // Add edges from a range of (source, target) pairs and edge properties that
+ // are unsorted
+ template <typename InputIterator, typename EPIterator>
+ inline void
+ add_edges_internal(InputIterator first, InputIterator last,
+ EPIterator ep_iter, EPIterator ep_iter_end) {
+ this->add_edges_internal(first, last, ep_iter, ep_iter_end, identity_property_map());
+ }
+
+ using inherited_vertex_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;}
+ typename forward_type::inherited_edge_properties& edge_properties() { return m_forward; }
+ const typename forward_type::inherited_edge_properties& edge_properties() const { return m_forward; }
+
+ forward_type m_forward;
+ backward_type m_backward;
+ GraphProperty m_property;
};
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// Construction functions
-template<BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS>
+template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
inline Vertex
-add_vertex(BOOST_DIR_CSR_GRAPH_TYPE& g) {
- 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;
+add_vertex(BOOST_CSR_GRAPH_TYPE& g) {
+ add_vertex(g, typename BOOST_CSR_GRAPH_TYPE::vertex_bundled());
}
template<BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS>
@@ -900,7 +1159,18 @@
add_vertex(BOOST_DIR_CSR_GRAPH_TYPE& g,
typename BOOST_DIR_CSR_GRAPH_TYPE::vertex_bundled const& p) {
Vertex old_num_verts_plus_one = g.m_forward.m_rowstart.size();
- g.m_forward.m_rowstart.push_back(EdgeIndex(0));
+ g.m_forward.m_rowstart.push_back(g.m_forward.m_rowstart.back());
+ g.vertex_properties().push_back(p);
+ return old_num_verts_plus_one - 1;
+}
+
+template<BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS>
+inline Vertex
+add_vertex(BOOST_BIDIR_CSR_GRAPH_TYPE& g,
+ typename BOOST_BIDIR_CSR_GRAPH_TYPE::vertex_bundled const& p) {
+ Vertex old_num_verts_plus_one = g.m_forward.m_rowstart.size();
+ g.m_forward.m_rowstart.push_back(g.m_forward.m_rowstart.back());
+ g.m_backward.m_rowstart.push_back(g.m_backward.m_rowstart.back());
g.vertex_properties().push_back(p);
return old_num_verts_plus_one - 1;
}
@@ -911,6 +1181,7 @@
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.m_backward.m_rowstart.resize(old_num_verts_plus_one + count, numedges);
g.vertex_properties().resize(num_vertices(g));
return old_num_verts_plus_one - 1;
}
@@ -1070,6 +1341,21 @@
return g.m_forward.m_column[e.idx];
}
+namespace detail {
+ template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
+ inline EdgeIndex get_actual_row_start
+ (const BOOST_CSR_GRAPH_TYPE& g,
+ EdgeIndex rowstart_i_minus_1, EdgeIndex rowstart_i)
+ {
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+ return rowstart_i;
+#else
+ // Special case to allow incremental construction
+ return (std::max)(rowstart_i_minus_1, rowstart_i);
+#endif
+ }
+}
+
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
inline std::pair<typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator,
typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator>
@@ -1079,14 +1365,9 @@
typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator it;
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)));
-#else
- // Special case to allow incremental construction
- return std::make_pair(it(ed(v, v_row_start)),
- it(ed(v, (std::max)(v_row_start, next_row_start))));
-#endif
+ it(ed(v, detail::get_actual_row_start
+ (g, v_row_start, next_row_start))));
}
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
@@ -1095,14 +1376,35 @@
{
EdgeIndex v_row_start = g.m_forward.m_rowstart[v];
EdgeIndex next_row_start = g.m_forward.m_rowstart[v + 1];
+ return detail::get_actual_row_start(g, v_row_start, next_row_start) - v_row_start;
+}
+
#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+
+template<BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS>
+inline std::pair<typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator,
+ typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator>
+in_edges(Vertex v, const BOOST_BIDIR_CSR_GRAPH_TYPE& g)
+{
+ typedef typename BOOST_BIDIR_CSR_GRAPH_TYPE::edge_descriptor ed;
+ typedef typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator it;
+ EdgeIndex v_row_start = g.m_backward.m_rowstart[v];
+ EdgeIndex next_row_start = g.m_backward.m_rowstart[v + 1];
+ return std::make_pair(it(ed(v, v_row_start)),
+ it(ed(v, next_row_start)));
+}
+
+template<BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS>
+inline EdgeIndex
+in_degree(Vertex v, const BOOST_BIDIR_CSR_GRAPH_TYPE& g)
+{
+ EdgeIndex v_row_start = g.m_backward.m_rowstart[v];
+ EdgeIndex next_row_start = g.m_backward.m_rowstart[v + 1];
return next_row_start - v_row_start;
-#else
- // Special case to allow incremental construction
- return (std::max)(v_row_start, next_row_start) - v_row_start;
-#endif
}
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+
// From AdjacencyGraph
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
inline std::pair<typename BOOST_CSR_GRAPH_TYPE::adjacency_iterator,
@@ -1111,15 +1413,10 @@
{
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_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_forward.m_column.begin() + v_row_start,
g.m_forward.m_column.begin() +
- (std::max)(v_row_start, next_row_start));
-#endif
+ detail::get_actual_row_start
+ (g, v_row_start, next_row_start));
}
// Extra, common functions
Modified: trunk/boost/graph/detail/compressed_sparse_row_struct.hpp
==============================================================================
--- trunk/boost/graph/detail/compressed_sparse_row_struct.hpp (original)
+++ trunk/boost/graph/detail/compressed_sparse_row_struct.hpp 2009-09-09 17:29:17 EDT (Wed, 09 Sep 2009)
@@ -48,12 +48,12 @@
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 {
+ // Forward declaration of CSR edge descriptor type, needed to pass to
+ // indexed_edge_properties.
+ template<typename Vertex, typename EdgeIndex>
+ class csr_edge_descriptor;
+
/** Compressed sparse row graph internal structure.
*
* Vertex and EdgeIndex should be unsigned integral types and should
@@ -403,6 +403,30 @@
};
+ template<typename Vertex, typename EdgeIndex>
+ class csr_edge_descriptor
+ {
+ public:
+ Vertex src;
+ EdgeIndex idx;
+
+ csr_edge_descriptor(Vertex src, EdgeIndex idx): src(src), idx(idx) {}
+ csr_edge_descriptor(): src(0), idx(0) {}
+
+ bool operator==(const csr_edge_descriptor& e) const {return idx == e.idx;}
+ bool operator!=(const csr_edge_descriptor& e) const {return idx != e.idx;}
+ bool operator<(const csr_edge_descriptor& e) const {return idx < e.idx;}
+ bool operator>(const csr_edge_descriptor& e) const {return idx > e.idx;}
+ bool operator<=(const csr_edge_descriptor& e) const {return idx <= e.idx;}
+ bool operator>=(const csr_edge_descriptor& e) const {return idx >= e.idx;}
+
+ template<typename Archiver>
+ void serialize(Archiver& ar, const unsigned int /*version*/)
+ {
+ ar & src & idx;
+ }
+ };
+
// Common out edge and edge iterators
template<typename CSRGraph>
class csr_out_edge_iterator
@@ -442,60 +466,180 @@
template<typename CSRGraph>
class csr_edge_iterator
+ : public iterator_facade<csr_edge_iterator<CSRGraph>,
+ typename CSRGraph::edge_descriptor,
+ std::input_iterator_tag,
+ typename CSRGraph::edge_descriptor>
{
- public:
- typedef std::forward_iterator_tag iterator_category;
+ private:
typedef typename CSRGraph::edge_descriptor edge_descriptor;
typedef typename CSRGraph::edges_size_type EdgeIndex;
- typedef edge_descriptor value_type;
-
- typedef const edge_descriptor* pointer;
-
- typedef edge_descriptor reference;
- typedef typename int_t<CHAR_BIT * sizeof(EdgeIndex)>::fast difference_type;
+ public:
csr_edge_iterator() : rowstart_array(0), current_edge(), end_of_this_vertex(0) {}
csr_edge_iterator(const CSRGraph& graph,
edge_descriptor current_edge,
- EdgeIndex end_of_this_vertex)
+ EdgeIndex end_of_this_vertex)
: rowstart_array(&graph.m_forward.m_rowstart[0]), current_edge(current_edge),
end_of_this_vertex(end_of_this_vertex) {}
- // From InputIterator
- reference operator*() const { return current_edge; }
- pointer operator->() const { return ¤t_edge; }
+ private:
+ friend class boost::iterator_core_access;
+
+ edge_descriptor dereference() const {return current_edge;}
- bool operator==(const csr_edge_iterator& o) const {
+ bool equal(const csr_edge_iterator& o) const {
return current_edge == o.current_edge;
}
- bool operator!=(const csr_edge_iterator& o) const {
- return current_edge != o.current_edge;
- }
- csr_edge_iterator& operator++() {
+ void increment() {
++current_edge.idx;
while (current_edge.idx == end_of_this_vertex) {
++current_edge.src;
end_of_this_vertex = rowstart_array[current_edge.src + 1];
}
- return *this;
- }
-
- csr_edge_iterator operator++(int) {
- csr_edge_iterator temp = *this;
- ++*this;
- return temp;
}
- private:
const EdgeIndex* rowstart_array;
edge_descriptor current_edge;
EdgeIndex end_of_this_vertex;
};
+ // Only for bidirectional graphs
+ template<typename CSRGraph>
+ class csr_in_edge_iterator
+ : public iterator_facade<csr_in_edge_iterator<CSRGraph>,
+ typename CSRGraph::edge_descriptor,
+ std::input_iterator_tag,
+ typename CSRGraph::edge_descriptor>
+ {
+ public:
+ typedef typename CSRGraph::edges_size_type EdgeIndex;
+ typedef typename CSRGraph::edge_descriptor edge_descriptor;
+
+ csr_in_edge_iterator() {}
+ // Implicit copy constructor OK
+ csr_in_edge_iterator(const CSRGraph& graph,
+ EdgeIndex index_in_backward_graph)
+ : m_graph(graph), m_index_in_backward_graph(index_in_backward_graph) {}
+
+ private:
+ // iterator_facade requirements
+ edge_descriptor dereference() const {
+ return edge_descriptor(
+ m_graph.m_backward.m_column[m_index_in_backward_graph],
+ m_graph.m_backward.m_edge_properties[m_index_in_backward_graph]);
+ }
+
+ bool equal(const csr_in_edge_iterator& other) const
+ { return m_index_in_backward_graph == other.m_index_in_backward_graph; }
+
+ void increment() { ++m_index_in_backward_graph; }
+ void decrement() { --m_index_in_backward_graph; }
+ void advance(std::ptrdiff_t n) { m_index_in_backward_graph += n; }
+
+ std::ptrdiff_t distance_to(const csr_in_edge_iterator& other) const
+ { return other.m_index_in_backward_graph - m_index_in_backward_graph; }
+
+ EdgeIndex m_index_in_backward_graph;
+ const CSRGraph& m_graph;
+
+ friend class iterator_core_access;
+ };
+
+ template <typename A, typename B>
+ struct transpose_pair {
+ typedef std::pair<B, A> result_type;
+ result_type operator()(const std::pair<A, B>& p) const {
+ return result_type(p.second, p.first);
+ }
+ };
+
+ template <typename Iter>
+ struct transpose_iterator_gen {
+ typedef typename std::iterator_traits<Iter>::value_type vt;
+ typedef typename vt::first_type first_type;
+ typedef typename vt::second_type second_type;
+ typedef transpose_pair<first_type, second_type> transpose;
+ typedef boost::transform_iterator<transpose, Iter> type;
+ static type make(Iter it) {
+ return type(it, transpose());
+ }
+ };
+
+ template <typename Iter>
+ typename transpose_iterator_gen<Iter>::type transpose_edges(Iter i) {
+ return transpose_iterator_gen<Iter>::make(i);
+ }
+
+ template<typename GraphT, typename VertexIndexMap>
+ class edge_to_index_pair
+ {
+ typedef typename boost::graph_traits<GraphT>::vertices_size_type
+ vertices_size_type;
+ typedef typename boost::graph_traits<GraphT>::edge_descriptor edge_descriptor;
+
+ public:
+ typedef std::pair<vertices_size_type, vertices_size_type> result_type;
+
+ edge_to_index_pair() : g(0), index() { }
+ edge_to_index_pair(const GraphT& g, const VertexIndexMap& index)
+ : g(&g), index(index)
+ { }
+
+ result_type operator()(edge_descriptor e) const
+ {
+ return result_type(get(index, source(e, *g)), get(index, target(e, *g)));
+ }
+
+ private:
+ const GraphT* g;
+ VertexIndexMap index;
+ };
+
+ template<typename GraphT, typename VertexIndexMap>
+ edge_to_index_pair<GraphT, VertexIndexMap>
+ make_edge_to_index_pair(const GraphT& g, const VertexIndexMap& index)
+ {
+ return edge_to_index_pair<GraphT, VertexIndexMap>(g, index);
+ }
+
+ template<typename GraphT>
+ edge_to_index_pair
+ <GraphT,
+ typename boost::property_map<GraphT,boost::vertex_index_t>::const_type>
+ make_edge_to_index_pair(const GraphT& g)
+ {
+ typedef typename boost::property_map<GraphT,
+ boost::vertex_index_t>::const_type
+ VertexIndexMap;
+ return edge_to_index_pair<GraphT, VertexIndexMap>(g,
+ get(boost::vertex_index,
+ g));
+ }
+
+ template<typename GraphT, typename VertexIndexMap, typename Iter>
+ boost::transform_iterator<edge_to_index_pair<GraphT, VertexIndexMap>, Iter>
+ make_edge_to_index_pair_iter(const GraphT& g, const VertexIndexMap& index,
+ Iter it) {
+ return boost::transform_iterator<edge_to_index_pair<GraphT, VertexIndexMap>, Iter>(it, edge_to_index_pair<GraphT, VertexIndexMap>(g, index));
+ }
} // namespace detail
+
+ template<typename Vertex, typename EdgeIndex>
+ struct hash<detail::csr_edge_descriptor<Vertex, EdgeIndex> >
+ {
+ std::size_t operator()
+ (detail::csr_edge_descriptor<Vertex, EdgeIndex> const& x) const
+ {
+ std::size_t hash = hash_value(x.src);
+ hash_combine(hash, x.idx);
+ return hash;
+ }
+ };
+
} // namespace boost
#endif // BOOST_GRAPH_COMPRESSED_SPARSE_ROW_STRUCT_HPP
Modified: trunk/boost/graph/detail/indexed_properties.hpp
==============================================================================
--- trunk/boost/graph/detail/indexed_properties.hpp (original)
+++ trunk/boost/graph/detail/indexed_properties.hpp 2009-09-09 17:29:17 EDT (Wed, 09 Sep 2009)
@@ -179,6 +179,10 @@
m_edge_properties.begin() + dest_begin + (src_end - src_begin));
}
+ typedef typename std::vector<Property>::iterator iterator;
+ iterator begin() {return m_edge_properties.begin();}
+ iterator end() {return m_edge_properties.end();}
+
private:
// Access to the derived object
Derived& derived() { return *static_cast<Derived*>(this); }
@@ -190,6 +194,17 @@
std::vector<Property> m_edge_properties;
};
+struct dummy_no_property_iterator
+: public boost::iterator_facade<dummy_no_property_iterator, no_property, std::random_access_iterator_tag> {
+ mutable no_property prop;
+ no_property& dereference() const {return prop;}
+ bool equal(const dummy_no_property_iterator&) const {return true;}
+ void increment() {}
+ void decrement() {}
+ void advance(std::ptrdiff_t) {}
+ std::ptrdiff_t distance_to(const dummy_no_property_iterator) const {return 0;}
+};
+
template<typename Derived, typename Descriptor>
class indexed_edge_properties<Derived, void, Descriptor>
{
@@ -216,6 +231,10 @@
void push_back(const edge_push_back_type&) { }
void move_range(std::size_t src_begin, std::size_t src_end, std::size_t dest_begin) {}
+ typedef dummy_no_property_iterator iterator;
+ iterator begin() {return dummy_no_property_iterator();}
+ iterator end() {return dummy_no_property_iterator();}
+
};
}
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-09 17:29:17 EDT (Wed, 09 Sep 2009)
@@ -1856,7 +1856,7 @@
// Readable Property Map concept requirements
typedef std::pair<ProcessID, EdgeIndex> value_type;
typedef value_type reference;
- typedef csr_edge_descriptor<Vertex, EdgeIndex> key_type;
+ typedef detail::csr_edge_descriptor<Vertex, EdgeIndex> key_type;
typedef readable_property_map_tag category;
};
@@ -2144,21 +2144,21 @@
namespace mpi {
template<typename Vertex, typename EdgeIndex>
- struct is_mpi_datatype<csr_edge_descriptor<Vertex, EdgeIndex> >
+ struct is_mpi_datatype<boost::detail::csr_edge_descriptor<Vertex, EdgeIndex> >
: mpl::true_ { };
}
namespace serialization {
template<typename Vertex, typename EdgeIndex>
- struct is_bitwise_serializable<csr_edge_descriptor<Vertex, EdgeIndex> >
+ struct is_bitwise_serializable<boost::detail::csr_edge_descriptor<Vertex, EdgeIndex> >
: mpl::true_ { };
template<typename Vertex, typename EdgeIndex>
- struct implementation_level<csr_edge_descriptor<Vertex, EdgeIndex> >
+ struct implementation_level<boost::detail::csr_edge_descriptor<Vertex, EdgeIndex> >
: mpl::int_<object_serializable> {} ;
template<typename Vertex, typename EdgeIndex>
- struct tracking_level<csr_edge_descriptor<Vertex, EdgeIndex> >
+ struct tracking_level<boost::detail::csr_edge_descriptor<Vertex, EdgeIndex> >
: mpl::int_<track_never> {} ;
}
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-09 17:29:17 EDT (Wed, 09 Sep 2009)
@@ -49,6 +49,9 @@
typedef boost::compressed_sparse_row_graph<boost::directedS, VertexData>
CSRGraphT;
+typedef boost::compressed_sparse_row_graph<boost::bidirectionalS, VertexData>
+ BidirCSRGraphT;
+
template <class G1, class VI1, class G2, class VI2, class IsomorphismMap>
void assert_graphs_equal(const G1& g1, const VI1& vi1,
const G2& g2, const VI2& vi2,
@@ -113,83 +116,81 @@
}
}
-template<typename GraphT, typename VertexIndexMap>
-class edge_to_index_pair
-{
- typedef typename boost::graph_traits<GraphT>::vertices_size_type
- vertices_size_type;
- typedef typename boost::graph_traits<GraphT>::edge_descriptor edge_descriptor;
-
- public:
- typedef std::pair<vertices_size_type, vertices_size_type> result_type;
-
- edge_to_index_pair() : g(0), index() { }
- edge_to_index_pair(const GraphT& g, const VertexIndexMap& index)
- : g(&g), index(index)
- { }
-
- result_type operator()(edge_descriptor e) const
- {
- return result_type(get(index, source(e, *g)), get(index, target(e, *g)));
- }
-
- private:
- const GraphT* g;
- VertexIndexMap index;
-};
-
-template<typename GraphT, typename VertexIndexMap>
-edge_to_index_pair<GraphT, VertexIndexMap>
-make_edge_to_index_pair(const GraphT& g, const VertexIndexMap& index)
-{
- return edge_to_index_pair<GraphT, VertexIndexMap>(g, index);
-}
-
-template<typename GraphT>
-edge_to_index_pair
- <GraphT,
- typename boost::property_map<GraphT,boost::vertex_index_t>::const_type>
-make_edge_to_index_pair(const GraphT& g)
-{
- typedef typename boost::property_map<GraphT,
- boost::vertex_index_t>::const_type
- VertexIndexMap;
- return edge_to_index_pair<GraphT, VertexIndexMap>(g,
- get(boost::vertex_index,
- g));
-}
-
-void check_consistency(const CSRGraphT& g) {
+template <typename Structure>
+void check_consistency_one(const Structure& g) {
// Do a bunch of tests on the graph internal data
#ifndef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// Check that m_last_source is valid
- BOOST_CHECK(g.m_last_source <= num_vertices(g));
+ BOOST_CHECK(g.m_last_source <= g.m_rowstart.size() - 1);
#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_forward.m_rowstart[0] == 0);
- for (CSRGraphT::vertices_size_type i = 0;
+ BOOST_CHECK(g.m_rowstart[0] == 0);
+ for (size_t i = 0;
#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
- i < num_vertices(g);
+ i < g.m_rowstart.size() - 1;
#else // !BOOST_GRAPH_USE_NEW_CSR_INTERFACE
i < g.m_last_source;
#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
++i) {
- 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));
+ BOOST_CHECK(g.m_rowstart[i + 1] >= g.m_rowstart[i]);
+ BOOST_CHECK(g.m_rowstart[i + 1] <= g.m_rowstart.back());
}
#ifndef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
- for (CSRGraphT::vertices_size_type i = g.m_last_source + 1;
- i < g.m_forward.m_rowstart.size(); ++i) {
+ for (size_t i = g.m_last_source + 1;
+ i < g.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_forward.m_column[i] < num_vertices(g));
+ for (size_t i = 0; i < g.m_rowstart.back(); ++i) {
+ BOOST_CHECK(g.m_column[i] < g.m_rowstart.size() - 1);
}
}
+template <typename Graph>
+void check_consistency_dispatch(const Graph& g,
+ boost::incidence_graph_tag) {
+ check_consistency_one(g.m_forward);
+}
+
+template <class G>
+void assert_bidir_equal_in_both_dirs(const G& g) {
+ BOOST_CHECK (g.m_forward.m_rowstart.size() == g.m_backward.m_rowstart.size());
+ BOOST_CHECK (g.m_forward.m_column.size() == g.m_backward.m_column.size());
+ typedef typename boost::graph_traits<G>::vertex_descriptor Vertex;
+ typedef typename boost::graph_traits<G>::edges_size_type EdgeIndex;
+ std::vector<boost::tuple<EdgeIndex, Vertex, Vertex> > edges_forward, edges_backward;
+ for (Vertex i = 0; i < g.m_forward.m_rowstart.size() - 1; ++i) {
+ for (EdgeIndex j = g.m_forward.m_rowstart[i];
+ j < g.m_forward.m_rowstart[i + 1]; ++j) {
+ edges_forward.push_back(boost::make_tuple(j, i, g.m_forward.m_column[j]));
+ }
+ }
+ for (Vertex i = 0; i < g.m_backward.m_rowstart.size() - 1; ++i) {
+ for (EdgeIndex j = g.m_backward.m_rowstart[i];
+ j < g.m_backward.m_rowstart[i + 1]; ++j) {
+ edges_backward.push_back(boost::make_tuple(g.m_backward.m_edge_properties[j], g.m_backward.m_column[j], i));
+ }
+ }
+ std::sort(edges_forward.begin(), edges_forward.end());
+ std::sort(edges_backward.begin(), edges_backward.end());
+ BOOST_CHECK (edges_forward == edges_backward);
+}
+
+template <typename Graph>
+void check_consistency_dispatch(const Graph& g,
+ boost::bidirectional_graph_tag) {
+ check_consistency_one(g.m_forward);
+ check_consistency_one(g.m_backward);
+ assert_bidir_equal_in_both_dirs(g);
+}
+
+template <typename Graph>
+void check_consistency(const Graph& g) {
+ check_consistency_dispatch(g, typename boost::graph_traits<Graph>::traversal_category());
+}
+
template<typename OrigGraph>
void graph_test(const OrigGraph& g)
{
@@ -205,9 +206,9 @@
// Check constructing a graph from iterators
CSRGraphT g3(boost::edges_are_sorted,
boost::make_transform_iterator(edges(g2).first,
- make_edge_to_index_pair(g2)),
+ boost::detail::make_edge_to_index_pair(g2)),
boost::make_transform_iterator(edges(g2).second,
- make_edge_to_index_pair(g2)),
+ boost::detail::make_edge_to_index_pair(g2)),
num_vertices(g));
check_consistency(g3);
BOOST_CHECK((std::size_t)std::distance(edges(g3).first, edges(g3).second)
@@ -488,6 +489,12 @@
assert_graphs_equal(g, boost::identity_property_map(),
g2, boost::identity_property_map(),
boost::identity_property_map());
+ std::cout << "Testing bidir CSR graph built from unsorted edges" << std::endl;
+ BidirCSRGraphT g2b(boost::edges_are_unsorted_multi_pass, unsorted_edges, unsorted_edges + sizeof(unsorted_edges) / sizeof(*unsorted_edges), 6);
+ graph_test(g2b);
+ assert_graphs_equal(g, boost::identity_property_map(),
+ g2b, boost::identity_property_map(),
+ boost::identity_property_map());
std::cout << "Testing CSR graph built using add_edges" << std::endl;
// Test building a graph using add_edges on unsorted lists
CSRGraphT g3(boost::edges_are_unsorted, unsorted_edges, unsorted_edges, 6); // Empty range
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