Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r51099 - in trunk: boost/graph libs/graph/test
From: asutton_at_[hidden]
Date: 2009-02-08 10:34:25


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

Log:
Integrated degree centrality and test.

Added:
   trunk/boost/graph/degree_centrality.hpp (contents, props changed)
      - copied, changed from r51086, /sandbox/SOC/2007/graphs/boost/graph/degree_centrality.hpp
   trunk/libs/graph/test/degree_centrality.cpp (contents, props changed)
      - copied, changed from r51086, /sandbox/SOC/2007/graphs/libs/graph/test/runtime/degree_centrality.cpp
Text files modified:
   trunk/boost/graph/degree_centrality.hpp | 210 +++++++++++++++++++--------------------
   trunk/libs/graph/test/Jamfile.v2 | 1
   trunk/libs/graph/test/closeness_centrality.cpp | 26 ++--
   trunk/libs/graph/test/degree_centrality.cpp | 4
   4 files changed, 116 insertions(+), 125 deletions(-)

Copied: trunk/boost/graph/degree_centrality.hpp (from r51086, /sandbox/SOC/2007/graphs/boost/graph/degree_centrality.hpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/boost/graph/degree_centrality.hpp (original)
+++ trunk/boost/graph/degree_centrality.hpp 2009-02-08 10:34:25 EST (Sun, 08 Feb 2009)
@@ -1,140 +1,130 @@
-// (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_DEGREE_CENTRALITY_HXX
-#define BOOST_GRAPH_DEGREE_CENTRALITY_HXX
+#ifndef BOOST_GRAPH_DEGREE_CENTRALITY_HPP
+#define BOOST_GRAPH_DEGREE_CENTRALITY_HPP
 
-#include <boost/graph/new_graph_concepts.hpp>
+#include <boost/graph/graph_concepts.hpp>
 
-namespace boost
+namespace boost {
+
+template <typename Graph>
+struct degree_centrality_measure
 {
- template <typename Graph>
- struct degree_centrality_measure
- {
- typedef typename graph_traits<Graph>::degree_size_type degree_type;
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_type;
- };
-
- template <typename Graph>
- struct influence_measure
- : public degree_centrality_measure<Graph>
- {
- typedef degree_centrality_measure<Graph> base_type;
- typedef typename base_type::degree_type degree_type;
- typedef typename base_type::vertex_type vertex_type;
-
- inline degree_type operator ()(vertex_type v, const Graph& g)
- {
- function_requires< IncidenceGraphConcept<Graph> >();
- return out_degree(v, g);
- }
- };
-
- template <typename Graph>
- inline influence_measure<Graph>
- measure_influence(const Graph&)
- { return influence_measure<Graph>(); }
-
-
- template <typename Graph>
- struct prestige_measure
- : public degree_centrality_measure<Graph>
- {
- typedef degree_centrality_measure<Graph> base_type;
- typedef typename base_type::degree_type degree_type;
- typedef typename base_type::vertex_type vertex_type;
-
- inline degree_type operator ()(vertex_type v, const Graph& g)
- {
- function_requires< BidirectionalGraphConcept<Graph> >();
- return in_degree(v, g);
- }
- };
-
- template <typename Graph>
- inline prestige_measure<Graph>
- measure_prestige(const Graph&)
- { return prestige_measure<Graph>(); }
-
-
- template <typename Graph, typename Vertex, typename Measure>
- inline typename Measure::degree_type
- degree_centrality(const Graph& g, Vertex v, Measure measure)
- {
- function_requires< DegreeMeasureConcept<Measure, Graph> >();
- return measure(v, g);
- }
+ typedef typename graph_traits<Graph>::degree_size_type degree_type;
+ typedef typename graph_traits<Graph>::vertex_descriptor vertex_type;
+};
+
+template <typename Graph>
+struct influence_measure
+ : public degree_centrality_measure<Graph>
+{
+ typedef degree_centrality_measure<Graph> base_type;
+ typedef typename base_type::degree_type degree_type;
+ typedef typename base_type::vertex_type vertex_type;
 
- template <typename Graph, typename Vertex>
- inline typename graph_traits<Graph>::degree_size_type
- degree_centrality(const Graph& g, Vertex v)
+ inline degree_type operator ()(vertex_type v, const Graph& g)
     {
- return degree_centrality(g, v, measure_influence(g));
+ function_requires< IncidenceGraphConcept<Graph> >();
+ return out_degree(v, g);
     }
+};
 
+template <typename Graph>
+inline influence_measure<Graph>
+measure_influence(const Graph&)
+{ return influence_measure<Graph>(); }
 
- // These are just alias functions, intended to provide a more
- // "semantic" interface.
 
- template <typename Graph, typename Vertex>
- inline typename graph_traits<Graph>::degree_size_type
- influence(const Graph& g, Vertex v)
+template <typename Graph>
+struct prestige_measure
+ : public degree_centrality_measure<Graph>
+{
+ typedef degree_centrality_measure<Graph> base_type;
+ typedef typename base_type::degree_type degree_type;
+ typedef typename base_type::vertex_type vertex_type;
+
+ inline degree_type operator ()(vertex_type v, const Graph& g)
     {
- return degree_centrality(g, v, measure_influence(g));
+ function_requires< BidirectionalGraphConcept<Graph> >();
+ return in_degree(v, g);
     }
+};
 
+template <typename Graph>
+inline prestige_measure<Graph>
+measure_prestige(const Graph&)
+{ return prestige_measure<Graph>(); }
 
- template <typename Graph, typename Vertex>
- inline typename graph_traits<Graph>::degree_size_type
- prestige(const Graph& g, Vertex v)
- {
- return degree_centrality(g, v, measure_prestige(g));
- }
 
+template <typename Graph, typename Vertex, typename Measure>
+inline typename Measure::degree_type
+degree_centrality(const Graph& g, Vertex v, Measure measure)
+{
+ function_requires< DegreeMeasureConcept<Measure, Graph> >();
+ return measure(v, g);
+}
 
- template <typename Graph, typename CentralityMap, typename Measure>
- inline void
- all_degree_centralities(const Graph& g, CentralityMap cent, Measure measure)
- {
- function_requires< VertexListGraphConcept<Graph> >();
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
- function_requires< WritablePropertyMapConcept<CentralityMap,Vertex> >();
- typedef typename property_traits<CentralityMap>::value_type Centrality;
-
- VertexIterator i, end;
- for(tie(i, end) = vertices(g); i != end; ++i) {
- Centrality c = degree_centrality(g, *i, measure);
- put(cent, *i, c);
- }
- }
+template <typename Graph, typename Vertex>
+inline typename graph_traits<Graph>::degree_size_type
+degree_centrality(const Graph& g, Vertex v)
+{
+ return degree_centrality(g, v, measure_influence(g));
+}
 
- template <typename Graph, typename CentralityMap>
- inline void all_degree_centralities(const Graph& g, CentralityMap cent)
- {
- all_degree_centralities(g, cent, measure_influence(g));
- }
 
- // More helper functions for computing influence and prestige.
- // I hate the names of these functions, but influence and prestige
- // don't pluralize too well.
+// These are alias functions, intended to provide a more expressive interface.
 
- template <typename Graph, typename CentralityMap>
- inline void all_influence_values(const Graph& g, CentralityMap cent)
- {
- all_degree_centralities(g, cent, measure_influence(g));
- }
+template <typename Graph, typename Vertex>
+inline typename graph_traits<Graph>::degree_size_type
+influence(const Graph& g, Vertex v)
+{ return degree_centrality(g, v, measure_influence(g)); }
 
- template <typename Graph, typename CentralityMap>
- inline void all_prestige_values(const Graph& g, CentralityMap cent)
- {
- all_degree_centralities(g, cent, measure_prestige(g));
+
+template <typename Graph, typename Vertex>
+inline typename graph_traits<Graph>::degree_size_type
+prestige(const Graph& g, Vertex v)
+{ return degree_centrality(g, v, measure_prestige(g)); }
+
+
+template <typename Graph, typename CentralityMap, typename Measure>
+inline void
+all_degree_centralities(const Graph& g, CentralityMap cent, Measure measure)
+{
+ function_requires< VertexListGraphConcept<Graph> >();
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+ function_requires< WritablePropertyMapConcept<CentralityMap,Vertex> >();
+ typedef typename property_traits<CentralityMap>::value_type Centrality;
+
+ VertexIterator i, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ Centrality c = degree_centrality(g, *i, measure);
+ put(cent, *i, c);
     }
 }
 
+template <typename Graph, typename CentralityMap>
+inline void all_degree_centralities(const Graph& g, CentralityMap cent)
+{ all_degree_centralities(g, cent, measure_influence(g)); }
+
+// More helper functions for computing influence and prestige.
+// I hate the names of these functions, but influence and prestige
+// don't pluralize too well.
+
+template <typename Graph, typename CentralityMap>
+inline void all_influence_values(const Graph& g, CentralityMap cent)
+{ all_degree_centralities(g, cent, measure_influence(g)); }
+
+template <typename Graph, typename CentralityMap>
+inline void all_prestige_values(const Graph& g, CentralityMap cent)
+{ all_degree_centralities(g, cent, measure_prestige(g)); }
+
+} /* namespace boost */
+
 #endif
 
 

Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2 (original)
+++ trunk/libs/graph/test/Jamfile.v2 2009-02-08 10:34:25 EST (Sun, 08 Feb 2009)
@@ -101,6 +101,7 @@
     [ run bron_kerbosch_all_cliques.cpp ]
     [ run tiernan_all_cycles.cpp ]
     [ run closeness_centrality.cpp ]
+ [ run degree_centrality.cpp ]
 
     $(optional_tests)
     ;

Modified: trunk/libs/graph/test/closeness_centrality.cpp
==============================================================================
--- trunk/libs/graph/test/closeness_centrality.cpp (original)
+++ trunk/libs/graph/test/closeness_centrality.cpp 2009-02-08 10:34:25 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
@@ -53,7 +53,7 @@
     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
     typedef typename graph_traits<Graph>::edge_descriptor Edge;
 
- typedef exterior_vertex_property<Graph, float> CentralityProperty;
+ typedef exterior_vertex_property<Graph, double> CentralityProperty;
     typedef typename CentralityProperty::container_type CentralityContainer;
     typedef typename CentralityProperty::map_type CentralityMap;
 
@@ -78,11 +78,11 @@
     floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
     all_closeness_centralities(g, dm, cm);
 
- BOOST_ASSERT(cm[v[0]] == float(1)/5);
- BOOST_ASSERT(cm[v[1]] == float(1)/7);
- BOOST_ASSERT(cm[v[2]] == float(1)/7);
- BOOST_ASSERT(cm[v[3]] == float(1)/9);
- BOOST_ASSERT(cm[v[4]] == float(1)/6);
+ BOOST_ASSERT(cm[v[0]] == double(1)/5);
+ BOOST_ASSERT(cm[v[1]] == double(1)/7);
+ BOOST_ASSERT(cm[v[2]] == double(1)/7);
+ BOOST_ASSERT(cm[v[3]] == double(1)/9);
+ BOOST_ASSERT(cm[v[4]] == double(1)/6);
 }
 
 template <typename Graph>
