[Boost-commit] svn:boost r51097 - in trunk/boost/graph: . detail property_maps

Subject: [Boost-commit] svn:boost r51097 - in trunk/boost/graph: . detail property_maps
From: asutton_at_[hidden]
Date: 2009-02-08 10:28:32

Author: asutton
Date: 2009-02-08 10:28:31 EST (Sun, 08 Feb 2009)
New Revision: 51097
URL: http://svn.boost.org/trac/boost/changeset/51097

Log:
Importing exterior_property framework and associated property map helpers.
Integrating closeness_centrality algorithm.

Added:
   trunk/boost/graph/closeness_centrality.hpp   (contents, props changed)
      - copied, changed from r51086, /sandbox/SOC/2007/graphs/boost/graph/closeness_centrality.hpp
   trunk/boost/graph/detail/geodesic.hpp   (contents, props changed)
      - copied, changed from r51086, /sandbox/SOC/2007/graphs/boost/graph/detail/geodesic.hpp
   trunk/boost/graph/detail/index.hpp   (contents, props changed)
      - copied, changed from r51086, /sandbox/SOC/2007/graphs/boost/graph/detail/index.hpp
   trunk/boost/graph/exterior_property.hpp   (contents, props changed)
      - copied, changed from r51086, /sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp
   trunk/boost/graph/property_maps/constant_property_map.hpp   (contents, props changed)
      - copied, changed from r51086, /sandbox/SOC/2007/graphs/boost/graph/constant_property_map.hpp
   trunk/boost/graph/property_maps/container_property_map.hpp   (contents, props changed)
      - copied, changed from r51086, /sandbox/SOC/2007/graphs/boost/graph/container_property_map.hpp
   trunk/boost/graph/property_maps/matrix_property_map.hpp   (contents, props changed)
      - copied, changed from r51086, /sandbox/SOC/2007/graphs/boost/graph/matrix_property_map.hpp
Text files modified: 
   trunk/boost/graph/bron_kerbosch_all_cliques.hpp            |     4                                         
   trunk/boost/graph/closeness_centrality.hpp                 |   274 +++++++++++++++++++-------------------- 
   trunk/boost/graph/detail/geodesic.hpp                      |   211 +++++++++++++++---------------          
   trunk/boost/graph/detail/index.hpp                         |    13 +                                       
   trunk/boost/graph/exterior_property.hpp                    |   177 ++++++++++++++-----------               
   trunk/boost/graph/property_maps/constant_property_map.hpp  |    91 ++++++------                            
   trunk/boost/graph/property_maps/container_property_map.hpp |     6                                         
   trunk/boost/graph/property_maps/matrix_property_map.hpp    |     8                                         
   trunk/boost/graph/tiernan_all_cycles.hpp                   |     4                                         
   9 files changed, 400 insertions(+), 388 deletions(-)

Modified: trunk/boost/graph/bron_kerbosch_all_cliques.hpp
==============================================================================
--- trunk/boost/graph/bron_kerbosch_all_cliques.hpp	(original)
+++ trunk/boost/graph/bron_kerbosch_all_cliques.hpp	2009-02-08 10:28:31 EST (Sun, 08 Feb 2009)
@@ -4,8 +4,8 @@
 // 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_CLIQUE_HXX
-#define BOOST_GRAPH_CLIQUE_HXX
+#ifndef BOOST_GRAPH_CLIQUE_HPP
+#define BOOST_GRAPH_CLIQUE_HPP
 
 #include <vector>
 #include <deque>

