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;
+}