1 //=======================================================================
2 // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee
3 // Copyright 2009 Trustees of Indiana University.
4 // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
5 //
6 // Distributed under the Boost Software License, Version 1.0. (See
7 // accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9 //
10 // NOTE: Based off of dijkstra-example.cpp
11 //=======================================================================
12 #include <boost/config.hpp>
13 #include <iostream>
14 #include <fstream>
15
16 #include <boost/graph/graph_traits.hpp>
17 #include <boost/graph/adjacency_list.hpp>
18 #include <boost/graph/dijkstra_shortest_paths_no_color_map.hpp>
19 #include <boost/property_map/property_map.hpp>
20
21 using namespace boost;
22
main(int,char * [])23 int main(int, char*[])
24 {
25 typedef adjacency_list< listS, vecS, directedS, no_property,
26 property< edge_weight_t, int > >
27 graph_t;
28 typedef graph_traits< graph_t >::vertex_descriptor vertex_descriptor;
29 typedef std::pair< int, int > Edge;
30
31 const int num_nodes = 5;
32 enum nodes
33 {
34 A,
35 B,
36 C,
37 D,
38 E
39 };
40 char name[] = "ABCDE";
41 Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E),
42 Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), Edge(E, B) };
43 int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 };
44 int num_arcs = sizeof(edge_array) / sizeof(Edge);
45 graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes);
46 property_map< graph_t, edge_weight_t >::type weightmap
47 = get(edge_weight, g);
48 std::vector< vertex_descriptor > p(num_vertices(g));
49 std::vector< int > d(num_vertices(g));
50 vertex_descriptor s = vertex(A, g);
51
52 dijkstra_shortest_paths_no_color_map(g, s,
53 predecessor_map(boost::make_iterator_property_map(
54 p.begin(), get(boost::vertex_index, g)))
55 .distance_map(boost::make_iterator_property_map(
56 d.begin(), get(boost::vertex_index, g))));
57
58 std::cout << "distances and parents:" << std::endl;
59 graph_traits< graph_t >::vertex_iterator vi, vend;
60 for (boost::tie(vi, vend) = vertices(g); vi != vend; ++vi)
61 {
62 std::cout << "distance(" << name[*vi] << ") = " << d[*vi] << ", ";
63 std::cout << "parent(" << name[*vi] << ") = " << name[p[*vi]]
64 << std::endl;
65 }
66 std::cout << std::endl;
67
68 std::ofstream dot_file("figs/dijkstra-no-color-map-eg.dot");
69
70 dot_file << "digraph D {\n"
71 << " rankdir=LR\n"
72 << " size=\"4,3\"\n"
73 << " ratio=\"fill\"\n"
74 << " edge[style=\"bold\"]\n"
75 << " node[shape=\"circle\"]\n";
76
77 graph_traits< graph_t >::edge_iterator ei, ei_end;
78 for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
79 {
80 graph_traits< graph_t >::edge_descriptor e = *ei;
81 graph_traits< graph_t >::vertex_descriptor u = source(e, g),
82 v = target(e, g);
83 dot_file << name[u] << " -> " << name[v] << "[label=\""
84 << get(weightmap, e) << "\"";
85 if (p[v] == u)
86 dot_file << ", color=\"black\"";
87 else
88 dot_file << ", color=\"grey\"";
89 dot_file << "]";
90 }
91 dot_file << "}";
92 return EXIT_SUCCESS;
93 }
94