boost_1_45_0/libs/graph/doc/kevin_bacon.html - nest-learning-thermostat/5.0/boost - Git at Google

 <HTML>
 <!--
      Copyright (c) Jeremy Siek 2000

      Distributed under the Boost Software License, Version 1.0.
      (See accompanying file LICENSE_1_0.txt or copy at
      http://www.boost.org/LICENSE_1_0.txt)
   -->
 <Head>
 <Title>Kevin Bacon Example</Title>
 <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
         ALINK="#ff0000">
 <IMG SRC="../../../boost.png"
      ALT="C++ Boost" width="277" height="86">

 <BR Clear>

 <H1>Six Degrees of Kevin Bacon</H1>

 <P>
 A fun application of graph theory comes up in the popular game ``Six
 Degrees of Kevin Bacon''. The idea of the game is to connect an actor
 to Kevin Bacon through a trail of actors who appeared together in
 movies, and do so in less than six steps. For example, Theodore
 Hesburgh (President Emeritus of the University of Notre Dame) was in
 the movie ``Rudy'' with the actor Gerry Becker, who was in the movie
 ``Sleepers'' with Kevin Bacon. Why Kevin Bacon? For some reason the
 three students who invented the game, Mike Ginelli, Craig Fass, and
 Brian Turtle decided that Kevin Bacon is the center of the
 entertainment world. The Kevin Bacon game is quite similar to the <a
 href="http://www.oakland.edu/~grossman/erdoshp.html">Erd&ouml;s
 Number</a> which has ``been a part of the folklore of
 mathematicians throughout the world for many years''.

 <P>
 The ``Six Degrees of Kevin Bacon'' game is really a graph problem.  If
 you assign each actor to a vertex, and add an edge between two actors
 if they have appeared together in a movie, then you have a graph that
 represents the data for this game. Then the problem of finding a trail
 of actors to Kevin Bacon becomes a traditional graph problem: that of
 finding a <I>path</I> between two vertices. Since we wish to find a
 path that is shorter than six steps, ideally we would find the
 <I>shortest path</I> between the vertices. One might think to apply
 Dijkstra's shortest path algorithm to this problem, but that would be
 overkill since Dijkstra's algorithm is meant for situations when each
 edge has an associated length (or weight) and the goal is to find the
 path with the shortest cumulative length. Since we are only concerned
 with finding the shortest paths in terms of the number of edges the
 breadth-first search algorithm will solve the problem (and use less
 time than Dijkstra's).

 <P>

 <H2>Input File and Graph Setup</H2>

 <P>
 For this example we will use a much smaller graph than all movies and
 all actors. The full source code for this example is in <a
 href="../example/kevin-bacon.cpp"><TT>examples/kevin-bacon.cpp</TT></a>.
 We have supplied a file <TT>kevin-bacon.dat</TT> which contains a list
 of actor pairs who appeared in the same movie. Each line of the file
 contains an actor's name, a movie, and another actor that appeared in
 the movie. The ``;'' character is used as a separator. Here is an
 excerpt.

 <P>
 <PRE>
 Patrick Stewart;Prince of Egypt, The (1998);Steve Martin
 </PRE>

 <P>
 Our first task will be to read in the file and create a graph from
 it. We use a <TT>std::ifstream</TT> to input the file.

 <P>
 <PRE>
   std::ifstream datafile("./kevin-bacon.dat");
   if (!datafile) {
     std::cerr &lt;&lt; "No ./kevin-bacon.dat file" &lt;&lt; std::endl;
     return EXIT_FAILURE;
   }
 </PRE>

 <P>
 We will want to attach the actor's names to the vertices in the graph,
 and the movie names to the edges. We use the <TT>property</TT> class to
 specify the addition of these vertex and edge properties to the graph.
 We choose to use an undirected graph, because the relationship of
 actors appearing together in a movie is symmetric.

 <P>
 <PRE>
   using namespace boost;
   typedef adjacency_list&lt;vecS, vecS, undirectedS,
     property&lt;vertex_name_t, string&gt;,
     property&lt;edge_name_t, string &gt; &gt;
   &gt; Graph;
 </PRE>

 <P>
 To access the properties, we will need to obtain property map
 objects from the graph. The following code shows how this is done.

 <P>
 <PRE>
   property_map&lt;Graph, vertex_name_t&gt;::type actor_name = get(vertex_name, g);
   property_map&lt;Graph, edge_name_t&gt;::type connecting_movie = get(edge_name, g);
 </PRE>

 <P>
 Next we can start to loop through the file, parsing each line into a
 sequence of tokens using the <a href="../../tokenizer/index.html">Boost
 Tokenizer Library</a>.

 <P>
 <PRE>
   for (std::string line; std::getline(datafile, line);) {
     char_delimiters_separator&lt;char&gt; sep(false, "", ";");
     tokenizer&lt;&gt; line_toks(line, sep);
     ...
   }
 </PRE>

 <P>
 Each line of the input corresponds to an edge in the graph, with the
 two actors as the vertices incident to the edge, and the movie name
 will be a property attached to the edge. One challenge in creating the
 graph from this format of input is that the edges are specified by a
 pair of actor names. As we add vertices to the graph, we'll need to
 create a map from actor names to their vertices so that later
 appearances of the same actor (on a different edge) can be linked with
 the correct vertex in the graph. The <a
 href="http://www.sgi.com/tech/stl/Map.html"><TT>std::map</TT></a>
 can be used to implement this mapping.

 <P>
 <PRE>
   typedef graph_traits&lt;Graph&gt;::vertex_descriptor Vertex;
   typedef std::map&lt;string, Vertex&gt; NameVertexMap;
   NameVertexMap actors;
 </PRE>

 <P>
 The first token will be an actor's name. If the actor is not already
 in our actor's map we will add a vertex to the graph, set the name
 property of the vertex, and record the vertex descriptor in the map.
 If the actor is already in the graph, we will retrieve the vertex
 descriptor from the map's <TT>pos</TT> iterator.

 <P>
 <PRE>
   NameVertexMap::iterator pos;
   bool inserted;
   Vertex u, v;

   tokenizer&lt;&gt;::iterator i = line_toks.begin();
   std::string actors_name = *i++;

   tie(pos, inserted) = actors.insert(std::make_pair(actors_name, Vertex()));
   if (inserted) {
     u = add_vertex(g);
     actor_name[u] = actors_name;
     pos-&gt;second = u;
   } else
     u = pos-&gt;second;
 </PRE>

 <P>
 The second token is the name of the movie, and the third token is the
 other actor. We use the same technique as above to insert the second
 actor into the graph.

 <P>
 <PRE>
   std::string movie_name = *i++;

   tie(pos, inserted) = actors.insert(std::make_pair(*i, Vertex()));
   if (inserted) {
     v = add_vertex(g);
     actor_name[v] = *i;
     pos-&gt;second = v;
   } else
     v = pos-&gt;second;
 </PRE>

 <P>
 The final step is to add an edge connecting the two actors, and record
 the name of the connecting movie.

 <P>
 <PRE>
   graph_traits&lt;Graph&gt;::edge_descriptor e;
   tie(e, inserted) = add_edge(u, v, g);
   if (inserted)
     connecting_movie[e] = movie_name;
 </PRE>

 <P>

 <H2>A Custom Visitor Class</H2>

 <P>
 We create a custom visitor class to record the Kevin Bacon
 numbers. The Kevin Bacon number will be the shortest distances from
 each actor to Kevin Bacon. This distance has also been referred to as
 the ``Bacon Number'' in memory of the ``Erdos Number'' used to rank
 mathematicians according to how many publications separate them from
 Paul Erdos. The shortest distance to from Kevin Bacon to each actor
 will follow the breadth-first tree. The BFS algorithm identifies edges
 that belong to the breadth-first tree and calls our visitor's
 <tt>tree_edge</tt> function. We record the distance to the target
 vertex as one plus the distance to the source vertex.


 <PRE>
   template &lt;typename DistanceMap&gt;
   class bacon_number_recorder : public default_bfs_visitor
   {
   public:
     bacon_number_recorder(DistanceMap dist) : d(dist) { }

     template &lt;typename Edge, typename Graph&gt;
     void tree_edge(Edge e, const Graph& g) const
     {
       typename graph_traits&lt;Graph&gt;::vertex_descriptor
 	u = source(e, g), v = target(e, g);
 	d[v] = d[u] + 1;
     }
   private:
       DistanceMap d;
   };
   // Convenience function
   template &lt;typename DistanceMap&gt;
   bacon_number_recorder&lt;DistanceMap&gt;
   record_bacon_number(DistanceMap d)
   {
     return bacon_number_recorder&lt;DistanceMap&gt;(d);
   }
 </PRE>

 <P>
 We will use a vector to store the bacon numbers.

 <P>
 <PRE>
   std::vector&lt;int&gt; bacon_number(num_vertices(g));
 </PRE>

 <H2>Apply the Breadth-First Search</H2>

 <P>
 The BFS algorithm requires a source vertex as input; of course this
 will be Kevin Bacon. We now call the BGL BFS algorithm, passing in the
 graph, source vertex, and the visitor.

 <P>
 <PRE>
   Vertex src = actors["Kevin Bacon"];
   bacon_number[src] = 0;

   breadth_first_search(g, src, visitor(record_bacon_number(&amp;bacon_number[0])));
 </PRE>

 <P>
 We can output the Bacon number for each actor simply by looping
 through all the vertices in the graph and use them to index into the
 <TT>bacon_number</TT> vector.

 <P>
 <PRE>
   graph_traits&lt;Graph&gt;::vertex_iterator i, end;
   for (boost::tie(i, end) = vertices(g); i != end; ++i)
     std::cout &lt;&lt; actor_name[*i] &lt;&lt; "'s bacon number is "
               &lt;&lt; bacon_number[*i] &lt;&lt; std::endl;
 </PRE>

 <P>
 Note that vertex descriptor objects can not always be used as indices
 into vectors or arrays such as <TT>bacon_number</TT>. This is valid
 with the <TT>adjacency_list</TT> class with <TT>VertexList=vecS</TT>,
 but not with other variations of <TT>adjacency_list</TT>. A more
 generic way to index based on vertices is to use the ID property
 map (<TT>vertex_index_t</TT>) in coordination with the <A
 HREF="../../property_map/doc/iterator_property_map.html"><TT>iterator_property_map</TT></a>.

 <P>
 Here are some excepts from the output of the program.
 <PRE>
 William Shatner's bacon number is 2
 Denise Richards's bacon number is 1
 Kevin Bacon's bacon number is 0
 Patrick Stewart's bacon number is 2
 Steve Martin's bacon number is 1
 ...
 </PRE>


 <br>
 <HR>
 <TABLE>
 <TR valign=top>
 <TD nowrap>Copyright &copy; 2000-2001</TD><TD>
 <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
 </TD></TR></TABLE>

 </BODY>
 </HTML>
 <!--  LocalWords:  gif Hesburgh Ginelli Fass Erd vertices cerr namespace vecS
  -->
 <!--  LocalWords:  undirectedS Tokenizer sep tokenizer toks NameVertexMap pos
  -->
 <!--  LocalWords:  bool Erdos BFS typename DistanceMap bfs const num BGL src
  -->
 <!--  LocalWords:  indices Shatner's Richards's siek htm
  -->
	<HTML>
	<!--
	Copyright (c) Jeremy Siek 2000

	Distributed under the Boost Software License, Version 1.0.
	(See accompanying file LICENSE_1_0.txt or copy at
	http://www.boost.org/LICENSE_1_0.txt)
	-->
	<Head>
	<Title>Kevin Bacon Example</Title>
	<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
	ALINK="#ff0000">
	<IMG SRC="../../../boost.png"
	ALT="C++ Boost" width="277" height="86">

	<BR Clear>

	<H1>Six Degrees of Kevin Bacon</H1>

	<P>
	A fun application of graph theory comes up in the popular game ``Six
	Degrees of Kevin Bacon''. The idea of the game is to connect an actor
	to Kevin Bacon through a trail of actors who appeared together in
	movies, and do so in less than six steps. For example, Theodore
	Hesburgh (President Emeritus of the University of Notre Dame) was in
	the movie ``Rudy'' with the actor Gerry Becker, who was in the movie
	``Sleepers'' with Kevin Bacon. Why Kevin Bacon? For some reason the
	three students who invented the game, Mike Ginelli, Craig Fass, and
	Brian Turtle decided that Kevin Bacon is the center of the
	entertainment world. The Kevin Bacon game is quite similar to the <a
	href="http://www.oakland.edu/~grossman/erdoshp.html">Erdös
	Number</a> which has ``been a part of the folklore of
	mathematicians throughout the world for many years''.

	<P>
	The ``Six Degrees of Kevin Bacon'' game is really a graph problem. If
	you assign each actor to a vertex, and add an edge between two actors
	if they have appeared together in a movie, then you have a graph that
	represents the data for this game. Then the problem of finding a trail
	of actors to Kevin Bacon becomes a traditional graph problem: that of
	finding a <I>path</I> between two vertices. Since we wish to find a
	path that is shorter than six steps, ideally we would find the
	<I>shortest path</I> between the vertices. One might think to apply
	Dijkstra's shortest path algorithm to this problem, but that would be
	overkill since Dijkstra's algorithm is meant for situations when each
	edge has an associated length (or weight) and the goal is to find the
	path with the shortest cumulative length. Since we are only concerned
	with finding the shortest paths in terms of the number of edges the
	breadth-first search algorithm will solve the problem (and use less
	time than Dijkstra's).

	<P>

	<H2>Input File and Graph Setup</H2>

	<P>
	For this example we will use a much smaller graph than all movies and
	all actors. The full source code for this example is in <a
	href="../example/kevin-bacon.cpp"><TT>examples/kevin-bacon.cpp</TT></a>.
	We have supplied a file <TT>kevin-bacon.dat</TT> which contains a list
	of actor pairs who appeared in the same movie. Each line of the file
	contains an actor's name, a movie, and another actor that appeared in
	the movie. The ``;'' character is used as a separator. Here is an
	excerpt.

	<P>
	<PRE>
	Patrick Stewart;Prince of Egypt, The (1998);Steve Martin
	</PRE>

	<P>
	Our first task will be to read in the file and create a graph from
	it. We use a <TT>std::ifstream</TT> to input the file.

	<P>
	<PRE>
	std::ifstream datafile("./kevin-bacon.dat");
	if (!datafile) {
	std::cerr << "No ./kevin-bacon.dat file" << std::endl;
	return EXIT_FAILURE;
	}
	</PRE>

	<P>
	We will want to attach the actor's names to the vertices in the graph,
	and the movie names to the edges. We use the <TT>property</TT> class to
	specify the addition of these vertex and edge properties to the graph.
	We choose to use an undirected graph, because the relationship of
	actors appearing together in a movie is symmetric.

	<P>
	<PRE>
	using namespace boost;
	typedef adjacency_list<vecS, vecS, undirectedS,
	property<vertex_name_t, string>,
	property<edge_name_t, string > >
	> Graph;
	</PRE>

	<P>
	To access the properties, we will need to obtain property map
	objects from the graph. The following code shows how this is done.

	<P>
	<PRE>
	property_map<Graph, vertex_name_t>::type actor_name = get(vertex_name, g);
	property_map<Graph, edge_name_t>::type connecting_movie = get(edge_name, g);
	</PRE>

	<P>
	Next we can start to loop through the file, parsing each line into a
	sequence of tokens using the <a href="../../tokenizer/index.html">Boost
	Tokenizer Library</a>.

	<P>
	<PRE>
	for (std::string line; std::getline(datafile, line);) {
	char_delimiters_separator<char> sep(false, "", ";");
	tokenizer<> line_toks(line, sep);
	...
	}
	</PRE>

	<P>
	Each line of the input corresponds to an edge in the graph, with the
	two actors as the vertices incident to the edge, and the movie name
	will be a property attached to the edge. One challenge in creating the
	graph from this format of input is that the edges are specified by a
	pair of actor names. As we add vertices to the graph, we'll need to
	create a map from actor names to their vertices so that later
	appearances of the same actor (on a different edge) can be linked with
	the correct vertex in the graph. The <a
	href="http://www.sgi.com/tech/stl/Map.html"><TT>std::map</TT></a>
	can be used to implement this mapping.

	<P>
	<PRE>
	typedef graph_traits<Graph>::vertex_descriptor Vertex;
	typedef std::map<string, Vertex> NameVertexMap;
	NameVertexMap actors;
	</PRE>

	<P>
	The first token will be an actor's name. If the actor is not already
	in our actor's map we will add a vertex to the graph, set the name
	property of the vertex, and record the vertex descriptor in the map.
	If the actor is already in the graph, we will retrieve the vertex
	descriptor from the map's <TT>pos</TT> iterator.

	<P>
	<PRE>
	NameVertexMap::iterator pos;
	bool inserted;
	Vertex u, v;

	tokenizer<>::iterator i = line_toks.begin();
	std::string actors_name = *i++;

	tie(pos, inserted) = actors.insert(std::make_pair(actors_name, Vertex()));
	if (inserted) {
	u = add_vertex(g);
	actor_name[u] = actors_name;
	pos->second = u;
	} else
	u = pos->second;
	</PRE>

	<P>
	The second token is the name of the movie, and the third token is the
	other actor. We use the same technique as above to insert the second
	actor into the graph.

	<P>
	<PRE>
	std::string movie_name = *i++;

	tie(pos, inserted) = actors.insert(std::make_pair(*i, Vertex()));
	if (inserted) {
	v = add_vertex(g);
	actor_name[v] = *i;
	pos->second = v;
	} else
	v = pos->second;
	</PRE>

	<P>
	The final step is to add an edge connecting the two actors, and record
	the name of the connecting movie.

	<P>
	<PRE>
	graph_traits<Graph>::edge_descriptor e;
	tie(e, inserted) = add_edge(u, v, g);
	if (inserted)
	connecting_movie[e] = movie_name;
	</PRE>

	<P>

	<H2>A Custom Visitor Class</H2>

	<P>
	We create a custom visitor class to record the Kevin Bacon
	numbers. The Kevin Bacon number will be the shortest distances from
	each actor to Kevin Bacon. This distance has also been referred to as
	the ``Bacon Number'' in memory of the ``Erdos Number'' used to rank
	mathematicians according to how many publications separate them from
	Paul Erdos. The shortest distance to from Kevin Bacon to each actor
	will follow the breadth-first tree. The BFS algorithm identifies edges
	that belong to the breadth-first tree and calls our visitor's
	<tt>tree_edge</tt> function. We record the distance to the target
	vertex as one plus the distance to the source vertex.


	<PRE>
	template <typename DistanceMap>
	class bacon_number_recorder : public default_bfs_visitor
	{
	public:
	bacon_number_recorder(DistanceMap dist) : d(dist) { }

	template <typename Edge, typename Graph>
	void tree_edge(Edge e, const Graph& g) const
	{
	typename graph_traits<Graph>::vertex_descriptor
	u = source(e, g), v = target(e, g);
	d[v] = d[u] + 1;
	}
	private:
	DistanceMap d;
	};
	// Convenience function
	template <typename DistanceMap>
	bacon_number_recorder<DistanceMap>
	record_bacon_number(DistanceMap d)
	{
	return bacon_number_recorder<DistanceMap>(d);
	}
	</PRE>

	<P>
	We will use a vector to store the bacon numbers.

	<P>
	<PRE>
	std::vector<int> bacon_number(num_vertices(g));
	</PRE>

	<H2>Apply the Breadth-First Search</H2>

	<P>
	The BFS algorithm requires a source vertex as input; of course this
	will be Kevin Bacon. We now call the BGL BFS algorithm, passing in the
	graph, source vertex, and the visitor.

	<P>
	<PRE>
	Vertex src = actors["Kevin Bacon"];
	bacon_number[src] = 0;

	breadth_first_search(g, src, visitor(record_bacon_number(&bacon_number[0])));
	</PRE>

	<P>
	We can output the Bacon number for each actor simply by looping
	through all the vertices in the graph and use them to index into the
	<TT>bacon_number</TT> vector.

	<P>
	<PRE>
	graph_traits<Graph>::vertex_iterator i, end;
	for (boost::tie(i, end) = vertices(g); i != end; ++i)
	std::cout << actor_name[*i] << "'s bacon number is "
	<< bacon_number[*i] << std::endl;
	</PRE>

	<P>
	Note that vertex descriptor objects can not always be used as indices
	into vectors or arrays such as <TT>bacon_number</TT>. This is valid
	with the <TT>adjacency_list</TT> class with <TT>VertexList=vecS</TT>,
	but not with other variations of <TT>adjacency_list</TT>. A more
	generic way to index based on vertices is to use the ID property
	map (<TT>vertex_index_t</TT>) in coordination with the <A
	HREF="../../property_map/doc/iterator_property_map.html"><TT>iterator_property_map</TT></a>.

	<P>
	Here are some excepts from the output of the program.
	<PRE>
	William Shatner's bacon number is 2
	Denise Richards's bacon number is 1
	Kevin Bacon's bacon number is 0
	Patrick Stewart's bacon number is 2
	Steve Martin's bacon number is 1
	...
	</PRE>




	<br>
	<HR>
	<TABLE>
	<TR valign=top>
	<TD nowrap>Copyright © 2000-2001</TD><TD>
	<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
	</TD></TR></TABLE>

	</BODY>
	</HTML>
	<!-- LocalWords: gif Hesburgh Ginelli Fass Erd vertices cerr namespace vecS
	-->
	<!-- LocalWords: undirectedS Tokenizer sep tokenizer toks NameVertexMap pos
	-->
	<!-- LocalWords: bool Erdos BFS typename DistanceMap bfs const num BGL src
	-->
	<!-- LocalWords: indices Shatner's Richards's siek htm
	-->