From: asutton_at_[hidden]
Date: 2007-05-18 11:48:11
Author: asutton
Date: 2007-05-18 11:48:10 EDT (Fri, 18 May 2007)
New Revision: 4120
URL: http://svn.boost.org/trac/boost/changeset/4120
Log:
fixing example build
rehashed some of the code to use the bundled property accessors ([]) on the
graph class instead of property maps.
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/Jamfile.v2 | 9 ++-------
sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/kevin_bacon.cpp | 13 +++++++------
sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/movies.cpp | 24 ++++++------------------
sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/movies.hpp | 10 ----------
sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/six_degrees.cpp | 18 +++++++-----------
5 files changed, 22 insertions(+), 52 deletions(-)
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/Jamfile.v2
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/Jamfile.v2 (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/Jamfile.v2 2007-05-18 11:48:10 EDT (Fri, 18 May 2007)
@@ -1,15 +1,10 @@
exe kevin_bacon
: kevin_bacon.cpp movies.cpp
- : <include>../../../
+ : <include>../../../../
;
exe six_degrees
: six_degrees.cpp movies.cpp
- : <include>../../../
+ : <include>../../../../
;
-
-exe build_order
- : build_order.cpp
- : <include>../../../
- ;
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/kevin_bacon.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/kevin_bacon.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/kevin_bacon.cpp 2007-05-18 11:48:10 EDT (Fri, 18 May 2007)
@@ -50,7 +50,7 @@
// 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_bacons(BaconMap b)
+BaconNumberRecorder<BaconMap> record_bacon_numbers(BaconMap b)
{
return BaconNumberRecorder<BaconMap>(b);
}
@@ -72,9 +72,6 @@
ActorNameMap names = get(&Actor::name, g);
ActorBaconMap bacons = get(&Actor::bacon_number, g);
- // actually populate the index map
- build_vertex_index_map(g, indices);
-
// pick a starting vertex (kevin bacon, obviously) and set his
// number to 0.
Vertex kevin = actors["Kevin Bacon"];
@@ -82,12 +79,16 @@
// run a breadth-first search on the graph and record
// the kevin bacon numbers for each actor
- breadth_first_search(g, kevin, vertex_index_map(indices).visitor(record_bacons(bacons)));
+ breadth_first_search(g, kevin,
+ // named parameters
+ vertex_index_map(indices)
+ .visitor(record_bacon_numbers(bacons))
+ );
// 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 << bacons[*i] << " : " << names[*i] << "\n";
+ cout << g[*i].bacon_number << " : " << g[*i].name << "\n";
}
return 0;
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/movies.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/movies.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/movies.cpp 2007-05-18 11:48:10 EDT (Fri, 18 May 2007)
@@ -19,9 +19,6 @@
static Vertex
add_actor(Graph &g, ActorMap &actors, string &name)
{
- // get the actor name map associated with the graph
- ActorNameMap names = get(&Actor::name, g);
-
// try inserting the actors name into the actors map
Vertex v;
ActorMap::iterator it;
@@ -33,7 +30,10 @@
// the actors name
v = add_vertex(g);
it->second = v;
- names[v] = name;
+
+ // configure the vertex
+ g[v].index = num_vertices(g) - 1;
+ g[v].name = name;
}
else {
// otherwise, the name is already in the map, so just
@@ -47,14 +47,12 @@
static Edge
add_performance(Graph &g, Vertex u, Vertex v, string const& movie)
{
- // get the movie name map associated with the graph
- MovieNameMap movie_names = get(&Performance::movie, g);
-
Edge e;
bool inserted;
tie(e, inserted) = add_edge(u, v, g);
if(inserted) {
- movie_names[e] = movie;
+ g[e].weight = 1;
+ g[e].movie = movie;
}
return e;
}
@@ -90,16 +88,6 @@
}
}
-void
-build_vertex_index_map(Graph &g, ActorIndexMap &indices)
-{
- int index = 0;
- Graph::vertex_iterator i, j;
- for(tie(i, j) = vertices(g); i != j; ++i) {
- indices[*i] = index++;
- }
-}
-
Vertex
find_actor_vertex(const Graph& g, const ActorMap& actors, const std::string& name)
{
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/movies.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/movies.hpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/movies.hpp 2007-05-18 11:48:10 EDT (Fri, 18 May 2007)
@@ -46,16 +46,6 @@
// weight map to work with some algorithms.
struct Performance
{
- Performance()
- : weight(1)
- , movie()
- {}
-
- Performance(const Performance& copy)
- : weight(1)
- , movie(copy.movie)
- {}
-
unsigned weight;
std::string movie;
};
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/six_degrees.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/six_degrees.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/six_degrees.cpp 2007-05-18 11:48:10 EDT (Fri, 18 May 2007)
@@ -56,11 +56,11 @@
return -1;
}
- // The index map needs to be initialized before the shortest
- // path algorithm - it's used to help index parent vertices among
- // other things.
+ // Get the index map
+ // WARNING: The current method for implementing this is highly unstable
+ // if any of the vertices are removed - basically, you'd have to reassign
+ // the indices after a sequence of removals.
ActorIndexMap indices = get(&Actor::index, g);
- build_vertex_index_map(g, indices);
// The distance map records the shortest distance from the source to
// the the vertex represented at that index.
@@ -86,18 +86,14 @@
);
- // we're going to need the actor and movie names for this...
- ActorNameMap names = get(&Actor::name, g);
- MovieNameMap movies = get(&Performance::movie, g);
-
// print the movies in which the actors appear by iterating over
// the elements in the predecessor map
while(v != u) {
Vertex p = parents[v];
// what are our two names...
- string from = names[v];
- string to = names[p];
+ string from = g[v].name;
+ string to = g[p].name;
// what edge does (v,p) exist on. unforunately, because this isn't
// an adjacency matrix, we actually have to search the outgoing (or
@@ -113,7 +109,7 @@
}
// what's the movie name?
- string movie = movies[e];
+ string movie = g[e].movie;
// print out the path
cout << from << " starred with " << to << " in '" << movie << "'\n";