Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r56140 - trunk/libs/graph/doc
From: jewillco_at_[hidden]
Date: 2009-09-10 13:36:36

Next message: hartmut.kaiser_at_[hidden]: "[Boost-commit] svn:boost r56141 - trunk/libs/spirit/example/lex/static_lexer"
Previous message: bdawes_at_[hidden]: "[Boost-commit] svn:boost r56139 - in trunk: boost/filesystem libs/filesystem/test"

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 @@

 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 ith
 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 O(n + m), where n and m are the
 number of vertices and edges, respectively. The constants
 multiplied by n and m 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.
+ 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>.

 <ul>
 <li>Synopsis</li>
@@ -155,7 +162,7 @@
 edges_size_type numedges = 0,
 const GraphProperty& prop = GraphProperty());

- // New sorted edge list constructors (both interfaces)
+ // New sorted edge list constructors (both interfaces, directed only)
 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());

- // In-place unsorted edge list constructors (new interface only)
+ // In-place unsorted edge list constructors (new interface and directed only)
 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());

- // Miscellaneous constructors (both interfaces)
+ // Miscellaneous constructors (both interfaces, directed only)
 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);

- // Graph mutators (both interfaces)
+ // Graph mutators (both interfaces, directed only)
 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&);

+// Bidirectional Graph requirements (new interface and bidirectional only)
+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&);
+
// Adjacency Graph requirements (both interfaces)
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&gt::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);

-(new interface only)
+(new interface and directed only)
template<typename InputIterator, typename Graph>
void add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph& g);

-(new interface only)
+(new interface and directed only)
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);

-(new interface only)
+(new interface and directed only)
template<typename BidirectionalIterator, typename Graph>
void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, compressed_sparse_row_graph& g);

-(new interface only)
+(new interface and directed only)
template<typename BidirectionalIterator, typename EPIter, typename Graph>
void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, EPIter ep_iter, compressed_sparse_row_graph& g);

Next message: hartmut.kaiser_at_[hidden]: "[Boost-commit] svn:boost r56141 - trunk/libs/spirit/example/lex/static_lexer"
Previous message: bdawes_at_[hidden]: "[Boost-commit] svn:boost r56139 - in trunk: boost/filesystem libs/filesystem/test"

Date view	Thread view	Subject view	Author view

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