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