|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-08-13 12:58:20
Author: asutton
Date: 2007-08-13 12:58:07 EDT (Mon, 13 Aug 2007)
New Revision: 38621
URL: http://svn.boost.org/trac/boost/changeset/38621
Log:
New examples and fixups
Added:
sandbox/SOC/2007/graphs/libs/graph/examples/closeness_centrality.cpp (contents, props changed)
sandbox/SOC/2007/graphs/libs/graph/examples/comm_network.graph (contents, props changed)
sandbox/SOC/2007/graphs/libs/graph/examples/flow_network.hpp (contents, props changed)
sandbox/SOC/2007/graphs/libs/graph/examples/info_network.graph
- copied unchanged from r38572, /sandbox/SOC/2007/graphs/libs/graph/examples/information_network.graph
sandbox/SOC/2007/graphs/libs/graph/examples/norm_closeness.cpp (contents, props changed)
sandbox/SOC/2007/graphs/libs/graph/examples/social_network.hpp (contents, props changed)
Removed:
sandbox/SOC/2007/graphs/libs/graph/examples/information_network.graph
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/examples/Jamfile.v2 | 5 +++--
sandbox/SOC/2007/graphs/libs/graph/examples/degree_centrality.cpp | 36 +++++++++---------------------------
sandbox/SOC/2007/graphs/libs/graph/examples/helper.hpp | 36 ++++++++++++++++++++++++++++++++++++
sandbox/SOC/2007/graphs/libs/graph/examples/influence_prestige.cpp | 25 +++----------------------
sandbox/SOC/2007/graphs/libs/graph/examples/social_network.graph | 1 +
5 files changed, 52 insertions(+), 51 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-13 12:58:07 EDT (Mon, 13 Aug 2007)
@@ -6,5 +6,6 @@
;
exe degree_centrality : degree_centrality.cpp ;
-
-exe influence_prestige : influence_prestige.cpp ;
\ No newline at end of file
+exe influence_prestige : influence_prestige.cpp ;
+exe closeness_centrality : closeness_centrality.cpp ;
+exe norm_closeness : norm_closeness.cpp ;
Added: sandbox/SOC/2007/graphs/libs/graph/examples/closeness_centrality.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/closeness_centrality.cpp 2007-08-13 12:58:07 EDT (Mon, 13 Aug 2007)
@@ -0,0 +1,65 @@
+// (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;
+
+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);
+ }
+
+ //[compute_constant_distances
+ 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
+ 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) {
+ cout << setw(12) << setiosflags(ios::left)
+ << g[*i].name << cm[*i] << "\n";
+ }
+ //]
+
+ return 0;
+}
Added: sandbox/SOC/2007/graphs/libs/graph/examples/comm_network.graph
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/comm_network.graph 2007-08-13 12:58:07 EDT (Mon, 13 Aug 2007)
@@ -0,0 +1,12 @@
+Mary,Jill
+Jill,Scott
+Scott,Mary
+Scott,Bill
+Bill,Josh
+Josh,Frank
+Frank,Scott
+Frank,Anne
+Anne,Howard
+Howard,Frank
+Frank,Laurie
+Laurie,Mary
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-13 12:58:07 EDT (Mon, 13 Aug 2007)
@@ -4,36 +4,17 @@
// 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 <string>
-#include <vector>
-#include <map>
+#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;
-//[declare_social_network
-struct Person
-{
- string name;
-};
-
-typedef undirected_graph<Person> Graph;
-typedef graph_traits<Graph>::vertex_descriptor Vertex;
-
-typedef exterior_vertex_property<Graph, size_t> CentralityProperty;
-typedef CentralityProperty::container_type CentralityContainer;
-typedef CentralityProperty::map_type CentralityMap;
-
-typedef map<string, Vertex> VertexMap;
-//]
-
int
main(int argc, char *argv[])
{
@@ -42,8 +23,8 @@
map<string, Vertex> verts;
//]
- //[build_social_network
// 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(',');
@@ -56,18 +37,19 @@
}
//]
- //[measure_social_network
// Compute the degree centrality for graph
+ //[measure_social_network
CentralityContainer cents(num_vertices(g));
CentralityMap cm(cents, g);
degree_centrality(g, cm);
//]
- //[print_social_network
// Print the degree centrality of each vertex
+ //[print_social_network
graph_traits<Graph>::vertex_iterator i, end;
for(tie(i, end) = vertices(g); i != end; ++i) {
- cout << g[*i].name << ": " << cm[*i] << "\n";
+ cout << setiosflags(ios::left) << setw(12)
+ << g[*i].name << cm[*i] << "\n";
}
//]
Added: sandbox/SOC/2007/graphs/libs/graph/examples/flow_network.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/flow_network.hpp 2007-08-13 12:58:07 EDT (Mon, 13 Aug 2007)
@@ -0,0 +1,42 @@
+// (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)
+
+#ifndef BOOST_GRAPH_EXAMPLE_FLOW_NETWORK_HPP
+#define BOOST_GRAPH_EXAMPLE_FLOW_NETWORK_HPP
+
+#include <string>
+#include <map>
+
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/exterior_property.hpp>
+#include <boost/graph/constant_property_map.hpp>
+
+//[flow_network_types
+struct Actor
+{
+ std::string name;
+};
+
+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;
+typedef DistanceProperty::matrix_map_type DistanceMatrixMap;
+
+typedef boost::constant_property_map<Edge, int> WeightMap;
+
+typedef boost::exterior_vertex_property<Graph, unsigned> CentralityProperty;
+typedef CentralityProperty::container_type CentralityContainer;
+typedef CentralityProperty::map_type CentralityMap;
+
+typedef boost::exterior_vertex_property<Graph, float> ClosenessProperty;
+typedef ClosenessProperty::container_type ClosenessContainer;
+typedef ClosenessProperty::map_type ClosenessMap;
+
+#endif
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-13 12:58:07 EDT (Mon, 13 Aug 2007)
@@ -7,6 +7,8 @@
#ifndef BOOST_GRAPH_EXAMPLE_HELPER_HPP
#define BOOST_GRAPH_EXAMPLE_HELPER_HPP
+#include <algorithm>
+
//[add_named_vertex
template <typename Graph, typename VertexMap>
typename boost::graph_traits<Graph>::vertex_descriptor
@@ -35,4 +37,38 @@
}
//]
+//[property_comparator
+template <typename PropertyMap>
+struct property_greater
+{
+ typedef typename boost::property_traits<PropertyMap>::key_type Key;
+ property_greater(PropertyMap pm)
+ : m_prop(pm)
+ { }
+
+ bool operator ()(Key a, Key b) const
+ {
+ return get(m_prop, a) > get(m_prop, b);
+ }
+
+ PropertyMap m_prop;
+};
+//]
+
+//[sort_vertices
+template <typename VertexVector, typename Graph, typename PropertyMap>
+void
+sort_vertices(VertexVector& v, const Graph& g, PropertyMap pm)
+{
+ BOOST_ASSERT(v.size() == num_vertices(g));
+ size_t x = 0;
+ typename boost::graph_traits<Graph>::vertex_iterator i, end;
+ for(boost::tie(i, end) = boost::vertices(g); i != end; ++i) {
+ v[x++] = *i;
+ }
+
+ std::sort(v.begin(), v.end(), property_greater<PropertyMap>(pm));
+}
+//]
+
#endif
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-13 12:58:07 EDT (Mon, 13 Aug 2007)
@@ -14,36 +14,18 @@
#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;
-//[declare_information_network
-struct Person
-{
- string name;
-};
-
-typedef directed_graph<Person> Graph;
-typedef graph_traits<Graph>::vertex_descriptor Vertex;
-
-typedef exterior_vertex_property<Graph, size_t> CentralityProperty;
-typedef CentralityProperty::container_type CentralityContainer;
-typedef CentralityProperty::map_type CentralityMap;
-
-typedef map<string, Vertex> VertexMap;
-//]
-
int
main(int argc, char *argv[])
{
- //[setup_information_network
Graph g;
map<string, Vertex> verts;
- //]
- //[build_information_network
// Read in and build the graph
for(string line; getline(cin, line); ) {
if(line.empty()) continue;
@@ -55,10 +37,9 @@
Vertex v = add_named_vertex(g, second, verts);
add_edge(u, v, g);
}
- //]
- //[measure_information_network
// Compute the influence and prestige for the graph
+ //[compute_influence_prestige
CentralityContainer influence(num_vertices(g));
CentralityMap im(influence, g);
degree_centrality(g, im, measure_influence(g));
@@ -68,8 +49,8 @@
degree_centrality(g, pm, measure_prestige(g));
//]
- //[print_information_network
// 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;
Deleted: sandbox/SOC/2007/graphs/libs/graph/examples/information_network.graph
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/information_network.graph 2007-08-13 12:58:07 EDT (Mon, 13 Aug 2007)
+++ (empty file)
@@ -1,11 +0,0 @@
-myspace,digg
-blogger,digg
-blogger,slahsdot
-blogger,wikipedia
-digg,slashdot
-digg,wikipedia
-blogspot,slashdot
-blogspot,wikipedia
-slashdot,bbc
-slashdot,wikipedia
-bbc,wikipedia
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/examples/norm_closeness.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/norm_closeness.cpp 2007-08-13 12:58:07 EDT (Mon, 13 Aug 2007)
@@ -0,0 +1,84 @@
+// (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;
+}
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/social_network.graph
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/social_network.graph (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/social_network.graph 2007-08-13 12:58:07 EDT (Mon, 13 Aug 2007)
@@ -5,6 +5,7 @@
Josh,Bill
Scott,Frank
Laurie,Frank
+Mary,Laurie
Anne,Frank
Howard,Anne
Frank,Howard
Added: sandbox/SOC/2007/graphs/libs/graph/examples/social_network.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/social_network.hpp 2007-08-13 12:58:07 EDT (Mon, 13 Aug 2007)
@@ -0,0 +1,50 @@
+// (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)
+
+#ifndef BOOST_GRAPH_EXAMPLE_SOCIAL_NETWORK_HPP
+#define BOOST_GRAPH_EXAMPLE_SOCIAL_NETWORK_HPP
+
+#include <string>
+#include <map>
+
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/exterior_property.hpp>
+#include <boost/graph/constant_property_map.hpp>
+
+//[social_network_types
+struct Actor
+{
+ std::string name;
+};
+
+typedef boost::undirected_graph<Actor> Graph;
+typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
+typedef boost::graph_traits<Graph>::edge_descriptor Edge;
+//]
+
+//[distance_matrix_types
+typedef boost::exterior_vertex_property<Graph, int> DistanceProperty;
+typedef DistanceProperty::matrix_type DistanceMatrix;
+typedef DistanceProperty::matrix_map_type DistanceMatrixMap;
+//]
+
+//[constant_weight_map_types
+typedef boost::constant_property_map<Edge, int> WeightMap;
+//]
+
+//[centrality_map_types
+typedef boost::exterior_vertex_property<Graph, unsigned> CentralityProperty;
+typedef CentralityProperty::container_type CentralityContainer;
+typedef CentralityProperty::map_type CentralityMap;
+//]
+
+//[closeness_map_types
+typedef boost::exterior_vertex_property<Graph, float> ClosenessProperty;
+typedef ClosenessProperty::container_type ClosenessContainer;
+typedef ClosenessProperty::map_type ClosenessMap;
+//]
+
+#endif
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