1 | //=======================================================================
|
---|
2 | // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
|
---|
3 | // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
|
---|
4 | //
|
---|
5 | // Distributed under the Boost Software License, Version 1.0. (See
|
---|
6 | // accompanying file LICENSE_1_0.txt or copy at
|
---|
7 | // http://www.boost.org/LICENSE_1_0.txt)
|
---|
8 | //=======================================================================
|
---|
9 |
|
---|
10 | #include <boost/graph/dag_shortest_paths.hpp>
|
---|
11 | #include <boost/graph/adjacency_list.hpp>
|
---|
12 | #include <boost/graph/reverse_graph.hpp>
|
---|
13 |
|
---|
14 | #include <iostream>
|
---|
15 |
|
---|
16 | // Example from Introduction to Algorithms by Cormen, et all p.537.
|
---|
17 |
|
---|
18 | // Sample output:
|
---|
19 | // r: inifinity
|
---|
20 | // s: 0
|
---|
21 | // t: 2
|
---|
22 | // u: 6
|
---|
23 | // v: 5
|
---|
24 | // x: 3
|
---|
25 |
|
---|
26 | int main()
|
---|
27 | {
|
---|
28 | using namespace boost;
|
---|
29 | typedef adjacency_list<vecS, vecS, bidirectionalS,
|
---|
30 | property<vertex_distance_t, int>,
|
---|
31 | property<edge_weight_t, int> > graph_t;
|
---|
32 | graph_t g(6);
|
---|
33 | enum verts { r, s, t, u, v, x };
|
---|
34 | char name[] = "rstuvx";
|
---|
35 | add_edge(r, s, 5, g);
|
---|
36 | add_edge(r, t, 3, g);
|
---|
37 | add_edge(s, t, 2, g);
|
---|
38 | add_edge(s, u, 6, g);
|
---|
39 | add_edge(t, u, 7, g);
|
---|
40 | add_edge(t, v, 4, g);
|
---|
41 | add_edge(t, x, 2, g);
|
---|
42 | add_edge(u, v, -1, g);
|
---|
43 | add_edge(u, x, 1, g);
|
---|
44 | add_edge(v, x, -2, g);
|
---|
45 |
|
---|
46 | property_map<graph_t, vertex_distance_t>::type
|
---|
47 | d_map = get(vertex_distance, g);
|
---|
48 |
|
---|
49 | std::vector<default_color_type> color(num_vertices(g));
|
---|
50 | std::vector<std::size_t> pred(num_vertices(g));
|
---|
51 | default_dijkstra_visitor vis;
|
---|
52 | std::less<int> compare;
|
---|
53 | closed_plus<int> combine;
|
---|
54 | property_map<graph_t, edge_weight_t>::type w_map = get(edge_weight, g);
|
---|
55 |
|
---|
56 | // the following line compiles with boost 1.47 but not in boost 1.48...1.53
|
---|
57 | dag_shortest_paths(make_reverse_graph(g), s, d_map, w_map, &color[0], &pred[0],
|
---|
58 | vis, compare, combine, (std::numeric_limits<int>::max)(), 0);
|
---|
59 |
|
---|
60 | // dag_shortest_paths(make_reverse_graph(g), s, distance_map(d_map)); // this call works with 1.53
|
---|
61 |
|
---|
62 | graph_traits<graph_t>::vertex_iterator vi, vi_end;
|
---|
63 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
|
---|
64 | if (d_map[*vi] == (std::numeric_limits<int>::max)())
|
---|
65 | std::cout << name[*vi] << ": inifinity\n";
|
---|
66 | else
|
---|
67 | std::cout << name[*vi] << ": " << d_map[*vi] << '\n';
|
---|
68 | return 0;
|
---|
69 | }
|
---|