COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/all_pairs_shortest_path_test.cc @ 1732:edeee3cbd80c

Last change on this file since 1732:edeee3cbd80c was 1732:edeee3cbd80c, checked in by Balazs Dezso, 14 years ago

Bugfix

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