alpar@1956: /* -*- C++ -*-
alpar@1956:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@2553:  * Copyright (C) 2003-2008
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1956:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@1956:  *
alpar@1956:  * Permission to use, modify and distribute this software is granted
alpar@1956:  * provided that this copyright notice appears in all copies. For
alpar@1956:  * precise terms see the accompanying LICENSE file.
alpar@1956:  *
alpar@1956:  * This software is provided "AS IS" with no warranty of any kind,
alpar@1956:  * express or implied, and with no claim as to its suitability for any
alpar@1956:  * purpose.
alpar@1956:  *
alpar@1956:  */
alpar@1956: 
deba@1711: #include <iostream>
deba@1711: #include <vector>
deba@1711: 
alpar@2569: #include <lemon/math.h>
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@1745: #include <lemon/fib_heap.h>
deba@1745: 
deba@2335: #include <lemon/path.h>
deba@2335: 
deba@1711: #include <lemon/time_measure.h>
deba@1732: #include "test_tools.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:   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@2242:   typedef Graph::EdgeMap<int> LengthMap;
deba@2242:   typedef Graph::NodeMap<int> DistMap;
deba@1711: 
deba@1711:   const int n = argc > 1 ? atoi(argv[1]) : 20;
deba@2386:   const int e = argc > 2 ? atoi(argv[2]) : int(n * log(double(n)));
deba@2242:   const int m = argc > 3 ? atoi(argv[3]) : 100;
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@2242:     shift[node] = rnd[m];
deba@1711:   }
deba@1711: 
deba@1711:   for (int i = 0; i < e; ++i) {
deba@2242:     int s = rnd[n];
deba@2242:     int t = rnd[n];
deba@1711:     Edge edge = graph.addEdge(nodes[s], nodes[t]);
deba@2242:     length[edge] = rnd[m] - 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@2269:   typedef FibHeap<int, Graph::NodeMap<int> > IntFibHeap;
deba@2242:   Johnson<Graph, LengthMap>::DefStandardHeap<IntFibHeap>
deba@1745:     ::Create fibJohnson(graph, length);
deba@1745:   {
deba@1745:     Timer timer;
deba@1745:     fibJohnson.run();
deba@1745:     cout << "Johnson with fibonacci heap: " << timer << endl;
deba@1745:   }
deba@1745: 
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@2335:   bool checked_path = false;
deba@2335: 
deba@1711:   for (NodeIt it(graph); it != INVALID; ++it) {
deba@1711:     for (NodeIt jt(graph); jt != INVALID; ++jt) {
deba@1732:       check(johnson.connected(it, jt) == floyd.connected(it, jt),
deba@1732: 	    "Wrong connection in all pairs shortest path");
deba@1745:       check(johnson.connected(it, jt) == fibJohnson.connected(it, jt),
deba@1745: 	    "Wrong connection in all pairs shortest path");
deba@1711:       if (johnson.connected(it, jt)) {
deba@2335:         if (it != jt && !checked_path) {
deba@2335:           {
deba@2335:             Path<Graph> path = johnson.path(it, jt);
deba@2335:             check(checkPath(graph, path), "Wrong path.");
deba@2335:             check(pathSource(graph, path) == it, "Wrong path.");
deba@2335:             check(pathTarget(graph, path) == jt, "Wrong path.");
deba@2335:           }
deba@2335:           {
deba@2335:             Path<Graph> path = floyd.path(it, jt);
deba@2335:             check(checkPath(graph, path), "Wrong path.");
deba@2335:             check(pathSource(graph, path) == it, "Wrong path.");
deba@2335:             check(pathTarget(graph, path) == jt, "Wrong path.");
deba@2335:           }
deba@2335:           checked_path = true;
deba@2335:           std::cout << "Path checked" << std::endl;
deba@2335:         }
deba@1732: 	check(johnson.dist(it, jt) == floyd.dist(it, jt),
deba@1732: 	      "Wrong distance in all pairs shortest path");
deba@1745: 	check(johnson.dist(it, jt) == fibJohnson.dist(it, jt),
deba@1745: 	      "Wrong distance in all pairs shortest path");
deba@1711: 	if (it != jt) {
deba@1732:  	  check(johnson.dist(it, jt) == 
deba@1732: 		johnson.dist(it, johnson.predNode(it, jt)) +
deba@1763: 		length[johnson.predEdge(it, jt)],
deba@1732: 		"Wrong edge in all pairs shortest path");
deba@1745:  	  check(fibJohnson.dist(it, jt) == 
deba@1745: 		fibJohnson.dist(it, fibJohnson.predNode(it, jt)) +
deba@1763: 		length[fibJohnson.predEdge(it, jt)],
deba@1745: 		"Wrong edge in all pairs shortest path");
deba@1732: 	  check(floyd.dist(it, jt) == 
deba@1732: 		floyd.dist(it, floyd.predNode(it, jt)) +
deba@1763: 		length[floyd.predEdge(it, jt)],
deba@1732: 		"Wrong edge in all pairs shortest path");
deba@1711: 	}
deba@1711:       }
deba@1711:     }
deba@1711:   }
deba@1711: 
deba@1711:   return 0;
deba@1711: }