Changeset 372:e6a156fc186d in lemon-0.x for src/work/jacint/dijkstra.cc

Timestamp:

04/22/04 16:11:28 (20 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

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

Message:

 

File:

• src/work/jacint/dijkstra.cc (modified) (1 diff)

src/work/jacint/dijkstra.cc

@@ -2 +2 @@
 #include <fstream>
 
-#include <smart_graph.h>
-#include <list_graph.h>
-#include <dimacs.h>
+#include <list_graph.hh>
+#include <dimacs.hh>
 #include <dijkstra.h>
 #include <time_measure.h>
-
-#include <bin_heap.h>
-#include <fib_heap.h>
+#include <bin_heap.hh>
 
 using namespace hugo;
 
 int main(int, char **) {
-  typedef SmartGraph::Node Node;
-  typedef SmartGraph::NodeIt NodeIt;
-  typedef SmartGraph::InEdgeIt InEdgeIt; 
+  
+  typedef ListGraph Graph;
 
-  SmartGraph G;
+  typedef Graph::Node Node;
+  typedef Graph::EdgeIt EdgeIt;
+
+  Graph G;
   Node s, t;
-  SmartGraph::EdgeMap<int> cap(G);
+  Graph::EdgeMap<int> cap(G);
   readDimacsMaxFlow(std::cin, G, s, t, cap);
-
-  std::cout << "dijkstra demo ..." << std::endl;
+  Timer ts;
   
-  double pre_time=currTime();
-  Dijkstra<SmartGraph, int, FibHeap<SmartGraph::Node, int, 
-    SmartGraph::NodeMap<int> > > dijkstra_test(G, cap); 
-  dijkstra_test.run(s);
+  std::cout << "Testing dijkstra.h with Fibonacci-heap 
+implementation fib_heap.h ..." << std::endl;
+  
+  Dijkstra<Graph, int
+      //      , BinHeap<ListGraph::NodeIt, int, ListGraph::NodeMap<int> > 
+> dijkstra_test(G, s, cap);
+   ts.reset();
+    dijkstra_test.run();
+    std::cout << "elapsed time: " << ts << std::endl;
   double post_time=currTime();
     
-    std::cout << "running time with fib_heap: " 
-            << post_time-pre_time << " sec"<< std::endl; 
+  std::cout << "running time: " << post_time-pre_time << " sec"<< std::endl; 
  
-  pre_time=currTime();
-  Dijkstra<SmartGraph, int, BinHeap<SmartGraph::Node, int, 
-    SmartGraph::NodeMap<int> > > dijkstra_test2(G, cap);
-  dijkstra_test2.run(s);
-  post_time=currTime();
-  
-  std::cout << "running time with bin_heap: " 
-            << post_time-pre_time << " sec"<< std::endl; 
-  
+  EachEdgeIt e;
 
-  int hiba_fib=0;
-  int hiba_bin=0;
-  NodeIt u;
-  for ( G.first(u) ; G.valid(u); G.next(u) ) {
-    InEdgeIt e;
-    for ( G.first(e,u); G.valid(e); G.next(e) ) {
-      Node v=G.tail(e);
-      if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap[e] )
-        {
-          std::cout<<"Hibas el a fibonaccis Dijkstraban: " 
-                   << dijkstra_test.dist(u) - dijkstra_test.dist(v) - 
-            cap[e]<<std::endl;
-          ++hiba_fib;
-        }
-      if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap[e] )
-        {
-          std::cout<<"Hibas el a binarisos Dijkstraban: " 
-                   << dijkstra_test2.dist(u) - dijkstra_test2.dist(v) - 
-            cap[e]<<std::endl;
-          ++hiba_bin;
-        }
-      if ( e==dijkstra_test.pred(u) && 
-           dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap[e] )
-        {
-          std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<<
-            dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap[e]<<std::endl;
-          ++hiba_fib;
-        }
-      if ( e==dijkstra_test2.pred(u) && 
-           dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap[e] )
-        {
-          std::cout<<"Hibas fael a binarisos Dijkstraban: "<<
-            dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap[e]<<std::endl;
-          ++hiba_bin;
-        }
+  int hiba=0;
+
+  int edge=0;
+
+  for ( G.getFirst(e) ; G.valid(e); G.next(e) ) {
+    NodeIt u=G.tail(e);
+    NodeIt v=G.head(e);
+    ++edge;
+    if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap.get(e) ) {
+      std::cout<<"Hiba: "<<edge<<": "<<dijkstra_test.dist(v) - dijkstra_test.dist(u) - cap.get(e)<<std::endl;
+      ++hiba;
     }
- 
-    if ( dijkstra_test.dist(u) != dijkstra_test2.dist(u) ) 
-      std::cout << "Nem egyezik meg a tavolsag!"<<std::endl;
+  }
 
-
- }
-
-  std::cout << "Hibas elek szama a fibonaccis Dijkstraban: " 
-            << hiba_fib << " a " << G.edgeNum() <<"-bol."<< std::endl;
-  
-  std::cout << "Hibas elek szama a binarisos Dijkstraban: " 
-            << hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl;
-  
-
-
+  std::cout << "Osszhibas el: " << hiba << " osszel: " << G.edgeNum() << std::endl;
 
   return 0;