1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/all_pairs_shortest_path_test.cc Thu Oct 06 09:57:23 2005 +0000
1.3 @@ -0,0 +1,83 @@
1.4 +#include <iostream>
1.5 +#include <vector>
1.6 +
1.7 +#include <cmath>
1.8 +#include <cstdlib>
1.9 +
1.10 +#include <lemon/smart_graph.h>
1.11 +#include <lemon/dijkstra.h>
1.12 +#include <lemon/floyd_warshall.h>
1.13 +#include <lemon/johnson.h>
1.14 +
1.15 +#include <lemon/time_measure.h>
1.16 +
1.17 +using namespace lemon;
1.18 +using namespace std;
1.19 +
1.20 +int main(int argc, const char *argv[]) {
1.21 + srand(time(0));
1.22 + typedef SmartGraph Graph;
1.23 + typedef Graph::Node Node;
1.24 + typedef Graph::Edge Edge;
1.25 + typedef Graph::NodeIt NodeIt;
1.26 + typedef Graph::EdgeIt EdgeIt;
1.27 +
1.28 + typedef Graph::EdgeMap<double> LengthMap;
1.29 + typedef Graph::NodeMap<double> DistMap;
1.30 +
1.31 + const int n = argc > 1 ? atoi(argv[1]) : 20;
1.32 + const int e = argc > 2 ? atoi(argv[2]) : (int)(n * log(n));
1.33 + const double m = argc > 3 ? (double)atoi(argv[3]) : 100.0;
1.34 +
1.35 + Graph graph;
1.36 + LengthMap length(graph);
1.37 + vector<Node> nodes;
1.38 +
1.39 + DistMap shift(graph);
1.40 + for (int i = 0; i < n; ++i) {
1.41 + Node node = graph.addNode();
1.42 + nodes.push_back(node);
1.43 + shift[node] = m * (double)rand() / (RAND_MAX + 1.0);
1.44 + }
1.45 +
1.46 + for (int i = 0; i < e; ++i) {
1.47 + int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
1.48 + int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
1.49 + double c = m * (double)rand() / (RAND_MAX + 1.0);
1.50 + Edge edge = graph.addEdge(nodes[s], nodes[t]);
1.51 + length[edge] = c - shift[nodes[s]] + shift[nodes[t]];
1.52 + }
1.53 +
1.54 + Johnson<Graph, LengthMap> johnson(graph, length);
1.55 + {
1.56 + Timer timer;
1.57 + johnson.run();
1.58 + cout << "Johnson: " << timer << endl;
1.59 + }
1.60 +
1.61 + FloydWarshall<Graph, LengthMap> floyd(graph, length);
1.62 + {
1.63 + Timer timer;
1.64 + floyd.run();
1.65 + cout << "FloydWarshall: " << timer << endl;
1.66 + }
1.67 +
1.68 + for (NodeIt it(graph); it != INVALID; ++it) {
1.69 + for (NodeIt jt(graph); jt != INVALID; ++jt) {
1.70 + assert(johnson.connected(it, jt) == floyd.connected(it, jt));
1.71 + if (johnson.connected(it, jt)) {
1.72 + assert(johnson.dist(it, jt) == floyd.dist(it, jt));
1.73 + if (it != jt) {
1.74 + assert(johnson.dist(it, jt) ==
1.75 + johnson.dist(it, johnson.predNode(it, jt)) +
1.76 + length[johnson.pred(it, jt)]);
1.77 + assert(floyd.dist(it, jt) ==
1.78 + floyd.dist(it, floyd.predNode(it, jt)) +
1.79 + length[floyd.pred(it, jt)]);
1.80 + }
1.81 + }
1.82 + }
1.83 + }
1.84 +
1.85 + return 0;
1.86 +}