123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213 |
- //=======================================================================
- // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
- // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
- //
- // 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)
- //=======================================================================
- #include <boost/config.hpp>
- #include <iostream>
- #include <fstream>
- #include <string>
- #include <algorithm>
- #include <map>
- #include <boost/pending/stringtok.hpp>
- #include <boost/utility.hpp>
- #include <boost/graph/adjacency_list.hpp>
- #include <boost/graph/visitors.hpp>
- #include <boost/graph/breadth_first_search.hpp>
- #include <boost/graph/depth_first_search.hpp>
- template <class Distance>
- class calc_distance_visitor : public boost::bfs_visitor<>
- {
- public:
- calc_distance_visitor(Distance d) : distance(d) { }
- template <class Graph>
- void tree_edge(typename boost::graph_traits<Graph>::edge_descriptor e,
- Graph& g)
- {
- typename boost::graph_traits<Graph>::vertex_descriptor u, v;
- u = boost::source(e, g);
- v = boost::target(e, g);
- distance[v] = distance[u] + 1;
- }
- private:
- Distance distance;
- };
- template <class VertexNameMap, class DistanceMap>
- class print_tree_visitor : public boost::dfs_visitor<>
- {
- public:
- print_tree_visitor(VertexNameMap n, DistanceMap d) : name(n), distance(d) { }
- template <class Graph>
- void
- discover_vertex(typename boost::graph_traits<Graph>::vertex_descriptor v,
- Graph&)
- {
- typedef typename boost::property_traits<DistanceMap>::value_type Dist;
- // indentation based on depth
- for (Dist i = 0; i < distance[v]; ++i)
- std::cout << " ";
- std::cout << name[v] << std::endl;
- }
- template <class Graph>
- void tree_edge(typename boost::graph_traits<Graph>::edge_descriptor e,
- Graph& g)
- {
- distance[boost::target(e, g)] = distance[boost::source(e, g)] + 1;
- }
- private:
- VertexNameMap name;
- DistanceMap distance;
- };
- int
- main(int argc, const char** argv)
- {
- using namespace boost;
- std::ifstream datafile(argc >= 2 ? argv[1] : "./boost_web.dat");
- if (!datafile) {
- std::cerr << "No ./boost_web.dat file" << std::endl;
- return -1;
- }
- //===========================================================================
- // Declare the graph type and object, and some property maps.
- typedef adjacency_list<vecS, vecS, directedS,
- property<vertex_name_t, std::string,
- property<vertex_color_t, default_color_type> >,
- property<edge_name_t, std::string, property<edge_weight_t, int> >
- > Graph;
- typedef graph_traits<Graph> Traits;
- typedef Traits::vertex_descriptor Vertex;
- typedef Traits::edge_descriptor Edge;
- typedef std::map<std::string, Vertex> NameVertexMap;
- NameVertexMap name2vertex;
- Graph g;
- typedef property_map<Graph, vertex_name_t>::type NameMap;
- NameMap node_name = get(vertex_name, g);
- property_map<Graph, edge_name_t>::type link_name = get(edge_name, g);
- //===========================================================================
- // Read the data file and construct the graph.
-
- std::string line;
- while (std::getline(datafile,line)) {
- std::list<std::string> line_toks;
- boost::stringtok(line_toks, line, "|");
- NameVertexMap::iterator pos;
- bool inserted;
- Vertex u, v;
- std::list<std::string>::iterator i = line_toks.begin();
- boost::tie(pos, inserted) = name2vertex.insert(std::make_pair(*i, Vertex()));
- if (inserted) {
- u = add_vertex(g);
- put(node_name, u, *i);
- pos->second = u;
- } else
- u = pos->second;
- ++i;
- std::string hyperlink_name = *i++;
-
- boost::tie(pos, inserted) = name2vertex.insert(std::make_pair(*i, Vertex()));
- if (inserted) {
- v = add_vertex(g);
- put(node_name, v, *i);
- pos->second = v;
- } else
- v = pos->second;
- Edge e;
- boost::tie(e, inserted) = add_edge(u, v, g);
- if (inserted) {
- put(link_name, e, hyperlink_name);
- }
- }
- //===========================================================================
- // Calculate the diameter of the graph.
- typedef Traits::vertices_size_type size_type;
- typedef std::vector<size_type> IntVector;
- // Create N x N matrix for storing the shortest distances
- // between each vertex. Initialize all distances to zero.
- std::vector<IntVector> d_matrix(num_vertices(g),
- IntVector(num_vertices(g), 0));
- size_type i;
- for (i = 0; i < num_vertices(g); ++i) {
- calc_distance_visitor<size_type*> vis(&d_matrix[i][0]);
- Traits::vertex_descriptor src = vertices(g).first[i];
- breadth_first_search(g, src, boost::visitor(vis));
- }
- size_type diameter = 0;
- BOOST_USING_STD_MAX();
- for (i = 0; i < num_vertices(g); ++i)
- diameter = max BOOST_PREVENT_MACRO_SUBSTITUTION(diameter, *std::max_element(d_matrix[i].begin(),
- d_matrix[i].end()));
-
- std::cout << "The diameter of the boost web-site graph is " << diameter
- << std::endl << std::endl;
- std::cout << "Number of clicks from the home page: " << std::endl;
- Traits::vertex_iterator vi, vi_end;
- for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
- std::cout << d_matrix[0][*vi] << "\t" << node_name[*vi] << std::endl;
- std::cout << std::endl;
-
- //===========================================================================
- // Print out the breadth-first search tree starting at the home page
- // Create storage for a mapping from vertices to their parents
- std::vector<Traits::vertex_descriptor> parent(num_vertices(g));
- for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
- parent[*vi] = *vi;
- // Do a BFS starting at the home page, recording the parent of each
- // vertex (where parent is with respect to the search tree).
- Traits::vertex_descriptor src = vertices(g).first[0];
- breadth_first_search
- (g, src,
- boost::visitor(make_bfs_visitor(record_predecessors(&parent[0],
- on_tree_edge()))));
- // Add all the search tree edges into a new graph
- Graph search_tree(num_vertices(g));
- boost::tie(vi, vi_end) = vertices(g);
- ++vi;
- for (; vi != vi_end; ++vi)
- add_edge(parent[*vi], *vi, search_tree);
- std::cout << "The breadth-first search tree:" << std::endl;
- // Print out the search tree. We use DFS because it visits
- // the tree nodes in the order that we want to print out:
- // a directory-structure like format.
- std::vector<size_type> dfs_distances(num_vertices(g), 0);
- print_tree_visitor<NameMap, size_type*>
- tree_printer(node_name, &dfs_distances[0]);
- for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
- get(vertex_color, g)[*vi] = white_color;
- depth_first_visit(search_tree, src, tree_printer, get(vertex_color, g));
-
- return EXIT_SUCCESS;
- }
|