[Boost-commit] svn:boost r51101 - in trunk: boost/graph libs/graph/test

Subject: [Boost-commit] svn:boost r51101 - in trunk: boost/graph libs/graph/test
From: asutton_at_[hidden]
Date: 2009-02-08 10:57:42

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

Log:
Imported clustering coefficient, eccentricity and core numbers algorithms.
There is no test for core_numbers yet.

Added:
   trunk/boost/graph/clustering_coefficient.hpp   (contents, props changed)
      - copied, changed from r51086, /sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp
   trunk/boost/graph/core_numbers.hpp   (contents, props changed)
      - copied, changed from r51086, /sandbox/SOC/2007/graphs/boost/graph/core_numbers.hpp
   trunk/boost/graph/eccentricity.hpp   (contents, props changed)
      - copied, changed from r51086, /sandbox/SOC/2007/graphs/boost/graph/eccentricity.hpp
   trunk/libs/graph/test/clustering_coefficient.cpp   (contents, props changed)
      - copied, changed from r51086, /sandbox/SOC/2007/graphs/libs/graph/test/runtime/clustering_coefficient.cpp
   trunk/libs/graph/test/eccentricity.cpp   (contents, props changed)
      - copied, changed from r51086, /sandbox/SOC/2007/graphs/libs/graph/test/runtime/eccentricity.cpp
Text files modified: 
   trunk/boost/graph/clustering_coefficient.hpp     |   251 +++++++++++-----------                  
   trunk/boost/graph/core_numbers.hpp               |   437 +++++++++++++++++++-------------------- 
   trunk/boost/graph/eccentricity.hpp               |   194 +++++++----------                       
   trunk/boost/graph/geodesic_distance.hpp          |     6                                         
   trunk/libs/graph/test/Jamfile.v2                 |     2                                         
   trunk/libs/graph/test/clustering_coefficient.cpp |    59 ++--                                    
   trunk/libs/graph/test/eccentricity.cpp           |     9                                         
   7 files changed, 459 insertions(+), 499 deletions(-)

