test/all_pairs_shortest_path_test.cc
author deba
Tue, 31 Oct 2006 14:27:58 +0000
changeset 2282 9d7b12f83daa
parent 2242 16523135943d
child 2335 27aa03cd3121
permissions -rw-r--r--
Bug fixes
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2006
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #include <iostream>
    20 #include <vector>
    21 
    22 #include <cmath>
    23 #include <cstdlib>
    24 
    25 #include <lemon/smart_graph.h>
    26 #include <lemon/dijkstra.h>
    27 #include <lemon/floyd_warshall.h>
    28 #include <lemon/johnson.h>
    29 
    30 #include <lemon/fib_heap.h>
    31 
    32 #include <lemon/time_measure.h>
    33 #include "test_tools.h"
    34 
    35 using namespace lemon;
    36 using namespace std;
    37 
    38 int main(int argc, const char *argv[]) {
    39   typedef SmartGraph Graph;
    40   typedef Graph::Node Node;
    41   typedef Graph::Edge Edge;
    42   typedef Graph::NodeIt NodeIt;
    43   typedef Graph::EdgeIt EdgeIt;
    44 
    45   typedef Graph::EdgeMap<int> LengthMap;
    46   typedef Graph::NodeMap<int> DistMap;
    47 
    48   const int n = argc > 1 ? atoi(argv[1]) : 20;
    49   const int e = argc > 2 ? atoi(argv[2]) : (int)(n * log((double)n));
    50   const int m = argc > 3 ? atoi(argv[3]) : 100;
    51 
    52   Graph graph;
    53   LengthMap length(graph);
    54   vector<Node> nodes;
    55   
    56   DistMap shift(graph);
    57   for (int i = 0; i < n; ++i) {
    58     Node node = graph.addNode();
    59     nodes.push_back(node);
    60     shift[node] = rnd[m];
    61   }
    62 
    63   for (int i = 0; i < e; ++i) {
    64     int s = rnd[n];
    65     int t = rnd[n];
    66     Edge edge = graph.addEdge(nodes[s], nodes[t]);
    67     length[edge] = rnd[m] - shift[nodes[s]] + shift[nodes[t]];
    68   }
    69 
    70   Johnson<Graph, LengthMap> johnson(graph, length);
    71   {
    72     Timer timer;
    73     johnson.run();
    74     cout << "Johnson: " << timer << endl;
    75   }
    76 
    77   typedef FibHeap<int, Graph::NodeMap<int> > IntFibHeap;
    78   Johnson<Graph, LengthMap>::DefStandardHeap<IntFibHeap>
    79     ::Create fibJohnson(graph, length);
    80   {
    81     Timer timer;
    82     fibJohnson.run();
    83     cout << "Johnson with fibonacci heap: " << timer << endl;
    84   }
    85 
    86   FloydWarshall<Graph, LengthMap> floyd(graph, length);
    87   {
    88     Timer timer;
    89     floyd.run();
    90     cout << "FloydWarshall: " << timer << endl;
    91   }    
    92 
    93   for (NodeIt it(graph); it != INVALID; ++it) {
    94     for (NodeIt jt(graph); jt != INVALID; ++jt) {
    95       check(johnson.connected(it, jt) == floyd.connected(it, jt),
    96 	    "Wrong connection in all pairs shortest path");
    97       check(johnson.connected(it, jt) == fibJohnson.connected(it, jt),
    98 	    "Wrong connection in all pairs shortest path");
    99       if (johnson.connected(it, jt)) {
   100 	check(johnson.dist(it, jt) == floyd.dist(it, jt),
   101 	      "Wrong distance in all pairs shortest path");
   102 	check(johnson.dist(it, jt) == fibJohnson.dist(it, jt),
   103 	      "Wrong distance in all pairs shortest path");
   104 	if (it != jt) {
   105  	  check(johnson.dist(it, jt) == 
   106 		johnson.dist(it, johnson.predNode(it, jt)) +
   107 		length[johnson.predEdge(it, jt)],
   108 		"Wrong edge in all pairs shortest path");
   109  	  check(fibJohnson.dist(it, jt) == 
   110 		fibJohnson.dist(it, fibJohnson.predNode(it, jt)) +
   111 		length[fibJohnson.predEdge(it, jt)],
   112 		"Wrong edge in all pairs shortest path");
   113 	  check(floyd.dist(it, jt) == 
   114 		floyd.dist(it, floyd.predNode(it, jt)) +
   115 		length[floyd.predEdge(it, jt)],
   116 		"Wrong edge in all pairs shortest path");
   117 	}
   118       }
   119     }
   120   }
   121 
   122   return 0;
   123 }