Changeset 1745:d356e54bdafc in lemon-0.x for test/all_pairs_shortest_path_test.cc

Timestamp:

10/26/05 13:10:18 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2273

Message:

Upgrading tests

File:

• test/all_pairs_shortest_path_test.cc (modified) (4 diffs)

test/all_pairs_shortest_path_test.cc

@@ -9 +9 @@
 #include <lemon/floyd_warshall.h>
 #include <lemon/johnson.h>
+
+#include <lemon/fib_heap.h>
 
 #include <lemon/time_measure.h>
@@ -57 +59 @@
   }
 
+  typedef FibHeap<Node, double, Graph::NodeMap<int> > DoubleFibHeap;
+  Johnson<Graph, LengthMap>::DefStandardHeap<DoubleFibHeap>
+    ::Create fibJohnson(graph, length);
+  {
+    Timer timer;
+    fibJohnson.run();
+    cout << "Johnson with fibonacci heap: " << timer << endl;
+  }
+
   FloydWarshall<Graph, LengthMap> floyd(graph, length);
   {
@@ -68 +79 @@
       check(johnson.connected(it, jt) == floyd.connected(it, jt),
             "Wrong connection in all pairs shortest path");
+      check(johnson.connected(it, jt) == fibJohnson.connected(it, jt),
+            "Wrong connection in all pairs shortest path");
       if (johnson.connected(it, jt)) {
         check(johnson.dist(it, jt) == floyd.dist(it, jt),
+              "Wrong distance in all pairs shortest path");
+        check(johnson.dist(it, jt) == fibJohnson.dist(it, jt),
               "Wrong distance in all pairs shortest path");
         if (it != jt) {
@@ -75 +90 @@
                 johnson.dist(it, johnson.predNode(it, jt)) +
                 length[johnson.pred(it, jt)],
+                "Wrong edge in all pairs shortest path");
+          check(fibJohnson.dist(it, jt) == 
+                fibJohnson.dist(it, fibJohnson.predNode(it, jt)) +
+                length[fibJohnson.pred(it, jt)],
                 "Wrong edge in all pairs shortest path");
           check(floyd.dist(it, jt) ==