Copied: trunk/boost/graph/closeness_centrality.hpp (from r51086, /sandbox/SOC/2007/graphs/boost/graph/closeness_centrality.hpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/boost/graph/closeness_centrality.hpp	(original)
+++ trunk/boost/graph/closeness_centrality.hpp	2009-02-08 10:28:31 EST (Sun, 08 Feb 2009)
@@ -1,4 +1,4 @@
-// (C) Copyright Andrew Sutton 2007
+// (C) Copyright 2007-2009 Andrew Sutton
 //
 // Use, modification and distribution are subject to the
 // Boost Software License, Version 1.0 (See accompanying file
@@ -12,158 +12,146 @@
 
 namespace boost
 {
-    template <typename Graph,
-              typename DistanceType,
-              typename ResultType,
-              typename Reciprocal = detail::reciprocal<ResultType>
-        >
-    struct closeness_measure
-        : public geodesic_measure<Graph, DistanceType, ResultType>
-    {
-        typedef geodesic_measure< Graph, DistanceType, ResultType> base_type;
-        typedef typename base_type::distance_type distance_type;
-        typedef typename base_type::result_type result_type;
-
-        result_type operator ()(distance_type d, const Graph&)
-        {
-            function_requires< NumericValueConcept<DistanceType> >();
-            function_requires< NumericValueConcept<ResultType> >();
-            function_requires< AdaptableUnaryFunctionConcept<Reciprocal,ResultType,ResultType> >();
-            return
-                (d == base_type::infinite_distance()) ?
-                    base_type::zero_result() : rec(result_type(d));
-        }
-        Reciprocal rec;
-    };
-
-    template <typename Graph, typename DistanceMap>
-    inline closeness_measure<
-            Graph,
-            typename property_traits<DistanceMap>::value_type,
-            float,
-            detail::reciprocal<float> >
-    measure_closeness(const Graph&, DistanceMap)
-    {
-        typedef typename property_traits<DistanceMap>::value_type Distance;
-        return closeness_measure<Graph, Distance, float, detail::reciprocal<float> >();
-    }
-
-    template <typename T, typename Graph, typename DistanceMap>
-    inline closeness_measure<
-            Graph,
-            typename property_traits<DistanceMap>::value_type,
-            T,
-            detail::reciprocal<T> >
-    measure_closeness(const Graph&, DistanceMap)
-    {
-        typedef typename property_traits<DistanceMap>::value_type Distance;
-        return closeness_measure<Graph, Distance, T, detail::reciprocal<T> >();
-    }
-
-    template <typename T, typename Graph, typename DistanceMap, typename Reciprocal>
-    inline closeness_measure<
-            Graph,
-            typename property_traits<DistanceMap>::value_type,
-            T,
-            Reciprocal>
-    measure_closeness(const Graph&, DistanceMap)
-    {
-        typedef typename property_traits<DistanceMap>::value_type Distance;
-        return closeness_measure<Graph, Distance, T, Reciprocal>();
-    }
+template <typename Graph,
+          typename DistanceType,
+          typename ResultType,
+          typename Reciprocal = detail::reciprocal<ResultType> >
+struct closeness_measure
+    : public geodesic_measure<Graph, DistanceType, ResultType>
+{
+    typedef geodesic_measure< Graph, DistanceType, ResultType> base_type;
+    typedef typename base_type::distance_type distance_type;
+    typedef typename base_type::result_type result_type;
+
+    result_type operator ()(distance_type d, const Graph&)
+    {
+        function_requires< NumericValueConcept<DistanceType> >();
+        function_requires< NumericValueConcept<ResultType> >();
+        function_requires< AdaptableUnaryFunctionConcept<Reciprocal,ResultType,ResultType> >();
+        return (d == base_type::infinite_distance())
+            ? base_type::zero_result()
+            : rec(result_type(d));
+    }
+    Reciprocal rec;
+};
+
+template <typename Graph, typename DistanceMap>
+inline closeness_measure<
+        Graph, typename property_traits<DistanceMap>::value_type, double,
+        detail::reciprocal<double> >
+measure_closeness(const Graph&, DistanceMap)
+{
+    typedef typename property_traits<DistanceMap>::value_type Distance;
+    return closeness_measure<Graph, Distance, double, detail::reciprocal<double> >();
+}
 
-    template <typename Graph, typename DistanceMap,
-              typename Measure, typename Combinator>
-    inline typename Measure::result_type
-    closeness_centrality(const Graph& g,
-                         DistanceMap dist,
-                         Measure measure,
-                         Combinator combine)
-    {
-        function_requires< VertexListGraphConcept<Graph> >();
-        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-        function_requires< ReadablePropertyMapConcept<DistanceMap,Vertex> >();
-        typedef typename property_traits<DistanceMap>::value_type Distance;
-        function_requires< NumericValueConcept<Distance> >();
-        function_requires< DistanceMeasureConcept<Measure,Graph> >();
-
-        // NOTE: we could further reduce the requirements on this function
-        // by removing the call to num_vertices() and passing that as a
-        // parameter. I don't know if its worthwhile...
+template <typename T, typename Graph, typename DistanceMap>
+inline closeness_measure<
+        Graph, typename property_traits<DistanceMap>::value_type, T,
+        detail::reciprocal<T> >
+measure_closeness(const Graph&, DistanceMap)
+{
+    typedef typename property_traits<DistanceMap>::value_type Distance;
+    return closeness_measure<Graph, Distance, T, detail::reciprocal<T> >();
+}
 
-        Distance n = detail::combine_distances(g, dist, combine, Distance(0));
-        return measure(n, g);
-    }
+template <typename T, typename Graph, typename DistanceMap, typename Reciprocal>
+inline closeness_measure<
+        Graph, typename property_traits<DistanceMap>::value_type, T,
+        Reciprocal>
+measure_closeness(const Graph&, DistanceMap)
+{
+    typedef typename property_traits<DistanceMap>::value_type Distance;
+    return closeness_measure<Graph, Distance, T, Reciprocal>();
+}
 
-    template <typename Graph, typename DistanceMap, typename Measure>
-    inline typename Measure::result_type
-    closeness_centrality(const Graph& g, DistanceMap dist, Measure measure)
-    {
-        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;
+template <typename Graph,
+          typename DistanceMap,
+          typename Measure,
+          typename Combinator>
+inline typename Measure::result_type
+closeness_centrality(const Graph& g,
+                     DistanceMap dist,
+                     Measure measure,
+                     Combinator combine)
+{
+    function_requires< VertexListGraphConcept<Graph> >();
+    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+    function_requires< ReadablePropertyMapConcept<DistanceMap,Vertex> >();
+    typedef typename property_traits<DistanceMap>::value_type Distance;
+    function_requires< NumericValueConcept<Distance> >();
+    function_requires< DistanceMeasureConcept<Measure,Graph> >();
 
-        return closeness_centrality(g, dist, measure, std::plus<Distance>());
-    }
+    Distance n = detail::combine_distances(g, dist, combine, Distance(0));
+    return measure(n, g);
+}
 
-    template <typename Graph, typename DistanceMap>
-    inline float closeness_centrality(const Graph& g, DistanceMap dist)
-    {
-        return closeness_centrality(g, dist, measure_closeness(g, dist));
-    }
+template <typename Graph, typename DistanceMap, typename Measure>
+inline typename Measure::result_type
+closeness_centrality(const Graph& g, DistanceMap dist, Measure measure)
+{
+    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;
 
-    template <typename T, typename Graph, typename DistanceMap>
-    inline T closeness_centrality(const Graph& g, DistanceMap dist)
-    {
-        return closeness_centrality(g, dist, measure_closeness<T>(g, dist));
-    }
+    return closeness_centrality(g, dist, measure, std::plus<Distance>());
+}
 
-    template <typename Graph,
-              typename DistanceMatrixMap,
-              typename CentralityMap,
-              typename Measure>
-    inline void
-    all_closeness_centralities(const Graph& g,
-                               DistanceMatrixMap dist,
-                               CentralityMap cent,
-                               Measure measure)
-    {
-        function_requires< VertexListGraphConcept<Graph> >();
-        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-        function_requires< ReadablePropertyMapConcept<DistanceMatrixMap,Vertex> >();
-        typedef typename property_traits<DistanceMatrixMap>::value_type DistanceMap;
-        function_requires< ReadablePropertyMapConcept<DistanceMap,Vertex> >();
-        function_requires< WritablePropertyMapConcept<CentralityMap,Vertex> >();
-        typedef typename property_traits<DistanceMap>::value_type Distance;
-        typedef typename property_traits<CentralityMap>::value_type Centrality;
-
-        typename graph_traits<Graph>::vertex_iterator i, end;
-        for(tie(i, end) = vertices(g); i != end; ++i) {
-            DistanceMap dm = get(dist, *i);
-            Centrality c = closeness_centrality(g, dm, measure);
-            put(cent, *i, c);
-        }
+template <typename Graph, typename DistanceMap>
+inline double closeness_centrality(const Graph& g, DistanceMap dist)
+{ return closeness_centrality(g, dist, measure_closeness(g, dist)); }
+
+template <typename T, typename Graph, typename DistanceMap>
+inline T closeness_centrality(const Graph& g, DistanceMap dist)
+{ return closeness_centrality(g, dist, measure_closeness<T>(g, dist)); }
+
+template <typename Graph,
+          typename DistanceMatrixMap,
+          typename CentralityMap,
+          typename Measure>
+inline void
+all_closeness_centralities(const Graph& g,
+                           DistanceMatrixMap dist,
+                           CentralityMap cent,
+                           Measure measure)
+{
+    function_requires< VertexListGraphConcept<Graph> >();
+    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+    function_requires< ReadablePropertyMapConcept<DistanceMatrixMap,Vertex> >();
+    typedef typename property_traits<DistanceMatrixMap>::value_type DistanceMap;
+    function_requires< ReadablePropertyMapConcept<DistanceMap,Vertex> >();
+    function_requires< WritablePropertyMapConcept<CentralityMap,Vertex> >();
+    typedef typename property_traits<DistanceMap>::value_type Distance;
+    typedef typename property_traits<CentralityMap>::value_type Centrality;
+
+    typename graph_traits<Graph>::vertex_iterator i, end;
+    for(tie(i, end) = vertices(g); i != end; ++i) {
+        DistanceMap dm = get(dist, *i);
+        Centrality c = closeness_centrality(g, dm, measure);
+        put(cent, *i, c);
     }
+}
 
-    template <typename Graph,
-              typename DistanceMatrixMap,
-              typename CentralityMap>
-    inline void
-    all_closeness_centralities(const Graph& g,
-                               DistanceMatrixMap dist,
-                               CentralityMap cent)
-    {
-        function_requires< GraphConcept<Graph> >();
-        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-        function_requires< ReadablePropertyMapConcept<DistanceMatrixMap,Vertex> >();
-        typedef typename property_traits<DistanceMatrixMap>::value_type DistanceMap;
-        function_requires< ReadablePropertyMapConcept<DistanceMap,Vertex> >();
-        typedef typename property_traits<DistanceMap>::value_type Distance;
-        typedef typename property_traits<CentralityMap>::value_type Result;
+template <typename Graph,
+          typename DistanceMatrixMap,
+          typename CentralityMap>
+inline void
+all_closeness_centralities(const Graph& g,
+                            DistanceMatrixMap dist,
+                            CentralityMap cent)
+{
+    function_requires< GraphConcept<Graph> >();
+    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+    function_requires< ReadablePropertyMapConcept<DistanceMatrixMap,Vertex> >();
+    typedef typename property_traits<DistanceMatrixMap>::value_type DistanceMap;
+    function_requires< ReadablePropertyMapConcept<DistanceMap,Vertex> >();
+    typedef typename property_traits<DistanceMap>::value_type Distance;
+    typedef typename property_traits<CentralityMap>::value_type Result;
 
-        all_closeness_centralities(g, dist, cent, measure_closeness<Result>(g, DistanceMap()));
-    }
+    all_closeness_centralities(g, dist, cent, measure_closeness<Result>(g, DistanceMap()));
 }
 
+} /* namespace boost */
+
 #endif

Copied: trunk/boost/graph/detail/geodesic.hpp (from r51086, /sandbox/SOC/2007/graphs/boost/graph/detail/geodesic.hpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/boost/graph/detail/geodesic.hpp	(original)
+++ trunk/boost/graph/detail/geodesic.hpp	2009-02-08 10:28:31 EST (Sun, 08 Feb 2009)
@@ -1,4 +1,4 @@
-// (C) Copyright Andrew Sutton 2007
+// (C) Copyright 2007 Andrew Sutton
 //
 // Use, modification and distribution are subject to the
 // Boost Software License, Version 1.0 (See accompanying file
@@ -8,123 +8,122 @@
 #define BOOST_GRAPH_DETAIL_GEODESIC_HPP
 
 #include <functional>
-#include <boost/graph/new_graph_concepts.hpp>
+#include <boost/graph/graph_concepts.hpp>
 #include <boost/graph/numeric_values.hpp>
 
+// TODO: Should this really be in detail?
+
 namespace boost
 {
-    // This is a very good discussion on centrality measures. While I can't
-    // say that this has been the motivating factor for the design and
-    // implementation of ths centrality framework, it does provide a single
-    // point of reference for defining things like degree and closeness
-    // centrality. Plus, the bibliography seems fairly complete.
-    //
-    //     @article{citeulike:1144245,
-    //         author = {Borgatti, Stephen  P.  and Everett, Martin  G. },
-    //         citeulike-article-id = {1144245},
-    //         doi = {10.1016/j.socnet.2005.11.005},
-    //         journal = {Social Networks},
-    //         month = {October},
-    //         number = {4},
-    //         pages = {466--484},
-    //         priority = {0},
-    //         title = {A Graph-theoretic perspective on centrality},
-    //         url = {http://dx.doi.org/10.1016/j.socnet.2005.11.005},
-    //             volume = {28},
-    //             year = {2006}
-    //         }
-    //     }
-
-
-    namespace detail
+// This is a very good discussion on centrality measures. While I can't
+// say that this has been the motivating factor for the design and
+// implementation of ths centrality framework, it does provide a single
+// point of reference for defining things like degree and closeness
+// centrality. Plus, the bibliography seems fairly complete.
+//
+//     @article{citeulike:1144245,
+//         author = {Borgatti, Stephen  P. and Everett, Martin  G.},
+//         citeulike-article-id = {1144245},
+//         doi = {10.1016/j.socnet.2005.11.005},
+//         journal = {Social Networks},
+//         month = {October},
+//         number = {4},
+//         pages = {466--484},
+//         priority = {0},
+//         title = {A Graph-theoretic perspective on centrality},
+//         url = {http://dx.doi.org/10.1016/j.socnet.2005.11.005},
+//             volume = {28},
+//             year = {2006}
+//         }
+//     }
+
+namespace detail {
+    // Note that this assumes T == property_traits<DistanceMap>::value_type
+    // and that the args and return of combine are also T.
+    template <typename Graph,
+                typename DistanceMap,
+                typename Combinator,
+                typename Distance>
+    inline Distance
+    combine_distances(const Graph& g,
+                        DistanceMap dist,
+                        Combinator combine,
+                        Distance init)
     {
-        // Note that this assumes T == property_traits<DistanceMap>::value_type
-        // and that the args and return of combine are also T.
-        template <typename Graph,
-                  typename DistanceMap,
-                  typename Combinator,
-                  typename Distance>
-        inline Distance
-        combine_distances(const Graph& g,
-                          DistanceMap dist,
-                          Combinator combine,
-                          Distance init)
-        {
-            function_requires< VertexListGraphConcept<Graph> >();
-            typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-            typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
-            function_requires< ReadablePropertyMapConcept<DistanceMap,Vertex> >();
-            function_requires< NumericValueConcept<Distance> >();
-            typedef numeric_values<Distance> DistanceNumbers;
-            function_requires< AdaptableBinaryFunction<Combinator,Distance,Distance,Distance> >();
-
-            // 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) {
-                Vertex v = *i;
-                if(get(dist, v) != DistanceNumbers::infinity()) {
-                    ret = combine(ret, get(dist, v));
-                }
-                else {
-                    ret = DistanceNumbers::infinity();
-                    break;
-                }
+        function_requires< VertexListGraphConcept<Graph> >();
+        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+        typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+        function_requires< ReadablePropertyMapConcept<DistanceMap,Vertex> >();
+        function_requires< NumericValueConcept<Distance> >();
+        typedef numeric_values<Distance> DistanceNumbers;
+        function_requires< AdaptableBinaryFunction<Combinator,Distance,Distance,Distance> >();
+
+        // 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) {
+            Vertex v = *i;
+            if(get(dist, v) != DistanceNumbers::infinity()) {
+                ret = combine(ret, get(dist, v));
+            }
+            else {
+                ret = DistanceNumbers::infinity();
+                break;
             }
-            return ret;
         }
-
-
-        // Similar to std::plus<T>, but maximizes parameters
-        // rather than adding them.
-        template <typename T>
-        struct maximize : public std::binary_function<T, T, T>
-        {
-            T operator ()(T x, T y) const
-            { return std::max(x, y); }
-        };
-
-        // Another helper, like maximize() to help abstract functional
-        // concepts. This is trivially instantiated for builtin numeric
-        // types, but should be specialized for those types that have
-        // discrete notions of reciprocals.
-        template <typename T>
-        struct reciprocal : public std::unary_function<T, T>
-        {
-            typedef std::unary_function<T, T> function_type;
-            typedef typename function_type::result_type result_type;
-            typedef typename function_type::argument_type argument_type;
-            T operator ()(T t)
-            { return T(1) / t; }
-        };
+        return ret;
     }
 
-    // This type defines the basic facilities used for computing values
-    // based on the geodesic distances between vertices. Examples include
-    // closeness centrality and mean geodesic distance.
-    template <typename Graph,
-              typename DistanceType,
-              typename ResultType>
-    struct geodesic_measure
+    // Similar to std::plus<T>, but maximizes parameters
+    // rather than adding them.
+    template <typename T>
+    struct maximize : public std::binary_function<T, T, T>
     {
-        typedef DistanceType distance_type;
-        typedef ResultType result_type;
-        typedef typename graph_traits<Graph>::vertices_size_type size_type;
+        T operator ()(T x, T y) const
+        { return std::max(x, y); }
+    };
 
-        typedef numeric_values<distance_type> distance_values;
-        typedef numeric_values<result_type> result_values;
+    // Another helper, like maximize() to help abstract functional
+    // concepts. This is trivially instantiated for builtin numeric
+    // types, but should be specialized for those types that have
+    // discrete notions of reciprocals.
+    template <typename T>
+    struct reciprocal : public std::unary_function<T, T>
+    {
+        typedef std::unary_function<T, T> function_type;
+        typedef typename function_type::result_type result_type;
+        typedef typename function_type::argument_type argument_type;
+        T operator ()(T t)
+        { return T(1) / t; }
+    };
+} /* namespace detail */
 
-        static inline distance_type infinite_distance()
-        { return distance_values::infinity(); }
+// This type defines the basic facilities used for computing values
+// based on the geodesic distances between vertices. Examples include
+// closeness centrality and mean geodesic distance.
+template <typename Graph, typename DistanceType, typename ResultType>
+struct geodesic_measure
+{
+    typedef DistanceType distance_type;
+    typedef ResultType result_type;
+    typedef typename graph_traits<Graph>::vertices_size_type size_type;
 
-        static inline result_type infinite_result()
-        { return result_values::infinity(); }
+    typedef numeric_values<distance_type> distance_values;
+    typedef numeric_values<result_type> result_values;
+
+    static inline distance_type infinite_distance()
+    { return distance_values::infinity(); }
+
+    static inline result_type infinite_result()
+    { return result_values::infinity(); }
+
+    static inline result_type zero_result()
+    { return result_values::zero(); }
+};
+
+} /* namespace boost */
 
-        static inline result_type zero_result()
-        { return result_values::zero(); }
-    };
-}
 #endif

Copied: trunk/boost/graph/detail/index.hpp (from r51086, /sandbox/SOC/2007/graphs/boost/graph/detail/index.hpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/boost/graph/detail/index.hpp	(original)
+++ trunk/boost/graph/detail/index.hpp	2009-02-08 10:28:31 EST (Sun, 08 Feb 2009)
@@ -1,14 +1,19 @@
-// (C) Copyright Andrew Sutton 2007
+// (C) Copyright 2007-2009 Andrew Sutton
 //
 // 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_DETAIL_INDEX_HXX
-#define BOOST_GRAPH_DETAIL_INDEX_HXX
+#ifndef BOOST_GRAPH_DETAIL_INDEX_HPP
+#define BOOST_GRAPH_DETAIL_INDEX_HPP
 
 #include <boost/graph/graph_traits.hpp>
 
+// The structures in this module are responsible for selecting and defining
+// types for accessing a builting index map. Note that the selection of these
+// types requires the Graph parameter to model either VertexIndexGraph or
+// EdgeIndexGraph.
+
 namespace boost
 {
     namespace detail
@@ -51,6 +56,8 @@
             { return get(edge_index, g, k); }
         };
 
+        // NOTE: The Graph parameter MUST be a model of VertexIndexGraph or
+        // VertexEdgeGraph - whichever type Key is selecting.
         template <typename Graph, typename Key>
         struct choose_indexer
         {

Copied: trunk/boost/graph/exterior_property.hpp (from r51086, /sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp	(original)
+++ trunk/boost/graph/exterior_property.hpp	2009-02-08 10:28:31 EST (Sun, 08 Feb 2009)
@@ -1,4 +1,4 @@
-// (C) Copyright Andrew Sutton 2007
+// (C) Copyright 2007-2009 Andrew Sutton
 //
 // Use, modification and distribution are subject to the
 // Boost Software License, Version 1.0 (See accompanying file
@@ -8,93 +8,110 @@
 #define BOOST_GRAPH_EXTERIOR_PROPERTY_HPP
 
 #include <vector>
-#include <boost/graph/container_property_map.hpp>
-#include <boost/graph/matrix_property_map.hpp>
+#include <boost/graph/property_maps/container_property_map.hpp>
+#include <boost/graph/property_maps/matrix_property_map.hpp>
 
-namespace boost
-{
-    namespace detail
+namespace boost {
+namespace detail {
+    // The vector matrix provides a little abstraction over vector
+    // types that makes matrices easier to work with. Note that it's
+    // non-copyable, meaning you should be passing it by value.
+    template <typename Value>
+    struct vector_matrix
     {
-        // The vector matrix provides a little abstraction over vector
-        // types that makes matrices easier to work with. Note that it's
-        // non-copyable, meaning you should be passing it by value.
-        template <typename Value>
-        struct vector_matrix
-        {
-            typedef std::vector<Value> container_type;
-            typedef std::vector<container_type> matrix_type;
-
-            typedef container_type value_type;
-            typedef container_type& reference;
-            typedef const container_type const_reference;
-            typedef container_type* pointer;
-            typedef typename matrix_type::size_type size_type;
-
-            // Instantiate the matrix over n elements (creates an nxn matrix).
-            // The graph has to be passed in order to ensure the index maps
-            // are constructed correctly when returning indexible elements.
-            inline vector_matrix(size_type n)
-                : m_matrix(n, container_type(n))
-            { }
-
-            inline reference operator [](size_type n)
-            { return m_matrix[n]; }
-
-            inline const_reference operator [](size_type n) const
-            { return m_matrix[n]; }
-
-            matrix_type m_matrix;
-        };
-    }
+        typedef std::vector<Value> container_type;
+        typedef std::vector<container_type> matrix_type;
 
-    template <typename Graph, typename Key, typename Value>
-    struct exterior_property
-    {
-        typedef Key key_type;
-        typedef Value value_type;
+        typedef container_type value_type;
+        typedef container_type& reference;
+        typedef const container_type const_reference;
+        typedef container_type* pointer;
+        typedef typename matrix_type::size_type size_type;
+
+        // Instantiate the matrix over n elements (creates an nxn matrix).
+        // The graph has to be passed in order to ensure the index maps
+        // are constructed correctly when returning indexible elements.
+        inline vector_matrix(size_type n)
+            : m_matrix(n, container_type(n))
+        { }
 
-        typedef std::vector<Value> container_type;
-        typedef container_property_map<Graph, Key, container_type> map_type;
+        inline reference operator [](size_type n)
+        { return m_matrix[n]; }
 
-        typedef detail::vector_matrix<Value> matrix_type;
-        typedef matrix_property_map<Graph, Key, matrix_type> matrix_map_type;
+        inline const_reference operator [](size_type n) const
+        { return m_matrix[n]; }
 
-    private:
-        exterior_property() { }
-        exterior_property(const exterior_property&) { }
+        matrix_type m_matrix;
     };
+} /* namespace detail */
 
-    template <typename Graph, typename Value>
-    struct exterior_vertex_property
-    {
-        typedef exterior_property<
-                Graph,
-                typename graph_traits<Graph>::vertex_descriptor,
-                Value
-            > property_type;
-        typedef typename property_type::key_type key_type;
-        typedef typename property_type::value_type value_type;
-        typedef typename property_type::container_type container_type;
-        typedef typename property_type::map_type map_type;
-        typedef typename property_type::matrix_type matrix_type;
-        typedef typename property_type::matrix_map_type matrix_map_type;
-    };
+/**
+ * The exterior_property metafunction defines an appropriate set of types for
+ * creating an exterior property. An exterior property is comprised of a both
+ * a container and a property map that acts as its abstraction. An extension
+ * of this metafunction will select an appropriate "matrix" property that
+ * records values for pairs of vertices.
+ *
+ * @todo This does not currently support the ability to define exterior
+ * properties for graph types that do not model the IndexGraph concepts. A
+ * solution should not be especially difficult, but will require an extension
+ * of type traits to affect the type selection.
+ */
+template <typename Graph, typename Key, typename Value>
+struct exterior_property
+{
+    typedef Key key_type;
+    typedef Value value_type;
 
-    template <typename Graph, typename Value>
-    struct exterior_edge_property
-    {
-        typedef exterior_property<
-                Graph,
-                typename graph_traits<Graph>::edge_descriptor,
-                Value
-            > property_type;
-        typedef typename property_type::key_type key_type;
-        typedef typename property_type::value_type value_type;
-        typedef typename property_type::container_type container_type;
-        typedef typename property_type::map_type map_type;
-        typedef typename property_type::matrix_type matrix_type;
-        typedef typename property_type::matrix_map_type matrix_map_type;
-    };
-}
+    typedef std::vector<Value> container_type;
+    typedef container_property_map<Graph, Key, container_type> map_type;
+
+    typedef detail::vector_matrix<Value> matrix_type;
+    typedef matrix_property_map<Graph, Key, matrix_type> matrix_map_type;
+
+private:
+    exterior_property() { }
+    exterior_property(const exterior_property&) { }
+};
+
+/**
+ * Define a the container and property map types requried to create an exterior
+ * vertex property for the given value type. The Graph parameter is required to
+ * model the VertexIndexGraph concept.
+ */
+template <typename Graph, typename Value>
+struct exterior_vertex_property
+{
+    typedef exterior_property<
+            Graph, typename graph_traits<Graph>::vertex_descriptor, Value
+        > property_type;
+    typedef typename property_type::key_type key_type;
+    typedef typename property_type::value_type value_type;
+    typedef typename property_type::container_type container_type;
+    typedef typename property_type::map_type map_type;
+    typedef typename property_type::matrix_type matrix_type;
+    typedef typename property_type::matrix_map_type matrix_map_type;
+};
+
+/**
+ * Define a the container and property map types requried to create an exterior
+ * edge property for the given value type. The Graph parameter is required to
+ * model the EdgeIndexGraph concept.
+ */
+template <typename Graph, typename Value>
+struct exterior_edge_property
+{
+    typedef exterior_property<
+            Graph, typename graph_traits<Graph>::edge_descriptor, Value
+        > property_type;
+    typedef typename property_type::key_type key_type;
+    typedef typename property_type::value_type value_type;
+    typedef typename property_type::container_type container_type;
+    typedef typename property_type::map_type map_type;
+    typedef typename property_type::matrix_type matrix_type;
+    typedef typename property_type::matrix_map_type matrix_map_type;
+};
+
+} /* namespace boost */
 
 #endif

Copied: trunk/boost/graph/property_maps/constant_property_map.hpp (from r51086, /sandbox/SOC/2007/graphs/boost/graph/constant_property_map.hpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/boost/graph/constant_property_map.hpp	(original)
+++ trunk/boost/graph/property_maps/constant_property_map.hpp	2009-02-08 10:28:31 EST (Sun, 08 Feb 2009)
@@ -1,4 +1,4 @@
-// (C) Copyright Andrew Sutton 2007
+// (C) Copyright 2007-2009 Andrew Sutton
 //
 // Use, modification and distribution are subject to the
 // Boost Software License, Version 1.0 (See accompanying file
@@ -9,50 +9,51 @@
 
 #include <boost/property_map.hpp>
 
-namespace boost
+
+// TODO: This should really be part of the property maps library rather than
+// the Boost.Graph library.
+
+namespace boost {
+
+/**
+ * A constant property is one, that regardless of the edge or vertex given,
+ * will always return a constant value.
+ */
+template <typename Key, typename Value>
+struct constant_property_map
+    : public boost::put_get_helper<
+            const Value&,
+            constant_property_map<Key, Value>
+    >
 {
-    // A constant property is one, that regardless of the
-    // edge or vertex given, will always return a constant
-    // value.
-
-    // The key is pretty much anything it doesn't matter. The
-    // value has to be default and copy constructible.
-
-    template <typename Key, typename Value>
-    struct constant_property_map
-        : public boost::put_get_helper<
-                const Value&,
-                constant_property_map<Key, Value> >
-    {
-        typedef Key key_type;
-        typedef Value value_type;
-        typedef const Value& reference;
-        typedef boost::readable_property_map_tag category;
-
-        constant_property_map()
-            : m_value()
-        { }
-
-        constant_property_map(const value_type &value)
-            : m_value(value)
-        { }
-
-        constant_property_map(const constant_property_map& copy)
-            : m_value(copy.m_value)
-        { }
-
-        inline reference operator [](const key_type& v) const
-        { return m_value; }
-
-        value_type m_value;
-    };
-
-    template <typename Key, typename Value>
-    inline constant_property_map<Key, Value>
-    make_constant_property(const Value& value)
-    {
-        return constant_property_map<Key, Value>(value);
-    }
-}
+    typedef Key key_type;
+    typedef Value value_type;
+    typedef const Value& reference;
+    typedef boost::readable_property_map_tag category;
+
+    constant_property_map()
+        : m_value()
+    { }
+
+    constant_property_map(const value_type &value)
+        : m_value(value)
+    { }
+
+    constant_property_map(const constant_property_map& copy)
+        : m_value(copy.m_value)
+    { }
+
+    inline reference operator [](const key_type& v) const
+    { return m_value; }
+
+    value_type m_value;
+};
+
+template <typename Key, typename Value>
+inline constant_property_map<Key, Value>
+make_constant_property(const Value& value)
+{ return constant_property_map<Key, Value>(value); }
+
+} /* namespace boost */
 
 #endif

Copied: trunk/boost/graph/property_maps/container_property_map.hpp (from r51086, /sandbox/SOC/2007/graphs/boost/graph/container_property_map.hpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/boost/graph/container_property_map.hpp	(original)
+++ trunk/boost/graph/property_maps/container_property_map.hpp	2009-02-08 10:28:31 EST (Sun, 08 Feb 2009)
@@ -1,11 +1,11 @@
-// (C) Copyright Andrew Sutton 2007
+// (C) Copyright 2007-2009 Andrew Sutton
 //
 // 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_CONTAINER_PROPERTY_MAP_HXX
-#define BOOST_GRAPH_CONTAINER_PROPERTY_MAP_HXX
+#ifndef BOOST_GRAPH_CONTAINER_PROPERTY_MAP_HPP
+#define BOOST_GRAPH_CONTAINER_PROPERTY_MAP_HPP
 
 #include <boost/graph/detail/index.hpp>
 #include <boost/property_map.hpp>

Copied: trunk/boost/graph/property_maps/matrix_property_map.hpp (from r51086, /sandbox/SOC/2007/graphs/boost/graph/matrix_property_map.hpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/boost/graph/matrix_property_map.hpp	(original)
+++ trunk/boost/graph/property_maps/matrix_property_map.hpp	2009-02-08 10:28:31 EST (Sun, 08 Feb 2009)
@@ -1,13 +1,13 @@
-// (C) Copyright Andrew Sutton 2007
+// (C) Copyright 2007-2009 Andrew Sutton
 //
 // 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_MATRIX_PROPERTY_MAP_HXX
-#define BOOST_GRAPH_MATRIX_PROPERTY_MAP_HXX
+#ifndef BOOST_GRAPH_MATRIX_PROPERTY_MAP_HPP
+#define BOOST_GRAPH_MATRIX_PROPERTY_MAP_HPP
 
-#include <boost/graph/container_property_map.hpp>
+#include <boost/graph/property_maps/container_property_map.hpp>
 
 namespace boost
 {

Modified: trunk/boost/graph/tiernan_all_cycles.hpp
==============================================================================
--- trunk/boost/graph/tiernan_all_cycles.hpp	(original)
+++ trunk/boost/graph/tiernan_all_cycles.hpp	2009-02-08 10:28:31 EST (Sun, 08 Feb 2009)
@@ -4,8 +4,8 @@
 // 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_CYCLE_HXX
-#define BOOST_GRAPH_CYCLE_HXX
+#ifndef BOOST_GRAPH_CYCLE_HPP
+#define BOOST_GRAPH_CYCLE_HPP
 
 #include <vector>