[Boost-commit] svn:boost r7377

From: asutton_at_[hidden]
Date: 2007-07-06 14:09:54

Author: asutton
Date: 2007-07-06 14:09:52 EDT (Fri, 06 Jul 2007)
New Revision: 7377
URL: http://svn.boost.org/trac/boost/changeset/7377

Log:
- Removed the older geodesic header
- Moved all distance computations into distance.hpp
- Implemented geodesic_distance(), mean_geodesic_distance(),
  closeness(), eccentricity(), eccentricities(), radius(),
  diameter(), center(), and periphery() - basically anything
  I could think to build related to distance measures
- Did some work on the reference docs
- Experimented with some Boost.Parameter prototypes for
  connectivity and distributions

Added:
   sandbox/SOC/2007/graphs/boost/graph/distance.hpp
   sandbox/SOC/2007/graphs/boost/graph/named_parameters.hpp
   sandbox/SOC/2007/graphs/libs/graph/test/components.cpp
   sandbox/SOC/2007/graphs/libs/graph/test/distance.cpp
Removed:
   sandbox/SOC/2007/graphs/boost/graph/geodesic.hpp
Text files modified: 
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk                          |     6                                         
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connected_components.qbk |     8                                         
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connectivity.qbk         |   109 ++++++++++++++++++++++----              
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/directed_graph.qbk       |    73 +++++++++++------                       
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/distributions.qbk        |   166 +++++++++++++++++++++++++-------------- 
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/reference.qbk            |     3                                         
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/undirected_graph.qbk     |     2                                         
   sandbox/SOC/2007/graphs/libs/graph/examples/movies/stats.cpp                        |     3                                         
   sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2                                  |    15 +++                                     
   9 files changed, 270 insertions(+), 115 deletions(-)

Added: sandbox/SOC/2007/graphs/boost/graph/distance.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/distance.hpp	2007-07-06 14:09:52 EDT (Fri, 06 Jul 2007)
@@ -0,0 +1,208 @@
+// (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_DISTANCE_HPP
+#define BOOST_GRAPH_DISTANCE_HPP
+
+// boost includes
+#include <boost/graph/named_parameters.hpp>
+#include <boost/graph/properties.hpp>
+#include <boost/graph/adjacency_list.hpp>
+
+namespace boost
+{
+    namespace detail
+    {
+        template <typename Graph, typename DistanceMap>
+        inline typename property_traits<DistanceMap>::value_type
+        sum_distances(const Graph& g, DistanceMap dist)
+        {
+            size_t ret = 0;
+            typename graph_traits<Graph>::vertex_iterator i, end;
+            for(tie(i, end) = vertices(g); i != end; ++i) {
+                ret += dist[*i];
+            }
+            return ret;
+        }
+    }
+
+
+    // These measures operate on the first vertex given. This is to say that
+    // closeness(g, v, dist) will return the closeness of the vertex v with
+    // respect to all other vertices in the graph.
+    //
+    // Note that the target vertex in each algorithm is essentially a dummy
+    // parameter (for now). If the distance map isn't supplied, then we
+    // may shell to default computations.
+    //
+    // Vertex distance measures:
+    // - geodesic_distance
+    // - mean_geodesic_distance
+    // - closeness
+    // - eccentricity
+    //
+    // Graph distance measures:
+    // - radius
+    // - diameter
+    //
+    // Note that two versions of each algorithm exist. One takes a precomputed
+    // distance map or matrix while the other computes it on the fly by trying
+    // to guess an algorithm to use.
+
+
+    template <typename Graph, typename DistanceMap>
+    inline typename property_traits<DistanceMap>::value_type
+    geodesic_distance(const Graph& g,
+                      typename graph_traits<Graph>::vertex_descriptor v,
+                      DistanceMap dist)
+    {
+        return dist[get(vertex_index, g, v)];
+    }
+
+    template <typename Graph, typename DistanceMap>
+    inline double
+    mean_geodesic_distance(const Graph& g,
+                           DistanceMap dist)
+    {
+        return (double)detail::sum_distances(g, dist) / (double)num_vertices(g);
+    }
+
+    template <typename Graph, typename DistanceMap>
+    inline double
+    closeness(const Graph& g,
+              DistanceMap dist)
+    {
+        return 1.0 / (double)detail::sum_distances(g, dist);
+    }
+
+    // Can we abstract the computation of max on distances to max of
+    // something else that we can put into a distance map? For example,
+    // this is the max of geodesics... What if we wanted some other
+    // operator?
+
+    template <typename Graph, typename DistanceMap>
+    inline typename property_traits<DistanceMap>::value_type
+    eccentricity(const Graph& g,
+                 DistanceMap dist)
+    {
+        typename property_traits<DistanceMap>::value_type ret = 0;
+        typename graph_traits<Graph>::vertex_iterator i, end;
+        for(tie(i, end) = vertices(g); i != end; ++i) {
+            ret = std::max(ret, dist[*i]);
+        }
+        return ret;
+    }
+
+    // The computation of eccentricities, radius and diameter are all
+    // closely related. Basically, these computations can be run at
+    // the same time - compute eccentricities of all vertices, and
+    // the radius and diameter of the graph.
+
+    template <typename Graph, typename DistanceMatrix, typename EccentricityMap>
+    void
+    eccentricities(const Graph& g, DistanceMatrix& dist, EccentricityMap ecc)
+    {
+        typename Graph::vertex_iterator i, j, end;
+        for(tie(i, end) = vertices(g); i != end; ++i) {
+            // compute the max eccentricity "in-place"
+            typename property_traits<EccentricityMap>::value_type& ei = ecc[*i];
+            for(j = vertices(g).first; j != end; ++j) {
+                ei = std::max(ei, dist[*i][*j]);
+            }
+        }
+    }
+
+    template <typename Graph, typename EccentricityMap>
+    inline typename property_traits<EccentricityMap>::value_type
+    radius(const Graph& g, EccentricityMap ecc)
+    {
+        typedef typename property_traits<EccentricityMap>::value_type eccentricity;
+
+        eccentricity ret = ecc[*vertices(g).first];
+        typename Graph::vertex_iterator i, end;
+        for(tie(i, end) = vertices(g); i != end; ++i) {
+            ret = std::min(ret, ecc[*i]);
+        }
+        return ret;
+    }
+
+    template <typename Graph, typename EccentricityMap>
+    inline typename property_traits<EccentricityMap>::value_type
+    diameter(const Graph& g, EccentricityMap ecc)
+    {
+        typedef typename property_traits<EccentricityMap>::value_type eccentricity;
+
+        eccentricity ret = ecc[*vertices(g).first];
+        typename Graph::vertex_iterator i, end;
+        for(tie(i, end) = vertices(g); i != end; ++i) {
+            ret = std::max(ret, ecc[*i]);
+        }
+        return ret;
+    }
+
+    // The following functions are pretty much gimmes once we've computed
+    // some of the other properties (like eccentricities, radius, and
+    // diameter).
+
+    namespace detail
+    {
+        template <typename Graph, typename EccentricityMap, typename Inserter>
+        inline void
+        radial_grouping(const Graph& g,
+                        EccentricityMap ecc,
+                        Inserter ins,
+                        typename property_traits<EccentricityMap>::value_type level)
+        {
+            typename Graph::vertex_iterator i, end;
+            for(tie(i, end) = vertices(g); i != end; ++i) {
+                if(ecc[*i] == level) {
+                    *ins++ = *i;
+                }
+            }
+        }
+    }
+
+    template <typename Graph, typename EccentricityMap, typename Inserter>
+    inline void
+    center(const Graph& g,
+           typename property_traits<EccentricityMap>::value_type r,
+           EccentricityMap ecc,
+           Inserter ins)
+    {
+        return detail::radial_grouping(g, ecc, ins, r);
+    }
+
+    template <typename Graph, typename EccentricityMap, typename Inserter>
+    inline void
+    center(const Graph& g,
+           EccentricityMap ecc,
+           Inserter ins)
+    {
+        return detail::radial_grouping(g, ecc, ins, radius(g, ecc));
+    }
+
+
+    template <typename Graph, typename EccentricityMap, typename Inserter>
+    inline void
+    periphery(const Graph& g,
+              typename property_traits<EccentricityMap>::value_type d,
+              EccentricityMap ecc,
+              Inserter ins)
+    {
+        return detail::radial_grouping(g, ecc, ins, d);
+    }
+
+    template <typename Graph, typename EccentricityMap, typename Inserter>
+    inline void
+    periphery(const Graph& g,
+              EccentricityMap ecc,
+              Inserter ins)
+    {
+        return detail::radial_grouping(g, ecc, ins, diameter(g, ecc));
+    }
+}
+
+#endif

