[Boost-commit] svn:boost r51251 - trunk/libs/graph/examples

Subject: [Boost-commit] svn:boost r51251 - trunk/libs/graph/examples
From: asutton_at_[hidden]
Date: 2009-02-14 08:56:38

Author: asutton
Date: 2009-02-14 08:56:37 EST (Sat, 14 Feb 2009)
New Revision: 51251
URL: http://svn.boost.org/trac/boost/changeset/51251

Log:
Importing examples from SOC 2007
Added:
   trunk/libs/graph/examples/
   trunk/libs/graph/examples/Jamfile.v2   (contents, props changed)
   trunk/libs/graph/examples/bron_kerbosch_clique_number.cpp   (contents, props changed)
   trunk/libs/graph/examples/bron_kerbosch_print_cliques.cpp   (contents, props changed)
   trunk/libs/graph/examples/closeness_centrality.cpp   (contents, props changed)
   trunk/libs/graph/examples/clustering_coefficient.cpp   (contents, props changed)
   trunk/libs/graph/examples/comm_network.graph   (contents, props changed)
   trunk/libs/graph/examples/degree_centrality.cpp   (contents, props changed)
   trunk/libs/graph/examples/eccentricity.cpp   (contents, props changed)
   trunk/libs/graph/examples/helper.hpp   (contents, props changed)
   trunk/libs/graph/examples/inclusive_mean_geodesic.cpp   (contents, props changed)
   trunk/libs/graph/examples/influence_prestige.cpp   (contents, props changed)
   trunk/libs/graph/examples/info_network.graph   (contents, props changed)
   trunk/libs/graph/examples/mean_geodesic.cpp   (contents, props changed)
   trunk/libs/graph/examples/prism_3_2.graph   (contents, props changed)
   trunk/libs/graph/examples/prob_network.graph   (contents, props changed)
   trunk/libs/graph/examples/scaled_closeness_centrality.cpp   (contents, props changed)
   trunk/libs/graph/examples/social_network.graph   (contents, props changed)
   trunk/libs/graph/examples/tiernan_girth_circumference.cpp   (contents, props changed)
   trunk/libs/graph/examples/tiernan_print_cycles.cpp   (contents, props changed)

Added: trunk/libs/graph/examples/Jamfile.v2
==============================================================================
--- (empty file)
+++ trunk/libs/graph/examples/Jamfile.v2	2009-02-14 08:56:37 EST (Sat, 14 Feb 2009)
@@ -0,0 +1,19 @@
+
+project
+    : requirements
+        <include>../../../
+        <include>$BOOST_ROOT
+    ;
+
+exe degree_centrality : degree_centrality.cpp ;
+exe influence_prestige : influence_prestige.cpp ;
+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 ;
+exe clustering_coefficient : clustering_coefficient.cpp ;
+exe tiernan_print_cycles : tiernan_print_cycles.cpp ;
+exe tiernan_girth_circumference : tiernan_girth_circumference.cpp ;
+exe bron_kerbosch_print_cliques : bron_kerbosch_print_cliques.cpp ;
+exe bron_kerbosch_clique_number : bron_kerbosch_clique_number.cpp ;

Added: trunk/libs/graph/examples/bron_kerbosch_clique_number.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/examples/bron_kerbosch_clique_number.cpp	2009-02-14 08:56:37 EST (Sat, 14 Feb 2009)
@@ -0,0 +1,36 @@
+// (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)
+
+//[code_bron_kerbosch_clique_number
+#include <iostream>
+
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/bron_kerbosch_all_cliques.hpp>
+
+#include "helper.hpp"
+
+using namespace std;
+using namespace boost;
+
+// Declare the graph type and its vertex and edge types.
+typedef undirected_graph<> Graph;
+typedef graph_traits<Graph>::vertex_descriptor Vertex;
+typedef graph_traits<Graph>::edge_descriptor Edge;
+
+int
+main(int argc, char *argv[])
+{
+    // Create the graph and read it from standard input.
+    Graph g;
+    read_graph(g, cin);
+
+    // Use the Bron-Kerbosch algorithm to find all cliques, and
+    size_t c = bron_kerbosch_clique_number(g);
+    cout << "clique number: " << c << endl;
+
+    return 0;
+}
+//]