Copied: trunk/boost/graph/clustering_coefficient.hpp (from r51086, /sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp	(original)
+++ trunk/boost/graph/clustering_coefficient.hpp	2009-02-08 10:57:41 EST (Sun, 08 Feb 2009)
@@ -1,158 +1,157 @@
-// (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_CLUSTERING_COEFFICIENT_HXX
-#define BOOST_GRAPH_CLUSTERING_COEFFICIENT_HXX
+#ifndef BOOST_GRAPH_CLUSTERING_COEFFICIENT_HPP
+#define BOOST_GRAPH_CLUSTERING_COEFFICIENT_HPP
 
 #include <boost/utility.hpp>
 #include <boost/graph/graph_traits.hpp>
-#include <boost/graph/new_graph_concepts.hpp>
+#include <boost/graph/graph_concepts.hpp>
 
 namespace boost
 {
-    namespace detail
+namespace detail
+{
+    template <class Graph>
+    inline typename graph_traits<Graph>::degree_size_type
+    possible_edges(const Graph& g, std::size_t k, directed_tag)
     {
-        template <class Graph>
-        inline typename graph_traits<Graph>::degree_size_type
-        possible_edges(const Graph& g, std::size_t k, directed_tag)
-        {
-            function_requires< GraphConcept<Graph> >();
-            typedef typename graph_traits<Graph>::degree_size_type T;
-            return T(k) * (T(k) - 1);
-        }
-
-        template <class Graph>
-        inline typename graph_traits<Graph>::degree_size_type
-        possible_edges(const Graph& g, size_t k, undirected_tag)
-        {
-            // dirty little trick...
-            return possible_edges(g, k, directed_tag()) / 2;
-        }
-
-        // This template matches directedS and bidirectionalS.
-        template <class Graph>
-        inline typename graph_traits<Graph>::degree_size_type
-        count_edges(const Graph& g,
-                    typename Graph::vertex_descriptor u,
-                    typename Graph::vertex_descriptor v,
-                    directed_tag)
-
-        {
-            function_requires< AdjacencyMatrixConcept<Graph> >();
-            return (edge(u, v, g).second ? 1 : 0) +
-                   (edge(v, u, g).second ? 1 : 0);
-        }
-
-        // This template matches undirectedS
-        template <class Graph>
-        inline typename graph_traits<Graph>::degree_size_type
-        count_edges(const Graph& g,
-                    typename Graph::vertex_descriptor u,
-                    typename Graph::vertex_descriptor v,
-                    undirected_tag)
-        {
-            function_requires< AdjacencyMatrixConcept<Graph> >();
-            return edge(u, v, g).second ? 1 : 0;
-        }
+        function_requires< GraphConcept<Graph> >();
+        typedef typename graph_traits<Graph>::degree_size_type T;
+        return T(k) * (T(k) - 1);
     }
 
-    template <typename Graph, typename Vertex>
+    template <class Graph>
     inline typename graph_traits<Graph>::degree_size_type
-    num_paths_through_vertex(const Graph& g, Vertex v)
+    possible_edges(const Graph& g, size_t k, undirected_tag)
     {
-        function_requires< AdjacencyGraphConcept<Graph> >();
-        typedef typename graph_traits<Graph>::directed_category Directed;
-        typedef typename graph_traits<Graph>::adjacency_iterator AdjacencyIterator;
-
-        // TODO: There should actually be a set of neighborhood functions
-        // for things like this (num_neighbors() would be great).
-
-        AdjacencyIterator i, end;
-        tie(i, end) = adjacent_vertices(v, g);
-        std::size_t k = std::distance(i, end);
-        return detail::possible_edges(g, k, Directed());
+        // dirty little trick...
+        return possible_edges(g, k, directed_tag()) / 2;
     }
 
-    template <typename Graph, typename Vertex>
+    // This template matches directedS and bidirectionalS.
+    template <class Graph>
     inline typename graph_traits<Graph>::degree_size_type
-    num_triangles_on_vertex(const Graph& g, Vertex v)
-    {
-        function_requires< IncidenceGraphConcept<Graph> >();
-        function_requires< AdjacencyGraphConcept<Graph> >();
-        typedef typename graph_traits<Graph>::degree_size_type Degree;
-        typedef typename graph_traits<Graph>::directed_category Directed;
-        typedef typename graph_traits<Graph>::adjacency_iterator AdjacencyIterator;
-
-        // TODO: I might be able to reduce the requirement from adjacency graph
-        // to incidence graph by using out edges.
-
-        Degree count(0);
-        AdjacencyIterator i, j, end;
-        for(tie(i, end) = adjacent_vertices(v, g); i != end; ++i) {
-            for(j = next(i); j != end; ++j) {
-                count += detail::count_edges(g, *i, *j, Directed());
-            }
-        }
-        return count;
-    }
+    count_edges(const Graph& g,
+                typename Graph::vertex_descriptor u,
+                typename Graph::vertex_descriptor v,
+                directed_tag)
 
-    template <typename T, typename Graph, typename Vertex>
-    inline T
-    clustering_coefficient(const Graph& g, Vertex v)
     {
-        T zero(0);
-        T routes = T(num_paths_through_vertex(g, v));
-        return (routes > zero) ?
-            T(num_triangles_on_vertex(g, v)) / routes : zero;
+        function_requires< AdjacencyMatrixConcept<Graph> >();
+        return (edge(u, v, g).second ? 1 : 0) +
+                (edge(v, u, g).second ? 1 : 0);
     }
 
-    template <typename Graph, typename Vertex>
-    inline float
-    clustering_coefficient(const Graph& g, Vertex v)
+    // This template matches undirectedS
+    template <class Graph>
+    inline typename graph_traits<Graph>::degree_size_type
+    count_edges(const Graph& g,
+                typename Graph::vertex_descriptor u,
+                typename Graph::vertex_descriptor v,
+                undirected_tag)
     {
-        return clustering_coefficient<float>(g, v);
+        function_requires< AdjacencyMatrixConcept<Graph> >();
+        return edge(u, v, g).second ? 1 : 0;
     }
+}
 
-    template <typename Graph, typename ClusteringMap>
-    inline typename property_traits<ClusteringMap>::value_type
-    all_clustering_coefficients(const Graph& g, ClusteringMap cm)
-    {
-        function_requires< VertexListGraphConcept<Graph> >();
-        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-        typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
-        function_requires< WritablePropertyMapConcept<ClusteringMap,Vertex> >();
-        typedef typename property_traits<ClusteringMap>::value_type Coefficient;
-
-        Coefficient sum(0);
-        VertexIterator i, end;
-        for(tie(i, end) = vertices(g); i != end; ++i) {
-            Coefficient cc = clustering_coefficient<Coefficient>(g, *i);
-            put(cm, *i, cc);
-            sum += cc;
-        }
-        return sum / Coefficient(num_vertices(g));
+template <typename Graph, typename Vertex>
+inline typename graph_traits<Graph>::degree_size_type
+num_paths_through_vertex(const Graph& g, Vertex v)
+{
+    function_requires< AdjacencyGraphConcept<Graph> >();
+    typedef typename graph_traits<Graph>::directed_category Directed;
+    typedef typename graph_traits<Graph>::adjacency_iterator AdjacencyIterator;
+
+    // TODO: There should actually be a set of neighborhood functions
+    // for things like this (num_neighbors() would be great).
+
+    AdjacencyIterator i, end;
+    tie(i, end) = adjacent_vertices(v, g);
+    std::size_t k = std::distance(i, end);
+    return detail::possible_edges(g, k, Directed());
+}
+
+template <typename Graph, typename Vertex>
+inline typename graph_traits<Graph>::degree_size_type
+num_triangles_on_vertex(const Graph& g, Vertex v)
+{
+    function_requires< IncidenceGraphConcept<Graph> >();
+    function_requires< AdjacencyGraphConcept<Graph> >();
+    typedef typename graph_traits<Graph>::degree_size_type Degree;
+    typedef typename graph_traits<Graph>::directed_category Directed;
+    typedef typename graph_traits<Graph>::adjacency_iterator AdjacencyIterator;
+
+    // TODO: I might be able to reduce the requirement from adjacency graph
+    // to incidence graph by using out edges.
+
+    Degree count(0);
+    AdjacencyIterator i, j, end;
+    for(tie(i, end) = adjacent_vertices(v, g); i != end; ++i) {
+        for(j = next(i); j != end; ++j) {
+            count += detail::count_edges(g, *i, *j, Directed());
+        }
+    }
+    return count;
+} /* namespace detail */
+
+template <typename T, typename Graph, typename Vertex>
+inline T
+clustering_coefficient(const Graph& g, Vertex v)
+{
+    T zero(0);
+    T routes = T(num_paths_through_vertex(g, v));
+    return (routes > zero) ?
+        T(num_triangles_on_vertex(g, v)) / routes : zero;
+}
+
+template <typename Graph, typename Vertex>
+inline double
+clustering_coefficient(const Graph& g, Vertex v)
+{ return clustering_coefficient<double>(g, v); }
+
+template <typename Graph, typename ClusteringMap>
+inline typename property_traits<ClusteringMap>::value_type
+all_clustering_coefficients(const Graph& g, ClusteringMap cm)
+{
+    function_requires< VertexListGraphConcept<Graph> >();
+    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+    typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+    function_requires< WritablePropertyMapConcept<ClusteringMap,Vertex> >();
+    typedef typename property_traits<ClusteringMap>::value_type Coefficient;
+
+    Coefficient sum(0);
+    VertexIterator i, end;
+    for(tie(i, end) = vertices(g); i != end; ++i) {
+        Coefficient cc = clustering_coefficient<Coefficient>(g, *i);
+        put(cm, *i, cc);
+        sum += cc;
     }
+    return sum / Coefficient(num_vertices(g));
+}
 
-    template <typename Graph, typename ClusteringMap>
-    inline typename property_traits<ClusteringMap>::value_type
-    mean_clustering_coefficient(const Graph& g, ClusteringMap cm)
-    {
-        function_requires< VertexListGraphConcept<Graph> >();
-        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-        typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
-        function_requires< ReadablePropertyMapConcept<ClusteringMap,Vertex> >();
-        typedef typename property_traits<ClusteringMap>::value_type Coefficient;
-
-        Coefficient cc(0);
-        VertexIterator i, end;
-        for(tie(i, end) = vertices(g); i != end; ++i) {
-            cc += get(cm, *i);
-        }
-        return cc / Coefficient(num_vertices(g));
+template <typename Graph, typename ClusteringMap>
+inline typename property_traits<ClusteringMap>::value_type
+mean_clustering_coefficient(const Graph& g, ClusteringMap cm)
+{
+    function_requires< VertexListGraphConcept<Graph> >();
+    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+    typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+    function_requires< ReadablePropertyMapConcept<ClusteringMap,Vertex> >();
+    typedef typename property_traits<ClusteringMap>::value_type Coefficient;
+
+    Coefficient cc(0);
+    VertexIterator i, end;
+    for(tie(i, end) = vertices(g); i != end; ++i) {
+        cc += get(cm, *i);
     }
+    return cc / Coefficient(num_vertices(g));
 }
 
+} /* namespace boost */
+
 #endif

Copied: trunk/boost/graph/core_numbers.hpp (from r51086, /sandbox/SOC/2007/graphs/boost/graph/core_numbers.hpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/boost/graph/core_numbers.hpp	(original)
+++ trunk/boost/graph/core_numbers.hpp	2009-02-08 10:57:41 EST (Sun, 08 Feb 2009)
@@ -1,11 +1,9 @@
-//=======================================================================
 // Copyright 2007 Stanford University
 // Authors: David Gleich
 //
 // Distributed under the Boost Software License, Version 1.0. (See
 // accompanying file LICENSE_1_0.txt or copy at
 // http://www.boost.org/LICENSE_1_0.txt)
-//=======================================================================
 
 #ifndef BOOST_GRAPH_CORE_NUMBERS_HPP
 #define BOOST_GRAPH_CORE_NUMBERS_HPP
@@ -13,253 +11,248 @@
 #include <boost/pending/mutable_queue.hpp>
 
 /*
- *KCore
+ * KCore
  *
- *Requirement:
- *      IncidenceGraph
+ * Requirement: IncidenceGraph
  */
 
 namespace boost {
 
-    // A linear time O(m) algorithm to compute the indegree core number
-    // of a graph for unweighted graphs.
-    //
-    // and a O((n+m) log n) algorithm to compute the in-edge-weight core
-    // numbers of a weighted graph.
-    //
-    // The linear algorithm comes from:
-    //      @article{DBLP:journals/corr/cs-DS-0310049,
-    //          author = {Vladimir Batagelj and Matjaz Zaversnik},
-    //          title     = {An O(m) Algorithm for Cores Decomposition of Networks},
-    //          journal   = {The Computing Research Repository (CoRR)},
-    //          volume    = {cs.DS/0310049},
-    //          year      = {2003},
-    //          ee        = {http://arxiv.org/abs/cs.DS/0310049},
-    //          bibsource = {DBLP, http://dblp.uni-trier.de}
-    //      }
-
-    namespace detail
+// A linear time O(m) algorithm to compute the in-degree core number
+// of a graph for unweighted graphs.
+//
+// and a O((n+m) log n) algorithm to compute the in-edge-weight core
+// numbers of a weighted graph.
+//
+// The linear algorithm comes from:
+//      @article{DBLP:journals/corr/cs-DS-0310049,
+//          author = {Vladimir Batagelj and Matjaz Zaversnik},
+//          title     = {An O(m) Algorithm for Cores Decomposition of Networks},
+//          journal   = {The Computing Research Repository (CoRR)},
+//          volume    = {cs.DS/0310049},
+//          year      = {2003},
+//          ee        = {http://arxiv.org/abs/cs.DS/0310049},
+//          bibsource = {DBLP, http://dblp.uni-trier.de}
+//      }
+
+namespace detail {
+    // implement a constant_property_map to simplify compute_in_degree
+    // for the weighted and unweighted case
+    // this is based on dummy property map
+    // TODO: This is virtually the same as constant_property_map in
+    // graph/property_maps. Perhaps we should be using that instead of this..
+    template <typename ValueType>
+    class constant_value_property_map
+        : public boost::put_get_helper<ValueType,
+            constant_value_property_map<ValueType>
+        >
     {
+    public:
+        typedef void key_type;
+        typedef ValueType value_type;
+        typedef const ValueType& reference;
+        typedef boost::readable_property_map_tag category;
+        inline constant_value_property_map(ValueType cc) : c(cc) { }
+        inline constant_value_property_map(const constant_value_property_map<ValueType>& x)
+            : c(x.c) { }
+        template <class Vertex>
+        inline reference operator[](Vertex) const { return c; }
+    protected:
+        ValueType c;
+    };
 
-        // implement a constant_property_map to simplify compute_in_degree
-        // for the weighted and unweighted case
-        // this is based on dummy property map
-        template <typename ValueType>
-        class constant_value_property_map
-            : public boost::put_get_helper<ValueType,
-            constant_value_property_map<ValueType>  >
-        {
-        public:
-            typedef void key_type;
-            typedef ValueType value_type;
-            typedef const ValueType& reference;
-            typedef boost::readable_property_map_tag category;
-            inline constant_value_property_map(ValueType cc) : c(cc) { }
-            inline constant_value_property_map(const constant_value_property_map<ValueType>& x)
-              : c(x.c) { }
-            template <class Vertex>
-            inline reference operator[](Vertex) const { return c; }
-        protected:
-            ValueType c;
-        };
-
-
-        // the core numbers start as the indegree or inweight.  This function
-        // will initialize these values
-        template <typename Graph, typename CoreMap, typename EdgeWeightMap>
-        void compute_in_degree_map(Graph& g, CoreMap d, EdgeWeightMap wm)
-        {
-            typename graph_traits<Graph>::vertex_iterator vi,vi_end;
-            typename graph_traits<Graph>::out_edge_iterator ei,ei_end;
-            for (tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
-                put(d,*vi,0);
-            }
-            for (tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
-                for (tie(ei,ei_end) = out_edges(*vi,g); ei!=ei_end; ++ei) {
-                    put(d,target(*ei,g),get(d,target(*ei,g))+get(wm,*ei));
-                }
-            }
-        }
-
-        // the version for weighted graphs is a little different
-        template <typename Graph, typename CoreMap,
-            typename EdgeWeightMap, typename MutableQueue>
-        typename property_traits<CoreMap>::value_type
-        core_numbers_impl(Graph& g, CoreMap c, EdgeWeightMap wm,
-            MutableQueue& Q)
-        {
-            typename property_traits<CoreMap>::value_type v_cn = 0;
-            typedef typename graph_traits<Graph>::vertex_descriptor vertex;
-            while (!Q.empty())
-            {
-                // remove v from the Q, and then decrease the core numbers
-                // of its successors
-                vertex v = Q.top();
-                Q.pop();
-                v_cn = get(c,v);
-                typename graph_traits<Graph>::out_edge_iterator oi,oi_end;
-                for (tie(oi,oi_end) = out_edges(v,g); oi!=oi_end; ++oi) {
-                    vertex u = target(*oi,g);
-                    // if c[u] > c[v], then u is still in the graph,
-                    if (get(c,u) > v_cn) {
-                        // remove the edge
-                        put(c,u,get(c,u)-get(wm,*oi));
-                        Q.update(u);
-                    }
-                }
-            }
-            return (v_cn);
+    // the core numbers start as the indegree or inweight.  This function
+    // will initialize these values
+    template <typename Graph, typename CoreMap, typename EdgeWeightMap>
+    void compute_in_degree_map(Graph& g, CoreMap d, EdgeWeightMap wm)
+    {
+        typename graph_traits<Graph>::vertex_iterator vi,vi_end;
+        typename graph_traits<Graph>::out_edge_iterator ei,ei_end;
+        for (tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
+            put(d,*vi,0);
         }
-
-        template <typename Graph, typename CoreMap, typename EdgeWeightMap,
-            typename IndexMap>
-        typename property_traits<CoreMap>::value_type
-        core_numbers_dispatch(Graph&g, CoreMap c, EdgeWeightMap wm,
-            IndexMap im)
-        {
-            typedef typename property_traits<CoreMap>::value_type D;
-            typedef std::less<D> Cmp;
-            typedef indirect_cmp<CoreMap,Cmp > IndirectCmp;
-            IndirectCmp icmp(c, Cmp());
-            // build the mutable queue
-            typedef typename graph_traits<Graph>::vertex_descriptor vertex;
-            typedef mutable_queue<vertex, std::vector<vertex>, IndirectCmp,
-                IndexMap> MutableQueue;
-            MutableQueue Q(num_vertices(g), icmp, im);
-            typename graph_traits<Graph>::vertex_iterator vi,vi_end;
-            for (tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
-                Q.push(*vi);
+        for (tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
+            for (tie(ei,ei_end) = out_edges(*vi,g); ei!=ei_end; ++ei) {
+                put(d,target(*ei,g),get(d,target(*ei,g))+get(wm,*ei));
             }
-            return core_numbers_impl(g, c, wm, Q);
         }
+    }
 
-        // the version for the unweighted case
-        // for this functions CoreMap must be initialized
-        // with the in degree of each vertex
-        template <typename Graph, typename CoreMap, typename PositionMap>
-        typename property_traits<CoreMap>::value_type
-        core_numbers_impl(Graph& g, CoreMap c, PositionMap pos)
+    // the version for weighted graphs is a little different
+    template <typename Graph, typename CoreMap,
+        typename EdgeWeightMap, typename MutableQueue>
+    typename property_traits<CoreMap>::value_type
+    core_numbers_impl(Graph& g, CoreMap c, EdgeWeightMap wm, MutableQueue& Q)
+    {
+        typename property_traits<CoreMap>::value_type v_cn = 0;
+        typedef typename graph_traits<Graph>::vertex_descriptor vertex;
+        while (!Q.empty())
         {
-            typedef typename graph_traits<Graph>::vertices_size_type size_type;
-            typedef typename graph_traits<Graph>::degree_size_type degree_type;
-            typedef typename graph_traits<Graph>::vertex_descriptor vertex;
-            typename graph_traits<Graph>::vertex_iterator vi,vi_end;
-
-            // store the vertex core numbers
-            typename property_traits<CoreMap>::value_type v_cn = 0;
-
-		    // compute the maximum degree (degrees are in the coremap)
-            typename graph_traits<Graph>::degree_size_type max_deg = 0;
-		    for (tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
-                max_deg = (std::max)(max_deg, get(c,*vi));
-            }
-            // store the vertices in bins by their degree
-            // allocate two extra locations to ease boundary cases
-            std::vector<size_type> bin(max_deg+2);
-            for (tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
-                ++bin[get(c,*vi)];
-            }
-            // this loop sets bin[d] to the starting position of vertices
-		    // with degree d in the vert array for the bucket sort
-            size_type cur_pos = 0;
-		    for (degree_type cur_deg = 0; cur_deg < max_deg+2; ++cur_deg) {
-			    degree_type tmp = bin[cur_deg];
-			    bin[cur_deg] = cur_pos;
-			    cur_pos += tmp;
-		    }
-            // perform the bucket sort with pos and vert so that
-            // pos[0] is the vertex of smallest degree
-            std::vector<vertex> vert(num_vertices(g));
-            for (tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
-                vertex v=*vi;
-                size_type p=bin[get(c,v)];
-			    put(pos,v,p);
-			    vert[p]=v;
-			    ++bin[get(c,v)];
-		    }
-            // we ``abused'' bin while placing the vertices, now,
-		    // we need to restore it
-		    std::copy(boost::make_reverse_iterator(bin.end()-2),
-			    boost::make_reverse_iterator(bin.begin()),
-			    boost::make_reverse_iterator(bin.end()-1));
-            // now simulate removing the vertices
-            for (size_type i=0; i < num_vertices(g); ++i) {
-			    vertex v = vert[i];
-                v_cn = get(c,v);
-                typename graph_traits<Graph>::out_edge_iterator oi,oi_end;
-                for (tie(oi,oi_end) = out_edges(v,g); oi!=oi_end; ++oi) {
-                    vertex u = target(*oi,g);
-                    // if c[u] > c[v], then u is still in the graph,
-                    if (get(c,u) > v_cn) {
-                        degree_type deg_u = get(c,u);
-                        degree_type pos_u = get(pos,u);
-                        // w is the first vertex with the same degree as u
-					    // (this is the resort operation!)
-					    degree_type pos_w = bin[deg_u];
-					    vertex w = vert[pos_w];
-                        if (u!=v) {
-                    	    // swap u and w
-                            put(pos,u,pos_w);
-                            put(pos,w,pos_u);
-						    vert[pos_w] = u;
-						    vert[pos_u] = w;
-                        }
-                        // now, the vertices array is sorted assuming
-					    // we perform the following step
-					    // start the set of vertices with degree of u
-					    // one into the future (this now points at vertex
-					    // w which we swapped with u).
-					    ++bin[deg_u];
-					    // we are removing v from the graph, so u's degree
-					    // decreases
-					    put(c,u,get(c,u)-1);
-                    }
+            // remove v from the Q, and then decrease the core numbers
+            // of its successors
+            vertex v = Q.top();
+            Q.pop();
+            v_cn = get(c,v);
+            typename graph_traits<Graph>::out_edge_iterator oi,oi_end;
+            for (tie(oi,oi_end) = out_edges(v,g); oi!=oi_end; ++oi) {
+                vertex u = target(*oi,g);
+                // if c[u] > c[v], then u is still in the graph,
+                if (get(c,u) > v_cn) {
+                    // remove the edge
+                    put(c,u,get(c,u)-get(wm,*oi));
+                    Q.update(u);
                 }
             }
-            return v_cn;
         }
-
-    } // namespace detail
-
-    template <typename Graph, typename CoreMap>
-    typename property_traits<CoreMap>::value_type
-    core_numbers(Graph& g, CoreMap c)
-    {
-        typedef typename graph_traits<Graph>::vertices_size_type size_type;
-        detail::compute_in_degree_map(g,c,
-            detail::constant_value_property_map<
-                typename property_traits<CoreMap>::value_type>(1) );
-        return detail::core_numbers_impl(g,c,
-            make_iterator_property_map(
-                std::vector<size_type>(num_vertices(g)).begin(),get(vertex_index, g))
-        );
+        return (v_cn);
     }
 
     template <typename Graph, typename CoreMap, typename EdgeWeightMap,
-        typename VertexIndexMap >
+              typename IndexMap>
     typename property_traits<CoreMap>::value_type
-    core_numbers(Graph& g, CoreMap c, EdgeWeightMap wm, VertexIndexMap vim)
+    core_numbers_dispatch(Graph&g, CoreMap c, EdgeWeightMap wm, IndexMap im)
     {
-        typedef typename graph_traits<Graph>::vertices_size_type size_type;
-        detail::compute_in_degree_map(g,c,wm);
-        return detail::core_numbers_dispatch(g,c,wm,vim);
+        typedef typename property_traits<CoreMap>::value_type D;
+        typedef std::less<D> Cmp;
+        typedef indirect_cmp<CoreMap,Cmp > IndirectCmp;
+        IndirectCmp icmp(c, Cmp());
+        // build the mutable queue
+        typedef typename graph_traits<Graph>::vertex_descriptor vertex;
+        typedef mutable_queue<vertex, std::vector<vertex>, IndirectCmp,
+            IndexMap> MutableQueue;
+        MutableQueue Q(num_vertices(g), icmp, im);
+        typename graph_traits<Graph>::vertex_iterator vi,vi_end;
+        for (tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
+            Q.push(*vi);
+        }
+        return core_numbers_impl(g, c, wm, Q);
     }
 
-    template <typename Graph, typename CoreMap, typename EdgeWeightMap>
+    // the version for the unweighted case
+    // for this functions CoreMap must be initialized
+    // with the in degree of each vertex
+    template <typename Graph, typename CoreMap, typename PositionMap>
     typename property_traits<CoreMap>::value_type
-    core_numbers(Graph& g, CoreMap c, EdgeWeightMap wm)
+    core_numbers_impl(Graph& g, CoreMap c, PositionMap pos)
     {
         typedef typename graph_traits<Graph>::vertices_size_type size_type;
-        detail::compute_in_degree_map(g,c,wm);
-        return detail::core_numbers_dispatch(g,c,wm,get(vertex_index,g));
+        typedef typename graph_traits<Graph>::degree_size_type degree_type;
+        typedef typename graph_traits<Graph>::vertex_descriptor vertex;
+        typename graph_traits<Graph>::vertex_iterator vi,vi_end;
+
+        // store the vertex core numbers
+        typename property_traits<CoreMap>::value_type v_cn = 0;
+
+        // compute the maximum degree (degrees are in the coremap)
+        typename graph_traits<Graph>::degree_size_type max_deg = 0;
+        for (tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
+            max_deg = (std::max)(max_deg, get(c,*vi));
+        }
+        // store the vertices in bins by their degree
+        // allocate two extra locations to ease boundary cases
+        std::vector<size_type> bin(max_deg+2);
+        for (tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
+            ++bin[get(c,*vi)];
+        }
+        // this loop sets bin[d] to the starting position of vertices
+        // with degree d in the vert array for the bucket sort
+        size_type cur_pos = 0;
+        for (degree_type cur_deg = 0; cur_deg < max_deg+2; ++cur_deg) {
+            degree_type tmp = bin[cur_deg];
+            bin[cur_deg] = cur_pos;
+            cur_pos += tmp;
+        }
+        // perform the bucket sort with pos and vert so that
+        // pos[0] is the vertex of smallest degree
+        std::vector<vertex> vert(num_vertices(g));
+        for (tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) {
+            vertex v=*vi;
+            size_type p=bin[get(c,v)];
+            put(pos,v,p);
+            vert[p]=v;
+            ++bin[get(c,v)];
+        }
+        // we ``abused'' bin while placing the vertices, now,
+        // we need to restore it
+        std::copy(boost::make_reverse_iterator(bin.end()-2),
+            boost::make_reverse_iterator(bin.begin()),
+            boost::make_reverse_iterator(bin.end()-1));
+        // now simulate removing the vertices
+        for (size_type i=0; i < num_vertices(g); ++i) {
+            vertex v = vert[i];
+            v_cn = get(c,v);
+            typename graph_traits<Graph>::out_edge_iterator oi,oi_end;
+            for (tie(oi,oi_end) = out_edges(v,g); oi!=oi_end; ++oi) {
+                vertex u = target(*oi,g);
+                // if c[u] > c[v], then u is still in the graph,
+                if (get(c,u) > v_cn) {
+                    degree_type deg_u = get(c,u);
+                    degree_type pos_u = get(pos,u);
+                    // w is the first vertex with the same degree as u
+                    // (this is the resort operation!)
+                    degree_type pos_w = bin[deg_u];
+                    vertex w = vert[pos_w];
+                    if (u!=v) {
+                        // swap u and w
+                        put(pos,u,pos_w);
+                        put(pos,w,pos_u);
+                        vert[pos_w] = u;
+                        vert[pos_u] = w;
+                    }
+                    // now, the vertices array is sorted assuming
+                    // we perform the following step
+                    // start the set of vertices with degree of u
+                    // one into the future (this now points at vertex
+                    // w which we swapped with u).
+                    ++bin[deg_u];
+                    // we are removing v from the graph, so u's degree
+                    // decreases
+                    put(c,u,get(c,u)-1);
+                }
+            }
+        }
+        return v_cn;
     }
 
-    template <typename Graph, typename CoreMap>
-    typename property_traits<CoreMap>::value_type
-    weighted_core_numbers(Graph& g, CoreMap c)
-    {
-        return core_numbers(g,c,get(edge_weight,g));
-    }
+} // namespace detail
+
+template <typename Graph, typename CoreMap>
+typename property_traits<CoreMap>::value_type
+core_numbers(Graph& g, CoreMap c)
+{
+    typedef typename graph_traits<Graph>::vertices_size_type size_type;
+    detail::compute_in_degree_map(g,c,
+        detail::constant_value_property_map<
+            typename property_traits<CoreMap>::value_type>(1) );
+    return detail::core_numbers_impl(g,c,
+        make_iterator_property_map(
+            std::vector<size_type>(num_vertices(g)).begin(),get(vertex_index, g))
+    );
+}
+
+template <typename Graph, typename CoreMap, typename EdgeWeightMap,
+          typename VertexIndexMap>
+typename property_traits<CoreMap>::value_type
+core_numbers(Graph& g, CoreMap c, EdgeWeightMap wm, VertexIndexMap vim)
+{
+    typedef typename graph_traits<Graph>::vertices_size_type size_type;
+    detail::compute_in_degree_map(g,c,wm);
+    return detail::core_numbers_dispatch(g,c,wm,vim);
+}
+
+template <typename Graph, typename CoreMap, typename EdgeWeightMap>
+typename property_traits<CoreMap>::value_type
+core_numbers(Graph& g, CoreMap c, EdgeWeightMap wm)
+{
+    typedef typename graph_traits<Graph>::vertices_size_type size_type;
+    detail::compute_in_degree_map(g,c,wm);
+    return detail::core_numbers_dispatch(g,c,wm,get(vertex_index,g));
+}
+
+template <typename Graph, typename CoreMap>
+typename property_traits<CoreMap>::value_type
+weighted_core_numbers(Graph& g, CoreMap c)
+{ return core_numbers(g,c,get(edge_weight,g)); }
 
 } // namespace boost
 

Copied: trunk/boost/graph/eccentricity.hpp (from r51086, /sandbox/SOC/2007/graphs/boost/graph/eccentricity.hpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/boost/graph/eccentricity.hpp	(original)
+++ trunk/boost/graph/eccentricity.hpp	2009-02-08 10:57:41 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,127 +12,97 @@
 
 namespace boost
 {
-    template <typename Graph,
-              typename DistanceMap,
-              typename Combinator>
-    inline typename property_traits<DistanceMap>::value_type
-    eccentricity(const Graph& g, DistanceMap dist, Combinator combine)
-    {
-        function_requires< GraphConcept<Graph> >();
-        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-        function_requires< ReadablePropertyMapConcept<DistanceMap,Vertex> >();
-        typedef typename property_traits<DistanceMap>::value_type Distance;
+template <typename Graph,
+            typename DistanceMap,
+            typename Combinator>
+inline typename property_traits<DistanceMap>::value_type
+eccentricity(const Graph& g, DistanceMap dist, Combinator combine)
+{
+    function_requires< GraphConcept<Graph> >();
+    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+    function_requires< ReadablePropertyMapConcept<DistanceMap,Vertex> >();
+    typedef typename property_traits<DistanceMap>::value_type Distance;
 
-        return detail::combine_distances(g, dist, combine, Distance(0));
-    }
+    return detail::combine_distances(g, dist, combine, Distance(0));
+}
 
-    template <typename Graph, typename DistanceMap>
-    inline typename property_traits<DistanceMap>::value_type
-    eccentricity(const Graph& g, DistanceMap dist)
-    {
-        function_requires< GraphConcept<Graph> >();
-        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-        function_requires< ReadablePropertyMapConcept<DistanceMap,Vertex> >();
-        typedef typename property_traits<DistanceMap>::value_type Distance;
+template <typename Graph, typename DistanceMap>
+inline typename property_traits<DistanceMap>::value_type
+eccentricity(const Graph& g, DistanceMap dist)
+{
+    function_requires< GraphConcept<Graph> >();
+    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+    function_requires< ReadablePropertyMapConcept<DistanceMap,Vertex> >();
+    typedef typename property_traits<DistanceMap>::value_type Distance;
 
-        return eccentricity(g, dist, detail::maximize<Distance>());
-    }
+    return eccentricity(g, dist, detail::maximize<Distance>());
+}
 
-    template <typename Graph, typename DistanceMatrix, typename EccentricityMap>
-    inline std::pair<typename property_traits<EccentricityMap>::value_type,
-                     typename property_traits<EccentricityMap>::value_type>
-    all_eccentricities(const Graph& g, const DistanceMatrix& dist, EccentricityMap ecc)
-    {
-        function_requires< VertexListGraphConcept<Graph> >();
-        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-        typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
-        function_requires< ReadablePropertyMapConcept<DistanceMatrix,Vertex> >();
-        typedef typename property_traits<DistanceMatrix>::value_type DistanceMap;
-        function_requires< WritablePropertyMapConcept<EccentricityMap,Vertex> >();
-        typedef typename property_traits<EccentricityMap>::value_type Eccentricity;
-
-        Eccentricity
-                r = numeric_values<Eccentricity>::infinity(),
-                d = numeric_values<Eccentricity>::zero();
-        VertexIterator i, end;
-        tie(i, end) = vertices(g);
-        for(tie(i, end) = vertices(g); i != end; ++i) {
-            DistanceMap dm = get(dist, *i);
-            Eccentricity e = eccentricity(g, dm);
-            put(ecc, *i, e);
-
-            // track the radius and diameter at the same time
-            r = std::min(r, e);
-            d = std::max(d, e);
-        }
-        return make_pair(r, d);
+template <typename Graph, typename DistanceMatrix, typename EccentricityMap>
+inline std::pair<typename property_traits<EccentricityMap>::value_type,
+                    typename property_traits<EccentricityMap>::value_type>
+all_eccentricities(const Graph& g, const DistanceMatrix& dist, EccentricityMap ecc)
+{
+    function_requires< VertexListGraphConcept<Graph> >();
+    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+    typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+    function_requires< ReadablePropertyMapConcept<DistanceMatrix,Vertex> >();
+    typedef typename property_traits<DistanceMatrix>::value_type DistanceMap;
+    function_requires< WritablePropertyMapConcept<EccentricityMap,Vertex> >();
+    typedef typename property_traits<EccentricityMap>::value_type Eccentricity;
+
+    Eccentricity
+            r = numeric_values<Eccentricity>::infinity(),
+            d = numeric_values<Eccentricity>::zero();
+    VertexIterator i, end;
+    tie(i, end) = vertices(g);
+    for(tie(i, end) = vertices(g); i != end; ++i) {
+        DistanceMap dm = get(dist, *i);
+        Eccentricity e = eccentricity(g, dm);
+        put(ecc, *i, e);
+
+        // track the radius and diameter at the same time
+        r = std::min(r, e);
+        d = std::max(d, e);
     }
+    return make_pair(r, d);
+}
 
-
-    template <typename Graph, typename EccentricityMap>
-    inline typename property_traits<EccentricityMap>::value_type
-    radius(const Graph& g, EccentricityMap ecc)
-    {
-        function_requires< VertexListGraphConcept<Graph> >();
-        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-        typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
-        function_requires< ReadablePropertyMapConcept<EccentricityMap, Vertex> >();
-        typedef typename property_traits<EccentricityMap>::value_type Eccentricity;
-
-        VertexIterator i, end;
-        tie(i, end) = vertices(g);
-        Eccentricity ret = get(ecc, *i);
-        for(i = next(i); i != end; ++i) {
-            Eccentricity cur = get(ecc, *i);
-            ret = std::min(ret, cur);
-        }
-        return ret;
+template <typename Graph, typename EccentricityMap>
+inline std::pair<typename property_traits<EccentricityMap>::value_type,
+                    typename property_traits<EccentricityMap>::value_type>
+radius_and_diameter(const Graph& g, EccentricityMap ecc)
+{
+    function_requires< VertexListGraphConcept<Graph> >();
+    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+    typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+    function_requires< ReadablePropertyMapConcept<EccentricityMap, Vertex> >();
+    typedef typename property_traits<EccentricityMap>::value_type Eccentricity;
+
+    VertexIterator i, end;
+    tie(i, end) = vertices(g);
+    Eccentricity radius = get(ecc, *i);
+    Eccentricity diameter = get(ecc, *i);
+    for(i = next(i); i != end; ++i) {
+        Eccentricity cur = get(ecc, *i);
+        radius = std::min(radius, cur);
+        diameter = std::max(diameter, cur);
     }
+    return std::make_pair(radius, diameter);
+}
 
 
-    template <typename Graph, typename EccentricityMap>
-    inline typename property_traits<EccentricityMap>::value_type
-    diameter(const Graph& g, EccentricityMap ecc)
-    {
-        function_requires< VertexListGraphConcept<Graph> >();
-        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-        typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
-        function_requires< ReadablePropertyMapConcept<EccentricityMap, Vertex> >();
-        typedef typename property_traits<EccentricityMap>::value_type Eccentricity;
-
-        VertexIterator i, end;
-        tie(i, end) = vertices(g);
-        Eccentricity ret = get(ecc, *i);
-        for(i = next(i); i != end; ++i) {
-            Eccentricity cur = get(ecc, *i);
-            ret = std::max(ret, cur);
-        }
-        return ret;
-    }
+template <typename Graph, typename EccentricityMap>
+inline typename property_traits<EccentricityMap>::value_type
+radius(const Graph& g, EccentricityMap ecc)
+{ return radius_and_diameter(g, ecc).first; }
 
 
-    template <typename Graph, typename EccentricityMap>
-    inline std::pair<typename property_traits<EccentricityMap>::value_type,
-                     typename property_traits<EccentricityMap>::value_type>
-    radius_and_diameter(const Graph& g, EccentricityMap ecc)
-    {
-        function_requires< VertexListGraphConcept<Graph> >();
-        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-        typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
-        function_requires< ReadablePropertyMapConcept<EccentricityMap, Vertex> >();
-        typedef typename property_traits<EccentricityMap>::value_type Eccentricity;
-
-        VertexIterator i, end;
-        tie(i, end) = vertices(g);
-        Eccentricity radius = get(ecc, *i);
-        Eccentricity diameter = get(ecc, *i);
-        for(i = next(i); i != end; ++i) {
-            Eccentricity cur = get(ecc, *i);
-            radius = std::min(radius, cur);
-            diameter = std::max(diameter, cur);
-        }
-        return std::make_pair(radius, diameter);
-    }
-}
+template <typename Graph, typename EccentricityMap>
+inline typename property_traits<EccentricityMap>::value_type
+diameter(const Graph& g, EccentricityMap ecc)
+{ return radius_and_diameter(g, ecc).second; }
+
+} /* namespace boost */
 
 #endif

Modified: trunk/boost/graph/geodesic_distance.hpp
==============================================================================
--- trunk/boost/graph/geodesic_distance.hpp	(original)
+++ trunk/boost/graph/geodesic_distance.hpp	2009-02-08 10:57:41 EST (Sun, 08 Feb 2009)
@@ -38,10 +38,10 @@
 };
 
 template <typename Graph, typename DistanceMap>
-inline mean_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, float>
+inline mean_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, double>
 measure_mean_geodesic(const Graph&, DistanceMap)
 {
-    return mean_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, float>();
+    return mean_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, double>();
 }
 
 template <typename T, typename Graph, typename DistanceMap>
@@ -119,7 +119,7 @@
 }
 
 template <typename Graph, typename DistanceMap>
-inline float
+inline double
 mean_geodesic(const Graph& g, DistanceMap dist)
 { return mean_geodesic(g, dist, measure_mean_geodesic(g, dist)); }
 

Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2	(original)
+++ trunk/libs/graph/test/Jamfile.v2	2009-02-08 10:57:41 EST (Sun, 08 Feb 2009)
@@ -103,6 +103,8 @@
     [ run closeness_centrality.cpp ]
     [ run degree_centrality.cpp ]
     [ run mean_geodesic.cpp ]
+    [ run eccentricity.cpp ]
+    [ run clustering_coefficient.cpp ]
 
     $(optional_tests)
     ;

Copied: trunk/libs/graph/test/clustering_coefficient.cpp (from r51086, /sandbox/SOC/2007/graphs/libs/graph/test/runtime/clustering_coefficient.cpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/libs/graph/test/runtime/clustering_coefficient.cpp	(original)
+++ trunk/libs/graph/test/clustering_coefficient.cpp	2009-02-08 10:57:41 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
@@ -6,8 +6,6 @@
 
 #include <iostream>
 
-#include <boost/detail/lightweight_test.hpp>
-
 #include <boost/graph/undirected_graph.hpp>
 #include <boost/graph/directed_graph.hpp>
 #include <boost/graph/exterior_property.hpp>
@@ -20,15 +18,14 @@
 static const unsigned N = 5;
 
 template <typename Graph>
-        struct vertex_vector
+struct vertex_vector
 {
     typedef graph_traits<Graph> traits;
     typedef vector<typename traits::vertex_descriptor> type;
 };
 
 template <typename Graph>
-        void build_graph(Graph& g,
-                         typename vertex_vector<Graph>::type& v)
+void build_graph(Graph& g, typename vertex_vector<Graph>::type& v)
 {
     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 
@@ -50,7 +47,7 @@
 {
     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 
-    typedef exterior_vertex_property<Graph, float> ClusteringProperty;
+    typedef exterior_vertex_property<Graph, double> ClusteringProperty;
     typedef typename ClusteringProperty::container_type ClusteringContainer;
     typedef typename ClusteringProperty::map_type ClusteringMap;
 
@@ -61,38 +58,38 @@
     ClusteringContainer cc(num_vertices(g));
     ClusteringMap cm(cc, g);
 
-    BOOST_TEST(num_paths_through_vertex(g, v[0]) == 3);
-    BOOST_TEST(num_paths_through_vertex(g, v[1]) == 1);
-    BOOST_TEST(num_paths_through_vertex(g, v[2]) == 1);
-    BOOST_TEST(num_paths_through_vertex(g, v[3]) == 0);
-    BOOST_TEST(num_paths_through_vertex(g, v[4]) == 1);
-
-    BOOST_TEST(num_triangles_on_vertex(g, v[0]) == 1);
-    BOOST_TEST(num_triangles_on_vertex(g, v[1]) == 1);
-    BOOST_TEST(num_triangles_on_vertex(g, v[2]) == 1);
-    BOOST_TEST(num_triangles_on_vertex(g, v[3]) == 0);
-    BOOST_TEST(num_triangles_on_vertex(g, v[4]) == 0);
-
-    BOOST_TEST(clustering_coefficient(g, v[0]) == float(1)/3);
-    BOOST_TEST(clustering_coefficient(g, v[1]) == 1);
-    BOOST_TEST(clustering_coefficient(g, v[2]) == 1);
-    BOOST_TEST(clustering_coefficient(g, v[3]) == 0);
-    BOOST_TEST(clustering_coefficient(g, v[4]) == 0);
+    BOOST_ASSERT(num_paths_through_vertex(g, v[0]) == 3);
+    BOOST_ASSERT(num_paths_through_vertex(g, v[1]) == 1);
+    BOOST_ASSERT(num_paths_through_vertex(g, v[2]) == 1);
+    BOOST_ASSERT(num_paths_through_vertex(g, v[3]) == 0);
+    BOOST_ASSERT(num_paths_through_vertex(g, v[4]) == 1);
+
+    BOOST_ASSERT(num_triangles_on_vertex(g, v[0]) == 1);
+    BOOST_ASSERT(num_triangles_on_vertex(g, v[1]) == 1);
+    BOOST_ASSERT(num_triangles_on_vertex(g, v[2]) == 1);
+    BOOST_ASSERT(num_triangles_on_vertex(g, v[3]) == 0);
+    BOOST_ASSERT(num_triangles_on_vertex(g, v[4]) == 0);
+
+    BOOST_ASSERT(clustering_coefficient(g, v[0]) == double(1)/3);
+    BOOST_ASSERT(clustering_coefficient(g, v[1]) == 1);
+    BOOST_ASSERT(clustering_coefficient(g, v[2]) == 1);
+    BOOST_ASSERT(clustering_coefficient(g, v[3]) == 0);
+    BOOST_ASSERT(clustering_coefficient(g, v[4]) == 0);
 
     all_clustering_coefficients(g, cm);
 
-    BOOST_TEST(cm[v[0]] == float(1)/3);
-    BOOST_TEST(cm[v[1]] == 1);
-    BOOST_TEST(cm[v[2]] == 1);
-    BOOST_TEST(cm[v[3]] == 0);
-    BOOST_TEST(cm[v[4]] == 0);
+    BOOST_ASSERT(cm[v[0]] == double(1)/3);
+    BOOST_ASSERT(cm[v[1]] == 1);
+    BOOST_ASSERT(cm[v[2]] == 1);
+    BOOST_ASSERT(cm[v[3]] == 0);
+    BOOST_ASSERT(cm[v[4]] == 0);
 
     // I would have used check_close, but apparently, that requires
     // me to link this against a library - which I don't really want
     // to do. Basically, this makes sure that that coefficient is
     // within some tolerance (like 1/10 million).
-    float coef = mean_clustering_coefficient(g, cm);
-    BOOST_TEST((coef - (7.0f / 15.0f)) < 1e-7f);
+    double coef = mean_clustering_coefficient(g, cm);
+    BOOST_ASSERT((coef - (7.0f / 15.0f)) < 1e-7f);
 }
 
 int

Copied: trunk/libs/graph/test/eccentricity.cpp (from r51086, /sandbox/SOC/2007/graphs/libs/graph/test/runtime/eccentricity.cpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/libs/graph/test/runtime/eccentricity.cpp	(original)
+++ trunk/libs/graph/test/eccentricity.cpp	2009-02-08 10:57:41 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,12 +8,11 @@
 
 #include <boost/graph/undirected_graph.hpp>
 #include <boost/graph/directed_graph.hpp>
-#include <boost/graph/exterior_property.hpp>
-#include <boost/graph/constant_property_map.hpp>
-
 #include <boost/graph/floyd_warshall_shortest.hpp>
 #include <boost/graph/eccentricity.hpp>
-#include "io.hpp"
+#include <boost/graph/exterior_property.hpp>
+#include <boost/graph/property_maps/constant_property_map.hpp>
+
 
 using namespace std;
 using namespace boost;