test/all_pairs_shortest_path_test.cc
author kpeter
Thu, 13 Nov 2008 15:29:04 +0000
changeset 2629 84354c78b068
parent 2553 bfced05fa852
permissions -rw-r--r--
Improved constructors for min cost flow classes
Removing the non-zero lower bounds is faster
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2008
     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 <lemon/math.h>
    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/path.h>
    33 
    34 #include <lemon/time_measure.h>
    35 #include "test_tools.h"
    36 
    37 using namespace lemon;
    38 using namespace std;
    39 
    40 int main(int argc, const char *argv[]) {
    41   typedef SmartGraph Graph;
    42   typedef Graph::Node Node;
    43   typedef Graph::Edge Edge;
    44   typedef Graph::NodeIt NodeIt;
    45   typedef Graph::EdgeIt EdgeIt;
    46 
    47   typedef Graph::EdgeMap<int> LengthMap;
    48   typedef Graph::NodeMap<int> DistMap;
    49 
    50   const int n = argc > 1 ? atoi(argv[1]) : 20;
    51   const int e = argc > 2 ? atoi(argv[2]) : int(n * log(double(n)));
    52   const int m = argc > 3 ? atoi(argv[3]) : 100;
    53 
    54   Graph graph;
    55   LengthMap length(graph);
    56   vector<Node> nodes;
    57   
    58   DistMap shift(graph);
    59   for (int i = 0; i < n; ++i) {
    60     Node node = graph.addNode();
    61     nodes.push_back(node);
    62     shift[node] = rnd[m];
    63   }
    64 
    65   for (int i = 0; i < e; ++i) {
    66     int s = rnd[n];
    67     int t = rnd[n];
    68     Edge edge = graph.addEdge(nodes[s], nodes[t]);
    69     length[edge] = rnd[m] - shift[nodes[s]] + shift[nodes[t]];
    70   }
    71 
    72   Johnson<Graph, LengthMap> johnson(graph, length);
    73   {
    74     Timer timer;
    75     johnson.run();
    76     cout << "Johnson: " << timer << endl;
    77   }
    78 
    79   typedef FibHeap<int, Graph::NodeMap<int> > IntFibHeap;
    80   Johnson<Graph, LengthMap>::DefStandardHeap<IntFibHeap>
    81     ::Create fibJohnson(graph, length);
    82   {
    83     Timer timer;
    84     fibJohnson.run();
    85     cout << "Johnson with fibonacci heap: " << timer << endl;
    86   }
    87 
    88   FloydWarshall<Graph, LengthMap> floyd(graph, length);
    89   {
    90     Timer timer;
    91     floyd.run();
    92     cout << "FloydWarshall: " << timer << endl;
    93   }    
    94 
    95   bool checked_path = false;
    96 
    97   for (NodeIt it(graph); it != INVALID; ++it) {
    98     for (NodeIt jt(graph); jt != INVALID; ++jt) {
    99       check(johnson.connected(it, jt) == floyd.connected(it, jt),
   100 	    "Wrong connection in all pairs shortest path");
   101       check(johnson.connected(it, jt) == fibJohnson.connected(it, jt),
   102 	    "Wrong connection in all pairs shortest path");
   103       if (johnson.connected(it, jt)) {
   104         if (it != jt && !checked_path) {
   105           {
   106             Path<Graph> path = johnson.path(it, jt);
   107             check(checkPath(graph, path), "Wrong path.");
   108             check(pathSource(graph, path) == it, "Wrong path.");
   109             check(pathTarget(graph, path) == jt, "Wrong path.");
   110           }
   111           {
   112             Path<Graph> path = floyd.path(it, jt);
   113             check(checkPath(graph, path), "Wrong path.");
   114             check(pathSource(graph, path) == it, "Wrong path.");
   115             check(pathTarget(graph, path) == jt, "Wrong path.");
   116           }
   117           checked_path = true;
   118           std::cout << "Path checked" << std::endl;
   119         }
   120 	check(johnson.dist(it, jt) == floyd.dist(it, jt),
   121 	      "Wrong distance in all pairs shortest path");
   122 	check(johnson.dist(it, jt) == fibJohnson.dist(it, jt),
   123 	      "Wrong distance in all pairs shortest path");
   124 	if (it != jt) {
   125  	  check(johnson.dist(it, jt) == 
   126 		johnson.dist(it, johnson.predNode(it, jt)) +
   127 		length[johnson.predEdge(it, jt)],
   128 		"Wrong edge in all pairs shortest path");
   129  	  check(fibJohnson.dist(it, jt) == 
   130 		fibJohnson.dist(it, fibJohnson.predNode(it, jt)) +
   131 		length[fibJohnson.predEdge(it, jt)],
   132 		"Wrong edge in all pairs shortest path");
   133 	  check(floyd.dist(it, jt) == 
   134 		floyd.dist(it, floyd.predNode(it, jt)) +
   135 		length[floyd.predEdge(it, jt)],
   136 		"Wrong edge in all pairs shortest path");
   137 	}
   138       }
   139     }
   140   }
   141 
   142   return 0;
   143 }