Added: trunk/libs/graph/examples/bron_kerbosch_print_cliques.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/examples/bron_kerbosch_print_cliques.cpp	2009-02-14 08:56:37 EST (Sat, 14 Feb 2009)
@@ -0,0 +1,74 @@
+// (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)
+
+//[code_bron_kerbosch_print_cliques
+#include <iostream>
+
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/bron_kerbosch_all_cliques.hpp>
+
+#include "helper.hpp"
+
+using namespace std;
+using namespace boost;
+
+// The clique_printer is a visitor that will print the vertices that comprise
+// a clique. Note that the vertices are not given in any specific order.
+template <typename OutputStream>
+struct clique_printer
+{
+    clique_printer(OutputStream& stream)
+        : os(stream)
+    { }
+
+    template <typename Clique, typename Graph>
+    void clique(const Clique& c, const Graph& g)
+    {
+        // Iterate over the clique and print each vertex within it.
+        typename Clique::const_iterator i, end = c.end();
+        for(i = c.begin(); i != end; ++i) {
+            os << g[*i].name << " ";
+        }
+        os << endl;
+    }
+    OutputStream& os;
+};
+
+// 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;
+
+// The name map provides an abstract accessor for the names of
+// each vertex. This is used during graph creation.
+typedef property_map<Graph, string Actor::*>::type NameMap;
+
+int
+main(int argc, char *argv[])
+{
+    // Create the graph and and its name map accessor.
+    Graph g;
+    NameMap nm(get(&Actor::name, g));
+
+    // Read the graph from standard input.
+    read_graph(g, nm, cin);
+
+    // Instantiate the visitor for printing cliques
+    clique_printer<ostream> vis(cout);
+
+    // Use the Bron-Kerbosch algorithm to find all cliques, printing them
+    // as they are found.
+    bron_kerbosch_all_cliques(g, vis);
+
+    return 0;
+}
+//]

Added: trunk/libs/graph/examples/closeness_centrality.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/examples/closeness_centrality.cpp	2009-02-14 08:56:37 EST (Sat, 14 Feb 2009)
@@ -0,0 +1,85 @@
+// (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)
+
+//[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
+{
+    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;
+
+// The name map provides an abstract accessor for the names of
+// each vertex. This is used during graph creation.
+typedef property_map<Graph, string Actor::*>::type NameMap;
+
+// 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 a property map that provides access to[
+    // tha actor names.
+    Graph g;
+    NameMap nm(get(&Actor::name, g));
+
+    // Read the graph from standard input.
+    read_graph(g, nm, 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 closeness centrality for graph.
+    ClosenessContainer cents(num_vertices(g));
+    ClosenessMap cm(cents, g);
+    all_closeness_centralities(g, dm, cm);
+
+    // 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(cm, *i) << endl;
+    }
+
+    return 0;
+}
+//]

Added: trunk/libs/graph/examples/clustering_coefficient.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/examples/clustering_coefficient.cpp	2009-02-14 08:56:37 EST (Sat, 14 Feb 2009)
@@ -0,0 +1,69 @@
+// (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)
+
+
+//[code_clustering_coefficient
+#include <iostream>
+#include <iomanip>
+
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/exterior_property.hpp>
+#include <boost/graph/clustering_coefficient.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;
+
+// The name map provides an abstract accessor for the names of
+// each vertex. This is used during graph creation.
+typedef property_map<Graph, string Actor::*>::type NameMap;
+
+// The clustering property, container, and map define the containment
+// and abstract accessor for the clustering coefficients of vertices.
+typedef exterior_vertex_property<Graph, float> ClusteringProperty;
+typedef ClusteringProperty::container_type ClusteringContainer;
+typedef ClusteringProperty::map_type ClusteringMap;
+
+int
+main(int argc, char *argv[])
+{
+    // Create the graph and a name map that provides access to
+    // then actor names.
+    Graph g;
+    NameMap nm(get(&Actor::name, g));
+
+    // Read the graph from standard input.
+    read_graph(g, nm, cin);
+
+    // Compute the clustering coefficients of each vertex in the graph
+    // and the mean clustering coefficient which is returned from the
+    // computation.
+    ClusteringContainer coefs(num_vertices(g));
+    ClusteringMap cm(coefs, g);
+    float cc = all_clustering_coefficients(g, cm);
+
+    // Print the clustering coefficient 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(cm, *i) << endl;
+    }
+    cout << "mean clustering coefficient: " << cc << endl;
+
+    return 0;
+}
+//]

Added: trunk/libs/graph/examples/comm_network.graph
==============================================================================
--- (empty file)
+++ trunk/libs/graph/examples/comm_network.graph	2009-02-14 08:56:37 EST (Sat, 14 Feb 2009)
@@ -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

