1 //=======================================================================
2 // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
3 //
4 // Distributed under the Boost Software License, Version 1.0. (See
5 // accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 //=======================================================================
8 #include <boost/config.hpp>
9 #include <fstream>
10 #include <iostream>
11 #include <vector>
12 #include <iomanip>
13 #include <boost/property_map/property_map.hpp>
14 #include <boost/graph/adjacency_list.hpp>
15 #include <boost/graph/graphviz.hpp>
16 #include <boost/graph/johnson_all_pairs_shortest.hpp>
17
main()18 int main()
19 {
20 using namespace boost;
21 typedef adjacency_list< vecS, vecS, directedS, no_property,
22 property< edge_weight_t, int, property< edge_weight2_t, int > > >
23 Graph;
24 const int V = 6;
25 typedef std::pair< int, int > Edge;
26 Edge edge_array[] = { Edge(0, 1), Edge(0, 2), Edge(0, 3), Edge(0, 4),
27 Edge(0, 5), Edge(1, 2), Edge(1, 5), Edge(1, 3), Edge(2, 4), Edge(2, 5),
28 Edge(3, 2), Edge(4, 3), Edge(4, 1), Edge(5, 4) };
29 const std::size_t E = sizeof(edge_array) / sizeof(Edge);
30 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
31 // VC++ can't handle the iterator constructor
32 Graph g(V);
33 for (std::size_t j = 0; j < E; ++j)
34 add_edge(edge_array[j].first, edge_array[j].second, g);
35 #else
36 Graph g(edge_array, edge_array + E, V);
37 #endif
38
39 property_map< Graph, edge_weight_t >::type w = get(edge_weight, g);
40 int weights[] = { 0, 0, 0, 0, 0, 3, -4, 8, 1, 7, 4, -5, 2, 6 };
41 int* wp = weights;
42
43 graph_traits< Graph >::edge_iterator e, e_end;
44 for (boost::tie(e, e_end) = edges(g); e != e_end; ++e)
45 w[*e] = *wp++;
46
47 std::vector< int > d(V, (std::numeric_limits< int >::max)());
48 int D[V][V];
49 johnson_all_pairs_shortest_paths(g, D, distance_map(&d[0]));
50
51 std::cout << " ";
52 for (int k = 0; k < V; ++k)
53 std::cout << std::setw(5) << k;
54 std::cout << std::endl;
55 for (int i = 0; i < V; ++i)
56 {
57 std::cout << std::setw(3) << i << " -> ";
58 for (int j = 0; j < V; ++j)
59 {
60 if (D[i][j] == (std::numeric_limits< int >::max)())
61 std::cout << std::setw(5) << "inf";
62 else
63 std::cout << std::setw(5) << D[i][j];
64 }
65 std::cout << std::endl;
66 }
67
68 std::ofstream fout("figs/johnson-eg.dot");
69 fout << "digraph A {\n"
70 << " rankdir=LR\n"
71 << "size=\"5,3\"\n"
72 << "ratio=\"fill\"\n"
73 << "edge[style=\"bold\"]\n"
74 << "node[shape=\"circle\"]\n";
75
76 graph_traits< Graph >::edge_iterator ei, ei_end;
77 for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
78 fout << source(*ei, g) << " -> " << target(*ei, g)
79 << "[label=" << get(edge_weight, g)[*ei] << "]\n";
80
81 fout << "}\n";
82 return 0;
83 }
84