COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/all_pairs_shortest_path_test.cc @ 1823:cb082cdf3667

Last change on this file since 1823:cb082cdf3667 was 1763:49045f2d28d4, checked in by Balazs Dezso, 18 years ago

pred => predEdge rename

File size: 3.0 KB
Line 
1#include <iostream>
2#include <vector>
3
4#include <cmath>
5#include <cstdlib>
6
7#include <lemon/smart_graph.h>
8#include <lemon/dijkstra.h>
9#include <lemon/floyd_warshall.h>
10#include <lemon/johnson.h>
11
12#include <lemon/fib_heap.h>
13
14#include <lemon/time_measure.h>
15#include "test_tools.h"
16
17using namespace lemon;
18using namespace std;
19
20int main(int argc, const char *argv[]) {
21  srand(time(0));
22  typedef SmartGraph Graph;
23  typedef Graph::Node Node;
24  typedef Graph::Edge Edge;
25  typedef Graph::NodeIt NodeIt;
26  typedef Graph::EdgeIt EdgeIt;
27
28  typedef Graph::EdgeMap<double> LengthMap;
29  typedef Graph::NodeMap<double> DistMap;
30
31  const int n = argc > 1 ? atoi(argv[1]) : 20;
32  const int e = argc > 2 ? atoi(argv[2]) : (int)(n * log((double)n));
33  const double m = argc > 3 ? (double)atoi(argv[3]) : 100.0;
34
35  Graph graph;
36  LengthMap length(graph);
37  vector<Node> nodes;
38 
39  DistMap shift(graph);
40  for (int i = 0; i < n; ++i) {
41    Node node = graph.addNode();
42    nodes.push_back(node);
43    shift[node] = m * (double)rand() / (RAND_MAX + 1.0);
44  }
45
46  for (int i = 0; i < e; ++i) {
47    int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
48    int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
49    double c = m * (double)rand() / (RAND_MAX + 1.0);
50    Edge edge = graph.addEdge(nodes[s], nodes[t]);
51    length[edge] = c - shift[nodes[s]] + shift[nodes[t]];
52  }
53
54  Johnson<Graph, LengthMap> johnson(graph, length);
55  {
56    Timer timer;
57    johnson.run();
58    cout << "Johnson: " << timer << endl;
59  }
60
61  typedef FibHeap<Node, double, Graph::NodeMap<int> > DoubleFibHeap;
62  Johnson<Graph, LengthMap>::DefStandardHeap<DoubleFibHeap>
63    ::Create fibJohnson(graph, length);
64  {
65    Timer timer;
66    fibJohnson.run();
67    cout << "Johnson with fibonacci heap: " << timer << endl;
68  }
69
70  FloydWarshall<Graph, LengthMap> floyd(graph, length);
71  {
72    Timer timer;
73    floyd.run();
74    cout << "FloydWarshall: " << timer << endl;
75  }   
76
77  for (NodeIt it(graph); it != INVALID; ++it) {
78    for (NodeIt jt(graph); jt != INVALID; ++jt) {
79      check(johnson.connected(it, jt) == floyd.connected(it, jt),
80            "Wrong connection in all pairs shortest path");
81      check(johnson.connected(it, jt) == fibJohnson.connected(it, jt),
82            "Wrong connection in all pairs shortest path");
83      if (johnson.connected(it, jt)) {
84        check(johnson.dist(it, jt) == floyd.dist(it, jt),
85              "Wrong distance in all pairs shortest path");
86        check(johnson.dist(it, jt) == fibJohnson.dist(it, jt),
87              "Wrong distance in all pairs shortest path");
88        if (it != jt) {
89          check(johnson.dist(it, jt) ==
90                johnson.dist(it, johnson.predNode(it, jt)) +
91                length[johnson.predEdge(it, jt)],
92                "Wrong edge in all pairs shortest path");
93          check(fibJohnson.dist(it, jt) ==
94                fibJohnson.dist(it, fibJohnson.predNode(it, jt)) +
95                length[fibJohnson.predEdge(it, jt)],
96                "Wrong edge in all pairs shortest path");
97          check(floyd.dist(it, jt) ==
98                floyd.dist(it, floyd.predNode(it, jt)) +
99                length[floyd.predEdge(it, jt)],
100                "Wrong edge in all pairs shortest path");
101        }
102      }
103    }
104  }
105
106  return 0;
107}
Note: See TracBrowser for help on using the repository browser.