Deleted: sandbox/SOC/2007/graphs/boost/graph/geodesic.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/geodesic.hpp	2007-07-06 14:09:52 EDT (Fri, 06 Jul 2007)
+++ (empty file)
@@ -1,71 +0,0 @@
-
-#ifndef DIAMETER_HXX
-#define DIAMETER_HXX
-
-// std includes
-#include <vector>
-#include <limits>
-
-// boost includes
-#include <boost/graph/johnson_all_pairs_shortest.hpp>
-
-/**
- * Compute the diameter of the graoh - which is essentially the longest
- * of all shortest paths (or the longest geodesic). At the moment, this
- * algorithm uses johnson's variant which runs in O(n*m*log n). Note that
- * when the graph is dense (i.e., m -> n^2), this takes O(n^3 * log n)
- * which is actually worse than floyd warshall. However, this should run
- * fine on power-law graphs since they're relatively sparse. Normally
- * distributed graphs might not be so lucky.
- *
- * There's some strange variations of this algorithm. For example,
- * if the graph is unconnected, then it really doesn't have an actual
- * diameter. If we igore infinite lenghts, then we are computing the
- * diameter of the largest connected component - which may actually
- * by acceptable.
- */
-template <
-    typename Graph,
-    typename Matrix
-    >
-int
-diameter(Graph &g, Matrix &d)
-{
-    using namespace std;
-    using namespace boost;
-
-    // various graph types
-    typedef Graph graph;
-    typedef typename graph_traits<graph>::vertex_descriptor vertex;
-
-    // matrix types
-
-    // for convenience, get the number of vertices
-    size_t n = num_vertices(g);
-
-    // find all pairs of shortest paths
-    int ret = 0;
-    bool success = johnson_all_pairs_shortest_paths(g, d);
-    if(success) {
-	// compute the maximum distance of elements in graph
-	for(size_t i = 0; i < n; ++i) {
-	    for(size_t j = 0; j < n; ++j) {
-		int dist = d[i][j];
-
-		// don't compute distances for disconnected
-		// vertices - this is kind of a weird point
-		// of logic
-		if(dist != numeric_limits<int>::max()) {
-		    if(dist > ret) {
-			ret = dist;
-		    }
-		}
-	    }
- 	}
-    }
-
-    return ret;
-}
-
-#endif
-

Added: sandbox/SOC/2007/graphs/boost/graph/named_parameters.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/named_parameters.hpp	2007-07-06 14:09:52 EDT (Fri, 06 Jul 2007)
@@ -0,0 +1,36 @@
+// (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_NAMED_PARAMETERS_HPP
+#define BOOST_GRAPH_NAMED_PARAMETERS_HPP
+
+// boost includes
+#include <boost/parameter.hpp>
+
+namespace boost
+{
+    BOOST_PARAMETER_NAME(graph)
+
+    // data and data sets
+    BOOST_PARAMETER_NAME(distribution)
+    BOOST_PARAMETER_NAME(in_distribution)
+    BOOST_PARAMETER_NAME(out_distribution)
+    BOOST_PARAMETER_NAME(histogram)
+    BOOST_PARAMETER_NAME(in_histogram)
+    BOOST_PARAMETER_NAME(out_histogram)
+    BOOST_PARAMETER_NAME(components)
+    BOOST_PARAMETER_NAME(is_connected)
+
+    // various map-type parameters
+    BOOST_PARAMETER_NAME(distance_map)
+    BOOST_PARAMETER_NAME(component_map)
+    BOOST_PARAMETER_NAME(color_map)
+    BOOST_PARAMETER_NAME(vertex_index_map)
+
+    struct not_given {};
+}
+
+#endif

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk	2007-07-06 14:09:52 EDT (Fri, 06 Jul 2007)
@@ -80,6 +80,7 @@
 [template BoostEventVisitorList[] [link boost_graph.concepts.visitor_concepts.event_visitor_list EventVisitorList]]
 
 [/ Boost Reference Documentation]
