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

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;