[Boost-commit] svn:boost r38674 - in sandbox/SOC/2007/graphs/boost/graph: . detail

From: asutton_at_[hidden]
Date: 2007-08-15 08:39:05

Author: asutton
Date: 2007-08-15 08:39:04 EDT (Wed, 15 Aug 2007)
New Revision: 38674
URL: http://svn.boost.org/trac/boost/changeset/38674

Log:
Moved diameter, radius to eccentricity header
Added a radius_and_diameter() function
concept checking in all eccentricity-related functions

Removed:
   sandbox/SOC/2007/graphs/boost/graph/diameter.hpp
   sandbox/SOC/2007/graphs/boost/graph/radius.hpp
Text files modified: 
   sandbox/SOC/2007/graphs/boost/graph/detail/geodesic.hpp   |    11 +++-                                    
   sandbox/SOC/2007/graphs/boost/graph/eccentricity.hpp      |    91 +++++++++++++++++++++++++++++++++++++-- 
   sandbox/SOC/2007/graphs/boost/graph/geodesic_distance.hpp |    26 ----------                              
   3 files changed, 95 insertions(+), 33 deletions(-)

Modified: sandbox/SOC/2007/graphs/boost/graph/detail/geodesic.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/detail/geodesic.hpp	(original)
+++ sandbox/SOC/2007/graphs/boost/graph/detail/geodesic.hpp	2007-08-15 08:39:04 EDT (Wed, 15 Aug 2007)
@@ -58,13 +58,16 @@
             typedef numeric_values<Distance> DistanceNumbers;
             function_requires< AdaptableBinaryFunction<Combinator,Distance,Distance,Distance> >();
 
-            // If there's ever an infinite distance, then we simply
-            // return infinity.
+            // If there's ever an infinite distance, then we simply return
+            // infinity. Note that this /will/ include the a non-zero
+            // distance-to-self in the combined values. However, this is usually
+            // zero, so it shouldn't be too problematic.
             Distance ret = init;
             VertexIterator i, end;
             for(tie(i, end) = vertices(g); i != end; ++i) {
-                if(get(dist, *i) != DistanceNumbers::infinity()) {
-                    ret = combine(ret, get(dist, *i));
+                Vertex v = *i;
+                if(get(dist, v) != DistanceNumbers::infinity()) {
+                    ret = combine(ret, get(dist, v));
                 }
                 else {
                     ret = DistanceNumbers::infinity();

Deleted: sandbox/SOC/2007/graphs/boost/graph/diameter.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/diameter.hpp	2007-08-15 08:39:04 EDT (Wed, 15 Aug 2007)
+++ (empty file)
@@ -1,26 +0,0 @@
-// (C) Copyright Andrew Sutton 2007
-//
-// Use, modification and distribution are subject to the
-// Boost Software License, Version 1.0 (See accompanying file
-// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
-
-#ifndef BOOST_GRAPH_DIAMETER_HPP
-#define BOOST_GRAPH_DIAMETER_HPP
-
-namespace boost
-{
-    template <typename Graph, typename EccentricityMap>
-    inline typename property_traits<EccentricityMap>::value_type
-    graph_diameter(const Graph& g, EccentricityMap ecc)
-    {
-        typedef typename property_traits<EccentricityMap>::value_type T;
-        typename graph_traits<Graph>::vertex_iterator i, end;
-        T ret = ecc[*vertices(g).first];
-        for(tie(i, end) = vertices(g); i != end; ++i) {
-            ret = std::max(ret, ecc[*i]);
-        }
-        return ret;
-    }
-}
-
-#endif

Modified: sandbox/SOC/2007/graphs/boost/graph/eccentricity.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/eccentricity.hpp	(original)
+++ sandbox/SOC/2007/graphs/boost/graph/eccentricity.hpp	2007-08-15 08:39:04 EDT (Wed, 15 Aug 2007)
@@ -7,6 +7,7 @@
 #ifndef BOOST_GRAPH_ECCENTRICITY_HPP
 #define BOOST_GRAPH_ECCENTRICITY_HPP
 
+#include <boost/utility.hpp>
 #include <boost/graph/detail/geodesic.hpp>
 
 namespace boost
@@ -19,16 +20,23 @@
                         DistanceMap dist,
                         Combinator combine)
     {
+        function_requires< GraphConcept<Graph> >();
+        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+        function_requires< ReadablePropertyMapConcept<DistanceMap,Vertex> >();
         typedef typename property_traits<DistanceMap>::value_type Distance;
-        return detail::combine_distances(g, dist, combine,
-                                         Distance(0));
+
+        return detail::combine_distances(g, dist, combine, Distance(0));
     }
 
     template <typename Graph, typename DistanceMap>
     inline typename property_traits<DistanceMap>::value_type
     vertex_eccentricity(const Graph& g, DistanceMap dist)
     {
+        function_requires< GraphConcept<Graph> >();
+        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+        function_requires< ReadablePropertyMapConcept<DistanceMap,Vertex> >();
         typedef typename property_traits<DistanceMap>::value_type Distance;
+
         return vertex_eccentricity(g, dist, detail::maximize<Distance>());
     }
 
@@ -36,13 +44,86 @@
     inline void
     eccentricity(const Graph& g, const DistanceMatrix& dist, EccentricityMap ecc)
     {
+        function_requires< VertexListGraphConcept<Graph> >();
+        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+        typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+        function_requires< ReadablePropertyMapConcept<DistanceMatrix,Vertex> >();
         typedef typename property_traits<DistanceMatrix>::value_type DistanceMap;
-        typedef typename property_traits<DistanceMap>::value_type Distance;
+        function_requires< WritablePropertyMapConcept<EccentricityMap,Vertex> >();
+        typedef typename property_traits<EccentricityMap>::value_type Eccentricity;
 
-        typename graph_traits<Graph>::vertex_iterator i, end;
+        VertexIterator i, end;
         for(tie(i, end) = vertices(g); i != end; ++i) {
-            ecc[*i] = vertex_eccentricity(g, DistanceMap(dist[*i]));
+            DistanceMap dm = get(dist, *i);
+            Eccentricity e = vertex_eccentricity(g, dm);
+            put(ecc, *i, e);
+        }
+    }
+
+
+    template <typename Graph, typename EccentricityMap>
+    inline typename property_traits<EccentricityMap>::value_type
+    graph_radius(const Graph& g, EccentricityMap ecc)
+    {
+        function_requires< VertexListGraphConcept<Graph> >();
+        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+        typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+        function_requires< ReadablePropertyMapConcept<EccentricityMap, Vertex> >();
+        typedef typename property_traits<EccentricityMap>::value_type Eccentricity;
+
+        VertexIterator i, end;
+        tie(i, end) = vertices(g);
+        Eccentricity ret = get(ecc, *i);
+        for(i = next(i); i != end; ++i) {
+            Eccentricity cur = get(ecc, *i);
+            ret = std::min(ret, cur);
+        }
+        return ret;
+    }
+
+
+    template <typename Graph, typename EccentricityMap>
+    inline typename property_traits<EccentricityMap>::value_type
+    graph_diameter(const Graph& g, EccentricityMap ecc)
+    {
+        function_requires< VertexListGraphConcept<Graph> >();
+        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+        typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+        function_requires< ReadablePropertyMapConcept<EccentricityMap, Vertex> >();
+        typedef typename property_traits<EccentricityMap>::value_type Eccentricity;
+
+        VertexIterator i, end;
+        tie(i, end) = vertices(g);
+        Eccentricity ret = get(ecc, *i);
+        for(i = next(i); i != end; ++i) {
+            Eccentricity cur = get(ecc, *i);
+            ret = std::max(ret, cur);
+        }
+        return ret;
+    }
+
+
+    template <typename Graph, typename EccentricityMap>
+    inline std::pair<typename property_traits<EccentricityMap>::value_type,
+                     typename property_traits<EccentricityMap>::value_type>
+    graph_radius_and_diameter(const Graph& g, EccentricityMap ecc)
+    {
+        function_requires< VertexListGraphConcept<Graph> >();
+        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+        typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+        function_requires< ReadablePropertyMapConcept<EccentricityMap, Vertex> >();
+        typedef typename property_traits<EccentricityMap>::value_type Eccentricity;
+
+        VertexIterator i, end;
+        tie(i, end) = vertices(g);
+        Eccentricity radius = get(ecc, *i);
+        Eccentricity diameter = get(ecc, *i);
+        for(i = next(i); i != end; ++i) {
+            Eccentricity cur = get(ecc, *i);
+            radius = std::min(radius, cur);
+            diameter = std::max(diameter, cur);
         }
+        return std::make_pair(radius, diameter);
     }
 }
 

Modified: sandbox/SOC/2007/graphs/boost/graph/geodesic_distance.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/geodesic_distance.hpp	(original)
+++ sandbox/SOC/2007/graphs/boost/graph/geodesic_distance.hpp	2007-08-15 08:39:04 EDT (Wed, 15 Aug 2007)
@@ -34,7 +34,7 @@
             return
                 (d == base_type::infinite_distance()) ?
                     base_type::infinite_result() :
-                    div(result_type(d), result_type(num_vertices(g)));
+                    div(result_type(d), result_type(num_vertices(g) - 1));
         }
         Divides div;
     };