@@ -91,7 +91,7 @@
     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
     typedef typename graph_traits<Graph>::edge_descriptor Edge;
 
- typedef exterior_vertex_property<Graph, float> CentralityProperty;
+ typedef exterior_vertex_property<Graph, double> CentralityProperty;
     typedef typename CentralityProperty::container_type CentralityContainer;
     typedef typename CentralityProperty::map_type CentralityMap;
 
@@ -116,11 +116,11 @@
     floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
     all_closeness_centralities(g, dm, cm);
 
- BOOST_ASSERT(cm[v[0]] == float(0));
- BOOST_ASSERT(cm[v[1]] == float(0));
- BOOST_ASSERT(cm[v[2]] == float(0));
- BOOST_ASSERT(cm[v[3]] == float(1)/10);
- BOOST_ASSERT(cm[v[4]] == float(0));
+ BOOST_ASSERT(cm[v[0]] == double(0));
+ BOOST_ASSERT(cm[v[1]] == double(0));
+ BOOST_ASSERT(cm[v[2]] == double(0));
+ BOOST_ASSERT(cm[v[3]] == double(1)/10);
+ BOOST_ASSERT(cm[v[4]] == double(0));
 }
 
 int

Copied: trunk/libs/graph/test/degree_centrality.cpp (from r51086, /sandbox/SOC/2007/graphs/libs/graph/test/runtime/degree_centrality.cpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/libs/graph/test/runtime/degree_centrality.cpp (original)
+++ trunk/libs/graph/test/degree_centrality.cpp 2009-02-08 10:34:25 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,8 +8,8 @@
 
 #include <boost/graph/undirected_graph.hpp>
 #include <boost/graph/directed_graph.hpp>
-#include <boost/graph/exterior_property.hpp>
 #include <boost/graph/degree_centrality.hpp>
+#include <boost/graph/exterior_property.hpp>
 
 using namespace std;
 using namespace boost;


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk