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

Subject: [Boost-commit] svn:boost r72837 - in trunk: boost/graph libs/graph/doc
From: jewillco_at_[hidden]
Date: 2011-07-01 15:36:09

Author: jewillco
Date: 2011-07-01 15:36:08 EDT (Fri, 01 Jul 2011)
New Revision: 72837
URL: http://svn.boost.org/trac/boost/changeset/72837

Log:
Fixed ith_bandwidth for directed graphs; changed bandwidth to use the graph edges rather than scanning the out edges of every vertex; other small fixes
Text files modified: 
   trunk/boost/graph/bandwidth.hpp     |    22 +++++++++++++---------                  
   trunk/libs/graph/doc/bandwidth.html |     4 ++--                                    
   2 files changed, 15 insertions(+), 11 deletions(-)

Modified: trunk/boost/graph/bandwidth.hpp
==============================================================================
--- trunk/boost/graph/bandwidth.hpp	(original)
+++ trunk/boost/graph/bandwidth.hpp	2011-07-01 15:36:08 EDT (Fri, 01 Jul 2011)
@@ -21,15 +21,14 @@
                 VertexIndexMap index)
   {
     BOOST_USING_STD_MAX();
-    typedef typename graph_traits<Graph>::vertices_size_type size_type;
-    size_type b = 0;
+    using std::abs;
+    typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
+    vertices_size_type b = 0;
     typename graph_traits<Graph>::out_edge_iterator e, end;
     for (boost::tie(e, end) = out_edges(i, g); e != end; ++e) {
       int f_i = get(index, i);
       int f_j = get(index, target(*e, g));
-      using namespace std; // to call abs() unqualified
-      if(f_i > f_j)
-          b = max BOOST_PREVENT_MACRO_SUBSTITUTION (b, size_type(f_i - f_j));
+      b = max BOOST_PREVENT_MACRO_SUBSTITUTION (b, vertices_size_type(abs(f_i - f_j)));
     }
     return b;
   }
@@ -47,10 +46,15 @@
   bandwidth(const Graph& g, VertexIndexMap index)
   {
     BOOST_USING_STD_MAX();
-    typename graph_traits<Graph>::vertices_size_type b = 0;
-    typename graph_traits<Graph>::vertex_iterator i, end;
-    for (boost::tie(i, end) = vertices(g); i != end; ++i)
-        b = max BOOST_PREVENT_MACRO_SUBSTITUTION (b, ith_bandwidth(*i, g, index));
+    using std::abs;
+    typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
+    vertices_size_type b = 0;
+    typename graph_traits<Graph>::edge_iterator i, end;
+    for (boost::tie(i, end) = edges(g); i != end; ++i) {
+      int f_i = get(index, source(*i, g));
+      int f_j = get(index, target(*i, g));
+      b = max BOOST_PREVENT_MACRO_SUBSTITUTION (b, vertices_size_type(abs(f_i - f_j)));
+    }
     return b;
   }
 

Modified: trunk/libs/graph/doc/bandwidth.html
==============================================================================
--- trunk/libs/graph/doc/bandwidth.html	(original)
+++ trunk/libs/graph/doc/bandwidth.html	2011-07-01 15:36:08 EDT (Fri, 01 Jul 2011)
@@ -31,10 +31,10 @@
   bandwidth(const Graph& g, VertexIndexMap index_map)
 </pre>
 
-The <b><i>bandwidth</i></b> of an undirected graph is the maximum
+The <b><i>bandwidth</i></b> of a graph is the maximum
 distance between two adjacent vertices, with distance measured on a
 line upon which the vertices have been placed at unit intervals. To
-put it another way, if the vertices of an undirected graph
+put it another way, if the vertices of a graph
 <i>G=(V,E)</i> are each assigned an index from zero to <i>|V| - 1</i>
 given by <i>index[v]</i>, then the bandwidth of <i>G</i> is<br>
 <br>