Changeset 170:9091b1ebca27 in lemon-0.x for src/work

Timestamp:

03/11/04 19:17:20 (20 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

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

Message:

* empty log message *

Location:

src/work/jacint

Files:

• bin_heap.hh (added)
• dijkstra.cc (modified) (2 diffs)
• dijkstra.h (modified) (2 diffs)
• makefile (modified) (1 diff)

src/work/jacint/dijkstra.cc

@@ -7 +7 @@
 #include <time_measure.h>
 
+#include <bin_heap.hh>
+#include <fib_heap.h>
+
 using namespace hugo;
 
 int main(int, char **) {
   typedef ListGraph::NodeIt NodeIt;
-  typedef ListGraph::EachEdgeIt EachEdgeIt;
+  typedef ListGraph::EachNodeIt EachNodeIt;
+  typedef ListGraph::InEdgeIt InEdgeIt; 
 
   ListGraph G;
@@ -21 +25 @@
   
   double pre_time=currTime();
-    Dijkstra<ListGraph, int> dijkstra_test(G, s, cap);
+    Dijkstra<ListGraph, int, FibHeap<ListGraph::NodeIt, int, 
+    ListGraph::NodeMap<int> > > dijkstra_test(G, s, cap);
     dijkstra_test.run();
   double post_time=currTime();
     
-  std::cout << "running time: " << post_time-pre_time << " sec"<< std::endl; 
+  std::cout << "running time with fib_heap: " 
+            << post_time-pre_time << " sec"<< std::endl; 
  
-  int hiba=0;
-  EachEdgeIt e;
-  for ( G.getFirst(e) ; G.valid(e); G.next(e) ) {
-    NodeIt u=G.tail(e);
-    NodeIt v=G.head(e);
-    if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap.get(e) ) {
-      std::cout<<"Hiba: "<<dijkstra_test.dist(v) - dijkstra_test.dist(u) - cap.get(e)<<std::endl;
-      ++hiba;
+  pre_time=currTime();
+  Dijkstra<ListGraph, int, BinHeap<ListGraph::NodeIt, int, 
+    ListGraph::NodeMap<int> > > dijkstra_test2(G, s, cap);
+  dijkstra_test2.run();
+  post_time=currTime();
+  
+  std::cout << "running time with bin_heap: " 
+            << post_time-pre_time << " sec"<< std::endl; 
+  
+
+  int hiba_fib=0;
+  int hiba_bin=0;
+  EachNodeIt u;
+  for ( G.getFirst(u) ; G.valid(u); G.next(u) ) {
+    InEdgeIt e;
+    for ( G.getFirst(e,u); G.valid(e); G.next(e) ) {
+      NodeIt v=G.tail(e);
+      if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap.get(e) )
+        {
+          std::cout<<"Hibas el a fibonaccis Dijkstraban: " 
+                   << dijkstra_test.dist(u) - dijkstra_test.dist(v) - 
+            cap.get(e)<<std::endl;
+          ++hiba_fib;
+        }
+      if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap.get(e) )
+        {
+          std::cout<<"Hibas el a binarisos Dijkstraban: " 
+                   << dijkstra_test2.dist(u) - dijkstra_test2.dist(v) - 
+            cap.get(e)<<std::endl;
+          ++hiba_bin;
+        }
+      if ( e==dijkstra_test.pred(u) && 
+           dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap.get(e) )
+        {
+          std::cout<<"Hibas fael a fibonaccis Dijkstraban!"<<std::endl;
+          ++hiba_fib;
+        }
+      if ( e==dijkstra_test2.pred(u) && 
+           dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap.get(e) )
+        {
+          std::cout<<"Hibas fael a binarisos Dijkstraban!"<<std::endl;
+          ++hiba_bin;
+        }
     }
   }
 
-  std::cout << "Hibas elek szama: " << hiba << " a " << G.edgeNum() <<"-bol."<< 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;
 
   return 0;

src/work/jacint/dijkstra.h

@@ -1 +1 @@
 // -*- C++ -*-
+
+//ha predecessor az elejen nem invalid, akkor hagyd csak ugy
+//scanned mutatja hogy jo ertek van-e benne vagy szemet
+
 /* 
  *template <Graph, T, Heap=FibHeap>
@@ -25 +29 @@
  */
 
-#ifndef DIJKSTRA_HH
-#define DIJKSTRA_HH
+#ifndef DIJKSTRA_H
+#define DIJKSTRA_H
 
 #include <fib_heap.h>

src/work/jacint/makefile

@@ -17 +17 @@
         $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -o dijkstra dijkstra.cc
 
+prim: 
+        $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -o prim prim.cc
+
 clean:
         $(RM) *.o $(BINARIES) .depend