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

From: asutton_at_[hidden]
Date: 2007-08-21 12:54:48

Author: asutton
Date: 2007-08-21 12:54:47 EDT (Tue, 21 Aug 2007)
New Revision: 38828
URL: http://svn.boost.org/trac/boost/changeset/38828

Log:
Added examples for Bron-Kerbosch
Rewrote parts of other examples to abstract vertex names

Added:
   sandbox/SOC/2007/graphs/libs/graph/examples/bron_kerbosch_clique_number.cpp   (contents, props changed)
   sandbox/SOC/2007/graphs/libs/graph/examples/bron_kerbosch_print_cliques.cpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2007/graphs/libs/graph/examples/Jamfile.v2                      |     6 ++                                      
   sandbox/SOC/2007/graphs/libs/graph/examples/closeness_centrality.cpp        |    12 +++++-                                  
   sandbox/SOC/2007/graphs/libs/graph/examples/degree_centrality.cpp           |    12 +++++-                                  
   sandbox/SOC/2007/graphs/libs/graph/examples/eccentricity.cpp                |    12 +++++-                                  
   sandbox/SOC/2007/graphs/libs/graph/examples/helper.hpp                      |    77 ++++++++++++++++----------------------- 
   sandbox/SOC/2007/graphs/libs/graph/examples/inclusive_mean_geodesic.cpp     |    14 +++++--                                 
   sandbox/SOC/2007/graphs/libs/graph/examples/influence_prestige.cpp          |    12 +++++-                                  
   sandbox/SOC/2007/graphs/libs/graph/examples/mean_geodesic.cpp               |    12 +++++-                                  
   sandbox/SOC/2007/graphs/libs/graph/examples/scaled_closeness_centrality.cpp |    12 +++++-                                  
   9 files changed, 107 insertions(+), 62 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-21 12:54:47 EDT (Tue, 21 Aug 2007)
@@ -11,4 +11,8 @@
 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
+exe eccentricity : eccentricity.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: sandbox/SOC/2007/graphs/libs/graph/examples/bron_kerbosch_clique_number.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/bron_kerbosch_clique_number.cpp	2007-08-21 12:54:47 EDT (Tue, 21 Aug 2007)
@@ -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)
+
+//[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: sandbox/SOC/2007/graphs/libs/graph/examples/bron_kerbosch_print_cliques.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/bron_kerbosch_print_cliques.cpp	2007-08-21 12:54:47 EDT (Tue, 21 Aug 2007)
@@ -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)
+
+//[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;
+}
+//]

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-21 12:54:47 EDT (Tue, 21 Aug 2007)
@@ -29,6 +29,10 @@
 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;
@@ -48,9 +52,13 @@
 int
 main(int argc, char *argv[])
 {
-    // Create the graph and read it from standard input.
+    // Create the graph and a property map that provides access to[
+    // tha actor names.
     Graph g;
-    read_graph(g, cin);
+    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

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-21 12:54:47 EDT (Tue, 21 Aug 2007)
@@ -29,6 +29,10 @@
 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;
@@ -38,9 +42,13 @@
 int
 main(int argc, char *argv[])
 {
-    // Create the graph and read it from standard input.
+    // Create the graph and a property map that provides access
+    // to the actor names.
     Graph g;
-    read_graph(g, cin);
+    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));

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-21 12:54:47 EDT (Tue, 21 Aug 2007)
@@ -30,6 +30,10 @@
 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;
@@ -49,9 +53,13 @@
 int
 main(int argc, char *argv[])
 {
-    // Create the graph and read it from standard input.
+    // Create the graph and a name map that provides access to
+    // then actor names.
     Graph g;
-    read_graph(g, cin);
+    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

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-21 12:54:47 EDT (Tue, 21 Aug 2007)
@@ -12,9 +12,11 @@
 #include <map>
 #include <algorithm>
 
-template <typename Graph, typename VertexMap>
+#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, const std::string& name, VertexMap& vm)
+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;
@@ -24,23 +26,22 @@
     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 and associate it with this name.
+        // The name was unique so we need to add a vertex to the graph
         v = add_vertex(g);
-        g[v].name = name;
         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.
+        // We had alread inserted this name so we can return the
+        // associated vertex.
         v = iter->second;
     }
     return v;
 }
 
-template <typename Graph, typename InputStream>
+template <typename Graph, typename NameMap, typename InputStream>
 inline std::map<std::string, typename boost::graph_traits<Graph>::vertex_descriptor>
-read_graph(Graph& g, InputStream& is)
+read_graph(Graph& g, NameMap nm, InputStream& is)
 {
     typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
     std::map<std::string, Vertex> verts;
@@ -50,16 +51,25 @@
         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);
+        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 WeightMap, typename InputStream>
+template <typename Graph, typename InputStream>
 inline std::map<std::string, typename boost::graph_traits<Graph>::vertex_descriptor>
-read_weighted_graph(Graph& g, WeightMap wm, InputStream& is)
+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;
@@ -78,8 +88,8 @@
         ss >> p;
 
         // add the vertices to the graph
-        Vertex u = add_named_vertex(g, first, verts);
-        Vertex v = add_named_vertex(g, second, verts);
+        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;
@@ -89,38 +99,15 @@
 }
 
 
-//[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)
+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)
 {
-    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;
-    }
+    typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
+    typedef boost::null_property_map<Vertex, std::string> NameMap;
 
-    std::sort(v.begin(), v.end(), property_greater<PropertyMap>(pm));
+    return read_weighted_graph(g, NameMap(), wm, is);
 }
-//]
+
 
 #endif

Modified: sandbox/SOC/2007/graphs/libs/graph/examples/inclusive_mean_geodesic.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/inclusive_mean_geodesic.cpp	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/inclusive_mean_geodesic.cpp	2007-08-21 12:54:47 EDT (Tue, 21 Aug 2007)
@@ -61,6 +61,10 @@
 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;
@@ -84,13 +88,15 @@
 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).
+    // 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;
-    WeightMap wm(&g, &Link::probability);
+    NameMap nm(get(&WebPage::name, g));
+    WeightMap wm(get(&Link::probability, g));
 
     // Read the weighted graph from standard input.
-    read_weighted_graph(g, wm, cin);
+    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

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-21 12:54:47 EDT (Tue, 21 Aug 2007)
@@ -28,6 +28,10 @@
 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.
@@ -38,9 +42,13 @@
 int
 main(int argc, char *argv[])
 {
-    // Create the graph and read it from standard input.
+    // Create the graph and a property map that provides
+    // access to the actor names.
     Graph g;
-    read_graph(g, cin);
+    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));

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-21 12:54:47 EDT (Tue, 21 Aug 2007)
@@ -29,6 +29,10 @@
 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;
@@ -48,9 +52,13 @@
 int
 main(int argc, char *argv[])
 {
-    // Create the graph and read it from standard input.
+    // Create the graph and a property map that provides access
+    // to the actor names.
     Graph g;
-    read_graph(g, cin);
+    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

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-21 12:54:47 EDT (Tue, 21 Aug 2007)
@@ -56,6 +56,10 @@
 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;
@@ -75,9 +79,13 @@
 int
 main(int argc, char *argv[])
 {
-    // Create the graph and read it from standard input.
+    // Create the graph and a property map that provides access
+    // to the actor names.
     Graph g;
-    read_graph(g, cin);
+    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