+[template boost_graph_traits[] [link boost_graph.reference_guide.traits_classes.graph_traits `graph_traits`]]
 [template boost_undirected_graph[] [link boost_graph.reference_guide.graph_types.undirected_graph `undirected_graph`]]
 [template boost_directed_graph[] [link boost_graph.reference_guide.graph_types.directed_graph `directed_graph`]]
 [template boost_adjacency_list[] [link boost_graph.reference_guide.graph_types.adjacency_list `adjacecncy_list`]]
@@ -95,8 +96,9 @@
 
 [template boost_breadth_first_search[] [link boost_graph.reference_guide.algorithms.core_algorithms.breadth_first_search `breadth_first_search()`]]
 [template boost_depth_first_search[] [link boost_graph.reference_guide.algorithms.core_algorithms.depth_first_search `depth_first_search()`]]
-[template boost_dijkstra_shortest_paths[] [link boost_graph.reference_guide.algorithms.shortest_path_algorithms.dijkstra_shortest_paths `dijkstra_shortest_paths`]]
-[template boost_bellman_ford_shortest_paths[] [link boost_graph.reference_guide.algorithms.shortest_path_algorithms.bellman_ford_shortest_paths `bellman_ford_shortest_paths`]]
+[template boost_dijkstra_shortest_paths[] [link boost_graph.reference_guide.algorithms.shortest_path_algorithms.dijkstra_shortest_paths `dijkstra_shortest_paths()`]]
+[template boost_bellman_ford_shortest_paths[] [link boost_graph.reference_guide.algorithms.shortest_path_algorithms.bellman_ford_shortest_paths `bellman_ford_shortest_paths()`]]
+[template boost_connected_components[] [link boost_graph.reference_guide.algorithms.connectivity_algorithms.connected_components `connected_components()`]]
 
 [/ Contents ]
 [include introduction.qbk]

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connected_components.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connected_components.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connected_components.qbk	2007-07-06 14:09:52 EDT (Fri, 06 Jul 2007)
@@ -6,10 +6,10 @@
  /]
 
 [section Connected Components]
- template <class Graph, class ComponentMap, class P, class T, class R>
- typename property_traits<ComponentMap>::value_type
- connected_components(const Graph &g, ComponentMap c,
-                      const bgl_named_params<P,T,R>& params = ``/defaults/``);
+    template <class Graph, class ComponentMap, class P, class T, class R>
+    typename property_traits<ComponentMap>::value_type
+    connected_components(const Graph &g, ComponentMap c,
+                        const bgl_named_params<P,T,R>& params = ``/defaults/``);
 
 
 The connected_components() functions compute the connected components of an undirected

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connectivity.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connectivity.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connectivity.qbk	2007-07-06 14:09:52 EDT (Fri, 06 Jul 2007)
@@ -6,23 +6,98 @@
  /]
 
 [section Connectivity Measures]
+    size_t connectivity(
+        _graph,
+        _component_map,
+        _color_map = not_given(),
+        _vertex_index_map = not_given(),
+        _components = not_given())
+
+The `connectivity()` algorithm is essentially a wrapper around the
+[boost_connected_components] algorithm, but provides additional (and optional)
+functionality for working with connected components. The parameters are, with
+the exeption of `_components`, have the same purpose and requirements as
+documented in [boost_connected_components].
+
+If specified, the `_components` argument is populated with the vertices that
+appear in each component. This is to say for example, that all vertices in the
+`_component_map` with component id 0, will be placed into the vertex set
+at index 0 of the `_components` argument.
+
+This function returns the number of connected components in the graph. Note
+that the graph is connected if and only if this function returns 1.
+
+[h5 Where Defined]
+`boost/graph/connectivity.hpp`
+
+[h5 Parameters]
+[table
+    [[Type] [Parameter] [Description]]
+    [
+        [required, in] [`_graph`]
+        [
+            The graph object for which the distribution will be computed. If
+            the `_distribution` or `_in_distribution` arguments are supplied
+            when calling this function then `_graph` must be a model of
+            [BoostBidirectionalGraph]. If only `_out_distribution` is supplied,
+            then `_graph` must be a model of [BoostIncidenceGraph].
+        ]
+    ]
+    [
+        [optional, out]
+        [
+            `_distribution`
+
+            `_out_distribution`
+
+            `_in_distribution`
+        ]
+        [
+            The distribution parameters maps instances of vertex degree to the
+            number of observed vertices in the graph with that degree.
+
+            These parameters must model both the [SgiSequence] and
+            [SgiRandomAccessContainer] concepts (e.g., `std::vector`). The index type of the
+            distribution must be the same as `degree_size_type`. The `value_type` must
+            be integral (preferably unsigned).
+
+            If not supplied, these parameters assume the default value of `not_given`,
+            implying that no computation is performed.
+        ]
+    ]
+    [
+        [optional, out]
+        [
+            `_histogram`
+
+            `_out_histogram`
+
+            `_in_histogram`
+        ]
+        [
+            The distribution parameters maps instances of vertex degree to the
+            number of observed vertices in the graph with that degree.
+
+            The histogram output parameter must be a model of both [SgiSequence]
+            and [SgiRandomAccessContainer] (e.g., `std::vector`). The index type of the
+            distribution must be the same as `degree_size_type`. Additionally `value_type`
+            must be a model of the [SgiBackInsertionSequence] (e.g., `std::vector`).
+
+            If not supplied, these parameters assume the default value of `not_given`,
+            implying that no computation is performed.
+        ]
+    ]
+]
+
+[h5 Return Value]
+This function returns the number of connected components.
 
