[Boost-commit] svn:boost r4526

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";