boost_web_graph.cpp

//=======================================================================
// 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;
}