-Reference for connectivity measures. Apparently, these are just going to be
-simple wrappers around connected_components or strong_components to provide
-some extra information. These might include:
-
-* `is_connected()`, `is_strongly_connected()`
-* `largest_connected_component()`, `largest_strong_component()`
-
-We might extend these for biconnected components also. Essentially, these
-functions take the component map computed by the connectivity stuff as
-an input and produce results. If the connectivity map isn't provided,
-we could compute it on the fly.
-
-[Examples]
-
-``
- connected_comp
-``
+[h5 Complexity]
+
+[h5 Notes]
+
+[h5 Examples]
+
+[h5 Rationale]
 
 [endsect]
\ No newline at end of file

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/directed_graph.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/directed_graph.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/directed_graph.qbk	2007-07-06 14:09:52 EDT (Fri, 06 Jul 2007)
@@ -7,7 +7,12 @@
 
 [section Directed Graph]
 This section provides detailed information about the `directed_graph` class,
-its associated types, member functions and non-member interface.
+its associated types, member functions and non-member interface. A directed
+graph is one in which edges have distinct direction. Edges flow from a /source/
+vertex to a /target/ and are generally only traversed through the outgoing
+edges of a vertex. However, incoming edges are also accessible. The class
+provides a general purpose implementation of directed graphs and can be
+used with algorithms in the Boost Graph Library.
 
 [h4 Notation]
 The following notation is used in this documentation. The following type names
@@ -54,23 +59,24 @@
     [[`v`] [The value of a property (usually a template parameter)]]
 ]
 
-[h4 Vertex and Edge Storage]
-The `directed` graph class has four distinct storage compontents: one for each
-of vertices, edges, out-edges per vertex, and in-edges per vertex. Each of these
-storage components uses a `std::list`. This is important to remember when
-considering the performance of oeprations on these graphs.
-
-Note that mutating (modifying) edge operations on a graph must operate on three
-different lists. For example, adding an edge to the graph will insert the edge
-or descriptors into the edge list, the out-edge list of the source vertex, and
-the in-edge list of the target vertex. These lists are accessible via the
-`edges(g)`, `out_edges(v,g)`, and `in_edges(v,g)` respectively.
-
 [h4 Descriptor and Iterator Stability]
 With the `directed_graph` class, descriptors and iterators remain stable after
-most operations. This is to say that removing a vertex or edge will not invalidate
-descriptors and iterators to other vertices or edges except for the edge or
-vertex that was actually removed.
+all operations except descriptors and iterators to those edges or vertices being
+removed. Removing a vertex or edge will not invalidate descriptors or iterators
+referencing other vertices or edges.
+
+For example, consider the following code:
+
+    directed_graph<> g;
+    directed_graph<>::vertex_descriptor u = add_vertex(g);
+    directed_graph<>::vertex_descriptor v = add_vertex(g);
+    directed_graph<>::vertex_descriptor w = add_vertex(g);
+    remove_vertex(u);
+    add_edge(v, w, g);
+
+After running this program, the descriptor `u` will be invalid but `v` and `w` will
+still be valid so the call to `add_edge(v,w,g)` is also valid. Note that this
+property does not hold for all graph types.
 
 [h4 Vertex Indexing and Stability]
 The `directed_graph` class provides a built-in internal properties for vertex
@@ -81,6 +87,10 @@
 the only operation that invalidates vertex indices, but the vertices will need
 to be renumbered using the `renumber_vertex_indices()` function.
 
+The `remove_vertex_and_renumber_indices(vi,g)` function can be used to autmoatically
+renumber indices after removing the vertex referenced by the given iterator. Because
+this function runs in linear time, it should not be used for repeated removals.
+
 [h4 Template Parameters]
 There are three parameters to the `directed_graph` class.
 [table
@@ -103,14 +113,15 @@
 ]
 
 [h5 Model Of]
-VertexAndEdgeListGraph, MutablePropertyGraph, CopyConstructible, Assignable, and Serializable.
+[BoostIncidenceGraph], [BoostVertexListGraph], [BoostEdgeListGraph], [BoostAdjacencyGraph],
+[BoostMutableGraph], and [BoostPropertyGraph].
 
 [h5 Where Defined]
 `boost/graph/directed_graph.hpp`
 
 [h4 Associated Types]
 There are a number of useful types associated with the `directed_graph` class.
-Most of these are accessed through `graph_traits` or other template classes.
+Most of these are accessed through [boost_graph_traits] or other template classes.
 For convenience these types have been grouped by purpose.
 
 [h5 Descriptor Types]
@@ -119,17 +130,23 @@
     [
         [`graph_traits<directed_graph>::vertex_descriptor`]
         [
-            The type for the vertex descriptors associated with the graph.
+            The type for the vertex descriptors associated with the graph. The `vertex_descriptor`
+            models the [BoostDescriptor] and [NoConcept Hashable] concepts.
         ]
     ]
     [
         [`graph_traits<directed_graph>::edge_descriptor`]
         [
-            The type for the edge descriptors associated with the graph.
+            The type for the edge descriptors associated with the graph. The `edge_descriptor`
+            models the [BoostDescriptor] and [NoConcept Hashable] concepts.
         ]
     ]
 ]
 