Added: trunk/libs/graph/examples/degree_centrality.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/examples/degree_centrality.cpp	2009-02-14 08:56:37 EST (Sat, 14 Feb 2009)
@@ -0,0 +1,67 @@
+// (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)
+
+
+//[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;
+
+// The name map provides an abstract accessor for the names of
+// each vertex. This is used during graph creation.
+typedef property_map<Graph, string Actor::*>::type NameMap;
+
+// 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[])
+{
+    // Create the graph and a property map that provides access
+    // to the actor names.
+    Graph g;
+    NameMap nm(get(&Actor::name, g));
+
+    // Read the graph from standard input.
+    read_graph(g, nm, cin);
+
+    // Compute the degree centrality for graph.
+    CentralityContainer cents(num_vertices(g));
+    CentralityMap cm(cents, g);
+    all_degree_centralities(g, cm);
+
+    // 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] << endl;
+    }
+
+    return 0;
+}
+//]

Added: trunk/libs/graph/examples/eccentricity.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/examples/eccentricity.cpp	2009-02-14 08:56:37 EST (Sat, 14 Feb 2009)
@@ -0,0 +1,90 @@
+// (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)
+
+
+//[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;
+
+// The name map provides an abstract accessor for the names of
+// each vertex. This is used during graph creation.
+typedef property_map<Graph, string Actor::*>::type NameMap;
+
+// 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 a name map that provides access to
+    // then actor names.
+    Graph g;
+    NameMap nm(get(&Actor::name, g));
+
+    // Read the graph from standard input.
+    read_graph(g, nm, 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 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);
+    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;
+}
+//]

Added: trunk/libs/graph/examples/helper.hpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/examples/helper.hpp	2009-02-14 08:56:37 EST (Sat, 14 Feb 2009)
@@ -0,0 +1,113 @@
+// (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_HELPER_HPP
+#define BOOST_GRAPH_EXAMPLE_HELPER_HPP
+
+#include <string>
+#include <sstream>
+#include <map>
+#include <algorithm>
+
+#include <boost/graph/null_property_map.hpp>
+
+template <typename Graph, typename NameMap, typename VertexMap>
+typename boost::graph_traits<Graph>::vertex_descriptor
+add_named_vertex(Graph& g, NameMap nm, const std::string& name, VertexMap& vm)
+{
+    typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
+    typedef typename VertexMap::iterator Iterator;
+
+    Vertex v;
+    Iterator iter;
+    bool inserted;
+    tie(iter, inserted) = vm.insert(make_pair(name, Vertex()));
+    if(inserted) {
+        // The name was unique so we need to add a vertex to the graph
+        v = add_vertex(g);
+        iter->second = v;
+        put(nm, v, name);      // store the name in the name map
+    }
+    else {
+        // We had alread inserted this name so we can return the
+        // associated vertex.
+        v = iter->second;
+    }
+    return v;
+}
+
+template <typename Graph, typename NameMap, typename InputStream>
+inline std::map<std::string, typename boost::graph_traits<Graph>::vertex_descriptor>
+read_graph(Graph& g, NameMap nm, 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, nm, first, verts);
+        Vertex v = add_named_vertex(g, nm, second, verts);
+        add_edge(u, v, g);
+    }
+    return verts;
+}
+
+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;
+    typedef boost::null_property_map<Vertex, std::string> NameMap;
+    return read_graph(g, NameMap(), is);
+}
+
+template <typename Graph, typename NameMap, typename WeightMap, typename InputStream>
+inline std::map<std::string, typename boost::graph_traits<Graph>::vertex_descriptor>
+read_weighted_graph(Graph& g, NameMap nm, 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, nm, first, verts);
+        Vertex v = add_named_vertex(g, nm, second, verts);
+
+        // add the edge and set the weight
+        Edge e = add_edge(u, v, g).first;
+        put(wm, e, p);
+    }
+    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 boost::null_property_map<Vertex, std::string> NameMap;
+
+    return read_weighted_graph(g, NameMap(), wm, is);
+}
+
+
+#endif

Added: trunk/libs/graph/examples/inclusive_mean_geodesic.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/examples/inclusive_mean_geodesic.cpp	2009-02-14 08:56:37 EST (Sat, 14 Feb 2009)
@@ -0,0 +1,159 @@
+// (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;
+
+// The name map provides an abstract accessor for the names of
+// each vertex. This is used during graph creation.
+typedef property_map<Graph, string WebPage::*>::type NameMap;
+
+// 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, a name map that providse abstract access
+    // to the web page names, and the weight map as an accessor to
+    // the edge weights (or probabilities).
+    Graph g;
+    NameMap nm(get(&WebPage::name, g));
+    WeightMap wm(get(&Link::probability, g));
+
+    // Read the weighted graph from standard input.
+    read_weighted_graph(g, nm, 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);
+}
+//]

