test/all_pairs_shortest_path_test.cc
changeset 2335 27aa03cd3121
parent 2269 fb1c634fff29
child 2386 81b47fc5c444
equal deleted inserted replaced
6:36c20cf3e07d 7:c9e8098f489b
    26 #include <lemon/dijkstra.h>
    26 #include <lemon/dijkstra.h>
    27 #include <lemon/floyd_warshall.h>
    27 #include <lemon/floyd_warshall.h>
    28 #include <lemon/johnson.h>
    28 #include <lemon/johnson.h>
    29 
    29 
    30 #include <lemon/fib_heap.h>
    30 #include <lemon/fib_heap.h>
       
    31 
       
    32 #include <lemon/path.h>
    31 
    33 
    32 #include <lemon/time_measure.h>
    34 #include <lemon/time_measure.h>
    33 #include "test_tools.h"
    35 #include "test_tools.h"
    34 
    36 
    35 using namespace lemon;
    37 using namespace lemon;
    88     Timer timer;
    90     Timer timer;
    89     floyd.run();
    91     floyd.run();
    90     cout << "FloydWarshall: " << timer << endl;
    92     cout << "FloydWarshall: " << timer << endl;
    91   }    
    93   }    
    92 
    94 
       
    95   bool checked_path = false;
       
    96 
    93   for (NodeIt it(graph); it != INVALID; ++it) {
    97   for (NodeIt it(graph); it != INVALID; ++it) {
    94     for (NodeIt jt(graph); jt != INVALID; ++jt) {
    98     for (NodeIt jt(graph); jt != INVALID; ++jt) {
    95       check(johnson.connected(it, jt) == floyd.connected(it, jt),
    99       check(johnson.connected(it, jt) == floyd.connected(it, jt),
    96 	    "Wrong connection in all pairs shortest path");
   100 	    "Wrong connection in all pairs shortest path");
    97       check(johnson.connected(it, jt) == fibJohnson.connected(it, jt),
   101       check(johnson.connected(it, jt) == fibJohnson.connected(it, jt),
    98 	    "Wrong connection in all pairs shortest path");
   102 	    "Wrong connection in all pairs shortest path");
    99       if (johnson.connected(it, jt)) {
   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         }
   100 	check(johnson.dist(it, jt) == floyd.dist(it, jt),
   120 	check(johnson.dist(it, jt) == floyd.dist(it, jt),
   101 	      "Wrong distance in all pairs shortest path");
   121 	      "Wrong distance in all pairs shortest path");
   102 	check(johnson.dist(it, jt) == fibJohnson.dist(it, jt),
   122 	check(johnson.dist(it, jt) == fibJohnson.dist(it, jt),
   103 	      "Wrong distance in all pairs shortest path");
   123 	      "Wrong distance in all pairs shortest path");
   104 	if (it != jt) {
   124 	if (it != jt) {