|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-05-18 11:37:57
Author: asutton
Date: 2007-05-18 11:37:56 EDT (Fri, 18 May 2007)
New Revision: 4118
URL: http://svn.boost.org/trac/boost/changeset/4118
Log:
separating examples
Added:
sandbox/SOC/2007/graphs/libs/graph/examples/directed_files/
sandbox/SOC/2007/graphs/libs/graph/examples/directed_files/build_order.cpp
sandbox/SOC/2007/graphs/libs/graph/examples/directed_files/files
sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/examples/Jamfile.v2 | 5 ++++
sandbox/SOC/2007/graphs/libs/graph/examples/kevin_bacon.cpp | 11 ++++++++-
sandbox/SOC/2007/graphs/libs/graph/examples/movies | 9 ++++++-
sandbox/SOC/2007/graphs/libs/graph/examples/movies.cpp | 23 +++++++++++++++++++-
sandbox/SOC/2007/graphs/libs/graph/examples/movies.hpp | 29 ++++++++++++++++++++------
sandbox/SOC/2007/graphs/libs/graph/examples/six_degrees.cpp | 43 +++++++++++++++++++++++----------------
6 files changed, 89 insertions(+), 31 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-05-18 11:37:56 EDT (Fri, 18 May 2007)
@@ -7,4 +7,9 @@
exe six_degrees
: six_degrees.cpp movies.cpp
: <include>../../../
+ ;
+
+exe build_order
+ : build_order.cpp
+ : <include>../../../
;
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/examples/directed_files/build_order.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/directed_files/build_order.cpp 2007-05-18 11:37:56 EDT (Fri, 18 May 2007)
@@ -0,0 +1,135 @@
+// (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)
+
+// std includes
+#include <iostream>
+#include <string>
+#include <map>
+
+// boost includes
+#include <boost/tokenizer.hpp>
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/topological_sort.hpp>
+
+using namespace std;
+using namespace boost;
+
+struct Target
+{
+ int index;
+ string name;
+};
+
+typedef directed_graph<Target> Graph;
+typedef Graph::vertex_descriptor Vertex;
+typedef Graph::edge_descriptor Edge;
+typedef property_map<Graph::type, int Target::*>::type TargetIndexMap;
+typedef property_map<Graph::type, string Target::*>::type TargetNameMap;
+
+typedef map<string, Vertex> TargetMap;
+
+Vertex
+add_target(Graph& g, TargetMap& targets, const string& name)
+{
+ // try inserting the actors name into the actors map
+ Vertex v;
+ TargetMap::iterator it;
+ bool inserted;
+ tie(it, inserted) = targets.insert(make_pair(name, Vertex()));
+ if(inserted) {
+ // create a vertex for the name
+ v = add_vertex(g);
+
+ // associate the vertex with the name
+ it->second = v;
+
+ // configure the vertex properties
+ g[v].index = num_vertices(g) - 1;
+ g[v].name = name;
+ }
+ else {
+ // otherwise, the name is already in the map, so just
+ // return the iterator associated with it
+ v = it->second;
+ }
+
+ return v;
+}
+
+// Look very carefully at the add_edge() call in this function and
+// you'll notice that it switches the ordering of the vertices in
+// the edge that's being created. Unfortunately, the problem requires
+// that we model the direction of edges as "used-by", although our
+// input format is more of a "dependency" listing. This isn't really
+// a problem as long as we recognize the difference.
+Edge
+add_dependency(Graph &g, Vertex u, Vertex v)
+{
+ Edge e;
+ bool inserted;
+ tie(e, inserted) = add_edge(v, u, g);
+ return e;
+}
+
+int
+main(int argc, char* argv[])
+{
+ typedef list<Vertex> BuildOrder;
+ typedef boost::char_separator<char> separator;
+ typedef boost::tokenizer<separator> tokenizer;
+
+ Graph g;
+ TargetMap targets;
+
+ for(string line; getline(cin, line); ) {
+ // skip comment and blank lines
+ if(line[0] == '#' || line.empty()) {
+ continue;
+ }
+
+ // split the string on the dependency
+ size_t index = line.find_first_of(':');
+ if(index == string::npos) {
+ continue;
+ }
+ string target(line, 0, index);
+ string deps(line, index + 1);
+
+ // add the target to the build graph
+ Vertex u = add_target(g, targets, target);
+
+ // tokenize the dependencies
+ separator sep(" \t");
+ tokenizer tok(deps, sep);
+ tokenizer::iterator i = tok.begin(), j = tok.end();
+ for( ; i != j; ++i) {
+ string dep = *i;
+
+ // add this dependency as a target
+ Vertex v = add_target(g, targets, dep);
+
+ // add the edge
+ add_dependency(g, u, v);
+ }
+ }
+
+ // we need to create a vertex index map for the graph before
+ // we can generate the build order
+ TargetIndexMap indices = get(&Target::index, g);
+
+ // the build order is just a
+ BuildOrder order;
+ topological_sort(g, front_inserter(order),
+ // named parameters
+ vertex_index_map(indices)
+ );
+
+ // write out the build order...
+ BuildOrder::iterator i = order.begin(), j = order.end();
+ for( ; i != j; ++i) {
+ cout << g[*i].name << "\n";
+ }
+}
Added: sandbox/SOC/2007/graphs/libs/graph/examples/directed_files/files
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/directed_files/files 2007-05-18 11:37:56 EDT (Fri, 18 May 2007)
@@ -0,0 +1,22 @@
+# This basically follows make format rules. The target is
+# separated from the dependencies by a colon. Dependencies are
+# separated by whitespace. Notice: one target per line
+#
+# Example:
+# <target>: <dep1> <dep2>
+
+killerapp: libzigzag.a
+libzigzag.a: libfoobar.a zig.o zag.o
+libfoobar.a: foo.o bar.o
+foo.o: foo.cpp
+foo.cpp: zow.h dax.h
+bar.o: bar.cpp
+bar.cpp: boz.h yow.h dax.h
+yow.h: dax.h
+zig.o: zig.cpp
+zig.cpp: boz.h
+zag.o: zag.cpp
+zag.cpp: boz.h yow.h
+
+# uncomment this line to add a cycle
+# dax.h: bar.cpp
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/kevin_bacon.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/kevin_bacon.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/kevin_bacon.cpp 2007-05-18 11:37:56 EDT (Fri, 18 May 2007)
@@ -4,11 +4,14 @@
// Boost Software License, Version 1.0 (See accompanying file
// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+// std includes
#include <iostream>
+// boost includes
#include <boost/graph/visitors.hpp>
#include <boost/graph/breadth_first_search.hpp>
+// example includes
#include "movies.hpp"
using namespace std;
@@ -65,9 +68,13 @@
build_movie_graph(cin, g, actors);
// 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);
+ // 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"];
@@ -75,9 +82,9 @@
// run a breadth-first search on the graph and record
// the kevin bacon numbers for each actor
- breadth_first_search(g, kevin, visitor(record_bacons(bacons)));
+ breadth_first_search(g, kevin, vertex_index_map(indices).visitor(record_bacons(bacons)));
- // just run over the vertices and print the related info
+ // 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";
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/movies
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/movies (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/movies 2007-05-18 11:37:56 EDT (Fri, 18 May 2007)
@@ -1,6 +1,10 @@
+# Revised movie graph format...
+# <actor>;<actor>;<movie>
+# Notice no extra whitespace is allowed
+
William Shatner;Denise Richards;Loaded Weapon 1 (1993)
Denise Richards;Kevin Bacon;Wild Things (1998)
-Patrick Stewart;Steve Martin;Prince of Egypt, The (1998)
+Patrick Stewart;Steve Martin;The Prince of Egypt (1998)
Steve Martin;Kevin Bacon;Novocaine (2000)
Gerard Depardieu;Clint Howard;Unhook the Stars (1996)
Clint Howard;Kevin Bacon;My Dog Skip (2000)
@@ -69,4 +73,5 @@
John Belushi;Karen Allen;Animal House (1978)
John Lithgow;Mike Meyers;Shrek (2001)
John Lithgow;Sylvester Stallone;Cliffhanger (2001)
-Eddie Murphy;John Lithgow;Shrek (2001)
\ No newline at end of file
+Eddie Murphy;John Lithgow;Shrek (2001)
+Tim Matheson;Kevin Bacon;Animal House (1978)
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/movies.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/movies.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/movies.cpp 2007-05-18 11:37:56 EDT (Fri, 18 May 2007)
@@ -4,10 +4,13 @@
// Boost Software License, Version 1.0 (See accompanying file
// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+// std includes
#include <iostream>
+// boost includes
#include <boost/tokenizer.hpp>
+// example includes
#include "movies.hpp"
using namespace std;
@@ -17,7 +20,7 @@
add_actor(Graph &g, ActorMap &actors, string &name)
{
// get the actor name map associated with the graph
- ActorNameMap actor_names = get(&Actor::name, g);
+ ActorNameMap names = get(&Actor::name, g);
// try inserting the actors name into the actors map
Vertex v;
@@ -30,7 +33,7 @@
// the actors name
v = add_vertex(g);
it->second = v;
- actor_names[v] = name;
+ names[v] = name;
}
else {
// otherwise, the name is already in the map, so just
@@ -61,6 +64,12 @@
{
// pull all of the data from std in.
for(string line; getline(is, line); ) {
+ // skip any comment or blank lines
+ if(line[0] == '#' || line.empty()) {
+ continue;
+ }
+
+ // tokenize the string
char_delimiters_separator<char> sep(false, "", ";");
tokenizer<> tok(line, sep);
tokenizer<>::iterator i = tok.begin();
@@ -81,6 +90,16 @@
}
}
+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/movies.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/movies.hpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/movies.hpp 2007-05-18 11:37:56 EDT (Fri, 18 May 2007)
@@ -7,16 +7,32 @@
#ifndef MOVIES_HPP
#define MOVIES_HPP
+// std includes
#include <iosfwd>
#include <string>
#include <map>
+// boost includes
#include <boost/graph/undirected_graph.hpp>
+struct Actor;
+struct Performance;
+
+// 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 Graph::vertex_descriptor Vertex;
+typedef Graph::edge_descriptor Edge;
+
+
// The Actor struct contains properties about the actors in the
// movie graph.
struct Actor
{
+ int index;
+ int distance;
+ Vertex parent;
+
std::string name;
unsigned bacon_number;
};
@@ -44,25 +60,24 @@
std::string 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 Graph::vertex_descriptor Vertex;
-typedef Graph::edge_descriptor Edge;
-
// These property maps index information in the Actor and Performance
// 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, std::string Performance::*>::type MovieNameMap;
+
typedef boost::property_map<Graph::type, unsigned Performance::*>::type MovieWeightMap;
+typedef boost::property_map<Graph::type, std::string Performance::*>::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
typedef std::map<std::string, Vertex> ActorMap;
void build_movie_graph(std::istream &, Graph&, ActorMap&);
+void build_vertex_index_map(Graph&, ActorIndexMap &);
Vertex find_actor_vertex(const Graph&, const ActorMap&, const std::string&);
#endif
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/six_degrees.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/six_degrees.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/six_degrees.cpp 2007-05-18 11:37:56 EDT (Fri, 18 May 2007)
@@ -4,12 +4,15 @@
// Boost Software License, Version 1.0 (See accompanying file
// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+// std includes
#include <iostream>
#include <vector>
#include <map>
+// boost includes
#include <boost/graph/dijkstra_shortest_paths.hpp>
+// example includes
#include "movies.hpp"
using namespace std;
@@ -53,30 +56,34 @@
return -1;
}
- // keep the number of vertices for later...
- size_t n = num_vertices(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);
+ // The index map needs to be initialized before the shortest
+ // path algorithm - it's used to help index parent vertices among
+ // other things.
+ 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.
- typedef vector<int> DistanceMap;
- DistanceMap distances(n);
+ 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
- typedef vector<Vertex> PredecessorMap;
- PredecessorMap predecessors(n);
+ 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,
- weight_map(weights).
- distance_map(&distances[0]).
- predecessor_map(&predecessors[0]));
+ dijkstra_shortest_paths(g, u,
+ // named parameters
+ vertex_index_map(indices)
+ .weight_map(weights)
+ .distance_map(distances)
+ .predecessor_map(parents)
+ );
// we're going to need the actor and movie names for this...
@@ -86,7 +93,7 @@
// print the movies in which the actors appear by iterating over
// the elements in the predecessor map
while(v != u) {
- Vertex p = predecessors[v];
+ Vertex p = parents[v];
// what are our two names...
string from = names[v];
@@ -109,7 +116,7 @@
string movie = movies[e];
// print out the path
- cout << from << " with " << to << " in '" << movie << "'\n";
+ cout << from << " starred with " << to << " in '" << movie << "'\n";
// move to the next predecessor
v = p;
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk