1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
4 //
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>
10 #include <iostream>
11 #include <fstream>
12 #include <string>
13 #include <algorithm>
14 #include <map>
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>
21
22 template < class Distance >
23 class calc_distance_visitor : public boost::bfs_visitor<>
24 {
25 public:
calc_distance_visitor(Distance d)26 calc_distance_visitor(Distance d) : distance(d) {}
27
28 template < class Graph >
tree_edge(typename boost::graph_traits<Graph>::edge_descriptor e,Graph & g)29 void tree_edge(
30 typename boost::graph_traits< Graph >::edge_descriptor e, Graph& g)
31 {
32 typename boost::graph_traits< Graph >::vertex_descriptor u, v;
33 u = boost::source(e, g);
34 v = boost::target(e, g);
35 distance[v] = distance[u] + 1;
36 }
37
38 private:
39 Distance distance;
40 };
41
42 template < class VertexNameMap, class DistanceMap >
43 class print_tree_visitor : public boost::dfs_visitor<>
44 {
45 public:
print_tree_visitor(VertexNameMap n,DistanceMap d)46 print_tree_visitor(VertexNameMap n, DistanceMap d) : name(n), distance(d) {}
47 template < class Graph >
discover_vertex(typename boost::graph_traits<Graph>::vertex_descriptor v,Graph &)48 void discover_vertex(
49 typename boost::graph_traits< Graph >::vertex_descriptor v, Graph&)
50 {
51 typedef typename boost::property_traits< DistanceMap >::value_type Dist;
52 // indentation based on depth
53 for (Dist i = 0; i < distance[v]; ++i)
54 std::cout << " ";
55 std::cout << name[v] << std::endl;
56 }
57
58 template < class Graph >
tree_edge(typename boost::graph_traits<Graph>::edge_descriptor e,Graph & g)59 void tree_edge(
60 typename boost::graph_traits< Graph >::edge_descriptor e, Graph& g)
61 {
62 distance[boost::target(e, g)] = distance[boost::source(e, g)] + 1;
63 }
64
65 private:
66 VertexNameMap name;
67 DistanceMap distance;
68 };
69
main(int argc,const char ** argv)70 int main(int argc, const char** argv)
71 {
72 using namespace boost;
73
74 std::ifstream datafile(argc >= 2 ? argv[1] : "./boost_web.dat");
75 if (!datafile)
76 {
77 std::cerr << "No ./boost_web.dat file" << std::endl;
78 return -1;
79 }
80
81 //===========================================================================
82 // Declare the graph type and object, and some property maps.
83
84 typedef adjacency_list< vecS, vecS, directedS,
85 property< vertex_name_t, std::string,
86 property< vertex_color_t, default_color_type > >,
87 property< edge_name_t, std::string, property< edge_weight_t, int > > >
88 Graph;
89
90 typedef graph_traits< Graph > Traits;
91 typedef Traits::vertex_descriptor Vertex;
92 typedef Traits::edge_descriptor Edge;
93
94 typedef std::map< std::string, Vertex > NameVertexMap;
95 NameVertexMap name2vertex;
96 Graph g;
97
98 typedef property_map< Graph, vertex_name_t >::type NameMap;
99 NameMap node_name = get(vertex_name, g);
100 property_map< Graph, edge_name_t >::type link_name = get(edge_name, g);
101
102 //===========================================================================
103 // Read the data file and construct the graph.
104
105 std::string line;
106 while (std::getline(datafile, line))
107 {
108
109 std::list< std::string > line_toks;
110 boost::stringtok(line_toks, line, "|");
111
112 NameVertexMap::iterator pos;
113 bool inserted;
114 Vertex u, v;
115
116 std::list< std::string >::iterator i = line_toks.begin();
117
118 boost::tie(pos, inserted)
119 = name2vertex.insert(std::make_pair(*i, Vertex()));
120 if (inserted)
121 {
122 u = add_vertex(g);
123 put(node_name, u, *i);
124 pos->second = u;
125 }
126 else
127 u = pos->second;
128 ++i;
129
130 std::string hyperlink_name = *i++;
131
132 boost::tie(pos, inserted)
133 = name2vertex.insert(std::make_pair(*i, Vertex()));
134 if (inserted)
135 {
136 v = add_vertex(g);
137 put(node_name, v, *i);
138 pos->second = v;
139 }
140 else
141 v = pos->second;
142
143 Edge e;
144 boost::tie(e, inserted) = add_edge(u, v, g);
145 if (inserted)
146 {
147 put(link_name, e, hyperlink_name);
148 }
149 }
150
151 //===========================================================================
152 // Calculate the diameter of the graph.
153
154 typedef Traits::vertices_size_type size_type;
155 typedef std::vector< size_type > IntVector;
156 // Create N x N matrix for storing the shortest distances
157 // between each vertex. Initialize all distances to zero.
158 std::vector< IntVector > d_matrix(
159 num_vertices(g), IntVector(num_vertices(g), 0));
160
161 size_type i;
162 for (i = 0; i < num_vertices(g); ++i)
163 {
164 calc_distance_visitor< size_type* > vis(&d_matrix[i][0]);
165 Traits::vertex_descriptor src = vertices(g).first[i];
166 breadth_first_search(g, src, boost::visitor(vis));
167 }
168
169 size_type diameter = 0;
170 BOOST_USING_STD_MAX();
171 for (i = 0; i < num_vertices(g); ++i)
172 diameter = max BOOST_PREVENT_MACRO_SUBSTITUTION(diameter,
173 *std::max_element(d_matrix[i].begin(), d_matrix[i].end()));
174
175 std::cout << "The diameter of the boost web-site graph is " << diameter
176 << std::endl
177 << std::endl;
178
179 std::cout << "Number of clicks from the home page: " << std::endl;
180 Traits::vertex_iterator vi, vi_end;
181 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
182 std::cout << d_matrix[0][*vi] << "\t" << node_name[*vi] << std::endl;
183 std::cout << std::endl;
184
185 //===========================================================================
186 // Print out the breadth-first search tree starting at the home page
187
188 // Create storage for a mapping from vertices to their parents
189 std::vector< Traits::vertex_descriptor > parent(num_vertices(g));
190 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
191 parent[*vi] = *vi;
192
193 // Do a BFS starting at the home page, recording the parent of each
194 // vertex (where parent is with respect to the search tree).
195 Traits::vertex_descriptor src = vertices(g).first[0];
196 breadth_first_search(g, src,
197 boost::visitor(
198 make_bfs_visitor(record_predecessors(&parent[0], on_tree_edge()))));
199
200 // Add all the search tree edges into a new graph
201 Graph search_tree(num_vertices(g));
202 boost::tie(vi, vi_end) = vertices(g);
203 ++vi;
204 for (; vi != vi_end; ++vi)
205 add_edge(parent[*vi], *vi, search_tree);
206
207 std::cout << "The breadth-first search tree:" << std::endl;
208
209 // Print out the search tree. We use DFS because it visits
210 // the tree nodes in the order that we want to print out:
211 // a directory-structure like format.
212 std::vector< size_type > dfs_distances(num_vertices(g), 0);
213 print_tree_visitor< NameMap, size_type* > tree_printer(
214 node_name, &dfs_distances[0]);
215 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
216 get(vertex_color, g)[*vi] = white_color;
217 depth_first_visit(search_tree, src, tree_printer, get(vertex_color, g));
218
219 return EXIT_SUCCESS;
220 }
221