# HG changeset patch
# User jacint
# Date 1079047873 0
# Node ID de9849252e7834b8dd59d5072148d2e4c4c59033
# Parent  c645f4a2a6aeff1ebf282f7cf525cd865157674e
*** empty log message ***

diff -r c645f4a2a6ae -r de9849252e78 src/work/jacint/dijkstra.cc
--- a/src/work/jacint/dijkstra.cc	Thu Mar 11 19:24:28 2004 +0000
+++ b/src/work/jacint/dijkstra.cc	Thu Mar 11 23:31:13 2004 +0000
@@ -66,17 +66,24 @@
       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;
+	  std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<<
+	    dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap.get(e)<<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;
+	  std::cout<<"Hibas fael a binarisos Dijkstraban: "<<
+	    dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap.get(e)<<std::endl;
 	  ++hiba_bin;
 	}
     }
-  }
+ 
+    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;
@@ -84,5 +91,8 @@
   std::cout << "Hibas elek szama a binarisos Dijkstraban: " 
 	    << hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl;
 
+
+
+
   return 0;
 }
diff -r c645f4a2a6ae -r de9849252e78 src/work/jacint/fib_heap.h
--- a/src/work/jacint/fib_heap.h	Thu Mar 11 19:24:28 2004 +0000
+++ b/src/work/jacint/fib_heap.h	Thu Mar 11 23:31:13 2004 +0000
@@ -21,11 +21,14 @@
  *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item
  *     mustn't be in the heap.
  *
- *Item top() : returns the Item with least Prio
+ *Item top() : returns the Item with least Prio. 
+ *     Must be called only if heap is nonempty.
  *
  *Prio prio() : returns the least Prio
- *  
+ *     Must be called only if heap is nonempty.
+ *
  *Prio get(Item) : returns Prio of Item
+ *     Must be called only if Item is in heap.
  *
  *void pop() : deletes the Item with least Prio
  *
@@ -65,9 +68,9 @@
     
     std::vector<store> container;
     int minimum;
-    bool blank;
     ItemIntMap &iimap;
     Compare comp;
+    int num_items;
 
     enum state_enum {
       IN_HEAP = 0,
@@ -77,26 +80,23 @@
     
   public :
     
-    FibHeap(ItemIntMap &_iimap) : minimum(), blank(true), iimap(_iimap) {} 
+    FibHeap(ItemIntMap &_iimap) : minimum(), iimap(_iimap), num_items() {} 
     FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(), 
-      blank(true), iimap(_iimap), comp(_comp) {}
+      iimap(_iimap), comp(_comp), num_items() {}
     
     
     int size() const {
-      int s=0;
-      for ( unsigned int i=0; i!=container.size(); ++i )
-	if ( container[i].in ) ++s;
-      return s; 
+      return num_items; 
     }
 
 
-    bool empty() const { return blank; }
+    bool empty() const { return num_items==0; }
 
 
     void set (Item const it, PrioType const value) {
       int i=iimap.get(it);
       if ( i >= 0 && container[i].in ) {
-	if ( !comp(container[i].prio, value) ) decrease(it, value); 
+	if ( comp(value, container[i].prio) ) decrease(it, value); 
 	if ( comp(container[i].prio, value) ) increase(it, value); 
       } else push(it, value);
     }
@@ -118,62 +118,45 @@
 	container[i].marked=false;
       }
 
-      if ( !blank ) {
+      if ( num_items ) {
 	container[container[minimum].right_neighbor].left_neighbor=i;
 	container[i].right_neighbor=container[minimum].right_neighbor;
 	container[minimum].right_neighbor=i;
 	container[i].left_neighbor=minimum;
-	if ( !comp( container[minimum].prio, value) ) minimum=i; 
+	if ( comp( value, container[minimum].prio) ) minimum=i; 
       } else {
 	container[i].right_neighbor=container[i].left_neighbor=i;
 	minimum=i;	
-	blank=false;
       }
       container[i].prio=value;
+      ++num_items;
     }
     
 
     Item top() const {
-      if ( !blank ) { 
-	return container[minimum].name;
-      } else {
-	return Item();
-      }
+      return container[minimum].name;
     }
     
     
     PrioType prio() const {
-      if ( !blank ) { 
-	return container[minimum].prio;
-      } else {
-	return PrioType();
-      }
+      return container[minimum].prio;
     }
     
 
     const PrioType get(const Item& it) const {
-      int i=iimap.get(it);
-      
-      if ( i >= 0 && container[i].in ) { 
-	return container[i].prio;
-      } else {
-	return PrioType();
-      }
+      return container[iimap.get(it)].prio;
     }
 
 
