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