diff options
Diffstat (limited to 'src/boost/libs/graph/example/dave.cpp')
| -rw-r--r-- | src/boost/libs/graph/example/dave.cpp | 249 |
1 files changed, 249 insertions, 0 deletions
diff --git a/src/boost/libs/graph/example/dave.cpp b/src/boost/libs/graph/example/dave.cpp new file mode 100644 index 00000000..04c69f88 --- /dev/null +++ b/src/boost/libs/graph/example/dave.cpp @@ -0,0 +1,249 @@ +//======================================================================= +// 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; +} |