Subject: [Boost-commit] svn:boost r53655 - in trunk: boost/graph libs/graph/doc libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-06-05 14:21:43
Author: jewillco
Date: 2009-06-05 14:21:42 EDT (Fri, 05 Jun 2009)
New Revision: 53655
URL: http://svn.boost.org/trac/boost/changeset/53655
Log:
Reverted old version of CSR graph for compatibility, with a #define to switch between the modes; cleaned up interface of new CSR graph; fixed tests and docs accordingly
Text files modified:
trunk/boost/graph/compressed_sparse_row_graph.hpp | 231 ++++++++++++++++++++++++++++++++++++---
trunk/libs/graph/doc/compressed_sparse_row.html | 119 +++++++++++++++++--
trunk/libs/graph/test/csr_graph_test.cpp | 28 ++++
3 files changed, 336 insertions(+), 42 deletions(-)
Modified: trunk/boost/graph/compressed_sparse_row_graph.hpp
==============================================================================
--- trunk/boost/graph/compressed_sparse_row_graph.hpp (original)
+++ trunk/boost/graph/compressed_sparse_row_graph.hpp 2009-06-05 14:21:42 EDT (Fri, 05 Jun 2009)
@@ -1,4 +1,4 @@
-// Copyright 2005-2006 The Trustees of Indiana University.
+// 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
@@ -38,6 +38,17 @@
# error You will need a compiler that conforms better to the C++ standard.
#endif
+#ifndef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+#warning "Using deprecated BGL compressed sparse row graph interface --"
+#warning "please see the documentation for the new interface and then"
+#warning "#define BOOST_GRAPH_USE_NEW_CSR_INTERFACE before including"
+#warning "<boost/graph/compressed_sparse_row_graph.hpp>"
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+
+#ifndef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+#define BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+#endif
+
namespace boost {
// A tag type indicating that the graph in question is a compressed
@@ -51,6 +62,14 @@
inline void edges_are_sorted(edges_are_sorted_internal) {}
typedef void (*edges_are_sorted_t)(edges_are_sorted_internal);
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+// A type (edges_are_unsorted_t) and a value (edges_are_unsorted) used to
+// indicate that the edge list passed into the CSR graph is not sorted by
+// source vertex.
+struct edges_are_unsorted_internal {};
+inline void edges_are_unsorted(edges_are_unsorted_internal) {}
+typedef void (*edges_are_unsorted_t)(edges_are_unsorted_internal);
+
// A type (construct_inplace_from_sources_and_targets_t) and a value
// (construct_inplace_from_sources_and_targets) used to indicate that mutable
// vectors of sources and targets (and possibly edge properties) are being used
@@ -73,6 +92,8 @@
inline void construct_inplace_from_sources_and_targets_global(construct_inplace_from_sources_and_targets_global_internal) {}
typedef void (*construct_inplace_from_sources_and_targets_global_t)(construct_inplace_from_sources_and_targets_global_internal);
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+
/****************************************************************************
* Local helper macros to reduce typing and clutter later on. *
****************************************************************************/
@@ -88,6 +109,7 @@
template<typename Vertex, typename EdgeIndex>
class csr_edge_descriptor;
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
namespace detail {
// Less-than operator for comparing only the first elements of two arbitrary
// Boost tuples
@@ -98,6 +120,7 @@
}
};
}
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
/** Compressed sparse row graph.
*
@@ -199,26 +222,34 @@
// Default constructor: an empty graph.
compressed_sparse_row_graph()
- : m_rowstart(1, EdgeIndex(0)), m_column(0), m_property(),
- m_last_source(0) {}
+ : 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
+ {}
// With numverts vertices
compressed_sparse_row_graph(vertices_size_type numverts)
: inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
- m_column(0), m_last_source(numverts)
+ 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;
}
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// From number of vertices and unsorted list of edges
template <typename MultiPassInputIterator>
- compressed_sparse_row_graph(MultiPassInputIterator edge_begin,
+ compressed_sparse_row_graph(edges_are_unsorted_t,
+ MultiPassInputIterator edge_begin,
MultiPassInputIterator edge_end,
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty())
: inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
- m_column(0), m_property(prop), m_last_source(numverts)
+ m_column(0), m_property(prop)
{
// Put the degree of each vertex v into m_rowstart[v + 1]
for (MultiPassInputIterator i = edge_begin; i != edge_end; ++i)
@@ -248,13 +279,14 @@
// From number of vertices and unsorted list of edges, plus edge properties
template <typename MultiPassInputIterator, typename EdgePropertyIterator>
- compressed_sparse_row_graph(MultiPassInputIterator edge_begin,
+ compressed_sparse_row_graph(edges_are_unsorted_t,
+ MultiPassInputIterator edge_begin,
MultiPassInputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty())
: inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
- m_column(0), m_property(prop), m_last_source(numverts)
+ m_column(0), m_property(prop)
{
// Put the degree of each vertex v into m_rowstart[v + 1]
for (MultiPassInputIterator i = edge_begin; i != edge_end; ++i)
@@ -284,8 +316,94 @@
inherited_edge_properties::write_by_index(insert_pos, *ep_iter);
}
}
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+
+#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+
+ // From number of vertices and sorted list of edges (deprecated
+ // interface)
+ template<typename InputIterator>
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty& prop = GraphProperty())
+ : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
+ m_column(0), m_property(prop), m_last_source(numverts)
+ {
+ // 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;
+ maybe_reserve_edge_list_storage(edge_begin, edge_end, category());
+ } else {
+ m_column.reserve(numedges);
+ }
+
+ EdgeIndex current_edge = 0;
+ Vertex current_vertex_plus_one = 1;
+ m_rowstart[0] = 0;
+ for (InputIterator ei = edge_begin; ei != edge_end; ++ei) {
+ Vertex src = ei->first;
+ Vertex tgt = ei->second;
+ for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)
+ m_rowstart[current_vertex_plus_one] = current_edge;
+ m_column.push_back(tgt);
+ ++current_edge;
+ }
+
+ // The remaining vertices have no edges
+ for (; current_vertex_plus_one != numverts + 1; ++current_vertex_plus_one)
+ m_rowstart[current_vertex_plus_one] = current_edge;
+
+ // Default-construct properties for edges
+ inherited_edge_properties::resize(m_column.size());
+ }
+
+ // From number of vertices and sorted list of edges (deprecated
+ // interface)
+ template<typename InputIterator, typename EdgePropertyIterator>
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty& prop = GraphProperty())
+ : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
+ m_column(0), m_property(prop), m_last_source(numverts)
+ {
+ // 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;
+ maybe_reserve_edge_list_storage(edge_begin, edge_end, category());
+ } else {
+ m_column.reserve(numedges);
+ }
+
+ EdgeIndex current_edge = 0;
+ Vertex current_vertex_plus_one = 1;
+ m_rowstart[0] = 0;
+ for (InputIterator ei = edge_begin; ei != edge_end; ++ei, ++ep_iter) {
+ Vertex src = ei->first;
+ Vertex tgt = ei->second;
+ for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)
+ m_rowstart[current_vertex_plus_one] = current_edge;
+ m_column.push_back(tgt);
+ inherited_edge_properties::push_back(*ep_iter);
+ ++current_edge;
+ }
+
+ // The remaining vertices have no edges
+ for (; current_vertex_plus_one != numverts + 1; ++current_vertex_plus_one)
+ m_rowstart[current_vertex_plus_one] = current_edge;
+ }
+
+#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
- // From number of vertices and sorted list of edges
+ // From number of vertices and sorted list of edges (new interface)
template<typename InputIterator>
compressed_sparse_row_graph(edges_are_sorted_t,
InputIterator edge_begin, InputIterator edge_end,
@@ -293,7 +411,10 @@
edges_size_type numedges = 0,
const GraphProperty& prop = GraphProperty())
: inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
- m_column(0), m_property(prop), m_last_source(numverts)
+ m_column(0), 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
@@ -326,7 +447,7 @@
inherited_edge_properties::resize(m_column.size());
}
- // From number of vertices and sorted list of edges
+ // From number of vertices and sorted list of edges (new interface)
template<typename InputIterator, typename EdgePropertyIterator>
compressed_sparse_row_graph(edges_are_sorted_t,
InputIterator edge_begin, InputIterator edge_end,
@@ -335,7 +456,10 @@
edges_size_type numedges = 0,
const GraphProperty& prop = GraphProperty())
: inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
- m_column(0), m_property(prop), m_last_source(numverts)
+ m_column(0), 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
@@ -366,6 +490,7 @@
m_rowstart[current_vertex_plus_one] = current_edge;
}
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// From number of vertices and mutable vectors of sources and targets;
// vectors are returned with unspecified contents but are guaranteed not to
// share storage with the constructed graph.
@@ -375,7 +500,7 @@
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty())
: inherited_vertex_properties(numverts), m_rowstart(),
- m_column(), m_property(prop), m_last_source(numverts)
+ m_column(), m_property(prop)
{
assign_sources_and_targets_global(sources, targets, numverts, boost::identity_property_map());
}
@@ -393,7 +518,7 @@
GlobalToLocal global_to_local,
const GraphProperty& prop = GraphProperty())
: inherited_vertex_properties(numlocalverts), m_rowstart(),
- m_column(), m_property(prop), m_last_source(numlocalverts)
+ m_column(), m_property(prop)
{
assign_sources_and_targets_global(sources, targets, numlocalverts, global_to_local);
}
@@ -408,7 +533,7 @@
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty())
: inherited_vertex_properties(numverts), m_rowstart(),
- m_column(), m_property(prop), m_last_source(numverts)
+ m_column(), m_property(prop)
{
assign_sources_and_targets_global(sources, targets, edge_props, numverts, boost::identity_property_map());
}
@@ -427,7 +552,7 @@
GlobalToLocal global_to_local,
const GraphProperty& prop = GraphProperty())
: inherited_vertex_properties(numlocalverts), m_rowstart(),
- m_column(), m_property(prop), m_last_source(numlocalverts)
+ m_column(), m_property(prop)
{
assign_sources_and_targets_global(sources, targets, edge_props, numlocalverts, global_to_local);
}
@@ -551,13 +676,15 @@
this->m_edge_properties.swap(edge_props);
}
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+
// Requires IncidenceGraph, a vertex index map, and a vertex(n, g) function
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(), m_last_source(0)
+ : m_property()
{
assign(g, vi, numverts, numedges);
}
@@ -565,7 +692,7 @@
// Requires VertexListGraph and EdgeListGraph
template<typename Graph, typename VertexIndexMap>
compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi)
- : m_property(), m_last_source(0)
+ : m_property()
{
assign(g, vi, num_vertices(g), num_edges(g));
}
@@ -573,7 +700,7 @@
// Requires vertex index map plus requirements of previous constructor
template<typename Graph>
explicit compressed_sparse_row_graph(const Graph& g)
- : m_property(), m_last_source(0)
+ : m_property()
{
assign(g, get(vertex_index, g), num_vertices(g), num_edges(g));
}
@@ -598,13 +725,24 @@
for (Vertex i = 0; i != numverts; ++i) {
m_rowstart[i] = current_edge;
g_vertex v = vertex(i, g);
+#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
@@ -633,7 +771,11 @@
std::vector<EdgeIndex> m_rowstart;
std::vector<Vertex> m_column;
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>
@@ -690,8 +832,9 @@
return old_num_verts_plus_one - 1;
}
-// This function requires that src be at least as large as the largest source
-// in the graph so far
+#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+// This function requires that (src, tgt) be lexicographically at least as
+// large as the largest edge in the graph so far
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
inline typename BOOST_CSR_GRAPH_TYPE::edge_descriptor
add_edge(Vertex src, Vertex tgt, BOOST_CSR_GRAPH_TYPE& g) {
@@ -724,7 +867,7 @@
g.edge_properties().push_back(p);
return typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(src, num_edges_orig);
}
-
+#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
// From VertexListGraph
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
@@ -835,6 +978,43 @@
return i;
}
+#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+// These require that the out edges from a vertex are sorted, which is only
+// guaranteed by the old interface
+
+// Unlike for an adjacency_matrix, edge_range and edge take lg(out_degree(i))
+// time
+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>
+edge_range(Vertex i, Vertex j, const BOOST_CSR_GRAPH_TYPE& g)
+{
+ typedef typename std::vector<Vertex>::const_iterator adj_iter;
+ typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter;
+ typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor edge_desc;
+ 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();
+ return std::make_pair(out_edge_iter(edge_desc(i, idx_begin)),
+ out_edge_iter(edge_desc(i, idx_end)));
+}
+
+template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
+inline std::pair<typename BOOST_CSR_GRAPH_TYPE::edge_descriptor, bool>
+edge(Vertex i, Vertex j, const BOOST_CSR_GRAPH_TYPE& g)
+{
+ typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter;
+ std::pair<out_edge_iter, out_edge_iter> range = edge_range(i, j, g);
+ if (range.first == range.second)
+ return std::make_pair(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(),
+ false);
+ else
+ return std::make_pair(*range.first, true);
+}
+#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+
// Find an edge given its index in the graph
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
inline typename BOOST_CSR_GRAPH_TYPE::edge_descriptor
@@ -844,7 +1024,14 @@
assert (idx < num_edges(g));
row_start_iter src_plus_1 =
std::upper_bound(g.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,
+#else // !BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+ g.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
Modified: trunk/libs/graph/doc/compressed_sparse_row.html
==============================================================================
--- trunk/libs/graph/doc/compressed_sparse_row.html (original)
+++ trunk/libs/graph/doc/compressed_sparse_row.html 2009-06-05 14:21:42 EDT (Fri, 05 Jun 2009)
@@ -1,7 +1,7 @@
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<!--
- Copyright (c) 2005 Trustees of Indiana University
+ Copyright (c) 2005-2009 Trustees of Indiana University
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at
@@ -47,6 +47,17 @@
or edges from a CSR graph. Use this format in high-performance
applications or for very large graphs that you do not need to
change.</p>
+
+ <p>There are two interfaces to the compressed sparse row graph. The
+ old interface requires that all out edges from a single vertex are
+ sorted by target, and does not support construction of the graph from
+ unsorted arrays of sources and targets. The new interface has these
+ new constructors, but does not support incremental construction of the
+ graph or the <tt>edge_range()</tt> and <tt>edge()</tt> functions. The
+ old interface is the default, but will be removed in a later version of
+ Boost. To select the new interface, add <tt>#define
+ BOOST_GRAPH_USE_NEW_CSR_INTERFACE</tt> before including
+ <tt><boost/graph/compressed_sparse_row_graph.hpp></tt>.</p>
<p>The CSR format stores vertices and edges in separate arrays,
with the indices into these arrays corresponding to the identifier
@@ -103,17 +114,35 @@
<i>// Graph constructors</i>
<a href="#default-const">compressed_sparse_row_graph</a>();
+ <i>// Unsorted edge list constructors <b>(new interface only)</b></i>
template<typename MultiPassInputIterator>
- compressed_sparse_row_graph(MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
+ compressed_sparse_row_graph(edges_are_unsorted_t,
+ MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty());
template<typename MultiPassInputIterator, typename EdgePropertyIterator>
- compressed_sparse_row_graph(MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
+ compressed_sparse_row_graph(edges_are_unsorted_t,
+ MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty());
+ <i>// Old sorted edge list constructors <b>(old interface only)</b></i>
+ template<typename InputIterator>
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty& prop = GraphProperty());
+
+ template<typename InputIterator, typename EdgePropertyIterator>
+ compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type numverts,
+ edges_size_type numedges = 0,
+ const GraphProperty& prop = GraphProperty());
+
+ <i>// New sorted edge list constructors <b>(both interfaces)</b></i>
template<typename InputIterator>
<a href="#edge-sorted-const">compressed_sparse_row_graph</a>(edges_are_sorted_t,
InputIterator edge_begin, InputIterator edge_end,
@@ -129,6 +158,7 @@
edges_size_type numedges = 0,
const GraphProperty& prop = GraphProperty());
+ <i>// In-place unsorted edge list constructors <b>(new interface only)</b></i>
template<typename InputIterator>
<a href="#edge-inplace-const">compressed_sparse_row_graph</a>(construct_inplace_from_sources_and_targets_t,
std::vector<vertex_descriptor>& sources,
@@ -144,6 +174,7 @@
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty());
+ <i>// Miscellaneous constructors <b>(both interfaces)</b></i>
template<typename Graph, typename VertexIndexMap>
<a href="#graph-const">compressed_sparse_row_graph</a>(const Graph& g, const VertexIndexMap& vi,
vertices_size_type numverts,
@@ -155,7 +186,7 @@
template<typename Graph>
explicit compressed_sparse_row_graph(const Graph& g);
- <i>// Graph mutators</i>
+ <i>// Graph mutators (both interfaces)</i>
template<typename Graph, typename VertexIndexMap>
void assign(const Graph& g, const VertexIndexMap& vi,
vertices_size_type numverts, edges_size_type numedges);
@@ -166,36 +197,46 @@
template<typename Graph>
void assign(const Graph& g);
- <i>// Property Access</i>
+ <i>// Property Access (both interfaces)</i>
VertexProperty& operator[](vertex_descriptor v);
const VertexProperty& operator[](vertex_descriptor v) const;
EdgeProperty& operator[](edge_descriptor v);
const EdgeProperty& operator[](edge_descriptor v) const;
};
-<i>// Incidence Graph requirements</i>
+<i>// Incidence Graph requirements (both interfaces)</i>
vertex_descriptor source(edge_descriptor, const compressed_sparse_row_graph&);
vertex_descriptor target(edge_descriptor, const compressed_sparse_row_graph&);
std::pair<out_edge_iterator, out_edge_iterator>
out_edges(vertex_descriptor, const compressed_sparse_row_graph&);
degree_size_type out_degree(vertex_descriptor v, const compressed_sparse_row_graph&);
-<i>// Adjacency Graph requirements</i>
+<i>// Adjacency Graph requirements (both interfaces)</i>
std::pair<adjacency_iterator, adjacency_iterator>
adjacent_vertices(vertex_descriptor, const compressed_sparse_row_graph&);
-<i>// Vertex List Graph requirements</i>
+<i>// Vertex List Graph requirements (both interfaces)</i>
std::pair<vertex_iterator, vertex_iterator> vertices(const compressed_sparse_row_graph&);
vertices_size_type num_vertices(const compressed_sparse_row_graph&);
-<i>// Edge List Graph requirements</i>
+<i>// Edge List Graph requirements (both interfaces)</i>
std::pair<edge_iterator, edge_iterator> edges(const compressed_sparse_row_graph&);
edges_size_type num_edges(const compressed_sparse_row_graph&);
-<i>// Vertex access</i>
+<i>// Vertex access (both interfaces)</i>
vertex_descriptor vertex(vertices_size_type i, const compressed_sparse_row_graph&);
-<i>// Property map accessors</i>
+<i>// Edge access</i>
+<b>(old interface only)</b>
+std::pair<out_edge_iterator, out_edge_iterator>
+ edge_range(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&);
+<b>(old interface only)</b>
+std::pair<edge_descriptor, bool>
+ edge(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&);
+<b>(both interfaces)</b>
+edge_descriptor edge_from_index(edges_size_type i, const compressed_sparse_row_graph&);
+
+<i>// Property map accessors (both interfaces)</i>
template<typename PropertyTag>
property_map<compressed_sparse_row_graph, PropertyTag>::type
<a href="#get">get</a>(PropertyTag, compressed_sparse_row_graph& g)
@@ -223,7 +264,7 @@
void set_property(const compressed_sparse_row_graph& g, GraphPropertyTag,
const typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type& value);
-<i>// Incremental construction functions</i>
+<i>// Incremental construction functions (old interface only)</i>
template<typename Graph>
vertex_descriptor add_vertex(compressed_sparse_row_graph& g);
@@ -231,7 +272,7 @@
vertex_descriptor add_vertices(vertices_size_type count, compressed_sparse_row_graph& g);
template<typename Graph>
-edge_descriptor add_vertices(vertex_descriptor src, vertex_descriptor tgt, compressed_sparse_row_graph& g);
+edge_descriptor add_edge(vertex_descriptor src, vertex_descriptor tgt, compressed_sparse_row_graph& g);
} <i>// end namespace boost</i>
</pre>
@@ -361,7 +402,8 @@
<pre><a name="edge-const"></a>
template<typename MultiPassInputIterator>
- compressed_sparse_row_graph(MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
+ compressed_sparse_row_graph(edges_are_unsorted_t,
+ MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty());
</pre>
@@ -377,6 +419,7 @@
vertices for the edges, and must fall within the range <code>[0,
numverts)</code>. The edges in <code>[edge_begin,
edge_end)</code> do not need to be sorted.
+ <b>(This function is only provided by the new interface.)</b>
</p>
<p class="indent">
@@ -388,7 +431,8 @@
<pre><a name="edge-prop-const"></a>
template<typename MultiPassInputIterator, typename EdgePropertyIterator>
- compressed_sparse_row_graph(MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
+ compressed_sparse_row_graph(edges_are_unsorted_t,
+ MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
EdgePropertyIterator ep_iter,
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty());
@@ -406,6 +450,7 @@
m)</tt> will be used to initialize the properties on the edges
of the graph, where <tt>m</tt> is distance from
<tt>edge_begin</tt> to <tt>edge_end</tt>.
+ <b>(This function is only provided by the new interface.)</b>
</p>
<hr></hr>
@@ -434,7 +479,9 @@
numverts)</code>. The edges in <code>[edge_begin,
edge_end)</code> must be sorted so that all edges originating
from vertex <i>i</i> preceed any edges originating from all
- vertices <i>j</i> where <i>j > i</i>.
+ vertices <i>j</i> where <i>j > i</i>. <b>(The version of this
+ constructor without the <tt>edges_are_sorted</tt> tag is deprecated and
+ only provided by the old interface.)</b>
</p>
<p class="indent">
@@ -472,7 +519,9 @@
<tt>EdgeProperty</tt>. The iterator range <tt>[ep_iter, ep_ter +
m)</tt> will be used to initialize the properties on the edges
of the graph, where <tt>m</tt> is distance from
- <tt>edge_begin</tt> to <tt>edge_end</tt>.
+ <tt>edge_begin</tt> to <tt>edge_end</tt>. <b>(The version of this
+ constructor without the <tt>edges_are_sorted</tt> tag is deprecated and
+ only provided by the old interface.)</b>
</p>
<hr></hr>
@@ -493,6 +542,7 @@
share storage with the constructed graph (and so are safe to destroy).
The parameter <code>prop</code>, if provided, is used to initialize the
graph property.
+ <b>(This function is only provided by the new interface.)</b>
</p>
<hr></hr>
@@ -515,6 +565,7 @@
not share storage with the constructed graph (and so are safe to
destroy). The parameter <code>prop</code>, if provided, is used to
initialize the graph property.
+ <b>(This function is only provided by the new interface.)</b>
</p>
<hr></hr>
@@ -620,6 +671,37 @@
<hr></hr>
+ <a name="edge-access"></a><h3>Edge access</h3>
+ <pre><a name="edge_range"></a>
+ std::pair<out_edge_iterator, out_edge_iterator>
+ edge_range(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&);
+ </pre>
+
+ <p class="indent">
+ Returns all edges from <tt>u</tt> to <tt>v</tt>. Requires time
+ linear in the number of edges outgoing from <tt>u</tt>.
+ <b>(This function is only provided by the old interface.)</b>
+ </p>
+
+ <hr></hr>
+
+ <pre><a name="edge"></a>
+ std::pair<edge_descriptor, bool>
+ edge(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&);
+ </pre>
+
+ <p class="indent">
+ If there exists an edge <i>(u, v)</i> in the graph, returns the
+ descriptor for that edge and <tt>true</tt>; otherwise, the
+ second value in the pair will be <tt>false</tt>. If multiple
+ edges exist from <tt>u</tt> to <tt>v</tt>, the first edge will
+ be returned; use edge_range
+ to retrieve all edges.
+ <b>(This function is only provided by the old interface.)</b>
+ </p>
+
+ <hr></hr>
+
<pre><a name="edge_from_index"></a>
edge_descriptor edge_from_index(edges_size_type i, const compressed_sparse_row_graph&);
</pre>
@@ -720,6 +802,7 @@
Add a new vertex to the end of the graph <tt>g</tt>, and return a
descriptor for that vertex. The new vertex will be greater than any of
the previous vertices in <tt>g</tt>.
+ <b>(This function is only provided by the old interface.)</b>
</p>
<hr></hr>
@@ -732,6 +815,7 @@
Add <tt>count</tt> new vertices to the end of the graph <tt>g</tt>, and
return a descriptor for the smallest new vertex. The new vertices will
be greater than any of the previous vertices in <tt>g</tt>.
+ <b>(This function is only provided by the old interface.)</b>
</p>
<hr></hr>
@@ -746,6 +830,7 @@
whose source vertex is greater than <tt>src</tt>. If the vertex
<tt>src</tt> has out edges before this operation is called, there must be
none whose target is larger than <tt>tgt</tt>.
+ <b>(This function is only provided by the old interface.)</b>
</p>
<hr></hr>
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-06-05 14:21:42 EDT (Fri, 05 Jun 2009)
@@ -13,6 +13,9 @@
# undef _GLIBCXX_DEBUG
#endif
+// Use new CSR interface
+#define BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+
// Test for the compressed sparse row graph type
#include <boost/graph/compressed_sparse_row_graph.hpp>
#include <boost/graph/adjacency_list.hpp>
@@ -157,19 +160,29 @@
void check_consistency(const CSRGraphT& 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));
+#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);
- for (CSRGraphT::vertices_size_type i = 0; i < g.m_last_source; ++i) {
+ for (CSRGraphT::vertices_size_type i = 0;
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+ i < num_vertices(g);
+#else // !BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+ 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));
}
+#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);
}
+#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));
@@ -202,6 +215,7 @@
g3, boost::identity_property_map(),
boost::identity_property_map());
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// Check constructing a graph using in-place modification of vectors
{
std::vector<std::size_t> sources(num_edges(g2));
@@ -271,7 +285,11 @@
g3a, boost::identity_property_map(),
boost::identity_property_map());
}
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+
+ CSRGraphT::edge_iterator ei, ei_end;
+#ifndef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// Check constructing a graph using add_edge and add_vertices
CSRGraphT g4;
BOOST_CHECK(num_vertices(g4) == 0);
@@ -281,7 +299,6 @@
BOOST_CHECK(first_vert == 0);
BOOST_CHECK(num_vertices(g4) == num_vertices(g3));
- CSRGraphT::edge_iterator ei, ei_end;
int i;
for (boost::tie(ei, ei_end) = edges(g3), i = 0; ei != ei_end; ++ei, ++i) {
CSRGraphT::edge_descriptor e = add_edge(source(*ei, g3), target(*ei, g3), g4);
@@ -292,6 +309,7 @@
assert_graphs_equal(g3, boost::identity_property_map(),
g4, boost::identity_property_map(),
boost::identity_property_map());
+#endif // !BOOST_GRAPH_USE_NEW_CSR_INTERFACE
// Check edge_from_index (and implicitly the edge_index property map) for
// each edge in g2
@@ -436,6 +454,7 @@
// graph_test(1000, 0.1, seed);
graph_test(1000, 0.001, seed);
graph_test(1000, 0.0005, seed);
+#ifndef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
{
std::cout << "Testing partially constructed CSR graph" << std::endl;
CSRGraphT g;
@@ -452,16 +471,19 @@
}
graph_test(g);
}
+#endif // !BOOST_GRAPH_USE_NEW_CSR_INTERFACE
test_graph_properties();
test_vertex_and_edge_properties();
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
{
std::cout << "Testing CSR graph built from unsorted edges" << std::endl;
std::pair<int, int> unsorted_edges[] = {std::make_pair(5, 0), std::make_pair(3, 2), std::make_pair(4, 1), std::make_pair(4, 0), std::make_pair(0, 2), std::make_pair(5, 2)};
- CSRGraphT g(unsorted_edges, unsorted_edges + sizeof(unsorted_edges) / sizeof(*unsorted_edges), 6);
+ CSRGraphT g(boost::edges_are_unsorted, unsorted_edges, unsorted_edges + sizeof(unsorted_edges) / sizeof(*unsorted_edges), 6);
graph_test(g);
}
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
return 0;
}