# HG changeset patch
# User deba
# Date 1128592643 0
# Node ID 1d09b48e8d550962e86b6f2b10e226d0ef934f73
# Parent  f531c16dd923027008ea198b8456ccc11677f174
All pairs shortest path test

diff -r f531c16dd923 -r 1d09b48e8d55 test/Makefile.am
--- a/test/Makefile.am	Thu Oct 06 09:37:53 2005 +0000
+++ b/test/Makefile.am	Thu Oct 06 09:57:23 2005 +0000
@@ -1,4 +1,4 @@
-AM_CPPFLAGS = -I$(top_srcdir)
+AM_CPPFLAGS = -I$(top_srcdir) -fno-inline
 LDADD = $(top_builddir)/lemon/libemon.la
 
 EXTRA_DIST = preflow_graph.dim dijkstra_test.lgf
@@ -12,6 +12,7 @@
 	heap_test.h
 
 check_PROGRAMS = \
+	all_pairs_shortest_path_test \
 	bfs_test \
 	dfs_test \
 	dijkstra_test \
@@ -44,6 +45,7 @@
 TESTS = $(check_PROGRAMS)
 XFAIL_TESTS = test_tools_fail$(EXEEXT)
 
+all_pairs_shortest_path_test_SOURCES = all_pairs_shortest_path_test.cc
 bfs_test_SOURCES = bfs_test.cc
 dfs_test_SOURCES = dfs_test.cc
 dijkstra_test_SOURCES = dijkstra_test.cc
diff -r f531c16dd923 -r 1d09b48e8d55 test/all_pairs_shortest_path_test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/all_pairs_shortest_path_test.cc	Thu Oct 06 09:57:23 2005 +0000
@@ -0,0 +1,83 @@
+#include <iostream>
+#include <vector>
+
+#include <cmath>
+#include <cstdlib>
+
+#include <lemon/smart_graph.h>
+#include <lemon/dijkstra.h>
+#include <lemon/floyd_warshall.h>
+#include <lemon/johnson.h>
+
+#include <lemon/time_measure.h>
+
+using namespace lemon;
+using namespace std;
+
+int main(int argc, const char *argv[]) {
+  srand(time(0));
+  typedef SmartGraph Graph;
+  typedef Graph::Node Node;
+  typedef Graph::Edge Edge;
+  typedef Graph::NodeIt NodeIt;
+  typedef Graph::EdgeIt EdgeIt;
+
+  typedef Graph::EdgeMap<double> LengthMap;
+  typedef Graph::NodeMap<double> DistMap;
+
+  const int n = argc > 1 ? atoi(argv[1]) : 20;
+  const int e = argc > 2 ? atoi(argv[2]) : (int)(n * log(n));
+  const double m = argc > 3 ? (double)atoi(argv[3]) : 100.0;
+
+  Graph graph;
+  LengthMap length(graph);
+  vector<Node> nodes;
+  
+  DistMap shift(graph);
+  for (int i = 0; i < n; ++i) {
+    Node node = graph.addNode();
+    nodes.push_back(node);
+    shift[node] = m * (double)rand() / (RAND_MAX + 1.0);
+  }
+
+  for (int i = 0; i < e; ++i) {
+    int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
+    int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
+    double c = m * (double)rand() / (RAND_MAX + 1.0);
+    Edge edge = graph.addEdge(nodes[s], nodes[t]);
+    length[edge] = c - shift[nodes[s]] + shift[nodes[t]];
+  }
+
+  Johnson<Graph, LengthMap> johnson(graph, length);
+  {
+    Timer timer;
+    johnson.run();
+    cout << "Johnson: " << timer << endl;
+  }
+
+  FloydWarshall<Graph, LengthMap> floyd(graph, length);
+  {
+    Timer timer;
+    floyd.run();
+    cout << "FloydWarshall: " << timer << endl;
+  }    
+
+  for (NodeIt it(graph); it != INVALID; ++it) {
+    for (NodeIt jt(graph); jt != INVALID; ++jt) {
+      assert(johnson.connected(it, jt) == floyd.connected(it, jt));
+      if (johnson.connected(it, jt)) {
+	assert(johnson.dist(it, jt) == floyd.dist(it, jt));
+	if (it != jt) {
+ 	  assert(johnson.dist(it, jt) == 
+ 		 johnson.dist(it, johnson.predNode(it, jt)) +
+ 		 length[johnson.pred(it, jt)]);
+	  assert(floyd.dist(it, jt) == 
+		 floyd.dist(it, floyd.predNode(it, jt)) +
+		 length[floyd.pred(it, jt)]);
+	}
+      }
+    }
+  }
+
+  return 0;
+}