Subject: [Boost-commit] svn:boost r56140 - trunk/libs/graph/doc
From: jewillco_at_[hidden]
Date: 2009-09-10 13:36:36
Author: jewillco
Date: 2009-09-10 13:36:35 EDT (Thu, 10 Sep 2009)
New Revision: 56140
URL: http://svn.boost.org/trac/boost/changeset/56140
Log:
Added information about bidirectional support to CSR documentation
Text files modified:
trunk/libs/graph/doc/compressed_sparse_row.html | 36 ++++++++++++++++++++++++------------
1 files changed, 24 insertions(+), 12 deletions(-)
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-09-10 13:36:35 EDT (Thu, 10 Sep 2009)
@@ -40,7 +40,8 @@
<p>The class template <code>compressed_sparse_row_graph</code> is
a graph class that uses the compact Compressed Sparse Row (CSR)
- format to store directed graphs. While CSR graphs have much less
+ format to store directed (and bidirectional) graphs. While CSR graphs have
+ much less
overhead than many other graph formats (e.g., <a
href="adjacency_list.html"><code>adjacency_list</code></a>), they
do not provide any mutability: one cannot add or remove vertices
@@ -67,14 +68,20 @@
providing the offset of the first edge outgoing from each
vertex. Iteration over the out-edges for the <i>i</i><sup>th</sup>
vertex in the graph is achieved by
- visiting <tt>edge_array[vertex_array[i]]</tt>, <tt>edge_array[vertex_array[i]+1]</tt>,
+ visiting <tt>edge_array[vertex_array[i]]</tt>,
+ <tt>edge_array[vertex_array[i]+1]</tt>,
..., <tt>edge_array[vertex_array[i+1]]</tt>. This format minimizes
memory use to <i>O(n + m)</i>, where <i>n</i> and <i>m</i> are the
number of vertices and edges, respectively. The constants
multiplied by <i>n</i> and <i>m</i> are based on the size of the
integers needed to represent indices into the edge and vertex
arrays, respectively, which can be controlled using
- the template parameters.</p>
+ the template parameters. The
+ <tt>Directed</tt> template parameter controls whether one edge direction
+ (the default) or both directions are stored. A directed CSR graph has
+ <tt>Directed</tt> = <tt>directedS</tt> and a bidirectional CSR graph (only
+ supported with the new interface and with a limited set of constructors)
+ has <tt>Directed</tt> = <tt>bidirectionalS</tt>.</p>
<ul>
<li>Synopsis</li>
@@ -155,7 +162,7 @@
edges_size_type numedges = 0,
const GraphProperty& prop = GraphProperty());
- <i>// New sorted edge list constructors <b>(both interfaces)</b></i>
+ <i>// New sorted edge list constructors <b>(both interfaces, directed only)</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,
@@ -171,7 +178,7 @@
edges_size_type numedges = 0,
const GraphProperty& prop = GraphProperty());
- <i>// In-place unsorted edge list constructors <b>(new interface only)</b></i>
+ <i>// In-place unsorted edge list constructors <b>(new interface and directed 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,
@@ -187,7 +194,7 @@
vertices_size_type numverts,
const GraphProperty& prop = GraphProperty());
- <i>// Miscellaneous constructors <b>(both interfaces)</b></i>
+ <i>// Miscellaneous constructors <b>(both interfaces, directed only)</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,
@@ -199,7 +206,7 @@
template<typename Graph>
explicit compressed_sparse_row_graph(const Graph& g);
- <i>// Graph mutators (both interfaces)</i>
+ <i>// Graph mutators (both interfaces, directed only)</i>
template<typename Graph, typename VertexIndexMap>
void assign(const Graph& g, const VertexIndexMap& vi,
vertices_size_type numverts, edges_size_type numedges);
@@ -224,6 +231,11 @@
out_edges(vertex_descriptor, const compressed_sparse_row_graph&);
degree_size_type out_degree(vertex_descriptor v, const compressed_sparse_row_graph&);
+<i>// Bidirectional Graph requirements (new interface and bidirectional only)</i>
+std::pair<in_edge_iterator, in_edge_iterator>
+ in_edges(vertex_descriptor, const compressed_sparse_row_graph&);
+degree_size_type in_degree(vertex_descriptor v, const compressed_sparse_row_graph&);
+
<i>// Adjacency Graph requirements (both interfaces)</i>
std::pair<adjacency_iterator, adjacency_iterator>
adjacent_vertices(vertex_descriptor, const compressed_sparse_row_graph&);
@@ -259,7 +271,7 @@
<a href="#get">get</a>(PropertyTag, const compressed_sparse_row_graph& g)
template<typename PropertyTag, class X>
-typename property_traits<property_map<compressed_sparse_row_graph, PropertyTag>::const_type>::value_type
+typename property_traits<property_map<compressed_sparse_row_graph, PropertyTag>::const_type>::value_type
<a href="#get-x">get</a>(PropertyTag, const compressed_sparse_row_graph& g, X x)
template<typename PropertyTag, class X, class Value>
@@ -290,19 +302,19 @@
template<typename Graph>
edge_descriptor add_edge(vertex_descriptor src, vertex_descriptor tgt, compressed_sparse_row_graph& g);
-<b>(new interface only)</b>
+<b>(new interface and directed only)</b>
template<typename InputIterator, typename Graph>
void add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph& g);
-<b>(new interface only)</b>
+<b>(new interface and directed only)</b>
template<typename InputIterator, typename EPIter, typename Graph>
void add_edges(InputIterator first, InputIterator last, EPIter ep_first, EPIter ep_last, compressed_sparse_row_graph& g);
-<b>(new interface only)</b>
+<b>(new interface and directed only)</b>
template<typename BidirectionalIterator, typename Graph>
void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, compressed_sparse_row_graph& g);
-<b>(new interface only)</b>
+<b>(new interface and directed only)</b>
template<typename BidirectionalIterator, typename EPIter, typename Graph>
void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, EPIter ep_iter, compressed_sparse_row_graph& g);