From: asutton_at_[hidden]
Date: 2007-05-18 11:39:15
Author: asutton
Date: 2007-05-18 11:39:15 EDT (Fri, 18 May 2007)
New Revision: 4119
URL: http://svn.boost.org/trac/boost/changeset/4119
Log:
separating examples
Added:
sandbox/SOC/2007/graphs/libs/graph/examples/directed_files/Jamfile.v2
sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/Jamfile.v2
- copied unchanged from r4118, /sandbox/SOC/2007/graphs/libs/graph/examples/Jamfile.v2
sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/kevin_bacon.cpp
- copied unchanged from r4118, /sandbox/SOC/2007/graphs/libs/graph/examples/kevin_bacon.cpp
sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/movies
- copied unchanged from r4118, /sandbox/SOC/2007/graphs/libs/graph/examples/movies
sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/movies.cpp
- copied unchanged from r4118, /sandbox/SOC/2007/graphs/libs/graph/examples/movies.cpp
sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/movies.hpp
- copied unchanged from r4118, /sandbox/SOC/2007/graphs/libs/graph/examples/movies.hpp
sandbox/SOC/2007/graphs/libs/graph/examples/undirected_movies/six_degrees.cpp
- copied unchanged from r4118, /sandbox/SOC/2007/graphs/libs/graph/examples/six_degrees.cpp
Removed:
sandbox/SOC/2007/graphs/libs/graph/examples/Jamfile.v2
sandbox/SOC/2007/graphs/libs/graph/examples/kevin_bacon.cpp
sandbox/SOC/2007/graphs/libs/graph/examples/movies
sandbox/SOC/2007/graphs/libs/graph/examples/movies.cpp
sandbox/SOC/2007/graphs/libs/graph/examples/movies.hpp
sandbox/SOC/2007/graphs/libs/graph/examples/six_degrees.cpp
Deleted: sandbox/SOC/2007/graphs/libs/graph/examples/Jamfile.v2
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/Jamfile.v2 2007-05-18 11:39:15 EDT (Fri, 18 May 2007)
+++ (empty file)
@@ -1,15 +0,0 @@
-
-exe kevin_bacon
- : kevin_bacon.cpp movies.cpp
- : <include>../../../
- ;
-
-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/Jamfile.v2
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/directed_files/Jamfile.v2 2007-05-18 11:39:15 EDT (Fri, 18 May 2007)
@@ -0,0 +1,15 @@
+
+exe kevin_bacon
+ : kevin_bacon.cpp movies.cpp
+ : <include>../../../
+ ;
+
+exe six_degrees
+ : six_degrees.cpp movies.cpp
+ : <include>../../../
+ ;
+
+exe build_order
+ : build_order.cpp
+ : <include>../../../
+ ;
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/examples/kevin_bacon.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/kevin_bacon.cpp 2007-05-18 11:39:15 EDT (Fri, 18 May 2007)
+++ (empty file)
@@ -1,95 +0,0 @@
-// (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>
-
-// boost includes
-#include <boost/graph/visitors.hpp>
-#include <boost/graph/breadth_first_search.hpp>
-
-// example includes
-#include "movies.hpp"
-
-using namespace std;
-using namespace boost;
-
-// This visitor is responsible for recording (setting) the bacon numbers
-// of actors in the movie graph.
-template <typename BaconMap>
-struct BaconNumberRecorder : public bfs_visitor<>
-{
- BaconNumberRecorder(BaconMap b)
- : bacons(b)
- {}
-
- // The tree_edge() method is invoked when a vertex v is discovered
- // while exploring an edge (u,v). With respect to a BFS, this means
- // that v is in the next higher level (or depth) than u. Therefore,
- // the Kevin Bacon number of v should be one more than that of u.
- template <typename Edge, typename Graph>
- void tree_edge(Edge e, const Graph& g) const
- {
- typedef typename Graph::vertex_descriptor Vertex;
-
- // get the source and target vertices of this tree edge.
- Vertex
- u = source(e, g),
- v = target(e, g);
-
- // set the bacon number to 1 + u's bacon number
- bacons[v] = bacons[u] + 1;
- }
-
- BaconMap bacons;
-};
-
-// 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)
-{
- return BaconNumberRecorder<BaconMap>(b);
-}
-
-int
-main(int argc, char *argv[])
-{
- // instantiate the graph
- Graph g;
-
- // instantiate the graph-construction helping map
- ActorMap actors;
-
- // read the graph from stdin
- 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"];
- bacons[kevin] = 0;
-
- // 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)));
-
- // 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";
- }
-
- return 0;
-}
-
Deleted: sandbox/SOC/2007/graphs/libs/graph/examples/movies
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/movies 2007-05-18 11:39:15 EDT (Fri, 18 May 2007)
+++ (empty file)
@@ -1,77 +0,0 @@
-# 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;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)
-Sean Astin;Kevin Bacon;White Water Summer (1987)
-Theodore Hesburgh;Gerry Becker;Rudy (1993)
-Gerry Becker;Kevin Bacon;Sleepers (1996)
-Henry Fonda;Robert Wagner;Midway (1976)
-Robert Wagner;Kevin Bacon;Wild Things (1998)
-Mark Hamill;Bill Paxton;Slipstream (1989)
-Bill Paxton;Kevin Bacon;Apollo 13 (1995)
-Harrison Ford;Steve Altes;Random Hearts (1999)
-Steve Altes;Kevin Bacon;Hollow Man (2000)
-Alec Guinness;Theresa Russell;Kafka (1991)
-Theresa Russell;Kevin Bacon;Wild Things (1998)
-Carrie Fisher;Elisabeth Shue;Soapdish (1991)
-Elisabeth Shue;Kevin Bacon;Hollow Man (2000)
-Sean Connery;Peter Crombie;Rising Sun (1993)
-Peter Crombie;Kevin Bacon;My Dog Skip (2000)
-Dana Young;Bebe Drake;Bersaglio mobile (1967)
-Bebe Drake;William Devane;Report to the Commissioner (1975)
-A. Paliakov;Nikolai Brilling;Kutuzov (1944)
-Nikolai Brilling;Kathleen Byron;Otello (1955)
-Kathleen Byron;Tom Hanks;Saving Private Ryan (1998)
-Tom Hanks;Kevin Bacon;Apollo 13 (1995)
-Zoya Barantsevich;Nikolai Panov;Slesar i kantzler (1923)
-Nikolai Panov;Zoia Karabanova;Zhenshchina s kinzhalom (1916)
-Zoia Karabanova;William Challee;Song to Remember, A (1945)
-William Challee;William Devane;Irish Whiskey Rebellion (1972)
-William Devane;Kevin Bacon;Hollow Man (2000)
-P. Biryukov;Aleksandr Gromov;Pikovaya dama (1910)
-Aleksandr Gromov;Yelena Maksimova;Tikhij Don (1930)
-Yelena Maksimova;Lev Prygunov;Bezottsovshchina (1976)
-Lev Prygunov;Elisabeth Shue;Saint, The (1997)
-Yelena Chaika;Viktor Tourjansky;Ostrov zabenya (1917)
-Viktor Tourjansky;Olga Baclanova;Zagrobnaya skitalitsa (1915)
-Olga Baclanova;Angelo Rossitto;Freaks (1932)
-Angelo Rossitto;William Devane;The Dark (1979)
-Christel Holch;Aage Schmidt;Hvide Slavehandel, Den (1910)
-Aage Schmidt;Valso Holm;Begyndte ombord, Det (1937)
-Valso Holm;Max von Sydow;Spion 503 (1958)
-Max von Sydow;Diane Lane;Judge Dredd (1995)
-Diane Lane;Kevin Bacon;My Dog Skip (2000)
-Val Kilmer;Elisabeth Shue;Saint, The (1997)
-Marilyn Monroe;George Ives;Niagara (1953)
-George Ives;Kevin Bacon;Stir of Echoes (1999)
-Jacques Perrin;Vittorio Gassman;Deserto dei tartari, Il (1976)
-Vittorio Gassman;Kevin Bacon;Sleepers (1996)
-Kevin Bacon;Lori Singer;Footloose (1984)
-Kevin Bacon;John Lithgow;Footloose (1984)
-Kevin Bacon;Dianne Wiest;Footloose (1984)
-Kevin Bacon;Chris Penn;Footloose (1984)
-Kevin Bacon;Sarah Jessica Parker;Footloose (1984)
-Lori Singer;Tom Hanks;The Man With One Red Shoe (1985)
-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;Alec Guinness;Star Wars (1977)
-Carrie Fisher;Harrison Ford;Star Wars (1977)
-Carrie Fisher;Dan Akroyd;The Blues Brothers (1980)
-Carrie Fisher;John Belushi;The Blues Brothers (1980)
-John Belushi;Kevin Bacon;Animal House (1978)
-John Belushi;Tim Matheson;Animal House (1978)
-John Belushi;Tom Hulce;Animal House (1978)
-John Belushi;Peter Riegert;Animal House (1978)
-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)
-Tim Matheson;Kevin Bacon;Animal House (1978)
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/examples/movies.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/movies.cpp 2007-05-18 11:39:15 EDT (Fri, 18 May 2007)
+++ (empty file)
@@ -1,112 +0,0 @@
-// (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>
-
-// boost includes
-#include <boost/tokenizer.hpp>
-
-// example includes
-#include "movies.hpp"
-
-using namespace std;
-using namespace boost;
-
-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;
- bool inserted;
- tie(it, inserted) = actors.insert(make_pair(name, Vertex()));
- if(inserted) {
- // if the name was actually inserted, then add a new vertex
- // to the graph, configure the entry in the map, and set
- // the actors name
- v = add_vertex(g);
- it->second = v;
- names[v] = name;
- }
- else {
- // otherwise, the name is already in the map, so just
- // return the iterator associated with it
- v = it->second;
- }
-
- return v;
-}
-
-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;
- }
- return e;
-}
-
-void
-build_movie_graph(istream& is, Graph& g, ActorMap& actors)
-{
- // 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();
-
- // grab the first actor
- string first = *i++;
- string second = *i++;
- string movie = *i++;
-
- // get the vertices associated with the actors (adding them
- // to the graph if necessary).
- Vertex
- 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);
- }
-}
-
-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)
-{
- Vertex v = Graph::null_vertex();
- ActorMap::const_iterator i = actors.find(name);
- if(i != actors.end()) {
- v = i->second;
- }
- return v;
-}
Deleted: sandbox/SOC/2007/graphs/libs/graph/examples/movies.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/movies.hpp 2007-05-18 11:39:15 EDT (Fri, 18 May 2007)
+++ (empty file)
@@ -1,83 +0,0 @@
-// (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)
-
-#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;
-};
-
-// The Performance 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
-{
- Performance()
- : weight(1)
- , movie()
- {}
-
- Performance(const Performance& copy)
- : weight(1)
- , movie(copy.movie)
- {}
-
- unsigned weight;
- std::string movie;
-};
-
-// 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, 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
Deleted: sandbox/SOC/2007/graphs/libs/graph/examples/six_degrees.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/six_degrees.cpp 2007-05-18 11:39:15 EDT (Fri, 18 May 2007)
+++ (empty file)
@@ -1,126 +0,0 @@
-// (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 <vector>
-#include <map>
-
-// boost includes
-#include <boost/graph/dijkstra_shortest_paths.hpp>
-
-// example includes
-#include "movies.hpp"
-
-using namespace std;
-using namespace boost;
-
-int
-main(int argc, char *argv[])
-{
- string src = "Kevin Bacon";
- string tgt;
-
- // get the source and target nodes from the graph
- if(argc < 2) {
- cerr << "usage: actor_paths actor [actor] < movies";
- return -1;
- }
- else if(argc == 2) {
- tgt = argv[1];
- }
- else {
- src = argv[1];
- tgt = argv[2];
- }
-
- // instantiate the graph and the actor map
- Graph g;
- ActorMap actors;
-
- // read the graph from stdin
- build_movie_graph(cin, g, actors);
-
- // get the source and target vertices
- Vertex u = find_actor_vertex(g, actors, src);
- Vertex v = find_actor_vertex(g, actors, tgt);
- if(u == Graph::null_vertex()) {
- cerr << "could not find actor " << src << "\n";
- return -1;
- }
- if(v == Graph::null_vertex()) {
- cerr << "could not find actor " << tgt << "\n";
- 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.
- 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.
- 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)
- );
-
-
- // 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];
-
- // what edge does (v,p) exist on. unforunately, because this isn't
- // an adjacency matrix, we actually have to search the outgoing (or
- // incoming?) edges of v to find p, and get the edge associated with
- // that performance.
- Edge e;
- Graph::out_edge_iterator i, j;
- for(tie(i, j) = out_edges(v, g); i != j; ++i) {
- if(target(*i, g) == p) {
- e = *i;
- break;
- }
- }
-
- // what's the movie name?
- string movie = movies[e];
-
- // print out the path
- cout << from << " starred with " << to << " in '" << movie << "'\n";
-
- // move to the next predecessor
- v = p;
- }
-
- return 0;
-}