[Boost-commit] svn:boost r38751 - sandbox/SOC/2007/graphs/libs/graph/examples

From: asutton_at_[hidden]
Date: 2007-08-17 15:23:27

Author: asutton
Date: 2007-08-17 15:23:26 EDT (Fri, 17 Aug 2007)
New Revision: 38751
URL: http://svn.boost.org/trac/boost/changeset/38751

Log:
Completely rewrote all the examples so they're more "isolated"
Propagated function name changes
Added an example for redef'ing the geodesic measure

Added:
   sandbox/SOC/2007/graphs/libs/graph/examples/inclusive_mean_geodesic.cpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2007/graphs/libs/graph/examples/Jamfile.v2                      |     1                                         
   sandbox/SOC/2007/graphs/libs/graph/examples/closeness_centrality.cpp        |     6 +-                                      
   sandbox/SOC/2007/graphs/libs/graph/examples/degree_centrality.cpp           |     2                                         
   sandbox/SOC/2007/graphs/libs/graph/examples/eccentricity.cpp                |    78 ++++++++++++++++++++++++++------------- 
   sandbox/SOC/2007/graphs/libs/graph/examples/helper.hpp                      |    35 ++++++++++++++++-                       
   sandbox/SOC/2007/graphs/libs/graph/examples/influence_prestige.cpp          |     6 +-                                      
   sandbox/SOC/2007/graphs/libs/graph/examples/mean_geodesic.cpp               |    14 ++----                                  
   sandbox/SOC/2007/graphs/libs/graph/examples/scaled_closeness_centrality.cpp |     2                                         
   8 files changed, 98 insertions(+), 46 deletions(-)

Modified: sandbox/SOC/2007/graphs/libs/graph/examples/Jamfile.v2
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/Jamfile.v2	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/Jamfile.v2	2007-08-17 15:23:26 EDT (Fri, 17 Aug 2007)
@@ -10,4 +10,5 @@
 exe closeness_centrality : closeness_centrality.cpp ;
 exe scaled_closeness_centrality : scaled_closeness_centrality.cpp ;
 exe mean_geodesic : mean_geodesic.cpp ;
+exe inclusive_mean_geodesic : inclusive_mean_geodesic.cpp ;
 exe eccentricity : eccentricity.cpp ;
\ No newline at end of file

Modified: sandbox/SOC/2007/graphs/libs/graph/examples/closeness_centrality.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/closeness_centrality.cpp	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/closeness_centrality.cpp	2007-08-17 15:23:26 EDT (Fri, 17 Aug 2007)
@@ -21,7 +21,7 @@
 // The Actor type stores the name of each vertex in the graph.
 struct Actor
 {
-    std::string name;
+    string name;
 };
 
 // Declare the graph type and its vertex and edge types.
@@ -60,10 +60,10 @@
     WeightMap wm(1);
     floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
 
-    // Compute the degree centrality for graph
+    // Compute the closeness centrality for graph.
     ClosenessContainer cents(num_vertices(g));
     ClosenessMap cm(cents, g);
-    closeness_centrality(g, dm, cm);
+    all_closeness_centralities(g, dm, cm);
 
     // Print the closeness centrality of each vertex.
     graph_traits<Graph>::vertex_iterator i, end;

Modified: sandbox/SOC/2007/graphs/libs/graph/examples/degree_centrality.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/degree_centrality.cpp	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/degree_centrality.cpp	2007-08-17 15:23:26 EDT (Fri, 17 Aug 2007)
@@ -45,7 +45,7 @@
     // Compute the degree centrality for graph.
     CentralityContainer cents(num_vertices(g));
     CentralityMap cm(cents, g);
-    degree_centrality(g, cm);
+    all_degree_centralities(g, cm);
 
     // Print the degree centrality of each vertex.
     graph_traits<Graph>::vertex_iterator i, end;

Modified: sandbox/SOC/2007/graphs/libs/graph/examples/eccentricity.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/eccentricity.cpp	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/eccentricity.cpp	2007-08-17 15:23:26 EDT (Fri, 17 Aug 2007)
@@ -4,53 +4,79 @@
 // Boost Software License, Version 1.0 (See accompanying file
 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
 
-#include "social_network.hpp"
-#include "helper.hpp"
 
+//[eccentricity_example
 #include <iostream>
 #include <iomanip>
+
+#include <boost/graph/undirected_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 "helper.hpp"
 
 using namespace std;
 using namespace boost;
 
