[Boost-commit] svn:boost r56017 - in trunk: boost/graph libs/graph/doc

Subject: [Boost-commit] svn:boost r56017 - in trunk: boost/graph libs/graph/doc
From: jewillco_at_[hidden]
Date: 2009-09-04 11:08:03

Author: jewillco
Date: 2009-09-04 11:08:02 EDT (Fri, 04 Sep 2009)
New Revision: 56017
URL: http://svn.boost.org/trac/boost/changeset/56017

Log:
Added edge() function for new interface of CSR graph, enabling it to work with the Kolmogorov max-flow algorithm
Text files modified: 
   trunk/boost/graph/compressed_sparse_row_graph.hpp |    20 +++++++++++++++++++-                    
   trunk/libs/graph/doc/compressed_sparse_row.html   |     9 +++++----                               
   2 files changed, 24 insertions(+), 5 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-04 11:08:02 EDT (Fri, 04 Sep 2009)
@@ -1605,7 +1605,25 @@
   else
     return std::make_pair(*range.first, true);
 }
-#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+
+#else // !BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+// edge() can be provided in linear time for the new interface
+
+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 = out_edges(i, g);
+  for (; range.first != range.second; ++range.first) {
+    if (target(*range.first) == j)
+      return std::make_pair(*range.first, true);
+  }
+  return std::make_pair(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(),
+                        false);
+}
+
+#endif // !BOOST_GRAPH_USE_OLD_CSR_INTERFACE
 
 // Find an edge given its index in the graph
 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>

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-04 11:08:02 EDT (Fri, 04 Sep 2009)
@@ -243,7 +243,7 @@
 <b>(old interface only)</b>
 std::pair&lt;out_edge_iterator, out_edge_iterator&gt; 
   <a href="#edge_range">edge_range</a>(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&amp;);
-<b>(old interface only)</b>
+<b>(both interfaces)</b>
 std::pair&lt;edge_descriptor, bool&gt; 
   <a href="#edge">edge</a>(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&amp;);
 <b>(both interfaces)</b>
@@ -770,7 +770,7 @@
 
     <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>.
+      logarithmic in the number of edges outgoing from <tt>u</tt>.
       <b>(This function is only provided by the old interface.)</b>
     </p>
 
@@ -787,8 +787,9 @@
       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>
+      to retrieve all edges.  This function requires time logarithmic in the
+      number of edges outgoing from <tt>u</tt> for the old interface, and
+      linear time for the new interface.
     </p>
 
     <hr></hr>