From: asutton_at_[hidden]
Date: 2007-06-11 12:57:47
Author: asutton
Date: 2007-06-11 12:57:47 EDT (Mon, 11 Jun 2007)
New Revision: 4526
URL: http://svn.boost.org/trac/boost/changeset/4526
Log:
Changed some of the movie code to fit better with the documentation.
Reimplemented six-degrees to use a BFS rather than Dijkstra's.
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/examples/movies/kevin_bacon.cpp | 27 +++++++++----------
sandbox/SOC/2007/graphs/libs/graph/examples/movies/movies | 4 +-
sandbox/SOC/2007/graphs/libs/graph/examples/movies/movies.cpp | 10 +++---
sandbox/SOC/2007/graphs/libs/graph/examples/movies/movies.hpp | 19 +++++-------
sandbox/SOC/2007/graphs/libs/graph/examples/movies/six_degrees.cpp | 56 +++++++++++++++++++++++++++------------
5 files changed, 66 insertions(+), 50 deletions(-)
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/movies/kevin_bacon.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/movies/kevin_bacon.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/movies/kevin_bacon.cpp 2007-06-11 12:57:47 EDT (Mon, 11 Jun 2007)
@@ -19,11 +19,11 @@
// This visitor is responsible for recording (setting) the bacon numbers
// of actors in the movie graph.
-template <typename BaconMap>
-struct BaconNumberRecorder : public bfs_visitor<>
+template <typename DistanceMap>
+struct ActorDistanceRecorder : public bfs_visitor<>
{
- BaconNumberRecorder(BaconMap b)
- : bacons(b)
+ ActorDistanceRecorder(DistanceMap d)
+ : distances(d)
{}
// The tree_edge() method is invoked when a vertex v is discovered
@@ -41,18 +41,18 @@
v = target(e, g);
// set the bacon number to 1 + u's bacon number
- bacons[v] = bacons[u] + 1;
+ distances[v] = distances[u] + 1;
}
- BaconMap bacons;
+ DistanceMap distances;
};
// This is just a convenience function so we can call a function rather than
// explicitly instantiate the visitor type. It makes it more "action-oriented".
-template <typename BaconMap>
-BaconNumberRecorder<BaconMap> record_bacon_numbers(BaconMap b)
+template <typename DistanceMap>
+ActorDistanceRecorder<DistanceMap> record_actor_distances(DistanceMap d)
{
- return BaconNumberRecorder<BaconMap>(b);
+ return ActorDistanceRecorder<DistanceMap>(d);
}
int
@@ -69,26 +69,25 @@
// get the bacon number map associated with the graph
ActorIndexMap indices = get(&Actor::index, g);
- ActorNameMap names = get(&Actor::name, g);
- ActorBaconMap bacons = get(&Actor::bacon_number, g);
+ ActorDistanceMap dists = get(&Actor::distance, g);
// pick a starting vertex (kevin bacon, obviously) and set his
// number to 0.
Vertex kevin = actors["Kevin Bacon"];
- bacons[kevin] = 0;
+ dists[kevin] = 0;
// run a breadth-first search on the graph and record
// the kevin bacon numbers for each actor
breadth_first_search(g, kevin,
// named parameters
vertex_index_map(indices)
- .visitor(record_bacon_numbers(bacons))
+ .visitor(record_actor_distances(dists))
);
// just run over the vertices and print the back numbers
Graph::vertex_iterator i, j;
for(tie(i, j) = vertices(g); i != j; ++i) {
- cout << g[*i].bacon_number << " : " << g[*i].name << "\n";
+ cout << g[*i].distance << " : " << g[*i].name << "\n";
}
return 0;
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/movies/movies
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/movies/movies (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/movies/movies 2007-06-11 12:57:47 EDT (Mon, 11 Jun 2007)
@@ -61,7 +61,7 @@
Lori Singer;Carrie Fisher;The Man With One Red Shoe (1985)
Lori Singer;James Belushi;The Man With One Red Shoe (1985)
Lori Singer;David Ogden Stiers;The Man With One Red Shoe (1985)
-Carrie Fisher;Mark Himill;Star Wars (1977)
+Carrie Fisher;Mark Hamill;Star Wars (1977)
Carrie Fisher;Alec Guinness;Star Wars (1977)
Carrie Fisher;Harrison Ford;Star Wars (1977)
Carrie Fisher;Dan Akroyd;The Blues Brothers (1980)
@@ -74,4 +74,4 @@
John Lithgow;Mike Meyers;Shrek (2001)
John Lithgow;Sylvester Stallone;Cliffhanger (2001)
Eddie Murphy;John Lithgow;Shrek (2001)
-Tim Matheson;Kevin Bacon;Animal House (1978)
\ No newline at end of file
+Tim Matheson;Kevin Bacon;Animal House (1978)
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/movies/movies.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/movies/movies.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/movies/movies.cpp 2007-06-11 12:57:47 EDT (Mon, 11 Jun 2007)
@@ -45,14 +45,14 @@
}
static Edge
-add_performance(Graph &g, Vertex u, Vertex v, string const& movie)
+add_movie(Graph &g, Vertex u, Vertex v, string const& movie)
{
Edge e;
bool inserted;
tie(e, inserted) = add_edge(u, v, g);
if(inserted) {
g[e].weight = 1;
- g[e].movie = movie;
+ g[e].name = movie;
}
return e;
}
@@ -72,7 +72,7 @@
tokenizer<> tok(line, sep);
tokenizer<>::iterator i = tok.begin();
- // grab the first actor
+ // grab the actor names and the movie title
string first = *i++;
string second = *i++;
string movie = *i++;
@@ -83,8 +83,8 @@
u = add_actor(g, actors, first),
v = add_actor(g, actors, second);
- // create an edge (performance) linking the actors
- add_performance(g, u, v, movie);
+ // create an edge (movie) linking the actors
+ add_movie(g, u, v, movie);
}
}
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/movies/movies.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/movies/movies.hpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/movies/movies.hpp 2007-06-11 12:57:47 EDT (Mon, 11 Jun 2007)
@@ -16,11 +16,11 @@
#include <boost/graph/undirected_graph.hpp>
struct Actor;
-struct Performance;
+struct Movie;
// The Graph data structure is an undirected graph with vertices
// being represented by actors and edges, their co-performances.
-typedef boost::undirected_graph<Actor, Performance> Graph;
+typedef boost::undirected_graph<Actor, Movie> Graph;
typedef Graph::vertex_descriptor Vertex;
typedef Graph::edge_descriptor Edge;
@@ -32,35 +32,32 @@
int index;
int distance;
Vertex parent;
-
std::string name;
- unsigned bacon_number;
};
-// The Performance struct describes information about the performance
+// The Movie struct describes information about the performance
// of two actors - specifically, what movie and year they performed
// together in.
//
// Note that the edge property type contains a weight. While a performance
// wouldn't typically be weighted (it doesn't mean anything), we need a
// weight map to work with some algorithms.
-struct Performance
+struct Movie
{
unsigned weight;
- std::string movie;
+ std::string name;
};
-// These property maps index information in the Actor and Performance
+// These property maps index information in the Actor and Movie
// structures, respectively. They are used to access specific pieces
// of information inside the graph.
typedef boost::property_map<Graph::type, int Actor::*>::type ActorIndexMap;
typedef boost::property_map<Graph::type, int Actor::*>::type ActorDistanceMap;
typedef boost::property_map<Graph::type, Vertex Actor::*>::type ActorParentMap;
typedef boost::property_map<Graph::type, std::string Actor::*>::type ActorNameMap;
-typedef boost::property_map<Graph::type, unsigned Actor::*>::type ActorBaconMap;
-typedef boost::property_map<Graph::type, unsigned Performance::*>::type MovieWeightMap;
-typedef boost::property_map<Graph::type, std::string Performance::*>::type MovieNameMap;
+typedef boost::property_map<Graph::type, unsigned Movie::*>::type MovieWeightMap;
+typedef boost::property_map<Graph::type, std::string Movie::*>::type MovieNameMap;
// we use an extra map to help dynamically populate the graph.
// this maps actor names to the vertices that they're inserted as
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/movies/six_degrees.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/movies/six_degrees.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/movies/six_degrees.cpp 2007-06-11 12:57:47 EDT (Mon, 11 Jun 2007)
@@ -18,6 +18,40 @@
using namespace std;
using namespace boost;
+template <typename ParentMap>
+struct ActorParentRecorder : public bfs_visitor<>
+{
+ ActorParentRecorder(ParentMap d)
+ : parents(d)
+ {}
+
+ // record the parent
+ template <typename Edge, typename Graph>
+ void tree_edge(Edge e, const Graph& g) const
+ {
+ typedef typename Graph::vertex_descriptor Vertex;
+
+ Vertex
+ u = source(e, g),
+ v = target(e, g);
+
+ // the parent of v is u
+ parents[v] = u;
+ }
+
+ ParentMap parents;
+};
+
+// This is just a convenience function so we can call a function rather than
+// explicitly instantiate the visitor type. It makes it more "action-oriented".
+template <typename ParentMap>
+ActorParentRecorder<ParentMap> record_actor_parents(ParentMap d)
+{
+ return ActorParentRecorder<ParentMap>(d);
+}
+
+
+
int
main(int argc, char *argv[])
{
@@ -62,30 +96,16 @@
// the indices after a sequence of removals.
ActorIndexMap indices = get(&Actor::index, g);
- // The distance map records the shortest distance from the source to
- // the the vertex represented at that index.
- ActorDistanceMap distances = get(&Actor::distance, g);
-
// The predeceessor map records, for the vertex at each index, the
// predecessor (or parent) in the shortest-path tree. By iterating
// from predecessor to predecessor, we can find the shortest path
ActorParentMap parents = get(&Actor::parent, g);
- // The weight map records the weight of each edge. Since the movie
- // graph is naturally unweighted (and has no weight property for the
- // edges), we are "faking" it by creating it as an external property
- // with all weights initially set to 1.
- MovieWeightMap weights = get(&Performance::weight, g);
-
- dijkstra_shortest_paths(g, u,
- // named parameters
- vertex_index_map(indices)
- .weight_map(weights)
- .distance_map(distances)
- .predecessor_map(parents)
+ breadth_first_search(g, u,
+ vertex_index_map(indices)
+ .visitor(record_actor_parents(parents))
);
-
// print the movies in which the actors appear by iterating over
// the elements in the predecessor map
while(v != u) {
@@ -109,7 +129,7 @@
}
// what's the movie name?
- string movie = g[e].movie;
+ string movie = g[e].name;
// print out the path
cout << from << " starred with " << to << " in '" << movie << "'\n";