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

Subject: [Boost-commit] svn:boost r51249 - in trunk: boost/graph libs/graph/test
From: asutton_at_[hidden]
Date: 2009-02-14 08:29:09

Author: asutton
Date: 2009-02-14 08:29:07 EST (Sat, 14 Feb 2009)
New Revision: 51249
URL: http://svn.boost.org/trac/boost/changeset/51249

Log:
Updating core_numbers from David Gleich.

Added:
   trunk/libs/graph/test/core_numbers_test.cpp   (contents, props changed)
Text files modified: 
   trunk/boost/graph/core_numbers.hpp |   520 +++++++++++++++++++++++---------------- 
   trunk/libs/graph/test/Jamfile.v2   |     1                                         
   2 files changed, 306 insertions(+), 215 deletions(-)

Modified: trunk/boost/graph/core_numbers.hpp
==============================================================================
--- trunk/boost/graph/core_numbers.hpp	(original)
+++ trunk/boost/graph/core_numbers.hpp	2009-02-14 08:29:07 EST (Sat, 14 Feb 2009)
@@ -1,258 +1,348 @@
+//
+//=======================================================================
 // 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
 
 #include <boost/pending/mutable_queue.hpp>
+#include <boost/pending/indirect_cmp.hpp>
+#include <boost/graph/breadth_first_search.hpp>
+#include <boost/iterator/reverse_iterator.hpp>
 
 /*
- * KCore
+ * core_numbers
  *
  * Requirement: IncidenceGraph
  */
 
-namespace boost {
-
-// A linear time O(m) algorithm to compute the in-degree core number
-// of a graph for unweighted graphs.
+// History
 //
-// and a O((n+m) log n) algorithm to compute the in-edge-weight core
-// numbers of a weighted graph.
+// 30 July 2007
+// Added visitors to the implementation
 //
-// 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;
+// 8 February 2008
+// Fixed headers and missing typename
+
+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:
+    // Vladimir Batagelj and Matjaz Zaversnik, "An O(m) Algorithm for Cores
+    // Decomposition of Networks."  Sept. 1 2002.
+
+    template <typename Visitor, typename Graph>
+    struct CoreNumbersVisitorConcept {
+        void constraints()
+        {
+            function_requires< CopyConstructibleConcept<Visitor> >();
+            vis.examine_vertex(u,g);
+            vis.finish_vertex(u,g);
+            vis.examine_edge(e,g);
+        }
+        Visitor vis;
+        Graph g;
+        typename graph_traits<Graph>::vertex_descriptor u;
+        typename graph_traits<Graph>::edge_descriptor e;
     };
 
-    // 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 <class Visitors = null_visitor>
+    class core_numbers_visitor : public bfs_visitor<Visitors> {
+        public:
+        core_numbers_visitor() {}
+        core_numbers_visitor(Visitors vis)
+            : bfs_visitor<Visitors>(vis) {}
+
+        private:
+        template <class Vertex, class Graph>
+        void initialize_vertex(Vertex, Graph&) {}
+
+        template <class Vertex, class Graph>
+        void discover_vertex(Vertex , Graph&) {}
+
+        template <class Vertex, class Graph>
+        void gray_target(Vertex, Graph&) {}
+
+        template <class Vertex, class Graph>
+        void black_target(Vertex, Graph&) {}
+
+        template <class Edge, class Graph>
+        void tree_edge(Edge, Graph&) {}
+
+        template <class Edge, class Graph>
+        void non_tree_edge(Edge, Graph&) {}
+    };
+
+    template <class Visitors>
+    core_numbers_visitor<Visitors> make_core_numbers_visitor(Visitors vis)
+    { return core_numbers_visitor<Visitors>(vis); };
+
+    typedef core_numbers_visitor<> default_core_numbers_visitor;
+
+    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
+        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));
+                }
+            }
         }
-        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 Visitor>
+        typename property_traits<CoreMap>::value_type
+        core_numbers_impl(Graph& g, CoreMap c, EdgeWeightMap wm,
+            MutableQueue& Q, Visitor vis)
+        {
+            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();
+                vis.examine_vertex(v,g);
+                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) {
+                    vis.examine_edge(*oi,g);
+                    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);
+                    }
+                }
+                vis.finish_vertex(v,g);
             }
+            return (v_cn);
         }
-    }
 