+// The Actor type stores the name of each vertex in the graph.
+struct Actor
+{
+    string name;
+};
+
+// Declare the graph type and its vertex and edge types.
+typedef undirected_graph<Actor> Graph;
+typedef graph_traits<Graph>::vertex_descriptor Vertex;
+typedef graph_traits<Graph>::edge_descriptor Edge;
+
+// Declare a matrix type and its corresponding property map that
+// will contain the distances between each pair of vertices.
+typedef exterior_vertex_property<Graph, int> DistanceProperty;
+typedef DistanceProperty::matrix_type DistanceMatrix;
+typedef DistanceProperty::matrix_map_type DistanceMatrixMap;
+
+// Declare the weight map so that each edge returns the same value.
+typedef constant_property_map<Edge, int> WeightMap;
+
+// Declare a container and its corresponding property map that
+// will contain the resulting eccentricities of each vertex in
+// the graph.
+typedef boost::exterior_vertex_property<Graph, int> EccentricityProperty;
+typedef EccentricityProperty::container_type EccentricityContainer;
+typedef EccentricityProperty::map_type EccentricityMap;
+
 int
 main(int argc, char *argv[])
 {
+    // Create the graph and read it from standard input.
     Graph g;
-    map<string, Vertex> verts;
-
-    // Read in and build the graph
-    for(string line; getline(cin, line); ) {
-        if(line.empty()) continue;
-        size_t index = line.find_first_of(',');
-        string first(line, 0, index);
-        string second(line, index + 1);
-
-        Vertex u = add_named_vertex(g, first, verts);
-        Vertex v = add_named_vertex(g, second, verts);
-        add_edge(u, v, g);
-    }
+    read_graph(g, cin);
 
+    // Compute the distances between all pairs of vertices using
+    // the Floyd-Warshall algorithm. Note that the weight map is
+    // created so that every edge has a weight of 1.
     DistanceMatrix distances(num_vertices(g));
     DistanceMatrixMap dm(distances, g);
     WeightMap wm(1);
     floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
 
-    // Compute the degree centrality for graph
-    //[compute_eccentricity
+    // Compute the eccentricities for graph - this computation returns
+    // both the radius and diameter as well.
+    int r, d;
     EccentricityContainer eccs(num_vertices(g));
     EccentricityMap em(eccs, g);
-    eccentricity(g, dm, em);
-    int radius = graph_radius(g, em);
-    int diameter = graph_diameter(g, em);
-    //]
-
-    //[print_radius_diameter
-    cout << setw(10) << setiosflags(ios::left) << "radius" << radius << "\n";
-    cout << setw(10) << setiosflags(ios::left) << "diameter" << diameter << "\n";
-    //]
+    tie(r, d) = all_eccentricities(g, dm, em);
+
+    // Print the closeness centrality of each vertex.
+    graph_traits<Graph>::vertex_iterator i, end;
+    for(tie(i, end) = vertices(g); i != end; ++i) {
+        cout << setw(12) << setiosflags(ios::left)
+                << g[*i].name << get(em, *i) << endl;
+    }
+    cout << "radius: " << r << endl;
+    cout << "diamter: " << d << endl;
 
     return 0;
 }
+//]

Modified: sandbox/SOC/2007/graphs/libs/graph/examples/helper.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/helper.hpp	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/helper.hpp	2007-08-17 15:23:26 EDT (Fri, 17 Aug 2007)
@@ -8,6 +8,7 @@
 #define BOOST_GRAPH_EXAMPLE_HELPER_HPP
 
 #include <string>
+#include <sstream>
 #include <map>
 #include <algorithm>
 
@@ -38,9 +39,7 @@
 }
 
 template <typename Graph, typename InputStream>
-inline std::map<
-        std::string,
-        typename boost::graph_traits<Graph>::vertex_descriptor>
+inline std::map<std::string, typename boost::graph_traits<Graph>::vertex_descriptor>
 read_graph(Graph& g, InputStream& is)
 {
     typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
@@ -58,6 +57,36 @@
     return verts;
 }
 
+template <typename Graph, typename WeightMap, typename InputStream>
+inline std::map<std::string, typename boost::graph_traits<Graph>::vertex_descriptor>
+read_weighted_graph(Graph& g, WeightMap wm, InputStream& is)
+{
+    typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
+    typedef typename boost::graph_traits<Graph>::edge_descriptor Edge;
+    std::map<std::string, Vertex> verts;
+    for(std::string line; std::getline(is, line); ) {
+        if(line.empty()) continue;
+        std::size_t i = line.find_first_of(',');
+        std::size_t j = line.find_first_of(',', i + 1);
+        std::string first(line, 0, i);
+        std::string second(line, i + 1, j - i - 1);
+        std::string prob(line, j + 1);
+
+        // convert the probability to a float
+        std::stringstream ss(prob);
+        float p;
+        ss >> p;
+
+        // add the vertices to the graph
+        Vertex u = add_named_vertex(g, first, verts);
+        Vertex v = add_named_vertex(g, second, verts);
+
+        // add the edge and set the weight
+        Edge e = add_edge(u, v, g).first;
+        put(wm, e, p);
+    }
+    return verts;
+}
 
 
 //[property_comparator

