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;