-    // 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())
+        template <typename Graph, typename CoreMap, typename EdgeWeightMap,
+            typename IndexMap, typename CoreNumVisitor>
+        typename property_traits<CoreMap>::value_type
+        core_numbers_dispatch(Graph&g, CoreMap c, EdgeWeightMap wm,
+            IndexMap im, CoreNumVisitor vis)
+        {
+            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, vis);
+        }
+
+        // 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 Visitor>
+        typename property_traits<CoreMap>::value_type
+        core_numbers_impl(Graph& g, CoreMap c, PositionMap pos, Visitor vis)
         {
-            // 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);
+            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<typename graph_traits<Graph>::degree_size_type>)(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];
+                vis.examine_vertex(v,g);
+                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) {
+                    vis.examine_edge(*oi,g);
+                    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);
+                    }
                 }
+                vis.finish_vertex(v,g);
             }
+            return v_cn;
         }
-        return (v_cn);
+
+    } // namespace detail
+
+    // non-named parameter version for the unweighted case
+    template <typename Graph, typename CoreMap, typename CoreNumVisitor>
+    typename property_traits<CoreMap>::value_type
+    core_numbers(Graph& g, CoreMap c, CoreNumVisitor vis)
+    {
+        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)),
+            vis
+        );
     }
 
-    template <typename Graph, typename CoreMap, typename EdgeWeightMap,
-              typename IndexMap>
+    // non-named paramter version for the unweighted case
+    template <typename Graph, typename CoreMap>
     typename property_traits<CoreMap>::value_type
-    core_numbers_dispatch(Graph&g, CoreMap c, EdgeWeightMap wm, IndexMap im)
+    core_numbers(Graph& g, CoreMap c)
     {
-        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);
+        return core_numbers(g, c, make_core_numbers_visitor(null_visitor()));
     }
 
-    // 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>
+    // non-named parameter version for the weighted case
+    template <typename Graph, typename CoreMap, typename EdgeWeightMap,
+        typename VertexIndexMap, typename CoreNumVisitor>
     typename property_traits<CoreMap>::value_type
-    core_numbers_impl(Graph& g, CoreMap c, PositionMap pos)
+    core_numbers(Graph& g, CoreMap c, EdgeWeightMap wm, VertexIndexMap vim,
+        CoreNumVisitor vis)
     {
         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);
-                }
-            }
-        }
-        return v_cn;
+        detail::compute_in_degree_map(g,c,wm);
+        return detail::core_numbers_dispatch(g,c,wm,vim,vis);
     }
 
-} // namespace detail
+    // non-named parameter version for the weighted case
+//    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),
+//            make_core_numbers_visitor(null_visitor()));
+//    }
 
-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)); }
+    template <typename Graph, typename CoreMap>
+    typename property_traits<CoreMap>::value_type
+    weighted_core_numbers(Graph& g, CoreMap c)
+    {
+        return weighted_core_numbers(
+            g,c, make_core_numbers_visitor(null_visitor())
+        );
+    }
+
+    template <typename Graph, typename CoreMap, typename CoreNumVisitor>
+    typename property_traits<CoreMap>::value_type
+    weighted_core_numbers(Graph& g, CoreMap c, CoreNumVisitor vis)
+    { return core_numbers(g,c,get(edge_weight,g),get(vertex_index,g),vis); }
 
 } // namespace boost
 

Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2	(original)
+++ trunk/libs/graph/test/Jamfile.v2	2009-02-14 08:29:07 EST (Sat, 14 Feb 2009)
@@ -105,6 +105,7 @@
     [ run mean_geodesic.cpp ]
     [ run eccentricity.cpp ]
     [ run clustering_coefficient.cpp ]
+    [ run core_numbers_test.cpp ]
 
     $(optional_tests)
     ;