Added: trunk/libs/graph/examples/influence_prestige.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/examples/influence_prestige.cpp	2009-02-14 08:56:37 EST (Sat, 14 Feb 2009)
@@ -0,0 +1,75 @@
+// (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)
+
+//[influence_prestige_example
+#include <iostream>
+#include <iomanip>
+
+#include <boost/graph/directed_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 directed_graph<Actor> Graph;
+typedef graph_traits<Graph>::vertex_descriptor Vertex;
+typedef graph_traits<Graph>::edge_descriptor Edge;
+
+// The name map provides an abstract accessor for the names of
+// each vertex. This is used during graph creation.
+typedef property_map<Graph, string Actor::*>::type NameMap;
+
+// 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 a property map that provides
+    // access to the actor names.
+    Graph g;
+    NameMap nm(get(&Actor::name, g));
+
+    // Read the graph from standard input.
+    read_graph(g, nm, cin);
+
+    // Compute the influence for the graph.
+    CentralityContainer influence(num_vertices(g));
+    CentralityMap im(influence, g);
+    all_influence_values(g, im);
+
+    // Compute the influence for the graph.
+    CentralityContainer prestige(num_vertices(g));
+    CentralityMap pm(prestige, g);
+    all_prestige_values(g, pm);
+
+    // Print the degree centrality of each vertex
+    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] << endl;
+    }
+
+    return 0;
+}
+//]

Added: trunk/libs/graph/examples/info_network.graph
==============================================================================
--- (empty file)
+++ trunk/libs/graph/examples/info_network.graph	2009-02-14 08:56:37 EST (Sat, 14 Feb 2009)
@@ -0,0 +1,11 @@
+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: trunk/libs/graph/examples/mean_geodesic.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/examples/mean_geodesic.cpp	2009-02-14 08:56:37 EST (Sat, 14 Feb 2009)
@@ -0,0 +1,90 @@
+// (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)
+
+//[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
+{
+    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;
+
+// The name map provides an abstract accessor for the names of
+// each vertex. This is used during graph creation.
+typedef property_map<Graph, string Actor::*>::type NameMap;
+
+// 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 a property map that provides access
+    // to the actor names.
+    Graph g;
+    NameMap nm(get(&Actor::name, g));
+
+    // Read the graph from standad input.
+    read_graph(g, nm, 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 mean geodesic distances for each vertex in
+    // 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);
+    float sw = all_mean_geodesics(g, dm, 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 << setw(12) << setiosflags(ios::left)
+             << g[*i].name << get(gm, *i) << endl;
+    }
+    cout << "small world distance: " << sw << endl;
+
+
+    return 0;
+}
+//]

Added: trunk/libs/graph/examples/prism_3_2.graph
==============================================================================
--- (empty file)
+++ trunk/libs/graph/examples/prism_3_2.graph	2009-02-14 08:56:37 EST (Sat, 14 Feb 2009)
@@ -0,0 +1,16 @@
+0,1
+1,2
+2,0
+
+3,4
+4,5
+5,3
+
+0,3
+3,0
+
+1,4
+4,1
+
+2,5
+5,2
\ No newline at end of file

Added: trunk/libs/graph/examples/prob_network.graph
==============================================================================
--- (empty file)
+++ trunk/libs/graph/examples/prob_network.graph	2009-02-14 08:56:37 EST (Sat, 14 Feb 2009)
@@ -0,0 +1,18 @@
+myspace,myspace,.5
+myspace,digg,.5
+blogger,digg,.33
+blogger,slashdot,.33
+blogger,wikipedia,.33
+digg,slashdot,.33
+digg,wikipedia,.33
+digg,digg,.33
+blogspot,slashdot,.5
+blogspot,wikipedia,.5
+slashdot,bbc,.5
+slashdot,wikipedia,.5
+bbc,wikipedia,.5
+bbc,bbc,.5
+wikipedia,wikipedia,.25
+wikipedia,blogger,.25
+wikipedia,myspace,.25
+wikipedia,blogspot,.25
\ No newline at end of file

Added: trunk/libs/graph/examples/scaled_closeness_centrality.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/examples/scaled_closeness_centrality.cpp	2009-02-14 08:56:37 EST (Sat, 14 Feb 2009)
@@ -0,0 +1,115 @@
+// (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)
+
+//[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;
+
+// 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 = divides<Result> >
+struct scaled_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;
+};
+
+// 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;
+
+// The name map provides an abstract accessor for the names of
+// each vertex. This is used during graph creation.
+typedef property_map<Graph, string Actor::*>::type NameMap;
+
+// 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 a property map that provides access
+    // to the actor names.
+    Graph g;
+    NameMap nm(get(&Actor::name, g));
+
+    // Read the graph from standard input.
+    read_graph(g, nm, 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
+    ClosenessContainer cents(num_vertices(g));
+    ClosenessMap cm(cents, g);
+    all_closeness_centralities(g, dm, cm, m);
+
+    // 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 << get(cm, *i) << endl;
+    }
+
+    return 0;
+}
+//]

