|
sl@0
|
1 |
//=======================================================================
|
|
sl@0
|
2 |
// Copyright 2002 Indiana University.
|
|
sl@0
|
3 |
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
|
|
sl@0
|
4 |
//
|
|
sl@0
|
5 |
// Distributed under the Boost Software License, Version 1.0. (See
|
|
sl@0
|
6 |
// accompanying file LICENSE_1_0.txt or copy at
|
|
sl@0
|
7 |
// http://www.boost.org/LICENSE_1_0.txt)
|
|
sl@0
|
8 |
//=======================================================================
|
|
sl@0
|
9 |
/*
|
|
sl@0
|
10 |
* © Portions copyright (c) 2006-2007 Nokia Corporation. All rights reserved.
|
|
sl@0
|
11 |
*/
|
|
sl@0
|
12 |
|
|
sl@0
|
13 |
|
|
sl@0
|
14 |
/* Expected Output
|
|
sl@0
|
15 |
0 1 2 3 4 5 6 7 8 9
|
|
sl@0
|
16 |
0 0 99 111 123 103 107 125 105 111 123
|
|
sl@0
|
17 |
1 99 0 12 24 4 8 26 6 12 24
|
|
sl@0
|
18 |
2 111 12 0 12 16 20 24 18 24 26
|
|
sl@0
|
19 |
3 123 24 12 0 28 30 12 30 26 14
|
|
sl@0
|
20 |
4 103 4 16 28 0 4 22 2 8 20
|
|
sl@0
|
21 |
5 107 8 20 30 4 0 18 6 4 16
|
|
sl@0
|
22 |
6 125 26 24 12 22 18 0 24 14 2
|
|
sl@0
|
23 |
7 105 6 18 30 2 6 24 0 10 22
|
|
sl@0
|
24 |
8 111 12 24 26 8 4 14 10 0 12
|
|
sl@0
|
25 |
9 123 24 26 14 20 16 2 22 12 0
|
|
sl@0
|
26 |
*/
|
|
sl@0
|
27 |
|
|
sl@0
|
28 |
#include <boost/config.hpp>
|
|
sl@0
|
29 |
#include <fstream>
|
|
sl@0
|
30 |
#include <iostream>
|
|
sl@0
|
31 |
#include <vector>
|
|
sl@0
|
32 |
#include <iomanip>
|
|
sl@0
|
33 |
#include <boost/property_map.hpp>
|
|
sl@0
|
34 |
#include <boost/graph/adjacency_list.hpp>
|
|
sl@0
|
35 |
#include <boost/graph/graphviz.hpp>
|
|
sl@0
|
36 |
#include <boost/graph/johnson_all_pairs_shortest.hpp>
|
|
sl@0
|
37 |
#ifdef __SYMBIAN32__
|
|
sl@0
|
38 |
#include "std_log_result.h"
|
|
sl@0
|
39 |
#define LOG_FILENAME_LINE __FILE__, __LINE__
|
|
sl@0
|
40 |
#endif
|
|
sl@0
|
41 |
int main()
|
|
sl@0
|
42 |
{
|
|
sl@0
|
43 |
using namespace boost;
|
|
sl@0
|
44 |
typedef adjacency_list<vecS, vecS, undirectedS, no_property,
|
|
sl@0
|
45 |
property< edge_weight_t, int,
|
|
sl@0
|
46 |
property< edge_weight2_t, int > > > Graph;
|
|
sl@0
|
47 |
const int V = 10;
|
|
sl@0
|
48 |
typedef std::pair < int, int >Edge;
|
|
sl@0
|
49 |
Edge edge_array[] =
|
|
sl@0
|
50 |
{ Edge(0,1), Edge(1,2), Edge(2,3), Edge(1,4), Edge(2,5), Edge(3,6),
|
|
sl@0
|
51 |
Edge(4,5), Edge(5,6), Edge(4,7), Edge(5,8), Edge(6,9), Edge(7,8),
|
|
sl@0
|
52 |
Edge(8,9)
|
|
sl@0
|
53 |
};
|
|
sl@0
|
54 |
|
|
sl@0
|
55 |
const std::size_t E = sizeof(edge_array) / sizeof(Edge);
|
|
sl@0
|
56 |
|
|
sl@0
|
57 |
Graph g(edge_array, edge_array + E, V);
|
|
sl@0
|
58 |
|
|
sl@0
|
59 |
|
|
sl@0
|
60 |
property_map < Graph, edge_weight_t >::type w = get(edge_weight, g);
|
|
sl@0
|
61 |
int weights[] = { 99, 12, 12, 4, 99, 12, 4, 99, 2, 4, 2, 99, 12 };
|
|
sl@0
|
62 |
int *wp = weights;
|
|
sl@0
|
63 |
|
|
sl@0
|
64 |
graph_traits < Graph >::edge_iterator e, e_end;
|
|
sl@0
|
65 |
for (boost::tie(e, e_end) = edges(g); e != e_end; ++e)
|
|
sl@0
|
66 |
w[*e] = *wp++;
|
|
sl@0
|
67 |
|
|
sl@0
|
68 |
std::vector < int >d(V, (std::numeric_limits < int >::max)());
|
|
sl@0
|
69 |
int D[V][V];
|
|
sl@0
|
70 |
johnson_all_pairs_shortest_paths(g, D, distance_map(&d[0]));
|
|
sl@0
|
71 |
|
|
sl@0
|
72 |
std::cout << std::setw(5) <<" ";
|
|
sl@0
|
73 |
for (int k = 0; k < 10; ++k)
|
|
sl@0
|
74 |
std::cout << std::setw(5) << k ;
|
|
sl@0
|
75 |
std::cout << std::endl;
|
|
sl@0
|
76 |
for (int i = 0; i < 10; ++i) {
|
|
sl@0
|
77 |
std::cout <<std::setw(5) << i ;
|
|
sl@0
|
78 |
for (int j = 0; j < 10; ++j) {
|
|
sl@0
|
79 |
std::cout << std::setw(5) << D[i][j] ;
|
|
sl@0
|
80 |
}
|
|
sl@0
|
81 |
std::cout << std::endl;
|
|
sl@0
|
82 |
}
|
|
sl@0
|
83 |
|
|
sl@0
|
84 |
|
|
sl@0
|
85 |
#ifdef __SYMBIAN32__
|
|
sl@0
|
86 |
std_log(LOG_FILENAME_LINE,"[End Test Case ]");
|
|
sl@0
|
87 |
|
|
sl@0
|
88 |
testResultXml("johnson-test");
|
|
sl@0
|
89 |
close_log_file();
|
|
sl@0
|
90 |
#endif
|
|
sl@0
|
91 |
return 0;
|
|
sl@0
|
92 |
}
|