graph/example/dave.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 <iterator>
#include <vector>
#include <list>
// Use boost::queue instead of std::queue because std::queue doesn't
// model Buffer; it has to top() function. -Jeremy
#include <boost/pending/queue.hpp>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_utility.hpp>

using namespace std;
using namespace boost;
/*
  This example does a best-first-search (using dijkstra's) and
  simultaneously makes a copy of the graph (assuming the graph is
  connected).

  Example Graph: (p. 90 "Data Structures and Network Algorithms", Tarjan)

              g
            3+ +2
            / 1 \
           e+----f
           |+0 5++
           | \ / |
         10|  d  |12
           |8++\7|
           +/ | +|
           b 4|  c
            \ | +
            6+|/3
              a

  Sample Output:
a --> c d
b --> a d
c --> f
d --> c e f
e --> b g
f --> e g
g -->
Starting graph:
a(32767); c d
c(32767); f
d(32767); c e f
f(32767); e g
e(32767); b g
g(32767);
b(32767); a d
Result:
a(0); d c
d(4); f e c
c(3); f
f(9); g e
e(4); g b
g(7);
b(14); d a

*/

typedef property<vertex_color_t, default_color_type,
         property<vertex_distance_t,int> > VProperty;
typedef int weight_t;
typedef property<edge_weight_t,weight_t> EProperty;

typedef adjacency_list<vecS, vecS, directedS, VProperty, EProperty > Graph;


template <class Tag>
struct endl_printer
  : public boost::base_visitor< endl_printer<Tag> >
{
  typedef Tag event_filter;
  endl_printer(std::ostream& os) : m_os(os) { }
  template <class T, class Graph>
  void operator()(T, Graph&) { m_os << std::endl; }
  std::ostream& m_os;
};
template <class Tag>
endl_printer<Tag> print_endl(std::ostream& os, Tag) {
  return endl_printer<Tag>(os);
}

template <class PA, class Tag>
struct edge_printer
 : public boost::base_visitor< edge_printer<PA, Tag> >
{
  typedef Tag event_filter;

  edge_printer(PA pa, std::ostream& os) : m_pa(pa), m_os(os) { }

  template <class T, class Graph>
  void operator()(T x, Graph& g) {
    m_os << "(" << get(m_pa, source(x, g)) << ","
         << get(m_pa, target(x, g)) << ") ";
  }
  PA m_pa;
  std::ostream& m_os;
};
template <class PA, class Tag>
edge_printer<PA, Tag>
print_edge(PA pa, std::ostream& os, Tag) {
  return edge_printer<PA, Tag>(pa, os);
}


template <class NewGraph, class Tag>
struct graph_copier
  : public boost::base_visitor<graph_copier<NewGraph, Tag> >
{
  typedef Tag event_filter;

  graph_copier(NewGraph& graph) : new_g(graph) { }

  template <class Edge, class Graph>
  void operator()(Edge e, Graph& g) {
    add_edge(source(e, g), target(e, g), new_g);
  }
private:
  NewGraph& new_g;
};
template <class NewGraph, class Tag>
inline graph_copier<NewGraph, Tag>
copy_graph(NewGraph& g, Tag) {
  return graph_copier<NewGraph, Tag>(g);
}

template <class Graph, class Name>
void print(Graph& G, Name name)
{
  typename boost::graph_traits<Graph>::vertex_iterator ui, uiend;
  for (boost::tie(ui, uiend) = vertices(G); ui != uiend; ++ui) {
    cout << name[*ui] << " --> ";
    typename boost::graph_traits<Graph>::adjacency_iterator vi, viend;
    for(boost::tie(vi, viend) = adjacent_vertices(*ui, G); vi != viend; ++vi)
      cout << name[*vi] << " ";
    cout << endl;
  }

}


int
main(int , char* [])
{
  // Name and ID numbers for the vertices
  char name[] = "abcdefg";
  enum { a, b, c, d, e, f, g, N};

  Graph G(N);
  boost::property_map<Graph, vertex_index_t>::type
    vertex_id = get(vertex_index, G);

  std::vector<weight_t> distance(N, (numeric_limits<weight_t>::max)());
  typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
  std::vector<Vertex> parent(N);

  typedef std::pair<int,int> E;

  E edges[] = { E(a,c), E(a,d),
                E(b,a), E(b,d),
                E(c,f),
                E(d,c), E(d,e), E(d,f),
                E(e,b), E(e,g),
                E(f,e), E(f,g) };

  int weight[] = { 3, 4,
                   6, 8,
                   12,
                   7, 0, 5,
                   10, 3,
                   1, 2 };

  for (int i = 0; i < 12; ++i)
    add_edge(edges[i].first, edges[i].second, weight[i], G);

  print(G, name);

  adjacency_list<listS, vecS, directedS,
    property<vertex_color_t, default_color_type> > G_copy(N);

  cout << "Starting graph:" << endl;

  std::ostream_iterator<int> cout_int(std::cout, " ");
  std::ostream_iterator<char> cout_char(std::cout, " ");

  boost::queue<Vertex> Q;
  boost::breadth_first_search
    (G, vertex(a, G), Q,
     make_bfs_visitor(
     boost::make_list
      (write_property(make_iterator_property_map(name, vertex_id,
                                                name[0]),
                      cout_char, on_examine_vertex()),
       write_property(make_iterator_property_map(distance.begin(),
                                                vertex_id,
                                                distance[0]),
                      cout_int, on_examine_vertex()),
       print_edge(make_iterator_property_map(name, vertex_id,
                                            name[0]),
                  std::cout, on_examine_edge()),
       print_endl(std::cout, on_finish_vertex()))),
     get(vertex_color, G));

  std::cout << "about to call dijkstra's" << std::endl;

  parent[vertex(a, G)] = vertex(a, G);
  boost::dijkstra_shortest_paths
    (G, vertex(a, G),
     distance_map(make_iterator_property_map(distance.begin(), vertex_id,
                                             distance[0])).
     predecessor_map(make_iterator_property_map(parent.begin(), vertex_id,
                                                parent[0])).
     visitor(make_dijkstra_visitor(copy_graph(G_copy, on_examine_edge()))));

  cout << endl;
  cout << "Result:" << endl;
  boost::breadth_first_search
    (G, vertex(a, G),
     visitor(make_bfs_visitor(
     boost::make_list
     (write_property(make_iterator_property_map(name, vertex_id,
                                                name[0]),
                     cout_char, on_examine_vertex()),
      write_property(make_iterator_property_map(distance.begin(),
                                                vertex_id,
                                                distance[0]),
                     cout_int, on_examine_vertex()),
      print_edge(make_iterator_property_map(name, vertex_id,
                                            name[0]),
                 std::cout, on_examine_edge()),
      print_endl(std::cout, on_finish_vertex())))));

  return 0;
}