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