Added: sandbox/SOC/2007/graphs/libs/graph/examples/inclusive_mean_geodesic.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/inclusive_mean_geodesic.cpp	2007-08-17 15:23:26 EDT (Fri, 17 Aug 2007)
@@ -0,0 +1,153 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// 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)
+
+//[inclusive_mean_geodesic_example
+#include <iostream>
+#include <iomanip>
+
+#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/geodesic_distance.hpp>
+#include "helper.hpp"
+
+using namespace std;
+using namespace boost;
+
+// This template structure defines the function that we will apply
+// to compute both the per-vertex mean geodesic distances and the
+// graph's mean geodesic distance.
+template <typename Graph,
+          typename DistanceType,
+          typename ResultType,
+          typename Divides = divides<ResultType> >
+struct inclusive_average
+{
+    typedef DistanceType distance_type;
+    typedef ResultType result_type;
+
+    result_type operator ()(distance_type d, const Graph& g)
+    {
+        if(d == numeric_values<distance_type>::infinity()) {
+            return numeric_values<result_type>::infinity();
+        }
+        else {
+            return div(result_type(d), result_type(num_vertices(g)));
+        }
+    }
+    Divides div;
+};
+
+// The Page type stores the name of each vertex in the graph and
+// represents web pages that can be navigated to.
+struct WebPage
+{
+    string name;
+};
+
+// The Link type stores an associated probability of traveling
+// from one page to another.
+struct Link
+{
+    float probability;
+};
+
+// Declare the graph type and its vertex and edge types.
+typedef directed_graph<WebPage, Link> Graph;
+typedef graph_traits<Graph>::vertex_descriptor Vertex;
+typedef graph_traits<Graph>::edge_descriptor Edge;
+
+// Declare a matrix type and its corresponding property map that
+// will contain the distances between each pair of vertices.
+typedef exterior_vertex_property<Graph, float> DistanceProperty;
+typedef DistanceProperty::matrix_type DistanceMatrix;
+typedef DistanceProperty::matrix_map_type DistanceMatrixMap;
+
+// Declare the weight map as an accessor into the bundled
+// edge property.
+typedef property_map<Graph, float Link::*>::type WeightMap;
+
+// Declare a container and its corresponding property map that
+// will contain the resulting mean geodesic distances of each
+// vertex in the graph.
+typedef exterior_vertex_property<Graph, float> GeodesicProperty;
+typedef GeodesicProperty::container_type GeodesicContainer;
+typedef GeodesicProperty::map_type GeodesicMap;
+
+static float exclusive_geodesics(const Graph&, DistanceMatrixMap, GeodesicMap);
+static float inclusive_geodesics(const Graph&, DistanceMatrixMap, GeodesicMap);
+
+int
+main(int argc, char *argv[])
+{
+    // Create the graph and the weight map as an accessor to
+    // the edge weights (or probabilities in this case).
+    Graph g;
+    WeightMap wm(&g, &Link::probability);
+
+    // Read the weighted graph from standard input.
+    read_weighted_graph(g, wm, cin);
+
+    // Compute the distances between all pairs of vertices using
+    // the Floyd-Warshall algorithm. The weight map was created
+    // above so it could be populated when the graph was read in.
+    DistanceMatrix distances(num_vertices(g));
+    DistanceMatrixMap dm(distances, g);
+    floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
+
+    // Create the containers and the respective property maps that
+    // will contain the mean geodesics averaged both including
+    // self-loop distances and excluding them.
+    GeodesicContainer exclude(num_vertices(g));
+    GeodesicContainer include(num_vertices(g));
+    GeodesicMap exmap(exclude, g);
+    GeodesicMap inmap(include, g);
+
+    float ex = exclusive_geodesics(g, dm, exmap);
+    float in = inclusive_geodesics(g, dm, inmap);
+
+    // Print the mean geodesic distance of each vertex and finally,
+    // the graph itself.
+    cout << setw(12) << setiosflags(ios::left) << "vertex";
+    cout << setw(12) << setiosflags(ios::left) << "excluding";
+    cout << setw(12) << setiosflags(ios::left) << "including" << endl;
+    graph_traits<Graph>::vertex_iterator i, end;
+    for(tie(i, end) = vertices(g); i != end; ++i) {
+        cout << setw(12) << setiosflags(ios::left)
+             << g[*i].name
+             << setw(12) << get(exmap, *i)
+             << setw(12) << get(inmap, *i) << endl;
+    }
+    cout << "small world (excluding self-loops): " << ex << endl;
+    cout << "small world (including self-loops): " << in << endl;
+
+    return 0;
+}
+
+float
+exclusive_geodesics(const Graph& g, DistanceMatrixMap dm, GeodesicMap gm)
+{
+    // Compute the mean geodesic distances, which excludes distances
+    // of self-loops by default. Return the measure for the entire graph.
+    return all_mean_geodesics(g, dm, gm);
+}
+
+
+float
+inclusive_geodesics(const Graph &g, DistanceMatrixMap dm, GeodesicMap gm)
+{
+    // Create a new measure object for computing the mean geodesic
+    // distance of all vertices. This measure will actually be used
+    // for both averages.
+    inclusive_average<Graph, float, float> m;
+
+    // Compute the mean geodesic distance using the inclusive average
+    // to account for self-loop distances. Return the measure for the
+    // entire graph.
+    return all_mean_geodesics(g, dm, gm, m);
+}
+//]