@@ -53,7 +53,6 @@
         return mean_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, T>();
     }
 
-
     // This is a little different because it's expected that the result type
     // should (must?) be the same as the distance type. There's a type of
     // transitivity in this thinking... If the average of distances has type
@@ -68,38 +67,17 @@
         typedef geodesic_measure<Graph, DistanceType, DistanceType> base_type;
         typedef typename base_type::distance_type distance_type;
         typedef typename base_type::result_type result_type;
-        typedef typename base_type::size_type size_type;
 
         inline result_type operator ()(distance_type d, const Graph& g)
         {
             function_requires< VertexListGraphConcept<Graph> >();
-            typename graph_traits<Graph>::directed_category cat;
             function_requires< NumericValueConcept<DistanceType> >();
 
-            return this->average(d, num_vertices(g), cat);
-        }
-
-    private:
-        inline result_type
-        average(distance_type d, size_type n, undirected_tag)
-        {
-            if(d == base_type::infinite_distance()) {
-                return base_type::infinite_result();
-            }
-            else {
-                result_type f = (result_type(n) + 1) / result_type(2);
-                return d / f;
-            }
-        }
-
-        inline result_type
-        average(distance_type d, size_type n, directed_tag)
-        {
             if(d == base_type::infinite_distance()) {
                 return base_type::infinite_result();
             }
             else {
-                return result_type(d) / result_type(n);
+                return d / result_type(num_vertices(g));
             }
         }
     };

Deleted: sandbox/SOC/2007/graphs/boost/graph/radius.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/radius.hpp	2007-08-15 08:39:04 EDT (Wed, 15 Aug 2007)
+++ (empty file)
@@ -1,26 +0,0 @@
-// (C) Copyright Andrew Sutton 2007
-//
-// Use, modification and distribution are subject to the
-// Boost Software License, Version 1.0 (See accompanying file
-// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
-
-#ifndef BOOST_GRAPH_RADIUS_HPP
-#define BOOST_GRAPH_RADIUS_HPP
-
-namespace boost
-{
-    template <typename Graph, typename EccentricityMap>
-    inline typename property_traits<EccentricityMap>::value_type
-    graph_radius(const Graph& g, EccentricityMap ecc)
-    {
-        typedef typename property_traits<EccentricityMap>::value_type T;
-        typename graph_traits<Graph>::vertex_iterator i, end;
-        T ret = ecc[*vertices(g).first];
-        for(tie(i, end) = vertices(g); i != end; ++i) {
-            ret = std::min(ret, ecc[*i]);
-        }
-        return ret;
-    }
-}
-
-#endif