1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //=======================================================================
9 #include <boost/config.hpp>
15 #include <boost/pending/stringtok.hpp>
16 #include <boost/utility.hpp>
17 #include <boost/graph/adjacency_list.hpp>
18 #include <boost/graph/visitors.hpp>
19 #include <boost/graph/breadth_first_search.hpp>
20 #include <boost/graph/depth_first_search.hpp>
23 template <class Distance
>
24 class calc_distance_visitor
: public boost::bfs_visitor
<>
27 calc_distance_visitor(Distance d
) : distance(d
) { }
29 template <class Graph
>
30 void tree_edge(typename
boost::graph_traits
<Graph
>::edge_descriptor e
,
33 typename
boost::graph_traits
<Graph
>::vertex_descriptor u
, v
;
34 u
= boost::source(e
, g
);
35 v
= boost::target(e
, g
);
36 distance
[v
] = distance
[u
] + 1;
43 template <class VertexNameMap
, class DistanceMap
>
44 class print_tree_visitor
: public boost::dfs_visitor
<>
47 print_tree_visitor(VertexNameMap n
, DistanceMap d
) : name(n
), distance(d
) { }
48 template <class Graph
>
50 discover_vertex(typename
boost::graph_traits
<Graph
>::vertex_descriptor v
,
53 typedef typename
boost::property_traits
<DistanceMap
>::value_type Dist
;
54 // indentation based on depth
55 for (Dist i
= 0; i
< distance
[v
]; ++i
)
57 std::cout
<< name
[v
] << std::endl
;
60 template <class Graph
>
61 void tree_edge(typename
boost::graph_traits
<Graph
>::edge_descriptor e
,
64 distance
[boost::target(e
, g
)] = distance
[boost::source(e
, g
)] + 1;
75 using namespace boost
;
77 std::ifstream
datafile("./boost_web.dat");
79 std::cerr
<< "No ./boost_web.dat file" << std::endl
;
83 //===========================================================================
84 // Declare the graph type and object, and some property maps.
86 typedef adjacency_list
<vecS
, vecS
, directedS
,
87 property
<vertex_name_t
, std::string
,
88 property
<vertex_color_t
, default_color_type
> >,
89 property
<edge_name_t
, std::string
, property
<edge_weight_t
, int> >
92 typedef graph_traits
<Graph
> Traits
;
93 typedef Traits::vertex_descriptor Vertex
;
94 typedef Traits::edge_descriptor Edge
;
96 typedef std::map
<std::string
, Vertex
> NameVertexMap
;
97 NameVertexMap name2vertex
;
100 typedef property_map
<Graph
, vertex_name_t
>::type NameMap
;
101 NameMap node_name
= get(vertex_name
, g
);
102 property_map
<Graph
, edge_name_t
>::type link_name
= get(edge_name
, g
);
104 //===========================================================================
105 // Read the data file and construct the graph.
108 while (std::getline(datafile
,line
)) {
110 std::list
<std::string
> line_toks
;
111 boost::stringtok(line_toks
, line
, "|");
113 NameVertexMap::iterator pos
;
117 std::list
<std::string
>::iterator i
= line_toks
.begin();
119 boost::tie(pos
, inserted
) = name2vertex
.insert(std::make_pair(*i
, Vertex()));
122 put(node_name
, u
, *i
);
128 std::string hyperlink_name
= *i
++;
130 boost::tie(pos
, inserted
) = name2vertex
.insert(std::make_pair(*i
, Vertex()));
133 put(node_name
, v
, *i
);
139 boost::tie(e
, inserted
) = add_edge(u
, v
, g
);
141 put(link_name
, e
, hyperlink_name
);
145 //===========================================================================
146 // Calculate the diameter of the graph.
148 typedef Traits::vertices_size_type size_type
;
149 typedef std::vector
<size_type
> IntVector
;
150 // Create N x N matrix for storing the shortest distances
151 // between each vertex. Initialize all distances to zero.
152 std::vector
<IntVector
> d_matrix(num_vertices(g
),
153 IntVector(num_vertices(g
), 0));
156 for (i
= 0; i
< num_vertices(g
); ++i
) {
157 calc_distance_visitor
<size_type
*> vis(&d_matrix
[i
][0]);
158 Traits::vertex_descriptor src
= vertices(g
).first
[i
];
159 breadth_first_search(g
, src
, boost::visitor(vis
));
162 size_type diameter
= 0;
163 BOOST_USING_STD_MAX();
164 for (i
= 0; i
< num_vertices(g
); ++i
)
165 diameter
= max
BOOST_PREVENT_MACRO_SUBSTITUTION(diameter
, *std::max_element(d_matrix
[i
].begin(),
168 std::cout
<< "The diameter of the boost web-site graph is " << diameter
169 << std::endl
<< std::endl
;
171 std::cout
<< "Number of clicks from the home page: " << std::endl
;
172 Traits::vertex_iterator vi
, vi_end
;
173 for (boost::tie(vi
, vi_end
) = vertices(g
); vi
!= vi_end
; ++vi
)
174 std::cout
<< d_matrix
[0][*vi
] << "\t" << node_name
[*vi
] << std::endl
;
175 std::cout
<< std::endl
;
177 //===========================================================================
178 // Print out the breadth-first search tree starting at the home page
180 // Create storage for a mapping from vertices to their parents
181 std::vector
<Traits::vertex_descriptor
> parent(num_vertices(g
));
182 for (boost::tie(vi
, vi_end
) = vertices(g
); vi
!= vi_end
; ++vi
)
185 // Do a BFS starting at the home page, recording the parent of each
186 // vertex (where parent is with respect to the search tree).
187 Traits::vertex_descriptor src
= vertices(g
).first
[0];
190 boost::visitor(make_bfs_visitor(record_predecessors(&parent
[0],
193 // Add all the search tree edges into a new graph
194 Graph
search_tree(num_vertices(g
));
195 boost::tie(vi
, vi_end
) = vertices(g
);
197 for (; vi
!= vi_end
; ++vi
)
198 add_edge(parent
[*vi
], *vi
, search_tree
);
200 std::cout
<< "The breadth-first search tree:" << std::endl
;
202 // Print out the search tree. We use DFS because it visits
203 // the tree nodes in the order that we want to print out:
204 // a directory-structure like format.
205 std::vector
<size_type
> dfs_distances(num_vertices(g
), 0);
206 print_tree_visitor
<NameMap
, size_type
*>
207 tree_printer(node_name
, &dfs_distances
[0]);
208 for (boost::tie(vi
, vi_end
) = vertices(g
); vi
!= vi_end
; ++vi
)
209 get(vertex_color
, g
)[*vi
] = white_color
;
210 depth_first_visit(search_tree
, src
, tree_printer
, get(vertex_color
, g
));