COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/all_pairs_shortest_path_test.cc @ 1711:1d09b48e8d55

Last change on this file since 1711:1d09b48e8d55 was 1711:1d09b48e8d55, checked in by Balazs Dezso, 14 years ago

All pairs shortest path test

File size: 2.1 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/time_measure.h>
13
14using namespace lemon;
15using namespace std;
16
17int main(int argc, const char *argv[]) {
18  srand(time(0));
19  typedef SmartGraph Graph;
20  typedef Graph::Node Node;
21  typedef Graph::Edge Edge;
22  typedef Graph::NodeIt NodeIt;
23  typedef Graph::EdgeIt EdgeIt;
24
25  typedef Graph::EdgeMap<double> LengthMap;
26  typedef Graph::NodeMap<double> DistMap;
27
28  const int n = argc > 1 ? atoi(argv[1]) : 20;
29  const int e = argc > 2 ? atoi(argv[2]) : (int)(n * log(n));
30  const double m = argc > 3 ? (double)atoi(argv[3]) : 100.0;
31
32  Graph graph;
33  LengthMap length(graph);
34  vector<Node> nodes;
35 
36  DistMap shift(graph);
37  for (int i = 0; i < n; ++i) {
38    Node node = graph.addNode();
39    nodes.push_back(node);
40    shift[node] = m * (double)rand() / (RAND_MAX + 1.0);
41  }
42
43  for (int i = 0; i < e; ++i) {
44    int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
45    int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
46    double c = m * (double)rand() / (RAND_MAX + 1.0);
47    Edge edge = graph.addEdge(nodes[s], nodes[t]);
48    length[edge] = c - shift[nodes[s]] + shift[nodes[t]];
49  }
50
51  Johnson<Graph, LengthMap> johnson(graph, length);
52  {
53    Timer timer;
54    johnson.run();
55    cout << "Johnson: " << timer << endl;
56  }
57
58  FloydWarshall<Graph, LengthMap> floyd(graph, length);
59  {
60    Timer timer;
61    floyd.run();
62    cout << "FloydWarshall: " << timer << endl;
63  }   
64
65  for (NodeIt it(graph); it != INVALID; ++it) {
66    for (NodeIt jt(graph); jt != INVALID; ++jt) {
67      assert(johnson.connected(it, jt) == floyd.connected(it, jt));
68      if (johnson.connected(it, jt)) {
69        assert(johnson.dist(it, jt) == floyd.dist(it, jt));
70        if (it != jt) {
71          assert(johnson.dist(it, jt) ==
72                 johnson.dist(it, johnson.predNode(it, jt)) +
73                 length[johnson.pred(it, jt)]);
74          assert(floyd.dist(it, jt) ==
75                 floyd.dist(it, floyd.predNode(it, jt)) +
76                 length[floyd.pred(it, jt)]);
77        }
78      }
79    }
80  }
81
82  return 0;
83}
Note: See TracBrowser for help on using the repository browser.