Added: trunk/libs/graph/examples/social_network.graph
==============================================================================
--- (empty file)
+++ trunk/libs/graph/examples/social_network.graph	2009-02-14 08:56:37 EST (Sat, 14 Feb 2009)
@@ -0,0 +1,12 @@
+Scott,Jill
+Mary,Scott
+Jill,Mary
+Bill,Scott
+Josh,Bill
+Scott,Frank
+Laurie,Frank
+Mary,Laurie
+Anne,Frank
+Howard,Anne
+Frank,Howard
+Josh,Frank
\ No newline at end of file

Added: trunk/libs/graph/examples/tiernan_girth_circumference.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/examples/tiernan_girth_circumference.cpp	2009-02-14 08:56:37 EST (Sat, 14 Feb 2009)
@@ -0,0 +1,40 @@
+// (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)
+
+//[tiernan_girth_circumference
+#include <iostream>
+
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/tiernan_all_cycles.hpp>
+
+#include "helper.hpp"
+
+using namespace std;
+using namespace boost;
+
+// Declare the graph type and its vertex and edge types.
+typedef directed_graph<> Graph;
+typedef graph_traits<Graph>::vertex_descriptor Vertex;
+typedef graph_traits<Graph>::edge_descriptor Edge;
+
+int
+main(int argc, char *argv[])
+{
+    // Create the graph and read it from standard input.
+    Graph g;
+    read_graph(g, cin);
+
+    // Compute the girth and circumference simulataneously
+    size_t girth, circ;
+    tie(girth, circ) = tiernan_girth_and_circumference(g);
+
+    // Print the result
+    cout << "girth: " << girth << endl;
+    cout << "circumference: " << circ << endl;
+
+    return 0;
+}
+//]

Added: trunk/libs/graph/examples/tiernan_print_cycles.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/examples/tiernan_print_cycles.cpp	2009-02-14 08:56:37 EST (Sat, 14 Feb 2009)
@@ -0,0 +1,68 @@
+// (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)
+
+//[tiernan_print_cycles
+#include <iostream>
+
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/tiernan_all_cycles.hpp>
+
+#include "helper.hpp"
+
+using namespace std;
+using namespace boost;
+
+// The cycle_printer is a visitor that will print the path that comprises
+// the cycle. Note that the back() vertex of the path is not the same as
+// the front(). It is implicit in the listing of vertices that the back()
+// vertex is connected to the front().
+template <typename OutputStream>
+struct cycle_printer
+{
+    cycle_printer(OutputStream& stream)
+        : os(stream)
+    { }
+
+    template <typename Path, typename Graph>
+    void cycle(const Path& p, const Graph& g)
+    {
+        // Get the property map containing the vertex indices
+        // so we can print them.
+        typedef typename property_map<Graph, vertex_index_t>::const_type IndexMap;
+        IndexMap indices = get(vertex_index, g);
+
+        // Iterate over path printing each vertex that forms the cycle.
+        typename Path::const_iterator i, end = p.end();
+        for(i = p.begin(); i != end; ++i) {
+            os << get(indices, *i) << " ";
+        }
+        os << endl;
+    }
+    OutputStream& os;
+};
+
+// Declare the graph type and its vertex and edge types.
+typedef directed_graph<> Graph;
+typedef graph_traits<Graph>::vertex_descriptor Vertex;
+typedef graph_traits<Graph>::edge_descriptor Edge;
+
+int
+main(int argc, char *argv[])
+{
+    // Create the graph and read it from standard input.
+    Graph g;
+    read_graph(g, cin);
+
+    // Instantiate the visitor for printing cycles
+    cycle_printer<ostream> vis(cout);
+
+    // Use the Tiernan algorithm to visit all cycles, printing them
+    // as they are found.
+    tiernan_all_cycles(g, vis);
+
+    return 0;
+}
+//]