+Note that edge and vertex descriptors for the `unsigned_graph` can be used as keys for both
+[SgiSortedAssociativeContainer]s and [SgiHashedAssociativeContainer]s such as `std::map` and
+`std::tr1::unordered_map` respectively.
+
 [h5 Iterator Types]
 [table
     [[Type] [Description]]
@@ -137,35 +154,35 @@
         [`graph_traits<directed_graph>::vertex_iterator`]
         [
             The type for iterators returned by `vertices()`. Verex iterators are
-            models of the `BidirectionalIterator` concept.
+            models of the [SgiBidirectionalIterator] concept.
         ]
     ]
     [
         [`graph_traits<directed_graph>::edge_iterator`]
         [
             The type for iterators returned by `edges()`. Edge iterators are
-            models of the `BidirectionalIterator` concept.
+            models of the [SgiBidirectionalIterator] concept.
         ]
     ]
     [
         [`graph_traits<directed_graph>::out_edge_iterator`]
         [
             The type for iterators returned by `out_edges()`. Out-edge iterators
-            are models of the `BidirectionalIterator` concept.
+            are models of the [SgiBidirectionalIterator] concept.
         ]
     ]
     [
         [`graph_traits<directed_graph>::in_edge_iterator`]
         [
             The type for iterators returned by `in_edges()`. In-edge iterators
-            are models of the `BidirectionalIterator` concept.
+            are models of the [SgiBidirectionalIterator] concept.
         ]
     ]
     [
         [`graph_traits<directed_graph>::adjacency_iterator`]
         [
             The type for iterators returned by `adjacent_vertices`. Adjacency
-            iterators are models of the `BidirectionalIterator` concept.
+            iterators are models of the [SgiBidirectionalIterator] concept.
         ]
     ]
 ]
@@ -753,4 +770,10 @@
     ]
 ]
 
+[h4 Rationale]
+Unlike most graph classes in Boost.Graph, the `directed_graph` does not model the
+[BoostMutablePropertyGraph] concept. The reason for this is that it is relatively
+difficult from a usability standpoint to easily deduce the type to be passed as a
+property when adding vertices and edges - but especially vertices.
+
 [endsect]
\ No newline at end of file

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/distributions.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/distributions.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/distributions.qbk	2007-07-06 14:09:52 EDT (Fri, 06 Jul 2007)
@@ -6,29 +6,22 @@
  /]
 
 [section Degree Distributions]
- template <class Graph, class Distribution>
- void degree_distribution(const Graph &g, Distribution& dist);
+    void degree_distribution(
+        _graph,
+        _distribution = not_given(),
+        _out_distribution = not_given(),
+        _in_distribution = not_given())
+
+    void degree_histogram(
+        _graph,
+        _histogram = not_given(),
+        _out_histogram = not_given(),
+        _in_histogram = not_given())
 
- template <class Graph, class Distribution>
- void in_degree_distribution(const Graph &g, Distribution& dist);
-
- template <class Graph, class Distribution>
- void out_degree_distribution(const Graph &g, Distribution& dist);
-
-
- template <class Graph, class Histogram>
- void degree_histogram(const Graph &g, Histogram& dist);
-
- template <class Graph, class Histogram>
- void in_degree_histogram(const Graph &g, Histogram& dist);
-
- template <class Graph, class Histogram>
- void out_degree_histogram(const Graph &g, Histogram& dist);
-
-The degree distribution functions compute distributions of the degrees
+The degree distribution function compute distributions of the degrees
 of vertices in a graph. A distribution is mapping of an observable property
 to the number of occurences of that property. In this context, the observable
-property is the degree of a vertex (or in- and out- degree), which are in
+property is the degree of a vertex (or in- and out-degree), which are in
 the range \[0, /max{degree(v)}/\] Where /max{degree(v)}/ is the maximum degree
 of any vertex in a graph /G/. Therefore, the output distribution is mapping
 of vertex degree to its number of occurences in a graph.
@@ -39,48 +32,81 @@
 that degree. This is very useful if you want to quickly find all vertices with
 degree 0, or find the vertex with the highest degree.
 
-[heading Where Defined]
+In both of these functions, the computation of distribution or histogram
+depends on which optional parameters are passed to the function. If called as:
+
+    degree_distribution(g, _distribution = dist, _in_distribution = in_dist);
+
+The algorithm will compute both the degree destribution and in-degree distributions.
+Note that for undirected graphs, all three distributions or histograms will be
+identical.
+
+[h5 Where Defined]
 `boost/graph/degree_distribution.hpp`
 
-[heading Parameters]
+[h5 Parameters]
 [table
     [[Type] [Parameter] [Description]]
     [
-        [in] [`const Graph& g`]
+        [required, in] [`_graph`]
         [
-            The graph object for which the distribution will be computed. For
-            `degree_distributions()` and `in_degree_distribution()`, `g` must
-            be a model of a BidirectionalGraph. For `out_degree_distribution()`,
-            `g`, must model the IncidenceGraph concept.
+            The graph object for which the distribution will be computed. If
+            the `_distribution` or `_in_distribution` arguments are supplied
+            when calling this function then `_graph` must be a model of
+            [BoostBidirectionalGraph]. If only `_out_distribution` is supplied,
+            then `_graph` must be a model of [BoostIncidenceGraph].
         ]
     ]
     [
-        [out] [`Distribution& dist`]
+        [optional, out]
         [
-            The distribution parameter maps instances of degrees (numerically)
-            to the number of vertices in the graph that exhibit that degree.
+            `_distribution`
 
-            The distribution output parameter must be a model of both [SgiSequence]
-            and [SgiRandomAccessContainer] (e.g., `std::vector`). The index type of the
+            `_out_distribution`
+
+            `_in_distribution`
+        ]
+        [
+            The distribution parameters maps instances of vertex degree to the
+            number of observed vertices in the graph with that degree.
+
+            These parameters must model both the [SgiSequence] and
+            [SgiRandomAccessContainer] concepts (e.g., `std::vector`). The index type of the
             distribution must be the same as `degree_size_type`. The `value_type` must
             be integral (preferably unsigned).
+
+            If not supplied, these parameters assume the default value of `not_given`,
+            implying that no computation is performed.
         ]
     ]
     [
-        [out] [`Histogram& hist`]
+        [optional, out]
         [
-            The histogram parameter maps instances of degrees (numerically) to the
-            set of vertices that exhibit that degree.
+            `_histogram`
+
+            `_out_histogram`
+
+            `_in_histogram`
+        ]
+        [
+            The distribution parameters maps instances of vertex degree to the
+            number of observed vertices in the graph with that degree.
 
             The histogram output parameter must be a model of both [SgiSequence]
             and [SgiRandomAccessContainer] (e.g., `std::vector`). The index type of the
             distribution must be the same as `degree_size_type`. Additionally `value_type`
             must be a model of the [SgiBackInsertionSequence] (e.g., `std::vector`).
+
+            If not supplied, these parameters assume the default value of `not_given`,
+            implying that no computation is performed.
         ]
     ]
 ]
 
