deba@1711: #include <iostream>
deba@1711: #include <vector>
deba@1711: 
deba@1711: #include <cmath>
deba@1711: #include <cstdlib>
deba@1711: 
deba@1711: #include <lemon/smart_graph.h>
deba@1711: #include <lemon/dijkstra.h>
deba@1711: #include <lemon/floyd_warshall.h>
deba@1711: #include <lemon/johnson.h>
deba@1711: 
deba@1711: #include <lemon/time_measure.h>
deba@1711: 
deba@1711: using namespace lemon;
deba@1711: using namespace std;
deba@1711: 
deba@1711: int main(int argc, const char *argv[]) {
deba@1711:   srand(time(0));
deba@1711:   typedef SmartGraph Graph;
deba@1711:   typedef Graph::Node Node;
deba@1711:   typedef Graph::Edge Edge;
deba@1711:   typedef Graph::NodeIt NodeIt;
deba@1711:   typedef Graph::EdgeIt EdgeIt;
deba@1711: 
deba@1711:   typedef Graph::EdgeMap<double> LengthMap;
deba@1711:   typedef Graph::NodeMap<double> DistMap;
deba@1711: 
deba@1711:   const int n = argc > 1 ? atoi(argv[1]) : 20;
deba@1711:   const int e = argc > 2 ? atoi(argv[2]) : (int)(n * log(n));
deba@1711:   const double m = argc > 3 ? (double)atoi(argv[3]) : 100.0;
deba@1711: 
deba@1711:   Graph graph;
deba@1711:   LengthMap length(graph);
deba@1711:   vector<Node> nodes;
deba@1711:   
deba@1711:   DistMap shift(graph);
deba@1711:   for (int i = 0; i < n; ++i) {
deba@1711:     Node node = graph.addNode();
deba@1711:     nodes.push_back(node);
deba@1711:     shift[node] = m * (double)rand() / (RAND_MAX + 1.0);
deba@1711:   }
deba@1711: 
deba@1711:   for (int i = 0; i < e; ++i) {
deba@1711:     int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
deba@1711:     int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
deba@1711:     double c = m * (double)rand() / (RAND_MAX + 1.0);
deba@1711:     Edge edge = graph.addEdge(nodes[s], nodes[t]);
deba@1711:     length[edge] = c - shift[nodes[s]] + shift[nodes[t]];
deba@1711:   }
deba@1711: 
deba@1711:   Johnson<Graph, LengthMap> johnson(graph, length);
deba@1711:   {
deba@1711:     Timer timer;
deba@1711:     johnson.run();
deba@1711:     cout << "Johnson: " << timer << endl;
deba@1711:   }
deba@1711: 
deba@1711:   FloydWarshall<Graph, LengthMap> floyd(graph, length);
deba@1711:   {
deba@1711:     Timer timer;
deba@1711:     floyd.run();
deba@1711:     cout << "FloydWarshall: " << timer << endl;
deba@1711:   }    
deba@1711: 
deba@1711:   for (NodeIt it(graph); it != INVALID; ++it) {
deba@1711:     for (NodeIt jt(graph); jt != INVALID; ++jt) {
deba@1711:       assert(johnson.connected(it, jt) == floyd.connected(it, jt));
deba@1711:       if (johnson.connected(it, jt)) {
deba@1711: 	assert(johnson.dist(it, jt) == floyd.dist(it, jt));
deba@1711: 	if (it != jt) {
deba@1711:  	  assert(johnson.dist(it, jt) == 
deba@1711:  		 johnson.dist(it, johnson.predNode(it, jt)) +
deba@1711:  		 length[johnson.pred(it, jt)]);
deba@1711: 	  assert(floyd.dist(it, jt) == 
deba@1711: 		 floyd.dist(it, floyd.predNode(it, jt)) +
deba@1711: 		 length[floyd.pred(it, jt)]);
deba@1711: 	}
deba@1711:       }
deba@1711:     }
deba@1711:   }
deba@1711: 
deba@1711:   return 0;
deba@1711: }