johnson-test.cpp
2.66 KB
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
//=======================================================================
// Copyright 2002 Indiana University.
// 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)
//=======================================================================
/* Expected Output
0 1 2 3 4 5 6 7 8 9
0 0 99 111 123 103 107 125 105 111 123
1 99 0 12 24 4 8 26 6 12 24
2 111 12 0 12 16 20 24 18 24 26
3 123 24 12 0 28 30 12 30 26 14
4 103 4 16 28 0 4 22 2 8 20
5 107 8 20 30 4 0 18 6 4 16
6 125 26 24 12 22 18 0 24 14 2
7 105 6 18 30 2 6 24 0 10 22
8 111 12 24 26 8 4 14 10 0 12
9 123 24 26 14 20 16 2 22 12 0
*/
#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, undirectedS, no_property,
property< edge_weight_t, int, property< edge_weight2_t, int > > >
Graph;
const int V = 10;
typedef std::pair< int, int > Edge;
Edge edge_array[] = { Edge(0, 1), Edge(1, 2), Edge(2, 3), Edge(1, 4),
Edge(2, 5), Edge(3, 6), Edge(4, 5), Edge(5, 6), Edge(4, 7), Edge(5, 8),
Edge(6, 9), Edge(7, 8), Edge(8, 9) };
const std::size_t E = sizeof(edge_array) / sizeof(Edge);
Graph g(edge_array, edge_array + E, V);
property_map< Graph, edge_weight_t >::type w = get(edge_weight, g);
int weights[] = { 99, 12, 12, 4, 99, 12, 4, 99, 2, 4, 2, 99, 12 };
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 << std::setw(5) << " ";
for (int k = 0; k < 10; ++k)
std::cout << std::setw(5) << k;
std::cout << std::endl;
for (int i = 0; i < 10; ++i)
{
std::cout << std::setw(5) << i;
for (int j = 0; j < 10; ++j)
{
std::cout << std::setw(5) << D[i][j];
}
std::cout << std::endl;
}
return 0;
}