COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/all_pairs_shortest_path_test.cc @ 2391:14a343be7a5a

Last change on this file since 2391:14a343be7a5a was 2391:14a343be7a5a, checked in by Alpar Juttner, 17 years ago

Happy New Year to all source files!

File size: 4.1 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#include <iostream>
20#include <vector>
21
22#include <cmath>
23#include <cstdlib>
24
25#include <lemon/smart_graph.h>
26#include <lemon/dijkstra.h>
27#include <lemon/floyd_warshall.h>
28#include <lemon/johnson.h>
29
30#include <lemon/fib_heap.h>
31
32#include <lemon/path.h>
33
34#include <lemon/time_measure.h>
35#include "test_tools.h"
36
37using namespace lemon;
38using namespace std;
39
40int main(int argc, const char *argv[]) {
41  typedef SmartGraph Graph;
42  typedef Graph::Node Node;
43  typedef Graph::Edge Edge;
44  typedef Graph::NodeIt NodeIt;
45  typedef Graph::EdgeIt EdgeIt;
46
47  typedef Graph::EdgeMap<int> LengthMap;
48  typedef Graph::NodeMap<int> DistMap;
49
50  const int n = argc > 1 ? atoi(argv[1]) : 20;
51  const int e = argc > 2 ? atoi(argv[2]) : int(n * log(double(n)));
52  const int m = argc > 3 ? atoi(argv[3]) : 100;
53
54  Graph graph;
55  LengthMap length(graph);
56  vector<Node> nodes;
57 
58  DistMap shift(graph);
59  for (int i = 0; i < n; ++i) {
60    Node node = graph.addNode();
61    nodes.push_back(node);
62    shift[node] = rnd[m];
63  }
64
65  for (int i = 0; i < e; ++i) {
66    int s = rnd[n];
67    int t = rnd[n];
68    Edge edge = graph.addEdge(nodes[s], nodes[t]);
69    length[edge] = rnd[m] - shift[nodes[s]] + shift[nodes[t]];
70  }
71
72  Johnson<Graph, LengthMap> johnson(graph, length);
73  {
74    Timer timer;
75    johnson.run();
76    cout << "Johnson: " << timer << endl;
77  }
78
79  typedef FibHeap<int, Graph::NodeMap<int> > IntFibHeap;
80  Johnson<Graph, LengthMap>::DefStandardHeap<IntFibHeap>
81    ::Create fibJohnson(graph, length);
82  {
83    Timer timer;
84    fibJohnson.run();
85    cout << "Johnson with fibonacci heap: " << timer << endl;
86  }
87
88  FloydWarshall<Graph, LengthMap> floyd(graph, length);
89  {
90    Timer timer;
91    floyd.run();
92    cout << "FloydWarshall: " << timer << endl;
93  }   
94
95  bool checked_path = false;
96
97  for (NodeIt it(graph); it != INVALID; ++it) {
98    for (NodeIt jt(graph); jt != INVALID; ++jt) {
99      check(johnson.connected(it, jt) == floyd.connected(it, jt),
100            "Wrong connection in all pairs shortest path");
101      check(johnson.connected(it, jt) == fibJohnson.connected(it, jt),
102            "Wrong connection in all pairs shortest path");
103      if (johnson.connected(it, jt)) {
104        if (it != jt && !checked_path) {
105          {
106            Path<Graph> path = johnson.path(it, jt);
107            check(checkPath(graph, path), "Wrong path.");
108            check(pathSource(graph, path) == it, "Wrong path.");
109            check(pathTarget(graph, path) == jt, "Wrong path.");
110          }
111          {
112            Path<Graph> path = floyd.path(it, jt);
113            check(checkPath(graph, path), "Wrong path.");
114            check(pathSource(graph, path) == it, "Wrong path.");
115            check(pathTarget(graph, path) == jt, "Wrong path.");
116          }
117          checked_path = true;
118          std::cout << "Path checked" << std::endl;
119        }
120        check(johnson.dist(it, jt) == floyd.dist(it, jt),
121              "Wrong distance in all pairs shortest path");
122        check(johnson.dist(it, jt) == fibJohnson.dist(it, jt),
123              "Wrong distance in all pairs shortest path");
124        if (it != jt) {
125          check(johnson.dist(it, jt) ==
126                johnson.dist(it, johnson.predNode(it, jt)) +
127                length[johnson.predEdge(it, jt)],
128                "Wrong edge in all pairs shortest path");
129          check(fibJohnson.dist(it, jt) ==
130                fibJohnson.dist(it, fibJohnson.predNode(it, jt)) +
131                length[fibJohnson.predEdge(it, jt)],
132                "Wrong edge in all pairs shortest path");
133          check(floyd.dist(it, jt) ==
134                floyd.dist(it, floyd.predNode(it, jt)) +
135                length[floyd.predEdge(it, jt)],
136                "Wrong edge in all pairs shortest path");
137        }
138      }
139    }
140  }
141
142  return 0;
143}
Note: See TracBrowser for help on using the repository browser.