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