|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-08-17 09:15:13
Author: asutton
Date: 2007-08-17 09:15:11 EDT (Fri, 17 Aug 2007)
New Revision: 38738
URL: http://svn.boost.org/trac/boost/changeset/38738
Log:
Rewriting most of the examples
Added:
sandbox/SOC/2007/graphs/libs/graph/examples/scaled_closeness_centrality.cpp
- copied, changed from r38656, /sandbox/SOC/2007/graphs/libs/graph/examples/norm_closeness_centrality.cpp
Removed:
sandbox/SOC/2007/graphs/libs/graph/examples/norm_closeness_centrality.cpp
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/examples/Jamfile.v2 | 2
sandbox/SOC/2007/graphs/libs/graph/examples/closeness_centrality.cpp | 74 ++++++++++++++++++++--------------
sandbox/SOC/2007/graphs/libs/graph/examples/degree_centrality.cpp | 54 +++++++++++++------------
sandbox/SOC/2007/graphs/libs/graph/examples/flow_network.hpp | 2
sandbox/SOC/2007/graphs/libs/graph/examples/helper.hpp | 27 +++++++++++
sandbox/SOC/2007/graphs/libs/graph/examples/influence_prestige.cpp | 48 +++++++++++----------
sandbox/SOC/2007/graphs/libs/graph/examples/mean_geodesic.cpp | 72 +++++++++++++++++++++++----------
sandbox/SOC/2007/graphs/libs/graph/examples/scaled_closeness_centrality.cpp | 85 +++++++++++++++++++++++++--------------
8 files changed, 225 insertions(+), 139 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 09:15:11 EDT (Fri, 17 Aug 2007)
@@ -8,6 +8,6 @@
exe degree_centrality : degree_centrality.cpp ;
exe influence_prestige : influence_prestige.cpp ;
exe closeness_centrality : closeness_centrality.cpp ;
-exe norm_closeness_centrality : norm_closeness_centrality.cpp ;
+exe scaled_closeness_centrality : scaled_closeness_centrality.cpp ;
exe mean_geodesic : 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 09:15:11 EDT (Fri, 17 Aug 2007)
@@ -4,62 +4,74 @@
// 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"
-
+//[closeness_centrality_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/closeness_centrality.hpp>
+#include "helper.hpp"
using namespace std;
using namespace boost;
+// The Actor type stores the name of each vertex in the graph.
+struct Actor
+{
+ std::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 closeness centralities of each
+// vertex in the graph.
+typedef boost::exterior_vertex_property<Graph, float> ClosenessProperty;
+typedef ClosenessProperty::container_type ClosenessContainer;
+typedef ClosenessProperty::map_type ClosenessMap;
+
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_constant_distances
+ // 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_closeness_centrality
ClosenessContainer cents(num_vertices(g));
ClosenessMap cm(cents, g);
closeness_centrality(g, dm, cm);
- //]
- //[closeness_sort_vertices
- vector<Vertex> sorted(num_vertices(g));
- sort_vertices(sorted, g, cm);
- //]
-
- // Print the degree centrality of each vertex
- //[print_sorted_closeness
- vector<Vertex>::iterator i, end = sorted.end();
- for(i = sorted.begin(); i != end; ++i) {
+ // 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 << cm[*i] << "\n";
+ << g[*i].name << get(cm, *i) << endl;
}
- //]
return 0;
}
+//]
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 09:15:11 EDT (Fri, 17 Aug 2007)
@@ -4,54 +4,56 @@
// 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"
+//[degree_centrality_example
#include <iostream>
#include <iomanip>
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/exterior_property.hpp>
#include <boost/graph/degree_centrality.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 container type for degree centralities and its
+// corresponding property map.
+typedef exterior_vertex_property<Graph, unsigned> CentralityProperty;
+typedef CentralityProperty::container_type CentralityContainer;
+typedef CentralityProperty::map_type CentralityMap;
+
int
main(int argc, char *argv[])
{
- //[setup_social_network
+ // Create the graph and read it from standard input.
Graph g;
- map<string, Vertex> verts;
- //]
-
- // Read in and build the graph
- //[build_social_network
- 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 degree centrality for graph
- //[measure_social_network
+ // Compute the degree centrality for graph.
CentralityContainer cents(num_vertices(g));
CentralityMap cm(cents, g);
degree_centrality(g, cm);
- //]
- // Print the degree centrality of each vertex
- //[print_social_network
+ // Print the degree centrality of each vertex.
graph_traits<Graph>::vertex_iterator i, end;
for(tie(i, end) = vertices(g); i != end; ++i) {
cout << setiosflags(ios::left) << setw(12)
- << g[*i].name << cm[*i] << "\n";
+ << g[*i].name << cm[*i] << endl;
}
- //]
return 0;
}
+//]
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/flow_network.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/flow_network.hpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/flow_network.hpp 2007-08-17 09:15:11 EDT (Fri, 17 Aug 2007)
@@ -14,7 +14,6 @@
#include <boost/graph/exterior_property.hpp>
#include <boost/graph/constant_property_map.hpp>
-//[flow_network_types
struct Actor
{
std::string name;
@@ -23,7 +22,6 @@
typedef boost::directed_graph<Actor> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
typedef boost::graph_traits<Graph>::edge_descriptor Edge;
-//]
typedef boost::exterior_vertex_property<Graph, int> DistanceProperty;
typedef DistanceProperty::matrix_type DistanceMatrix;
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 09:15:11 EDT (Fri, 17 Aug 2007)
@@ -7,9 +7,10 @@
#ifndef BOOST_GRAPH_EXAMPLE_HELPER_HPP
#define BOOST_GRAPH_EXAMPLE_HELPER_HPP
+#include <string>
+#include <map>
#include <algorithm>
-//[add_named_vertex
template <typename Graph, typename VertexMap>
typename boost::graph_traits<Graph>::vertex_descriptor
add_named_vertex(Graph& g, const std::string& name, VertexMap& vm)
@@ -35,7 +36,29 @@
}
return v;
}
-//]
+
+template <typename Graph, typename InputStream>
+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;
+ std::map<std::string, Vertex> verts;
+ for(std::string line; std::getline(is, line); ) {
+ if(line.empty()) continue;
+ std::size_t index = line.find_first_of(',');
+ std::string first(line, 0, index);
+ std::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);
+ }
+ return verts;
+}
+
+
//[property_comparator
template <typename PropertyMap>
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 09:15:11 EDT (Fri, 17 Aug 2007)
@@ -4,62 +4,64 @@
// Boost Software License, Version 1.0 (See accompanying file
// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+//[influence_prestige_example
#include <iostream>
#include <iomanip>
-#include <string>
-#include <vector>
-#include <map>
#include <boost/graph/directed_graph.hpp>
#include <boost/graph/exterior_property.hpp>
#include <boost/graph/degree_centrality.hpp>
-#include "flow_network.hpp"
#include "helper.hpp"
using namespace std;
using namespace boost;
+// The Actor type stores the name of each vertex in the graph.
+struct Actor
+{
+ std::string name;
+};
+
+// Declare the graph type and its vertex and edge types.
+typedef directed_graph<Actor> Graph;
+typedef graph_traits<Graph>::vertex_descriptor Vertex;
+typedef graph_traits<Graph>::edge_descriptor Edge;
+
+// Declare a container type for influence and prestige (both
+// of which are degree centralities) and its corresponding
+// property map.
+typedef exterior_vertex_property<Graph, unsigned> CentralityProperty;
+typedef CentralityProperty::container_type CentralityContainer;
+typedef CentralityProperty::map_type CentralityMap;
+
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 influence and prestige for the graph
- //[compute_influence_prestige
+ // Compute the influence for the graph.
CentralityContainer influence(num_vertices(g));
CentralityMap im(influence, g);
degree_centrality(g, im, measure_influence(g));
+ // Compute the influence for the graph.
CentralityContainer prestige(num_vertices(g));
CentralityMap pm(prestige, g);
degree_centrality(g, pm, measure_prestige(g));
- //]
// Print the degree centrality of each vertex
- //[print_influence_prestige
graph_traits<Graph>::vertex_iterator i, end;
for(tie(i, end) = vertices(g); i != end; ++i) {
Vertex v = *i;
cout << setiosflags(ios::left) << setw(12)
<< g[v].name << "\t"
<< im[v] << "\t"
- << pm[v] << "\n";
+ << pm[v] << endl;
}
- //]
return 0;
}
+//]
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 09:15:11 EDT (Fri, 17 Aug 2007)
@@ -4,57 +4,83 @@
// 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"
-
+//[mean_geodesic_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/geodesic_distance.hpp>
+#include "helper.hpp"
using namespace std;
using namespace boost;
+// The Actor type stores the name of each vertex in the graph.
+struct Actor
+{
+ std::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 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;
+
+
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_mean_geodesics
+ // Compute the mean geodesic distances for each vertex in
+ // the graph.
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);
- //]
+ // Print the mean geodesic distance of each vertex and finally,
+ // the graph itself.
graph_traits<Graph>::vertex_iterator i, end;
for(tie(i, end) = vertices(g); i != end; ++i) {
- cout << g[*i].name << " : " << get(gm, *i) << "\n";
+ cout << setw(12) << setiosflags(ios::left)
+ << g[*i].name << get(gm, *i) << endl;
}
-
- //[print_graph_mean_geodesic
cout << "mean geodesic distance: " << geo << endl;
- //]
return 0;
}
+//]
Deleted: sandbox/SOC/2007/graphs/libs/graph/examples/norm_closeness_centrality.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/norm_closeness_centrality.cpp 2007-08-17 09:15:11 EDT (Fri, 17 Aug 2007)
+++ (empty file)
@@ -1,84 +0,0 @@
-// (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)
-
-#include "social_network.hpp"
-#include "helper.hpp"
-
-#include <iostream>
-#include <iomanip>
-#include <boost/graph/floyd_warshall_shortest.hpp>
-#include <boost/graph/closeness_centrality.hpp>
-
-using namespace std;
-using namespace boost;
-
-//[normalized_closeness_measure
-template <typename Graph,
- typename Distance,
- typename Result,
- typename Divide = std::divides<Result> >
-struct normalized_closeness_measure
-{
- typedef Distance distance_type;
- typedef Result result_type;
-
- Result operator ()(Distance d, const Graph& g)
- {
- if(d == numeric_values<Distance>::infinity()) {
- return numeric_values<Result>::zero();
- }
- else {
- return div(Result(num_vertices(g)), Result(d));
- }
- }
- Divide div;
-};
-//]
-
-int
-main(int argc, char *argv[])
-{
- 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);
- }
-
- 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_normalized_closeness
- ClosenessContainer cents(num_vertices(g));
- ClosenessMap cm(cents, g);
- normalized_closeness_measure<Graph, int, float> m;
- closeness_centrality(g, dm, cm, m);
- //]
-
- vector<Vertex> sorted(num_vertices(g));
- sort_vertices(sorted, g, cm);
-
- // Print the degree centrality of each vertex
- vector<Vertex>::iterator i, end = sorted.end();
- for(i = sorted.begin(); i != end; ++i) {
- cout << setw(12) << setiosflags(ios::left)
- << g[*i].name << cm[*i] << "\n";
- }
-
- return 0;
-}
Copied: sandbox/SOC/2007/graphs/libs/graph/examples/scaled_closeness_centrality.cpp (from r38656, /sandbox/SOC/2007/graphs/libs/graph/examples/norm_closeness_centrality.cpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/libs/graph/examples/norm_closeness_centrality.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/scaled_closeness_centrality.cpp 2007-08-17 09:15:11 EDT (Fri, 17 Aug 2007)
@@ -4,23 +4,31 @@
// 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"
-
+//[scaled_closeness_centrality_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/closeness_centrality.hpp>
+#include "helper.hpp"
using namespace std;
using namespace boost;
-//[normalized_closeness_measure
+// This template struct provides a generic version of a "scaling"
+// closeness measure. Specifically, this implementation divides
+// the number of vertices in the graph by the sum of geodesic
+// distances of each vertex. This measure allows customization
+// of the distance type, result type, and even the underlying
+// divide operation.
template <typename Graph,
typename Distance,
typename Result,
- typename Divide = std::divides<Result> >
-struct normalized_closeness_measure
+ typename Divide = divides<Result> >
+struct scaled_closeness_measure
{
typedef Distance distance_type;
typedef Result result_type;
@@ -36,49 +44,64 @@
}
Divide div;
};
-//]
+
+// The Actor type stores the name of each vertex in the graph.
+struct Actor
+{
+ std::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 closeness centralities of each
+// vertex in the graph.
+typedef boost::exterior_vertex_property<Graph, float> ClosenessProperty;
+typedef ClosenessProperty::container_type ClosenessContainer;
+typedef ClosenessProperty::map_type ClosenessMap;
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));
- //]
+
+ // Create the scaled closeness measure.
+ scaled_closeness_measure<Graph, int, float> m;
// Compute the degree centrality for graph
- //[compute_normalized_closeness
ClosenessContainer cents(num_vertices(g));
ClosenessMap cm(cents, g);
- normalized_closeness_measure<Graph, int, float> m;
closeness_centrality(g, dm, cm, m);
- //]
-
- vector<Vertex> sorted(num_vertices(g));
- sort_vertices(sorted, g, cm);
- // Print the degree centrality of each vertex
- vector<Vertex>::iterator i, end = sorted.end();
- for(i = sorted.begin(); i != end; ++i) {
+ // Print the scaled 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 << cm[*i] << "\n";
+ << g[*i].name << get(cm, *i) << endl;
}
return 0;
}
+//]
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