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;