-[h4 Complexity]
+[h5 Return Value]
+Both functions return `void`.
+
+[h5 Complexity]
 The time complexity of all these functions is /O(V)/.
 
 The space complexity for the distributions functisons is /O(max{degree(v)})/ where
@@ -88,46 +114,62 @@
 
 The space complexity for the histogram functions is /O(V + max{degree(v)})/.
 
-[h4 Notes]
+[h5 Notes]
 Because a graph may be a multigraph, there is no determinable upper bound on the
 size of the distribution or histogram parameters. As such they are required to
 be dynamically resized during the execution of the algorithm.
 
-For the distribution parameter, we recommend `std::vector<size_t>`. This satisfies
-all the requirements. For the histogram, we recommend using a `std::vector<Sequence<Vertex> >`
-where `Sequence` is one of `std::list`, `std::vector`, `std::deque`, or `std::queue`. The
-choice doesn't make much difference except that a `std::list` will require more allocations,
-but a `std::vector` will require more space. Also, note that `std::list::size()` function is
-not required to run in constant-time. The `Vertex` type must be
-`graph_traits<Graph>::vertex_descriptor`.
-
-If `dist` is the name of the output distribution after a call to `degree_distribution()`
-then the maximum degree is `dist.size() - 1`. The minimum degree corresponds to the index
-in `dist` with the first non-zero value.
+The recommended type for the distribution parameters is:
 
-[h4 Examples]
-The first example show how to compute and print the degree distribution.
+    std::vector<graph_traits<graph_type>::degree_size_type>
+
+where `graph_type` is the type of the `_graph` parameter. This satisfies the type
+requirements of the algorithms, and provides exceptional performance at the cost
+of extra memory overhead.
+
+The recommended type for the histogram parameters is:
+
+    std::vector<std::vector<graph_traits<graph_type>::vertex_descriptor> >
 
- undirected_graph<> g;
- // add vertices and edges to g
+Although this will consume more memory (due to the overhead of vector resizing),
+it may perform better than using `std::list` to store vertices of the same degree.
+This is because the `std::list::size()` function is not required to return in
+constant time.
+
+Note that if `dist` is the name of the output distribution after a call to
+`degree_distribution()` then the maximum degree is `dist.size() - 1`. The
+minimum degree corresponds to the index in `dist` with the first non-zero value.
+
+[h5 Examples]
+The first example show how to compute and print the degree distribution.
 
- std::vector<size_t> dist;
- degree_distribution(g, dist);
- copy(dist.begin(), dist.end(), ostream_iterator<size_t>(cout, " "));
+    undirected_graph<> g;
+    // add vertices and edges to g
 
+    std::vector<size_t> dist;
+    degree_distribution(g, dist);
+    copy(dist.begin(), dist.end(), ostream_iterator<size_t>(cout, " "));
 
 The following example shows how to access the vertex (or vertices) with the maximum
 degree by using the `degree_histogram()` algorithm. This prints the index of that
 vertex.
 
- undirected_graph<> g;
- // add vertice and edges to g
+    undirected_graph<> g;
+    // add vertice and edges to g
 
- typedef graph_traits<undirected_graph<> >::vertex_descriptor vertex_type;
- typedef std::vector<vertex_type> vertex_vector;
+    typedef graph_traits<undirected_graph<> >::vertex_descriptor vertex_type;
+    typedef std::vector<vertex_type> vertex_vector;
 
- std::vector<vertex_vector> hist;
- degree_histogram(g, hist);
- cout << get_vertex_index(hist.back().back()) << "\n";
+    std::vector<vertex_vector> hist;
+    degree_histogram(g, hist);
+    cout << get_vertex_index(hist.back().back()) << "\n";
+
+[h5 Rationale]
+The use of these functions varies somewhat from typical use of named parameters
+where default values are simply used to supply default information. Here, they
+are used to control functionality. It should also be noted that if no parameters
+are supplied, this algorithm still runs in linear time. However, there is no
+additional overhead for not supplying a parameter because operations on the
+`not_given` type are no-opped (they are instantiated as empty functions).
 
 [endsect]
\ No newline at end of file

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/reference.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/reference.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/reference.qbk	2007-07-06 14:09:52 EDT (Fri, 06 Jul 2007)
@@ -13,6 +13,9 @@
 [include adjacency_list.qbk]
 [endsect]
 
+[section Traits Classes]
+[endsect]
+
 [section Algorithms]
 [section Core Algorithms]
 [include breadth_first_search.qbk]

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/undirected_graph.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/undirected_graph.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/undirected_graph.qbk	2007-07-06 14:09:52 EDT (Fri, 06 Jul 2007)
@@ -10,7 +10,7 @@
 its associated types, member functions and non-member interface. An undirected graph
 is one in which edges have no direction - this is to say that edges can be "traveled"
 in both directions. This class provides general purpose implementation of undirected
-graphs and that can be used with algorithms in the Boost Graph Library.
+graphs and can be used with algorithms in the Boost Graph Library.
 
 [h4 Notation]
 The following notation is used in this documentation. The following type names

Modified: sandbox/SOC/2007/graphs/libs/graph/examples/movies/stats.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/movies/stats.cpp	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/movies/stats.cpp	2007-07-06 14:09:52 EDT (Fri, 06 Jul 2007)
@@ -12,9 +12,6 @@
 #include <boost/graph/degree_distribution.hpp>
 #include <boost/graph/connectivity.hpp>
 
-#include <typeinfo>
-#include <cxxabi.h>
-
 #include "movies.hpp"
 
 using namespace std;

Modified: sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2	2007-07-06 14:09:52 EDT (Fri, 06 Jul 2007)
@@ -22,4 +22,17 @@
 exe misc
     : misc.cpp
     : <include>../../../
-    ;
\ No newline at end of file
+    ;
+
+exe components
+    : components.cpp
+    : <include>$BOOST_ROOT
+    : <include>../../../
+    ;
+
+exe distance
+    : distance.cpp
+    : <include>$BOOST_ROOT
+    : <include>../../../
+    ;
+