Modified: sandbox/SOC/2007/graphs/libs/graph/examples/influence_prestige.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/influence_prestige.cpp	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/influence_prestige.cpp	2007-08-17 15:23:26 EDT (Fri, 17 Aug 2007)
@@ -20,7 +20,7 @@
 // The Actor type stores the name of each vertex in the graph.
 struct Actor
 {
-    std::string name;
+    string name;
 };
 
 // Declare the graph type and its vertex and edge types.
@@ -45,12 +45,12 @@
     // Compute the influence for the graph.
     CentralityContainer influence(num_vertices(g));
     CentralityMap im(influence, g);
-    degree_centrality(g, im, measure_influence(g));
+    all_influence_values(g, im);
 
     // Compute the influence for the graph.
     CentralityContainer prestige(num_vertices(g));
     CentralityMap pm(prestige, g);
-    degree_centrality(g, pm, measure_prestige(g));
+    all_prestige_values(g, pm);
 
     // Print the degree centrality of each vertex
     graph_traits<Graph>::vertex_iterator i, end;

Modified: sandbox/SOC/2007/graphs/libs/graph/examples/mean_geodesic.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/mean_geodesic.cpp	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/mean_geodesic.cpp	2007-08-17 15:23:26 EDT (Fri, 17 Aug 2007)
@@ -21,7 +21,7 @@
 // The Actor type stores the name of each vertex in the graph.
 struct Actor
 {
-    std::string name;
+    string name;
 };
 
 // Declare the graph type and its vertex and edge types.
@@ -45,7 +45,6 @@
 typedef GeodesicProperty::container_type GeodesicContainer;
 typedef GeodesicProperty::map_type GeodesicMap;
 
-
 int
 main(int argc, char *argv[])
 {
@@ -62,14 +61,11 @@
     floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
 
     // Compute the mean geodesic distances for each vertex in
-    // the graph.
+    // the graph and get the average mean geodesic distace (the
+    // so-called small-world distance) as a result.
     GeodesicContainer geodesics(num_vertices(g));
     GeodesicMap gm(geodesics, g);
-    mean_geodesic(g, dm, gm);
-
-    // Using the previously computed mean geodesic distances, compute
-    // the mean geodesic distance for the entire graph.
-    float geo = graph_mean_geodesic(g, gm);
+    float sw = all_mean_geodesics(g, dm, gm);
 
     // Print the mean geodesic distance of each vertex and finally,
     // the graph itself.
@@ -78,7 +74,7 @@
         cout << setw(12) << setiosflags(ios::left)
              << g[*i].name << get(gm, *i) << endl;
     }
-    cout << "mean geodesic distance: " << geo << endl;
+    cout << "small world distance: " << sw << endl;
 
 
     return 0;

Modified: sandbox/SOC/2007/graphs/libs/graph/examples/scaled_closeness_centrality.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/scaled_closeness_centrality.cpp	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/scaled_closeness_centrality.cpp	2007-08-17 15:23:26 EDT (Fri, 17 Aug 2007)
@@ -93,7 +93,7 @@
     // Compute the degree centrality for graph
     ClosenessContainer cents(num_vertices(g));
     ClosenessMap cm(cents, g);
-    closeness_centrality(g, dm, cm, m);
+    all_closeness_centralities(g, dm, cm, m);
 
     // Print the scaled closeness centrality of each vertex.
     graph_traits<Graph>::vertex_iterator i, end;