test/all_pairs_shortest_path_test.cc
changeset 1742 2637b9420d0a
parent 1711 1d09b48e8d55
child 1745 d356e54bdafc
equal deleted inserted replaced
0:22e33a6c8e8e 1:974cbccf54dd
     8 #include <lemon/dijkstra.h>
     8 #include <lemon/dijkstra.h>
     9 #include <lemon/floyd_warshall.h>
     9 #include <lemon/floyd_warshall.h>
    10 #include <lemon/johnson.h>
    10 #include <lemon/johnson.h>
    11 
    11 
    12 #include <lemon/time_measure.h>
    12 #include <lemon/time_measure.h>
       
    13 #include "test_tools.h"
    13 
    14 
    14 using namespace lemon;
    15 using namespace lemon;
    15 using namespace std;
    16 using namespace std;
    16 
    17 
    17 int main(int argc, const char *argv[]) {
    18 int main(int argc, const char *argv[]) {
    24 
    25 
    25   typedef Graph::EdgeMap<double> LengthMap;
    26   typedef Graph::EdgeMap<double> LengthMap;
    26   typedef Graph::NodeMap<double> DistMap;
    27   typedef Graph::NodeMap<double> DistMap;
    27 
    28 
    28   const int n = argc > 1 ? atoi(argv[1]) : 20;
    29   const int n = argc > 1 ? atoi(argv[1]) : 20;
    29   const int e = argc > 2 ? atoi(argv[2]) : (int)(n * log(n));
    30   const int e = argc > 2 ? atoi(argv[2]) : (int)(n * log((double)n));
    30   const double m = argc > 3 ? (double)atoi(argv[3]) : 100.0;
    31   const double m = argc > 3 ? (double)atoi(argv[3]) : 100.0;
    31 
    32 
    32   Graph graph;
    33   Graph graph;
    33   LengthMap length(graph);
    34   LengthMap length(graph);
    34   vector<Node> nodes;
    35   vector<Node> nodes;
    62     cout << "FloydWarshall: " << timer << endl;
    63     cout << "FloydWarshall: " << timer << endl;
    63   }    
    64   }    
    64 
    65 
    65   for (NodeIt it(graph); it != INVALID; ++it) {
    66   for (NodeIt it(graph); it != INVALID; ++it) {
    66     for (NodeIt jt(graph); jt != INVALID; ++jt) {
    67     for (NodeIt jt(graph); jt != INVALID; ++jt) {
    67       assert(johnson.connected(it, jt) == floyd.connected(it, jt));
    68       check(johnson.connected(it, jt) == floyd.connected(it, jt),
       
    69 	    "Wrong connection in all pairs shortest path");
    68       if (johnson.connected(it, jt)) {
    70       if (johnson.connected(it, jt)) {
    69 	assert(johnson.dist(it, jt) == floyd.dist(it, jt));
    71 	check(johnson.dist(it, jt) == floyd.dist(it, jt),
       
    72 	      "Wrong distance in all pairs shortest path");
    70 	if (it != jt) {
    73 	if (it != jt) {
    71  	  assert(johnson.dist(it, jt) == 
    74  	  check(johnson.dist(it, jt) == 
    72  		 johnson.dist(it, johnson.predNode(it, jt)) +
    75 		johnson.dist(it, johnson.predNode(it, jt)) +
    73  		 length[johnson.pred(it, jt)]);
    76 		length[johnson.pred(it, jt)],
    74 	  assert(floyd.dist(it, jt) == 
    77 		"Wrong edge in all pairs shortest path");
    75 		 floyd.dist(it, floyd.predNode(it, jt)) +
    78 	  check(floyd.dist(it, jt) == 
    76 		 length[floyd.pred(it, jt)]);
    79 		floyd.dist(it, floyd.predNode(it, jt)) +
       
    80 		length[floyd.pred(it, jt)],
       
    81 		"Wrong edge in all pairs shortest path");
    77 	}
    82 	}
    78       }
    83       }
    79     }
    84     }
    80   }
    85   }
    81 
    86