1.1 --- a/test/Makefile.am	Thu Oct 06 09:37:53 2005 +0000
     1.2 +++ b/test/Makefile.am	Thu Oct 06 09:57:23 2005 +0000
     1.3 @@ -1,4 +1,4 @@
     1.4 -AM_CPPFLAGS = -I$(top_srcdir)
     1.5 +AM_CPPFLAGS = -I$(top_srcdir) -fno-inline
     1.6  LDADD = $(top_builddir)/lemon/libemon.la
     1.7  
     1.8  EXTRA_DIST = preflow_graph.dim dijkstra_test.lgf
     1.9 @@ -12,6 +12,7 @@
    1.10  	heap_test.h
    1.11  
    1.12  check_PROGRAMS = \
    1.13 +	all_pairs_shortest_path_test \
    1.14  	bfs_test \
    1.15  	dfs_test \
    1.16  	dijkstra_test \
    1.17 @@ -44,6 +45,7 @@
    1.18  TESTS = $(check_PROGRAMS)
    1.19  XFAIL_TESTS = test_tools_fail$(EXEEXT)
    1.20  
    1.21 +all_pairs_shortest_path_test_SOURCES = all_pairs_shortest_path_test.cc
    1.22  bfs_test_SOURCES = bfs_test.cc
    1.23  dfs_test_SOURCES = dfs_test.cc
    1.24  dijkstra_test_SOURCES = dijkstra_test.cc

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/test/all_pairs_shortest_path_test.cc	Thu Oct 06 09:57:23 2005 +0000
     2.3 @@ -0,0 +1,83 @@
     2.4 +#include <iostream>
     2.5 +#include <vector>
     2.6 +
     2.7 +#include <cmath>
     2.8 +#include <cstdlib>
     2.9 +
    2.10 +#include <lemon/smart_graph.h>
    2.11 +#include <lemon/dijkstra.h>
    2.12 +#include <lemon/floyd_warshall.h>
    2.13 +#include <lemon/johnson.h>
    2.14 +
    2.15 +#include <lemon/time_measure.h>
    2.16 +
    2.17 +using namespace lemon;
    2.18 +using namespace std;
    2.19 +
    2.20 +int main(int argc, const char *argv[]) {
    2.21 +  srand(time(0));
    2.22 +  typedef SmartGraph Graph;
    2.23 +  typedef Graph::Node Node;
    2.24 +  typedef Graph::Edge Edge;
    2.25 +  typedef Graph::NodeIt NodeIt;
    2.26 +  typedef Graph::EdgeIt EdgeIt;
    2.27 +
    2.28 +  typedef Graph::EdgeMap<double> LengthMap;
    2.29 +  typedef Graph::NodeMap<double> DistMap;
    2.30 +
    2.31 +  const int n = argc > 1 ? atoi(argv[1]) : 20;
    2.32 +  const int e = argc > 2 ? atoi(argv[2]) : (int)(n * log(n));
    2.33 +  const double m = argc > 3 ? (double)atoi(argv[3]) : 100.0;
    2.34 +
    2.35 +  Graph graph;
    2.36 +  LengthMap length(graph);
    2.37 +  vector<Node> nodes;
    2.38 +  
    2.39 +  DistMap shift(graph);
    2.40 +  for (int i = 0; i < n; ++i) {
    2.41 +    Node node = graph.addNode();
    2.42 +    nodes.push_back(node);
    2.43 +    shift[node] = m * (double)rand() / (RAND_MAX + 1.0);
    2.44 +  }
    2.45 +
    2.46 +  for (int i = 0; i < e; ++i) {
    2.47 +    int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
    2.48 +    int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
    2.49 +    double c = m * (double)rand() / (RAND_MAX + 1.0);
    2.50 +    Edge edge = graph.addEdge(nodes[s], nodes[t]);
    2.51 +    length[edge] = c - shift[nodes[s]] + shift[nodes[t]];
    2.52 +  }
    2.53 +
    2.54 +  Johnson<Graph, LengthMap> johnson(graph, length);
    2.55 +  {
    2.56 +    Timer timer;
    2.57 +    johnson.run();
    2.58 +    cout << "Johnson: " << timer << endl;
    2.59 +  }
    2.60 +
    2.61 +  FloydWarshall<Graph, LengthMap> floyd(graph, length);
    2.62 +  {
    2.63 +    Timer timer;
    2.64 +    floyd.run();
    2.65 +    cout << "FloydWarshall: " << timer << endl;
    2.66 +  }    
    2.67 +
    2.68 +  for (NodeIt it(graph); it != INVALID; ++it) {
    2.69 +    for (NodeIt jt(graph); jt != INVALID; ++jt) {
    2.70 +      assert(johnson.connected(it, jt) == floyd.connected(it, jt));
    2.71 +      if (johnson.connected(it, jt)) {
    2.72 +	assert(johnson.dist(it, jt) == floyd.dist(it, jt));
    2.73 +	if (it != jt) {
    2.74 + 	  assert(johnson.dist(it, jt) == 
    2.75 + 		 johnson.dist(it, johnson.predNode(it, jt)) +
    2.76 + 		 length[johnson.pred(it, jt)]);
    2.77 +	  assert(floyd.dist(it, jt) == 
    2.78 +		 floyd.dist(it, floyd.predNode(it, jt)) +
    2.79 +		 length[floyd.pred(it, jt)]);
    2.80 +	}
    2.81 +      }
    2.82 +    }
    2.83 +  }
    2.84 +
    2.85 +  return 0;
    2.86 +}