-
-
     void pop() {
       /*The first case is that there are only one root.*/
       if ( container[minimum].left_neighbor==minimum ) {
 	container[minimum].in=false;
-	if ( container[minimum].degree==0 ) blank=true; 
-	else { 
+	if ( container[minimum].degree!=0 ) { 
 	  makeroot(container[minimum].child);
 	  minimum=container[minimum].child;
 	  balance();
-	} 
+	}
       } else {
 	int right=container[minimum].right_neighbor;
 	unlace(minimum);
@@ -193,23 +176,23 @@
 	minimum=right;
 	balance();
       } // the case where there are more roots
+      --num_items;   
     }
 
     
     void erase (const Item& it) {
       int i=iimap.get(it);
       
-      if ( i >= 0 && container[i].in ) { 
-	
-       if ( container[i].parent!=-1 ) {
-	 int p=container[i].parent;
-	 cut(i,p);	    
-	 cascade(p);
-	 minimum=i;     //As if its prio would be -infinity
-       }
-       pop();
-     }
-   }
+      if ( i >= 0 && container[i].in ) { 	
+	if ( container[i].parent!=-1 ) {
+	  int p=container[i].parent;
+	  cut(i,p);	    
+	  cascade(p);
+	}
+	minimum=i;     //As if its prio would be -infinity
+	pop();
+      }
+    }
     
 
     void decrease (Item it, PrioType const value) {
@@ -220,8 +203,8 @@
       if ( p!=-1 && comp(value, container[p].prio) ) {
 	cut(i,p);	    
 	cascade(p);
-	if ( comp(value, container[minimum].prio) ) minimum=i; 
-      }
+      }      
+      if ( comp(value, container[minimum].prio) ) minimum=i; 
     }
    
 
@@ -310,7 +293,7 @@
       }
       
       
-      /*Lacing i to the roots.*/
+      /*Lacing a to the roots.*/
       int right=container[minimum].right_neighbor;
       container[minimum].right_neighbor=a;
       container[a].left_neighbor=minimum;
@@ -392,9 +375,3 @@
   
 } //namespace hugo
 #endif 
-
-
-
-
-
-
diff -r c645f4a2a6ae -r de9849252e78 src/work/jacint/makefile
--- a/src/work/jacint/makefile	Thu Mar 11 19:24:28 2004 +0000
+++ b/src/work/jacint/makefile	Thu Mar 11 23:31:13 2004 +0000
@@ -3,7 +3,7 @@
 CXXFLAGS = -W -Wall -ansi -pedantic
 LEDAROOT = /ledasrc/LEDA-4.1
 
-BINARIES = dijkstra
+BINARIES = prim
 
 all: $(BINARIES)
 
