]>
git.proxmox.com Git - ceph.git/blob - ceph/src/boost/libs/graph/example/kevin-bacon2.cpp
1 //=======================================================================
2 // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
4 // Distributed under the Boost Software License, Version 1.0. (See
5 // accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 //=======================================================================
8 #include <boost/config.hpp>
12 #include <boost/tuple/tuple.hpp>
13 #include <boost/graph/adjacency_list.hpp>
14 #include <boost/graph/visitors.hpp>
15 #include <boost/graph/breadth_first_search.hpp>
17 #include <boost/graph/adj_list_serialize.hpp>
18 #include <boost/archive/text_iarchive.hpp>
19 #include <boost/serialization/string.hpp>
21 struct vertex_properties
{
24 template<class Archive
>
25 void serialize(Archive
& ar
, const unsigned int version
) {
30 struct edge_properties
{
33 template<class Archive
>
34 void serialize(Archive
& ar
, const unsigned int version
) {
39 using namespace boost
;
41 typedef adjacency_list
<vecS
, vecS
, undirectedS
,
42 vertex_properties
, edge_properties
> Graph
;
43 typedef graph_traits
<Graph
>::vertex_descriptor Vertex
;
44 typedef graph_traits
<Graph
>::edge_descriptor Edge
;
46 class bacon_number_recorder
: public default_bfs_visitor
49 bacon_number_recorder(int* dist
) : d(dist
) { }
51 void tree_edge(Edge e
, const Graph
& g
) const {
52 Vertex u
= source(e
, g
), v
= target(e
, g
);
61 std::ifstream
ifs("./kevin-bacon2.dat");
63 std::cerr
<< "No ./kevin-bacon2.dat file" << std::endl
;
66 archive::text_iarchive
ia(ifs
);
70 std::vector
<int> bacon_number(num_vertices(g
));
72 // Get the vertex for Kevin Bacon
74 graph_traits
<Graph
>::vertex_iterator i
, end
;
75 for (boost::tie(i
, end
) = vertices(g
); i
!= end
; ++i
)
76 if (g
[*i
].name
== "Kevin Bacon")
79 // Set Kevin's number to zero
80 bacon_number
[src
] = 0;
82 // Perform a breadth first search to compute everyone' Bacon number.
83 breadth_first_search(g
, src
,
84 visitor(bacon_number_recorder(&bacon_number
[0])));
86 for (boost::tie(i
, end
) = vertices(g
); i
!= end
; ++i
)
87 std::cout
<< g
[*i
].name
<< " has a Bacon number of "
88 << bacon_number
[*i
] << std::endl
;