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