Added: trunk/libs/graph/test/core_numbers_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/core_numbers_test.cpp	2009-02-14 08:29:07 EST (Sat, 14 Feb 2009)
@@ -0,0 +1,149 @@
+
+#include <vector>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/core_numbers.hpp>
+#include <boost/property_map.hpp>
+
+using namespace boost;
+
+const char* errstr = "";
+
+int test_1() {
+    // core numbers of sample graph
+    typedef adjacency_list<vecS,vecS,undirectedS> Graph;
+
+    Graph G(21);
+    add_edge(0,1,G);
+    add_edge(1,2,G);
+    add_edge(1,3,G);
+    add_edge(2,3,G);
+    add_edge(1,4,G);
+    add_edge(3,4,G);
+    add_edge(4,5,G);
+    add_edge(4,6,G);
+    add_edge(5,6,G);
+    add_edge(4,7,G);
+    add_edge(5,7,G);
+    add_edge(6,7,G);
+    add_edge(7,8,G);
+    add_edge(3,9,G);
+    add_edge(8,9,G);
+    add_edge(8,10,G);
+    add_edge(9,10,G);
+    add_edge(10,11,G);
+    add_edge(10,12,G);
+    add_edge(3,13,G);
+    add_edge(9,13,G);
+    add_edge(3,14,G);
+    add_edge(9,14,G);
+    add_edge(13,14,G);
+    add_edge(16,17,G);
+    add_edge(16,18,G);
+    add_edge(17,19,G);
+    add_edge(18,19,G);
+    add_edge(19,20,G);
+
+    std::vector<int> core_nums(num_vertices(G));
+    core_numbers(G,
+        make_iterator_property_map(core_nums.begin(), get(vertex_index,G)));
+
+    for (size_t i=0; i<num_vertices(G); ++i) {
+        printf("vertex %3zu : %i\n", i, core_nums[i]);
+    }
+
+    int correct[21]={1,2,2,3,3,3,3,3,2,3,2,1,1,3,3,0,2,2,2,2,1};
+    for (size_t i=0; i<num_vertices(G); ++i) {
+        if (core_nums[i] != correct[i]) {
+            return 1; // error!
+        }
+    }
+    return 0;
+}
+
+int test_2() {
+    // core numbers of sample graph
+    typedef adjacency_list < listS, vecS, undirectedS,
+        no_property, property < edge_weight_t, int > > graph_t;
+    int num_nodes = 3;
+    typedef std::pair<int,int> Edge;
+
+    Edge edge_array[] = { Edge(0,1), Edge(0,2), Edge(1,2) };
+    int weights[] = {-1, -2, -2};
+    int num_arcs = sizeof(edge_array) / sizeof(Edge);
+
+    graph_t G(edge_array, edge_array + num_arcs, weights, num_nodes);
+    property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, G);
+
+    std::vector<int> core_nums(num_vertices(G));
+    weighted_core_numbers(G,
+        make_iterator_property_map(core_nums.begin(), get(vertex_index,G)));
+
+    for (size_t i=0; i<num_vertices(G); ++i) {
+        printf("vertex %3zu : %i\n", i, core_nums[i]);
+    }
+
+    int correct[3]={-1,-1,-4};
+    for (size_t i=0; i<num_vertices(G); ++i) {
+        if (core_nums[i] != correct[i]) {
+            return 1; // error!
+        }
+    }
+    return 0;
+}
+
+int test_3() {
+    // core numbers of a directed graph, the core numbers of a directed
+    // cycle are always one
+    typedef adjacency_list < vecS, vecS, directedS > graph_t;
+    int num_nodes = 5;
+    typedef std::pair<int,int> Edge;
+
+    Edge edge_array[] = { Edge(0,1),Edge(1,2),Edge(2,3),Edge(3,4),Edge(4,0) };
+    int num_arcs = sizeof(edge_array) / sizeof(Edge);
+
+    graph_t G(edge_array, edge_array + num_arcs, num_nodes);
+
+    std::vector<int> core_nums(num_vertices(G));
+    core_numbers(G,
+        make_iterator_property_map(core_nums.begin(), get(vertex_index,G)));
+
+    for (size_t i=0; i<num_vertices(G); ++i) {
+        printf("vertex %3zu : %i\n", i, core_nums[i]);
+    }
+
+    int correct[5]={1,1,1,1,1};
+    for (size_t i=0; i<num_vertices(G); ++i) {
+        if (core_nums[i] != correct[i]) {
+            return 1; // error!
+        }
+    }
+    return 0;
+}
+
+int main(int argc, char **argv) {
+  int nfail = 0, ntotal = 0;
+  int rval;
+
+  const char* name;
+
+  name= "core_numbers";
+  rval= test_1(); ntotal++;
+  if (rval!= 0) { nfail++; printf("%20s  %50s\n", name, errstr); }
+  else { printf("%20s  success\n", name); }
+
+  name= "weighted_core_numbers";
+  rval= test_2(); ntotal++;
+  if (rval!= 0) { nfail++; printf("%20s  %50s\n", name, errstr); }
+  else { printf("%20s  success\n", name); }
+
+  name= "directed_corenums";
+  rval= test_3(); ntotal++;
+  if (rval!= 0) { nfail++; printf("%20s  %50s\n", name, errstr); }
+  else { printf("%20s  success\n", name); }
+
+  printf("\n");
+  printf("Total tests  : %3i\n", ntotal);
+  printf("Total failed : %3i\n", nfail);
+
+  return nfail!=0;
+}