Added: sandbox/SOC/2007/graphs/libs/graph/test/components.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/test/components.cpp	2007-07-06 14:09:52 EDT (Fri, 06 Jul 2007)
@@ -0,0 +1,123 @@
+// (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)
+
+#include <iostream>
+#include <iterator>
+#include <algorithm>
+#include <vector>
+#include <map>
+#include <tr1/unordered_map>
+#include <typeinfo>
+#include <cxxabi.h>
+
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/connectivity.hpp>
+
+using namespace std;
+using namespace boost;
+using namespace __cxxabiv1;
+
+template <typename Graph>
+void build_graph(Graph& g)
+{
+    typedef typename Graph::vertex_descriptor Vertex;
+
+    static const unsigned N = 5;
+    vector<Vertex> v(N);
+
+    // add some vertices
+    for(size_t i = 0; i < N; ++i) {
+        // v[i] = add_vertex(g);
+        v[i] = add_vertex(g);
+    }
+
+    // add some edges
+    add_edge(v[0], v[1], g);
+    add_edge(v[1], v[2], g);
+    add_edge(v[2], v[0], g);
+
+    add_edge(v[3], v[4], g);
+    // add_edge(v[0], v[4], g); // this makes it fully connected
+};
+
+void test_1()
+{
+    typedef adjacency_list<vecS, vecS, undirectedS> Graph;
+    Graph g;
+    build_graph(g);
+
+    vector<int> comps(num_vertices(g));
+    connectivity(g, &comps[0]);
+}
+
+void test_2()
+{
+    typedef adjacency_list<vecS, vecS, undirectedS> Graph;
+    Graph g;
+    build_graph(g);
+
+    vector<int> comps(num_vertices(g));
+    vector<default_color_type> colors(num_vertices(g));
+    connectivity(g, &comps[0],
+                           _color_map = &colors[0]);
+}
+
+void test_3()
+{
+    typedef adjacency_list<listS, listS, undirectedS> Graph;
+    typedef map<Graph::vertex_descriptor, int> IndexMap;
+    typedef map<Graph::vertex_descriptor, int> CompMap;
+    typedef associative_property_map<IndexMap> IndexProperties;
+    typedef associative_property_map<CompMap> CompProperties;
+
+    Graph g;
+    build_graph(g);
+
+    IndexMap indices;
+    CompMap comps;
+
+    int x = 0;
+    Graph::vertex_iterator i, end;
+    for(tie(i, end) = vertices(g); i != end; ++i) {
+        indices[*i] = x++;
+    }
+
+    CompProperties comp_map(comps);
+    IndexProperties index_map(indices);
+    connectivity(g, comp_map,
+                           _vertex_index_map = index_map);
+}
+
+void test_4()
+{
+    typedef undirected_graph<> Graph;
+    typedef tr1::unordered_map<Graph::vertex_descriptor, int> CompMap;
+    typedef associative_property_map<CompMap> CompProperties;
+    typedef std::vector<std::vector<Graph::vertex_descriptor> > Components;
+
+    Graph g;
+    build_graph(g);
+
+    CompMap comps;
+    CompProperties comp_map(comps);
+    Components ccomps;
+    connectivity(g, comp_map, _components = ccomps);
+
+    for(size_t i = 0; i < ccomps.size(); ++i) {
+        cout << i << ": " << ccomps[i].size() << "\n";
+    }
+}
+
+
+int
+main(int argc, char *argv[])
+{
+    test_1();
+    test_2();
+    test_3();
+    test_4();
+}