diff -r c645f4a2a6ae -r de9849252e78 src/work/jacint/prim.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/jacint/prim.cc	Thu Mar 11 23:31:13 2004 +0000
@@ -0,0 +1,49 @@
+#include <iostream>
+#include <fstream>
+
+#include <list_graph.hh>
+#include <dimacs.hh>
+#include <prim.h>
+#include <time_measure.h>
+
+#include <bin_heap.hh>
+#include <fib_heap.h>
+
+using namespace hugo;
+
+int main(int, char **) {
+  typedef ListGraph::NodeIt NodeIt;
+
+  ListGraph G;
+  NodeIt s, t;
+  ListGraph::EdgeMap<int> cap(G);
+  readDimacsMaxFlow(std::cin, G, s, t, cap);
+
+  std::cout << "prim demo ..." << std::endl;
+  
+  double pre_time=currTime();
+    Prim<ListGraph, int, FibHeap<ListGraph::NodeIt, int, 
+    ListGraph::NodeMap<int> > > prim_test(G, cap);
+    prim_test.run();
+  double post_time=currTime();
+    
+  std::cout << "running time with fib_heap: " 
+	    << post_time-pre_time << " sec"<< std::endl; 
+ 
+  pre_time=currTime();
+  Prim<ListGraph, int, BinHeap<ListGraph::NodeIt, int, 
+    ListGraph::NodeMap<int> > > prim_test2(G, cap);
+  prim_test2.run();
+  post_time=currTime();
+  
+  std::cout << "running time with bin_heap: " 
+	    << post_time-pre_time << " sec"<< std::endl; 
+  
+  std::cout<<"A minimalis feszitofa sulya fib kupaccal: "<< prim_test.weight() <<std::endl;
+  std::cout<<"A minimalis feszitofa sulya bin kupaccal: "<< prim_test2.weight() <<std::endl;
+  if ( prim_test.weight() != prim_test2.weight() ) 
+    std::cout<<"Nem egyezik meg!"<<std::endl; 
+  else std::cout<<"Megegyezik."<<std::endl; 
+
+  return 0;
+}
diff -r c645f4a2a6ae -r de9849252e78 src/work/jacint/prim.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/jacint/prim.h	Thu Mar 11 23:31:13 2004 +0000
@@ -0,0 +1,170 @@
+// -*- C++ -*-
+
+//kell hogy tree_edge invalid elekbol alljon, Szep 
+//lenne ha az elejen a konstrualas ilyet adna, de
+//ugy fest nem igy lesz, ekkor invalidalni kell
+
+/* 
+ *template <Graph, T, Heap=FibHeap>
+ *
+ *Constructor: 
+ *
+ *Prim(Graph G, Graph::EdgeMap<T> weight, NodeIt root=[G.first()])
+ *
+ *
+ *Methods:
+ *
+ *void run()
+ *
+ *  The followings functions should be used after run() was already run.
+ *
+ *T weight() : returns the minimum weight of a spanning tree of the
+ *   component of the root. 
+ *
+ *EdgeIt tree(NodeIt v) : returns the first edge in the path from v
+ *   to the root. Returns an invalid iterator if v=s or v is 
+ *   not reachable from the root.
+ *
+ *bool conn() : true iff G is connected
+ *
+ *bool reach(NodeIt v) : true iff v is in the same component as the root
+ *
+ *NodeIt root() : returns the root
+ *
+ */
+
+#ifndef PRIM_H
+#define PRIM_H
+
+#include <fib_heap.h>
+
+#include <iostream>
+
+namespace hugo {
+
+  template <typename Graph, typename T, 
+    typename Heap=FibHeap<typename Graph::NodeIt, T, 
+    typename Graph::NodeMap<int> > >
+    class Prim{
+      typedef typename Graph::NodeIt NodeIt;
+      typedef typename Graph::EachNodeIt EachNodeIt;
+      typedef typename Graph::EdgeIt EdgeIt;
+      typedef typename Graph::OutEdgeIt OutEdgeIt;
+      typedef typename Graph::InEdgeIt InEdgeIt;  
+
+      Graph& G;
+      NodeIt r;
+      typename Graph::NodeMap<EdgeIt> tree_edge;
+      typename Graph::NodeMap<T> min_weight;
+      typename Graph::EdgeMap<T>& edge_weight;
+      typename Graph::NodeMap<bool> reached;
+          
+  public :
+
+      Prim(Graph& _G, typename Graph::EdgeMap<T>& _edge_weight, 
+	   NodeIt const _r) : 
+      G(_G), r(_r), tree_edge(G), min_weight(G), 
+      edge_weight(_edge_weight), reached(G, false) { }
+
+      Prim(Graph& _G, typename Graph::EdgeMap<T>& _edge_weight) : 
+      G(_G), tree_edge(G), min_weight(G), edge_weight(_edge_weight), reached(G, false)
+      { 
+	EachNodeIt _r;	   //FIXME
+	G.getFirst(_r);
+	r=_r;
+      }
+
+
+      void run() {
+
+	typename Graph::NodeMap<bool> scanned(G, false);
+	typename Graph::NodeMap<int> heap_map(G,-1);
+	
+	Heap heap(heap_map);
+
+	heap.push(r,0); 
+	reached.set(r, true);
+
+	while ( !heap.empty() ) {
+
+	  NodeIt v=heap.top(); 
+	  min_weight.set(v, heap.get(v));
+	  heap.pop();
+	  scanned.set(v,true);
+
+	  OutEdgeIt e;
+	  for( G.getFirst(e,v); G.valid(e); G.next(e)) {
+	    NodeIt w=G.head(e); 
+	    
+	    if ( !scanned.get(w) ) {
+	      if ( !reached.get(w) ) {
+		reached.set(w,true);
+		heap.push(w, edge_weight.get(e)); 
+		tree_edge.set(w,e);
+	      } else if ( edge_weight.get(e) < heap.get(w) ) {
+		tree_edge.set(w,e);
+		heap.decrease(w, edge_weight.get(e)); 
+	      }
+	    }
+	  }
+
+	  InEdgeIt f;
+	  for( G.getFirst(f,v); G.valid(f); G.next(f)) {
+	    NodeIt w=G.tail(f); 
+	    
+	    if ( !scanned.get(w) ) {
+	      if ( !reached.get(w) ) {
+		reached.set(w,true);
+		heap.push(w, edge_weight.get(f)); 
+		tree_edge.set(w,f);
+	      } else if ( edge_weight.get(f) < heap.get(w) ) {
+		tree_edge.set(w,f);
+		heap.decrease(w, edge_weight.get(f)); 
+	      }
+	    }
+	  }
+	}
+      } 
+ 
+
+      T weight() {
+	T w=0;
+	EachNodeIt u;
+	for ( G.getFirst(u) ; G.valid(u) ; G.next(u) ) w+=min_weight.get(u);
+	return w;
+      }
+     
+
+      EdgeIt tree(NodeIt v) {
+	return tree_edge.get(v);
+      } 
+
+
+      bool conn() {
+	bool c=true;
+	EachNodeIt u;
+	for ( G.getFirst(u) ; G.valid(u) ; G.next(u) ) 
+	  if ( !reached.get(u) ) { 
+	    c=false;
+	    break;
+	  }
+	return c;
+      }
+
+
+      bool reach(NodeIt v) {
+	return reached.get(v);
+      }
+
+
+      NodeIt root() {
+	return r;
+      }
+
+    };
+
+}
+
+#endif
+
+