//=======================================================================
-// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
+// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
using namespace boost;
-template <typename DistanceMap>
+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;
- }
+ 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)
+bacon_number_recorder< DistanceMap > record_bacon_number(DistanceMap d)
{
- return bacon_number_recorder < DistanceMap > (d);
+ return bacon_number_recorder< DistanceMap >(d);
}
-
-int
-main(int argc, const char** argv)
+int main(int argc, const char** argv)
{
- std::ifstream datafile(argc >= 2 ? argv[1] : "./kevin-bacon.dat");
- if (!datafile) {
- std::cerr << "No ./kevin-bacon.dat file" << std::endl;
- return EXIT_FAILURE;
- }
-
- typedef adjacency_list < vecS, vecS, undirectedS, property < vertex_name_t,
- std::string >, property < edge_name_t, std::string > > Graph;
- Graph g;
-
- typedef property_map < Graph, vertex_name_t >::type actor_name_map_t;
- actor_name_map_t actor_name = get(vertex_name, g);
- typedef property_map < Graph, edge_name_t >::type movie_name_map_t;
- movie_name_map_t connecting_movie = get(edge_name, g);
-
- typedef graph_traits < Graph >::vertex_descriptor Vertex;
- typedef std::map < std::string, Vertex > NameVertexMap;
- NameVertexMap actors;
-
- for (std::string line; std::getline(datafile, line);) {
- char_delimiters_separator < char >sep(false, "", ";");
- tokenizer <> line_toks(line, sep);
- tokenizer <>::iterator i = line_toks.begin();
- std::string actors_name = *i++;
- NameVertexMap::iterator pos;
- bool inserted;
- Vertex u, v;
- boost::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;
-
- std::string movie_name = *i++;
-
- boost::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;
-
- graph_traits < Graph >::edge_descriptor e;
- boost::tie(e, inserted) = add_edge(u, v, g);
- if (inserted)
- connecting_movie[e] = movie_name;
-
- }
-
- std::vector < int >bacon_number(num_vertices(g));
-
- Vertex src = actors["Kevin Bacon"];
- bacon_number[src] = 0;
-
- breadth_first_search(g, src,
- visitor(record_bacon_number(&bacon_number[0])));
-
- graph_traits < Graph >::vertex_iterator i, end;
- for (boost::tie(i, end) = vertices(g); i != end; ++i) {
- std::cout << actor_name[*i] << " has a Bacon number of "
- << bacon_number[*i] << std::endl;
- }
-
- return 0;
+ std::ifstream datafile(argc >= 2 ? argv[1] : "./kevin-bacon.dat");
+ if (!datafile)
+ {
+ std::cerr << "No ./kevin-bacon.dat file" << std::endl;
+ return EXIT_FAILURE;
+ }
+
+ typedef adjacency_list< vecS, vecS, undirectedS,
+ property< vertex_name_t, std::string >,
+ property< edge_name_t, std::string > >
+ Graph;
+ Graph g;
+
+ typedef property_map< Graph, vertex_name_t >::type actor_name_map_t;
+ actor_name_map_t actor_name = get(vertex_name, g);
+ typedef property_map< Graph, edge_name_t >::type movie_name_map_t;
+ movie_name_map_t connecting_movie = get(edge_name, g);
+
+ typedef graph_traits< Graph >::vertex_descriptor Vertex;
+ typedef std::map< std::string, Vertex > NameVertexMap;
+ NameVertexMap actors;
+
+ for (std::string line; std::getline(datafile, line);)
+ {
+ char_delimiters_separator< char > sep(false, "", ";");
+ tokenizer<> line_toks(line, sep);
+ tokenizer<>::iterator i = line_toks.begin();
+ std::string actors_name = *i++;
+ NameVertexMap::iterator pos;
+ bool inserted;
+ Vertex u, v;
+ boost::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;
+
+ std::string movie_name = *i++;
+
+ boost::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;
+
+ graph_traits< Graph >::edge_descriptor e;
+ boost::tie(e, inserted) = add_edge(u, v, g);
+ if (inserted)
+ connecting_movie[e] = movie_name;
+ }
+
+ std::vector< int > bacon_number(num_vertices(g));
+
+ Vertex src = actors["Kevin Bacon"];
+ bacon_number[src] = 0;
+
+ breadth_first_search(
+ g, src, visitor(record_bacon_number(&bacon_number[0])));
+
+ graph_traits< Graph >::vertex_iterator i, end;
+ for (boost::tie(i, end) = vertices(g); i != end; ++i)
+ {
+ std::cout << actor_name[*i] << " has a Bacon number of "
+ << bacon_number[*i] << std::endl;
+ }
+
+ return 0;
}
projects / ceph.git / blobdiff