Added: sandbox/SOC/2007/graphs/libs/graph/test/distance.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/test/distance.cpp	2007-07-06 14:09:52 EDT (Fri, 06 Jul 2007)
@@ -0,0 +1,248 @@
+// (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)
+
+#include <iostream>
+#include <iterator>
+#include <algorithm>
+#include <vector>
+#include <map>
+#include <tr1/unordered_map>
+
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/dijkstra_shortest_paths.hpp>
+#include <boost/graph/johnson_all_pairs_shortest.hpp>
+#include <boost/graph/floyd_warshall_shortest.hpp>
+#include <boost/graph/distance.hpp>
+
+using namespace std;
+using namespace boost;
+
+struct VertexProperty
+{
+    int dummy;
+};
+
+struct EdgeProperty
+{
+    int weight;
+};
+
+template <typename Graph>
+void build_graph(Graph& g)
+{
+    typedef typename Graph::vertex_descriptor Vertex;
+    typedef typename Graph::edge_descriptor Edge;
+
+    static const unsigned N = 5;
+    vector<Vertex> v(N);
+    vector<Edge> e;
+
+    // add some vertices
+    for(size_t i = 0; i < N; ++i) {
+        // v[i] = add_vertex(g);
+        v[i] = add_vertex(g);
+    }
+
+    // add some edges (with weights)
+    e.push_back(add_edge(v[0], v[1], g).first);
+    e.push_back(add_edge(v[1], v[2], g).first);
+    e.push_back(add_edge(v[2], v[0], g).first);
+    e.push_back(add_edge(v[3], v[4], g).first);
+    e.push_back(add_edge(v[4], v[0], g).first);
+
+    g[e[0]].weight = 1;
+    g[e[1]].weight = 1;
+    g[e[2]].weight = 1;
+    g[e[3]].weight = 1;
+    g[e[4]].weight = 1;
+};
+
+template <typename Graph, typename DistanceMap>
+void dump_distance_map(const Graph& g, DistanceMap dists)
+{
+    typename Graph::vertex_iterator i, end;
+    for(tie(i, end) = vertices(g); i != end; ++i) {
+        cout << dists[*i] << " ";
+    }
+    cout << "\n";
+}
+
+template <typename Graph, typename DistanceMatrix>
+void dump_distance_matrix(const Graph& g, DistanceMatrix dists)
+{
+    typename Graph::vertex_iterator i, j, end;
+    for(tie(i, end) = vertices(g); i != end; ++i) {
+        for(j = vertices(g).first; j != end; ++j) {
+            cout << dists[*i][*j] << " ";
+        }
+        cout << "\n";
+    }
+}
+
+void test_1()
+{
+    // because this is defined w/vecS's, we don't have to work very
+    // hard on property maps
+
+    typedef adjacency_list<vecS, vecS, undirectedS, VertexProperty, EdgeProperty> Graph;
+    typedef Graph::vertex_descriptor Vertex;
+    typedef property_map<Graph, int EdgeProperty::*>::type WeightPropertyMap;
+    typedef vector<int> DistanceMap;
+    typedef iterator_property_map<DistanceMap::iterator,
+        property_map<Graph, vertex_index_t>::type> DistancePropertyMap;
+
+    Graph g;
+    build_graph(g);
+
+    Vertex v = *vertices(g).first;
+    WeightPropertyMap weights = get(&EdgeProperty::weight, g);
+
+    cout << "\nadjacency_list<vecS, vecS...>\n";
+    {
+        DistanceMap distances(num_vertices(g));
+        DistancePropertyMap dists(distances.begin());
+
+        dijkstra_shortest_paths(g, v,
+            weight_map(weights).
+            distance_map(dists));
+
+        cout << "* dists: "; dump_distance_map(g, dists);
+        cout << "* mean geo: " << mean_geodesic_distance(g, dists) << "\n";
+        cout << "* closeness: " << closeness(g, dists) << "\n";
+        cout << "* eccentricity: " << eccentricity(g, dists) << "\n";
+    }
+
+    {
+        typedef vector<DistanceMap> DistanceMatrix;
+
+        DistanceMatrix dists(num_vertices(g), DistanceMap(num_vertices(g)));
+
+        // compute all shortest paths
+        floyd_warshall_all_pairs_shortest_paths(g, dists,
+                weight_map(weights));
+
+        // use the distances in all-pairs to compute eccentricities
+        // for each vertex
+        DistanceMap eccentrics(num_vertices(g));
+        DistancePropertyMap eccs(eccentrics.begin());
+        eccentricities(g, dists, eccs);
+
+        cout << "* dists:\n"; dump_distance_matrix(g, dists);
+        cout << "* eccs: "; dump_distance_map(g, eccs);
+        cout << "* radius: " << radius(g, eccs) << "\n";
+        cout << "* diameter: " << diameter(g, eccs) << "\n";
+
+        vector<Vertex> cent;
+        center(g, eccs, back_inserter(cent));
+        cout << "center: ";
+        for(size_t x = 0; x < cent.size(); ++x) {
+            Vertex v = cent[x];
+            cout << get(vertex_index, g, v) << " ";
+        }
+        cout << "\n";
+
+        vector<Vertex> peri;
+        periphery(g, eccs, back_inserter(peri));
+        cout << "periphery: ";
+        for(size_t x = 0; x < peri.size(); ++x) {
+            Vertex v = peri[x];
+            cout << get(vertex_index, g, v) << " ";
+        }
+        cout << "\n";
+    }
+}
+
+void test_2()
+{
+}
+
+void test_3()
+{
+    typedef undirected_graph<VertexProperty, EdgeProperty> Graph;
+    typedef Graph::vertex_descriptor Vertex;
+
+    typedef property_map<Graph, int EdgeProperty::*>::type WeightPropertyMap;
+
+    typedef tr1::unordered_map<Vertex, int> DistanceMap;
+    typedef associative_property_map<DistanceMap> DistancePropertyMap;
+
+    Graph g;
+    build_graph(g);
+
+    Vertex v = *vertices(g).first;
+    WeightPropertyMap weights = get(&EdgeProperty::weight, g);
+
+    cout << "\nundirected_graph<...>\n";
+    {
+        DistanceMap distances(num_vertices(g));
+        DistancePropertyMap dists(distances);
+
+        // compute shortest paths
+        dijkstra_shortest_paths(g, v,
+            weight_map(weights).
+            distance_map(dists)
+            );
+
+        cout << "* dists: "; dump_distance_map(g, dists);
+        cout << "* mean geo: " << mean_geodesic_distance(g, dists) << "\n";
+        cout << "* closeness: " << closeness(g, dists) << "\n";
+        cout << "* eccentricity: " << eccentricity(g, dists) << "\n";
+    }
+
+    {
+        typedef tr1::unordered_map<Vertex, DistanceMap> DistanceMatrix;
+
+        DistanceMatrix dists(num_vertices(g));
+        Graph::vertex_iterator i, end;
+        for(tie(i, end) = vertices(g); i != end; ++i) {
+            dists[*i].rehash(num_vertices(g));
+        }
+
+        // compute all shortest paths
+        floyd_warshall_all_pairs_shortest_paths(g, dists,
+            weight_map(weights));
+
+        // use the distances in all-pairs to compute eccentricities
+        // for each vertex
+        DistanceMap eccentrics(num_vertices(g));
+        DistancePropertyMap eccs(eccentrics);
+        eccentricities(g, dists, eccs);
+
+        int r, d;
+        cout << "* dists:\n"; dump_distance_matrix(g, dists);
+        cout << "* eccs: "; dump_distance_map(g, eccs);
+        cout << "* radius: " << (r = radius(g, eccs)) << "\n";
+        cout << "* diameter: " << (d = diameter(g, eccs)) << "\n";
+
+        vector<Vertex> cent;
+        center(g, eccs, back_inserter(cent));
+        cout << "center: ";
+        for(size_t x = 0; x < cent.size(); ++x) {
+            Vertex v = cent[x];
+            cout << get(vertex_index, g, v) << " ";
+        }
+        cout << "\n";
+
+        vector<Vertex> peri;
+        periphery(g, eccs, back_inserter(peri));
+        cout << "periphery: ";
+        for(size_t x = 0; x < peri.size(); ++x) {
+            Vertex v = peri[x];
+            cout << get(vertex_index, g, v) << " ";
+        }
+        cout << "\n";
+    }
+}
+
+
+int
+main(int argc, char *argv[])
+{
+    test_1();
+    // test_2();
+    test_3();
+}