# HG changeset patch
# User jacint
# Date 1079734565 0
# Node ID 9222a9b8b323ae70b209610427319c8f81ccf04b
# Parent  6bc65a8a99c6dd8a17bdb7c151a73e9dc61d672b
updating

diff -r 6bc65a8a99c6 -r 9222a9b8b323 src/work/jacint/dijkstra.cc
--- a/src/work/jacint/dijkstra.cc	Fri Mar 19 21:15:14 2004 +0000
+++ b/src/work/jacint/dijkstra.cc	Fri Mar 19 22:16:05 2004 +0000
@@ -1,8 +1,9 @@
 #include <iostream>
 #include <fstream>
 
-#include <list_graph.hh>
-#include <dimacs.hh>
+#include <smart_graph.h>
+#include <list_graph.h>
+#include <dimacs.h>
 #include <dijkstra.h>
 #include <time_measure.h>
 
@@ -12,30 +13,30 @@
 using namespace hugo;
 
 int main(int, char **) {
-  typedef ListGraph::NodeIt NodeIt;
-  typedef ListGraph::EachNodeIt EachNodeIt;
-  typedef ListGraph::InEdgeIt InEdgeIt; 
+  typedef SmartGraph::Node Node;
+  typedef SmartGraph::NodeIt NodeIt;
+  typedef SmartGraph::InEdgeIt InEdgeIt; 
 
-  ListGraph G;
-  NodeIt s, t;
-  ListGraph::EdgeMap<int> cap(G);
+  SmartGraph G;
+  Node s, t;
+  SmartGraph::EdgeMap<int> cap(G);
   readDimacsMaxFlow(std::cin, G, s, t, cap);
 
   std::cout << "dijkstra demo ..." << std::endl;
   
   double pre_time=currTime();
-    Dijkstra<ListGraph, int, FibHeap<ListGraph::NodeIt, int, 
-    ListGraph::NodeMap<int> > > dijkstra_test(G, s, cap);
-    dijkstra_test.run();
+    Dijkstra<SmartGraph, int, FibHeap<SmartGraph::Node, int, 
+    SmartGraph::NodeMap<int> > > dijkstra_test(G, cap); 
+    dijkstra_test.run(s);
   double post_time=currTime();
     
   std::cout << "running time with fib_heap: " 
 	    << post_time-pre_time << " sec"<< std::endl; 
  
   pre_time=currTime();
-  Dijkstra<ListGraph, int, BinHeap<ListGraph::NodeIt, int, 
-    ListGraph::NodeMap<int> > > dijkstra_test2(G, s, cap);
-  dijkstra_test2.run();
+  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: " 
@@ -44,11 +45,11 @@
 
   int hiba_fib=0;
   int hiba_bin=0;
-  EachNodeIt u;
-  for ( G.getFirst(u) ; G.valid(u); G.next(u) ) {
+  NodeIt u;
+  for ( G.first(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);
+    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.get(e) )
 	{
 	  std::cout<<"Hibas el a fibonaccis Dijkstraban: " 
@@ -87,10 +88,10 @@
 
   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;
-
+  
 
 
 
diff -r 6bc65a8a99c6 -r 9222a9b8b323 src/work/jacint/dijkstra.h
--- a/src/work/jacint/dijkstra.h	Fri Mar 19 21:15:14 2004 +0000
+++ b/src/work/jacint/dijkstra.h	Fri Mar 19 22:16:05 2004 +0000
@@ -1,119 +1,120 @@
 // -*- 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>
+ *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
  *
  *Constructor: 
  *
- *Dijkstra(Graph G, NodeIt s, Graph::EdgeMap<T> length)
+ *Dijkstra(Graph G, LengthMap length)
  *
  *
- *Member functions:
+ *Methods:
  *
- *void run()
+ *void run(Node s)
  *
- *  The following function should be used after run() was already run.
+ *T dist(Node v) : After run(s) was run, it returns the distance from s to v. 
+ *   Returns T() if v is not reachable from s.
  *
- *T dist(NodeIt v) : returns the distance from s to v. 
- *   It is 0 if v is not reachable from s.
+ *Edge pred(Node v) : After run(s) was run, it returns the last 
+ *   edge of a shortest s-v path. It is INVALID for s and for 
+ *   the nodes not reachable from s.
  *
- *EdgeIt pred(NodeIt v) : returns the last edge 
- *   of a shortest s-v path. Returns an invalid iterator 
- *   if v=s or v is not reachable from s.
- *
- *bool reach(NodeIt v) : true iff v is reachable from s
+ *bool reached(Node v) : After run(s) was run, it is true iff v is 
+ *   reachable from s
  *
  */
 
-#ifndef DIJKSTRA_H
-#define DIJKSTRA_H
+#ifndef HUGO_DIJKSTRA_H
+#define HUGO_DIJKSTRA_H
 
 #include <fib_heap.h>
+#include <invalid.h>
 
 namespace hugo {
-
+  
   template <typename Graph, typename T, 
-    typename Heap=FibHeap<typename Graph::NodeIt, T, 
-    typename Graph::NodeMap<int> > >
-    class Dijkstra{
-      typedef typename Graph::NodeIt NodeIt;
-      typedef typename Graph::EdgeIt EdgeIt;
-      typedef typename Graph::OutEdgeIt OutEdgeIt;
-      
-      Graph& G;
-      NodeIt s;
-      typename Graph::NodeMap<EdgeIt> predecessor;
-      typename Graph::NodeMap<T> distance;
-      typename Graph::EdgeMap<T>& length;
-      typename Graph::NodeMap<bool> reached;
-          
+    typename Heap=FibHeap<typename Graph::Node, T, 
+    typename Graph::NodeMap<int> >, 
+    typename LengthMap=typename Graph::EdgeMap<T> >
+  class Dijkstra{
+    typedef typename Graph::Node Node;
+    typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::Edge Edge;
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    
+    const Graph& G;
+    const LengthMap& length;
+    typename Graph::NodeMap<Edge> predecessor;
+    typename Graph::NodeMap<T> distance;
+    typename Graph::NodeMap<bool> reach;
+    
   public :
-
+    
     /*
       The distance of the nodes is 0.
     */
-    Dijkstra(Graph& _G, NodeIt const _s, 
-	     typename Graph::EdgeMap<T>& _length) : 
-      G(_G), s(_s), predecessor(G), distance(G), 
-      length(_length), reached(G, false) { }
+    Dijkstra(Graph& _G, LengthMap& _length) : G(_G), 
+      length(_length), predecessor(_G), distance(_G), reach(_G) { }
     
+
+    void run(Node s) {
       
-      void run() {
+      NodeIt u;
+      for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
+	predecessor.set(u,INVALID);
+	distance.set(u,0);
+	reach.set(u,false);
+      }
+     
+      typename Graph::NodeMap<bool> scanned(G,false);
+      typename Graph::NodeMap<int> heap_map(G,-1);
+      
+      Heap heap(heap_map);
+
+      heap.push(s,0); 
+      reach.set(s, true);
+
+      while ( !heap.empty() ) {
 	
-	typename Graph::NodeMap<bool> scanned(G, false);
-	typename Graph::NodeMap<int> heap_map(G,-1);
+	Node v=heap.top(); 
+	T oldvalue=heap.get(v);
+	heap.pop();
+	distance.set(v, oldvalue);
+	scanned.set(v,true);
 
-	Heap heap(heap_map);
-
-	heap.push(s,0); 
-	reached.set(s, true);
-
-	while ( !heap.empty() ) {
-
-	  NodeIt v=heap.top(); 
-	  T oldvalue=heap.get(v);
-	  heap.pop();
-	  distance.set(v, oldvalue);
-	  scanned.set(v,true);
-
-	  OutEdgeIt e;
-	  for( G.getFirst(e,v); G.valid(e); G.next(e)) {
-	    NodeIt w=G.bNode(e); 
+	OutEdgeIt e;
+	for( G.first(e,v); G.valid(e); G.next(e)) {
+	  Node w=G.head(e); 
 	    
-	    if ( !scanned.get(w) ) {
-	      if ( !reached.get(w) ) {
-		reached.set(w,true);
-		heap.push(w,oldvalue+length.get(e)); 
-		predecessor.set(w,e);
-	      } else if ( oldvalue+length.get(e) < heap.get(w) ) {
-		predecessor.set(w,e);
-		heap.decrease(w, oldvalue+length.get(e)); 
-	      }
+	  if ( !scanned[w] ) {
+	    if ( !reach[w] ) {
+	      reach.set(w,true);
+	      heap.push(w,oldvalue+length[e]); 
+	      predecessor.set(w,e);
+	    } else if ( oldvalue+length[e] < heap.get(w) ) {
+	      predecessor.set(w,e);
+	      heap.decrease(w, oldvalue+length[e]); 
 	    }
 	  }
 	}
-      } 
-      
+      }
+    } 
+    
 
-      T dist(NodeIt v) {
-	return distance.get(v);
-      }
+    T dist(Node v) {
+      return distance[v];
+    }
 
 
-      EdgeIt pred(NodeIt v) {
-	if ( v!=s ) return predecessor.get(v);
-	else return EdgeIt();
-      }
+    Edge pred(Node v) {
+      return predecessor[v];
+    }
      
 
-      bool reach(NodeIt v) {
-	return reached.get(v);
-      }
-      
-    };
+    bool reached(Node v) {
+      return reach[v];
+    }
+    
+  };
   
 }
 
diff -r 6bc65a8a99c6 -r 9222a9b8b323 src/work/jacint/fib_heap.h
--- a/src/work/jacint/fib_heap.h	Fri Mar 19 21:15:14 2004 +0000
+++ b/src/work/jacint/fib_heap.h	Fri Mar 19 22:16:05 2004 +0000
@@ -143,11 +143,22 @@
     }
     
 
+
+
+    PrioType& operator[](const Item& it) const {
+      return container[iimap.get(it)].prio;
+    }
+    
+    const PrioType& operator[](const Item& it) const {
+      return container[iimap.get(it)].prio;
+    }
+
     const PrioType get(const Item& it) const {
       return container[iimap.get(it)].prio;
     }
 
 
+
     void pop() {
       /*The first case is that there are only one root.*/
       if ( container[minimum].left_neighbor==minimum ) {
diff -r 6bc65a8a99c6 -r 9222a9b8b323 src/work/jacint/makefile
--- a/src/work/jacint/makefile	Fri Mar 19 21:15:14 2004 +0000
+++ b/src/work/jacint/makefile	Fri Mar 19 22:16:05 2004 +0000
@@ -1,9 +1,9 @@
 CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
 CXX2 = g++-2.95
 CXXFLAGS = -W -Wall -ansi -pedantic
-LEDAROOT = /ledasrc/LEDA-4.1
+LEDAROOT ?= /ledasrc/LEDA-4.1
 
-BINARIES = preflow dijkstra prim
+BINARIES = dijkstra prim preflow
 
 all: $(BINARIES)
 
@@ -11,13 +11,13 @@
 sinclude .depend
 
 preflow: 
-	$(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -o preflow preflow.cc
+	$(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -I../alpar -o preflow preflow.cc 
 
 dijkstra: 
-	$(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -o dijkstra dijkstra.cc
+	$(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -I../alpar  -o dijkstra dijkstra.cc
 
 prim: 
-	$(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -o prim prim.cc
+	$(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -I../alpar -o prim prim.cc
 
 clean:
 	$(RM) *.o $(BINARIES) .depend
diff -r 6bc65a8a99c6 -r 9222a9b8b323 src/work/jacint/preflow.cc
--- a/src/work/jacint/preflow.cc	Fri Mar 19 21:15:14 2004 +0000
+++ b/src/work/jacint/preflow.cc	Fri Mar 19 22:16:05 2004 +0000
@@ -1,8 +1,8 @@
 #include <iostream>
 #include <fstream>
 
-#include <list_graph.hh>
-#include <dimacs.hh>
+#include <list_graph.h>
+#include <dimacs.h>
 #include <preflow.h>
 #include <time_measure.h>
 
@@ -11,11 +11,11 @@
 // Use a DIMACS max flow file as stdin.
 // read_dimacs_demo < dimacs_max_flow_file
 int main(int, char **) {
-  typedef ListGraph::NodeIt NodeIt;
-  typedef ListGraph::EachEdgeIt EachEdgeIt;
+  typedef ListGraph::Node Node;
+  typedef ListGraph::EdgeIt EdgeIt;
 
   ListGraph G;
-  NodeIt s, t;
+  Node s, t;
   ListGraph::EdgeMap<int> cap(G);
   readDimacsMaxFlow(std::cin, G, s, t, cap);
 
@@ -24,27 +24,30 @@
   double mintime=1000000;
 
   for ( int i=1; i!=11; ++i ) {
+    ListGraph::EdgeMap<int> flow(G);
     double pre_time=currTime();
-    preflow<ListGraph, int> max_flow_test(G, s, t, cap);
+    Preflow<ListGraph, int> max_flow_test(G, s, t, cap, flow);
+    max_flow_test.run();
     double post_time=currTime();
     if ( mintime > post_time-pre_time ) mintime = post_time-pre_time;
   }
 
-  double pre_time=currTime();
-    preflow<ListGraph, int> max_flow_test(G, s, t, cap);
-  double post_time=currTime();
-    
+  ListGraph::EdgeMap<int> flow(G);
+  Preflow<ListGraph, int> max_flow_test(G, s, t, cap, flow);
+  max_flow_test.run();
+  
   ListGraph::NodeMap<bool> cut(G);
   max_flow_test.minCut(cut); 
   int min_cut_value=0;
-  for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
+  EdgeIt e;
+  for(G.first(e); G.valid(e); G.next(e)) {
     if (cut.get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e);
   }
 
   ListGraph::NodeMap<bool> cut1(G);
   max_flow_test.minMinCut(cut1); 
   int min_min_cut_value=0;
-  for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
+  for(G.first(e); G.valid(e); G.next(e)) {
     if (cut.get(G.tail(e)) && !cut.get(G.head(e))) 
       min_min_cut_value+=cap.get(e);
   }
@@ -52,17 +55,13 @@
   ListGraph::NodeMap<bool> cut2(G);
   max_flow_test.maxMinCut(cut2); 
   int max_min_cut_value=0;
-  for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
+  for(G.first(e); G.valid(e); G.next(e)) {
     if (cut2.get(G.tail(e)) && !cut2.get(G.head(e))) 
       max_min_cut_value+=cap.get(e);
       }
   
   std::cout << "min time of 10 runs: " << mintime << " sec"<< std::endl; 
-  std::cout << "phase 0: " << max_flow_test.time-pre_time 
-	    << " sec"<< std::endl; 
-  std::cout << "phase 1: " << post_time-max_flow_test.time 
-	    << " sec"<< std::endl; 
-  std::cout << "flow value: "<< max_flow_test.maxFlow() << std::endl;
+  std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   std::cout << "min cut value: "<< min_cut_value << std::endl;
   std::cout << "min min cut value: "<< min_min_cut_value << std::endl;
   std::cout << "max min cut value: "<< max_min_cut_value << 
diff -r 6bc65a8a99c6 -r 9222a9b8b323 src/work/jacint/preflow.h
--- a/src/work/jacint/preflow.h	Fri Mar 19 21:15:14 2004 +0000
+++ b/src/work/jacint/preflow.h	Fri Mar 19 22:16:05 2004 +0000
@@ -1,7 +1,5 @@
 // -*- C++ -*-
 /*
-preflow.h
-by jacint. 
 Heuristics: 
  2 phase
  gap
@@ -12,17 +10,15 @@
  
 Parameters H0 and H1 are initialized to 20 and 10.
 
-The best preflow I could ever write.
+Constructors:
 
-The constructor runs the algorithm.
+Preflow(Graph, Node, Node, CapMap, FlowMap)
 
 Members:
 
-T maxFlow() : returns the value of a maximum flow
+void run()
 
-T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 
-
-FlowMap Flow() : returns the fixed maximum flow x
+T flowValue() : returns the value of a maximum flow
 
 void minMinCut(CutMap& M) : sets M to the characteristic vector of the 
      minimum min cut. M should be a map of bools initialized to false.
@@ -35,8 +31,8 @@
 
 */
 
-#ifndef PREFLOW_H
-#define PREFLOW_H
+#ifndef HUGO_PREFLOW_H
+#define HUGO_PREFLOW_H
 
 #define H0 20
 #define H1 1
@@ -44,33 +40,32 @@
 #include <vector>
 #include <queue>
 
-#include <time_measure.h>
-
 namespace hugo {
 
   template <typename Graph, typename T, 
     typename FlowMap=typename Graph::EdgeMap<T>,
     typename CapMap=typename Graph::EdgeMap<T> >
-  class preflow {
+  class Preflow {
     
+    typedef typename Graph::Node Node;
+    typedef typename Graph::Edge Edge;
     typedef typename Graph::NodeIt NodeIt;
-    typedef typename Graph::EdgeIt EdgeIt;
-    typedef typename Graph::EachNodeIt EachNodeIt;
     typedef typename Graph::OutEdgeIt OutEdgeIt;
     typedef typename Graph::InEdgeIt InEdgeIt;
     
-    Graph& G;
-    NodeIt s;
-    NodeIt t;
-    FlowMap flow;
-    CapMap& capacity;  
+    const Graph& G;
+    Node s;
+    Node t;
+    FlowMap& flow;
+    const CapMap& capacity;  
     T value;
 
   public:
-    double time;
-    preflow(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity ) :
-      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity)
-    {
+    Preflow(Graph& _G, Node _s, Node _t, CapMap& _capacity, FlowMap& _flow ) :
+      G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) {}
+
+
+    void run() {
 
       bool phase=0;        //phase 0 is the 1st phase, phase 1 is the 2nd
       int n=G.nodeNum(); 
@@ -94,35 +89,36 @@
       typename Graph::NodeMap<int> level(G,n);      
       typename Graph::NodeMap<T> excess(G); 
 
-      std::vector<NodeIt> active(n);
-      typename Graph::NodeMap<NodeIt> next(G);
+      std::vector<Node> active(n,INVALID);
+      typename Graph::NodeMap<Node> next(G,INVALID);
       //Stack of the active nodes in level i < n.
       //We use it in both phases.
 
-      typename Graph::NodeMap<NodeIt> left(G);
-      typename Graph::NodeMap<NodeIt> right(G);
-      std::vector<NodeIt> level_list(n);
+      typename Graph::NodeMap<Node> left(G,INVALID);
+      typename Graph::NodeMap<Node> right(G,INVALID);
+      std::vector<Node> level_list(n,INVALID);
       /*
 	List of the nodes in level i<n.
       */
 
       /*Reverse_bfs from t, to find the starting level.*/
       level.set(t,0);
-      std::queue<NodeIt> bfs_queue;
+      std::queue<Node> bfs_queue;
       bfs_queue.push(t);
 
       while (!bfs_queue.empty()) {
 
-	NodeIt v=bfs_queue.front();	
+	Node v=bfs_queue.front();	
 	bfs_queue.pop();
-	int l=level.get(v)+1;
+	int l=level[v]+1;
 
-	for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
-	  NodeIt w=G.tail(e);
-	  if ( level.get(w) == n && w != s ) {
+	InEdgeIt e;
+	for(G.first(e,v); G.valid(e); G.next(e)) {
+	  Node w=G.tail(e);
+	  if ( level[w] == n && w != s ) {
 	    bfs_queue.push(w);
-	    NodeIt first=level_list[l];
-	    if ( first != 0 ) left.set(first,w);
+	    Node first=level_list[l];
+	    if ( G.valid(first) ) left.set(first,w);
 	    right.set(w,first);
 	    level_list[l]=w;
 	    level.set(w, l);
@@ -134,18 +130,19 @@
       
 
       /* Starting flow. It is everywhere 0 at the moment. */     
-      for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e) 
+      OutEdgeIt e;
+      for(G.first(e,s); G.valid(e); G.next(e)) 
 	{
-	  T c=capacity.get(e);
+	  T c=capacity[e];
 	  if ( c == 0 ) continue;
-	  NodeIt w=G.head(e);
-	  if ( level.get(w) < n ) {	  
-	    if ( excess.get(w) == 0 && w!=t ) {
-	      next.set(w,active[level.get(w)]);
-	      active[level.get(w)]=w;
+	  Node w=G.head(e);
+	  if ( level[w] < n ) {	  
+	    if ( excess[w] == 0 && w!=t ) {
+	      next.set(w,active[level[w]]);
+	      active[level[w]]=w;
 	    }
 	    flow.set(e, c); 
-	    excess.set(w, excess.get(w)+c);
+	    excess.set(w, excess[w]+c);
 	  }
 	}
 
@@ -168,37 +165,38 @@
 	    end=true;
 	  } else {
 	    phase=1;
-	    time=currTime();
 	    level.set(s,0);
-	    std::queue<NodeIt> bfs_queue;
+	    std::queue<Node> bfs_queue;
 	    bfs_queue.push(s);
 	    
 	    while (!bfs_queue.empty()) {
 	      
-	      NodeIt v=bfs_queue.front();	
+	      Node v=bfs_queue.front();	
 	      bfs_queue.pop();
-	      int l=level.get(v)+1;
+	      int l=level[v]+1;
 	      
-	      for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
-		if ( capacity.get(e) == flow.get(e) ) continue;
-		NodeIt u=G.tail(e);
-		if ( level.get(u) >= n ) { 
+	      InEdgeIt e;
+	      for(G.first(e,v); G.valid(e); G.next(e)) {
+		if ( capacity[e] == flow[e] ) continue;
+		Node u=G.tail(e);
+		if ( level[u] >= n ) { 
 		  bfs_queue.push(u);
 		  level.set(u, l);
-		  if ( excess.get(u) > 0 ) {
+		  if ( excess[u] > 0 ) {
 		    next.set(u,active[l]);
 		    active[l]=u;
 		  }
 		}
 	      }
 	    
-	      for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) {
-		if ( 0 == flow.get(e) ) continue;
-		NodeIt u=G.head(e);
-		if ( level.get(u) >= n ) { 
+	      OutEdgeIt f;
+	      for(G.first(f,v); G.valid(f); G.next(f)) {
+		if ( 0 == flow[f] ) continue;
+		Node u=G.head(f);
+		if ( level[u] >= n ) { 
 		  bfs_queue.push(u);
 		  level.set(u, l);
-		  if ( excess.get(u) > 0 ) {
+		  if ( excess[u] > 0 ) {
 		    next.set(u,active[l]);
 		    active[l]=u;
 		  }
@@ -211,40 +209,41 @@
 	}
 	  
 	  
-	if ( active[b] == 0 ) --b; 
+	if ( !G.valid(active[b]) ) --b; 
 	else {
 	  end=false;  
 
-	  NodeIt w=active[b];
-	  active[b]=next.get(w);
-	  int lev=level.get(w);
-	  T exc=excess.get(w);
+	  Node w=active[b];
+	  active[b]=next[w];
+	  int lev=level[w];
+	  T exc=excess[w];
 	  int newlevel=n;       //bound on the next level of w
 	  
-	  for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
+	  OutEdgeIt e;
+	  for(G.first(e,w); G.valid(e); G.next(e)) {
 	    
-	    if ( flow.get(e) == capacity.get(e) ) continue; 
-	    NodeIt v=G.head(e);            
+	    if ( flow[e] == capacity[e] ) continue; 
+	    Node v=G.head(e);            
 	    //e=wv	    
 	    
-	    if( lev > level.get(v) ) {      
+	    if( lev > level[v] ) {      
 	      /*Push is allowed now*/
 	      
-	      if ( excess.get(v)==0 && v!=t && v!=s ) {
-		int lev_v=level.get(v);
+	      if ( excess[v]==0 && v!=t && v!=s ) {
+		int lev_v=level[v];
 		next.set(v,active[lev_v]);
 		active[lev_v]=v;
 	      }
 	      
-	      T cap=capacity.get(e);
-	      T flo=flow.get(e);
+	      T cap=capacity[e];
+	      T flo=flow[e];
 	      T remcap=cap-flo;
 	      
 	      if ( remcap >= exc ) {       
 		/*A nonsaturating push.*/
 		
 		flow.set(e, flo+exc);
-		excess.set(v, excess.get(v)+exc);
+		excess.set(v, excess[v]+exc);
 		exc=0;
 		break; 
 		
@@ -252,50 +251,51 @@
 		/*A saturating push.*/
 		
 		flow.set(e, cap);
-		excess.set(v, excess.get(v)+remcap);
+		excess.set(v, excess[v]+remcap);
 		exc-=remcap;
 	      }
-	    } else if ( newlevel > level.get(v) ){
-	      newlevel = level.get(v);
+	    } else if ( newlevel > level[v] ){
+	      newlevel = level[v];
 	    }	    
 	    
 	  } //for out edges wv 
 	
 	
 	if ( exc > 0 ) {	
-	  for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
+	  InEdgeIt e;
+	  for(G.first(e,w); G.valid(e); G.next(e)) {
 	    
-	    if( flow.get(e) == 0 ) continue; 
-	    NodeIt v=G.tail(e);  
+	    if( flow[e] == 0 ) continue; 
+	    Node v=G.tail(e);  
 	    //e=vw
 	    
-	    if( lev > level.get(v) ) {  
+	    if( lev > level[v] ) {  
 	      /*Push is allowed now*/
 	      
-	      if ( excess.get(v)==0 && v!=t && v!=s ) {
-		int lev_v=level.get(v);
+	      if ( excess[v]==0 && v!=t && v!=s ) {
+		int lev_v=level[v];
 		next.set(v,active[lev_v]);
 		active[lev_v]=v;
 	      }
 	      
-	      T flo=flow.get(e);
+	      T flo=flow[e];
 	      
 	      if ( flo >= exc ) { 
 		/*A nonsaturating push.*/
 		
 		flow.set(e, flo-exc);
-		excess.set(v, excess.get(v)+exc);
+		excess.set(v, excess[v]+exc);
 		exc=0;
 		break; 
 	      } else {                                               
 		/*A saturating push.*/
 		
-		excess.set(v, excess.get(v)+flo);
+		excess.set(v, excess[v]+flo);
 		exc-=flo;
 		flow.set(e,0);
 	      }  
-	    } else if ( newlevel > level.get(v) ) {
-	      newlevel = level.get(v);
+	    } else if ( newlevel > level[v] ) {
+	      newlevel = level[v];
 	    }	    
 	  } //for in edges vw
 	  
@@ -318,38 +318,37 @@
 	    b=newlevel;
 	  } else {
 	    //unlacing starts
-	    NodeIt right_n=right.get(w);
-	    NodeIt left_n=left.get(w);
+	    Node right_n=right[w];
+	    Node left_n=left[w];
 
-	    if ( right_n != 0 ) {
-	      if ( left_n != 0 ) {
+	    if ( G.valid(right_n) ) {
+	      if ( G.valid(left_n) ) {
 		right.set(left_n, right_n);
 		left.set(right_n, left_n);
 	      } else {
 		level_list[lev]=right_n;   
-		left.set(right_n, 0);
+		left.set(right_n, INVALID);
 	      } 
 	    } else {
-	      if ( left_n != 0 ) {
-		right.set(left_n, 0);
+	      if ( G.valid(left_n) ) {
+		right.set(left_n, INVALID);
 	      } else { 
-		level_list[lev]=0;   
-
+		level_list[lev]=INVALID;   
 	      } 
 	    } 
 	    //unlacing ends
 		
 	    //gapping starts
-	    if ( level_list[lev]==0 ) {
+	    if ( !G.valid(level_list[lev]) ) {
 	      
 	      for (int i=lev; i!=k ; ) {
-		NodeIt v=level_list[++i];
-		while ( v != 0 ) {
+		Node v=level_list[++i];
+		while ( G.valid(v) ) {
 		  level.set(v,n);
-		  v=right.get(v);
+		  v=right[v];
 		}
-		level_list[i]=0;
-		if ( !what_heur ) active[i]=0;
+		level_list[i]=INVALID;
+		if ( !what_heur ) active[i]=INVALID;
 	      }	     
 
 	      level.set(w,n);
@@ -365,10 +364,10 @@
 		active[newlevel]=w;
 		if ( what_heur ) b=newlevel;
 		if ( k < newlevel ) ++k;
-		NodeIt first=level_list[newlevel];
-		if ( first != 0 ) left.set(first,w);
+		Node first=level_list[newlevel];
+		if ( G.valid(first) ) left.set(first,w);
 		right.set(w,first);
-		left.set(w,0);
+		left.set(w,INVALID);
 		level_list[newlevel]=w;
 	      }
 	    }
@@ -398,7 +397,7 @@
       } // while(true)
 
 
-      value = excess.get(t);
+      value = excess[t];
       /*Max flow value.*/
      
     } //void run()
@@ -411,23 +410,11 @@
       Returns the maximum value of a flow.
      */
 
-    T maxFlow() {
+    T flowValue() {
       return value;
     }
 
 
-
-    /*
-      For the maximum flow x found by the algorithm, 
-      it returns the flow value on edge e, i.e. x(e). 
-    */
-   
-    T flowOnEdge(EdgeIt e) {
-      return flow.get(e);
-    }
-
-
-
     FlowMap Flow() {
       return flow;
       }
@@ -435,9 +422,10 @@
 
     
     void Flow(FlowMap& _flow ) {
-      for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v)
-	_flow.set(v,flow.get(v));
-	}
+      NodeIt v;
+      for(G.first(v) ; G.valid(v); G.next(v))
+	_flow.set(v,flow[v]);
+    }
 
 
 
@@ -448,26 +436,28 @@
     template<typename _CutMap>
     void minMinCut(_CutMap& M) {
     
-      std::queue<NodeIt> queue;
+      std::queue<Node> queue;
       
       M.set(s,true);      
       queue.push(s);
 
       while (!queue.empty()) {
-        NodeIt w=queue.front();
+        Node w=queue.front();
 	queue.pop();
 
-	for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
-	  NodeIt v=G.head(e);
-	  if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
+	OutEdgeIt e;
+	for(G.first(e,w) ; G.valid(e); G.next(e)) {
+	  Node v=G.head(e);
+	  if (!M[v] && flow[e] < capacity[e] ) {
 	    queue.push(v);
 	    M.set(v, true);
 	  }
 	} 
 
-	for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
-	  NodeIt v=G.tail(e);
-	  if (!M.get(v) && flow.get(e) > 0 ) {
+	InEdgeIt f;
+	for(G.first(f,w) ; G.valid(f); G.next(f)) {
+	  Node v=G.tail(f);
+	  if (!M[v] && flow[f] > 0 ) {
 	    queue.push(v);
 	    M.set(v, true);
 	  }
@@ -485,34 +475,38 @@
     template<typename _CutMap>
     void maxMinCut(_CutMap& M) {
     
-      std::queue<NodeIt> queue;
+      std::queue<Node> queue;
       
       M.set(t,true);        
       queue.push(t);
 
       while (!queue.empty()) {
-        NodeIt w=queue.front();
+        Node w=queue.front();
 	queue.pop();
 
-	for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
-	  NodeIt v=G.tail(e);
-	  if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
+
+	InEdgeIt e;
+	for(G.first(e,w) ; G.valid(e); G.next(e)) {
+	  Node v=G.tail(e);
+	  if (!M[v] && flow[e] < capacity[e] ) {
 	    queue.push(v);
 	    M.set(v, true);
 	  }
 	}
-
-	for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
-	  NodeIt v=G.head(e);
-	  if (!M.get(v) && flow.get(e) > 0 ) {
+	
+	OutEdgeIt f;
+	for(G.first(f,w) ; G.valid(f); G.next(f)) {
+	  Node v=G.head(f);
+	  if (!M[v] && flow[f] > 0 ) {
 	    queue.push(v);
 	    M.set(v, true);
 	  }
 	}
       }
 
-      for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v) {
-	M.set(v, !M.get(v));
+      NodeIt v;
+      for(G.first(v) ; G.valid(v); G.next(v)) {
+	M.set(v, !M[v]);
       }
 
     }
diff -r 6bc65a8a99c6 -r 9222a9b8b323 src/work/jacint/prim.cc
--- a/src/work/jacint/prim.cc	Fri Mar 19 21:15:14 2004 +0000
+++ b/src/work/jacint/prim.cc	Fri Mar 19 22:16:05 2004 +0000
@@ -1,8 +1,8 @@
 #include <iostream>
 #include <fstream>
 
-#include <list_graph.hh>
-#include <dimacs.hh>
+#include <list_graph.h>
+#include <dimacs.h>
 #include <prim.h>
 #include <time_measure.h>
 
@@ -12,17 +12,17 @@
 using namespace hugo;
 
 int main(int, char **) {
-  typedef ListGraph::NodeIt NodeIt;
+  typedef ListGraph::Node Node;
 
   ListGraph G;
-  NodeIt s, t;
+  Node 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, 
+    Prim<ListGraph, int, FibHeap<ListGraph::Node, int, 
     ListGraph::NodeMap<int> > > prim_test(G, cap);
     prim_test.run();
   double post_time=currTime();
@@ -31,7 +31,7 @@
 	    << post_time-pre_time << " sec"<< std::endl; 
  
   pre_time=currTime();
-  Prim<ListGraph, int, BinHeap<ListGraph::NodeIt, int, 
+  Prim<ListGraph, int, BinHeap<ListGraph::Node, int, 
     ListGraph::NodeMap<int> > > prim_test2(G, cap);
   prim_test2.run();
   post_time=currTime();
diff -r 6bc65a8a99c6 -r 9222a9b8b323 src/work/jacint/prim.h
--- a/src/work/jacint/prim.h	Fri Mar 19 21:15:14 2004 +0000
+++ b/src/work/jacint/prim.h	Fri Mar 19 22:16:05 2004 +0000
@@ -1,81 +1,82 @@
 // -*- 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>
+ *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
  *
  *Constructor: 
  *
- *Prim(Graph G, Graph::EdgeMap<T> weight, NodeIt root=[G.first()])
+ *Prim(Graph G, LengthMap weight)
  *
  *
  *Methods:
  *
- *void run()
+ *void run() : Runs the Prim-algorithm from a random node
  *
- *  The followings functions should be used after run() was already run.
+ *void run(Node r) : Runs the Prim-algorithm from node s
  *
- *T weight() : returns the minimum weight of a spanning tree of the
- *   component of the root. 
+ *T weight() : After run(r) was run, it 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.
+ *Edge tree(Node v) : After run(r) was run, it returns the 
+ *   first edge in the path from v to the root. Returns 
+ *   INVALID if v=r or v is not reachable from the root.
  *
- *bool conn() : true iff G is connected
+ *bool conn() : After run(r) was run, it is true iff G is connected
  *
- *bool reach(NodeIt v) : true iff v is in the same component as the root
+ *bool reached(Node v) : After run(r) was run, it is true 
+ *   iff v is in the same component as the root
  *
- *NodeIt root() : returns the root
+ *Node root() : returns the root
  *
  */
 
-#ifndef PRIM_H
-#define PRIM_H
+#ifndef HUGO_PRIM_H
+#define HUGO_PRIM_H
 
 #include <fib_heap.h>
-
-#include <iostream>
+#include <invalid.h>
 
 namespace hugo {
 
   template <typename Graph, typename T, 
-    typename Heap=FibHeap<typename Graph::NodeIt, T, 
-    typename Graph::NodeMap<int> > >
+    typename Heap=FibHeap<typename Graph::Node, T, 
+    typename Graph::NodeMap<int> >, 
+    typename LengthMap=typename Graph::EdgeMap<T> >
     class Prim{
+      typedef typename Graph::Node Node;
       typedef typename Graph::NodeIt NodeIt;
-      typedef typename Graph::EachNodeIt EachNodeIt;
-      typedef typename Graph::EdgeIt EdgeIt;
+      typedef typename Graph::Edge Edge;
       typedef typename Graph::OutEdgeIt OutEdgeIt;
       typedef typename Graph::InEdgeIt InEdgeIt;  
 
-      Graph& G;
-      NodeIt r;
-      typename Graph::NodeMap<EdgeIt> tree_edge;
+      const Graph& G;
+      const LengthMap& edge_weight;
+      typename Graph::NodeMap<Edge> tree_edge;
       typename Graph::NodeMap<T> min_weight;
-      typename Graph::EdgeMap<T>& edge_weight;
-      typename Graph::NodeMap<bool> reached;
+      typename Graph::NodeMap<bool> reach;
           
   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, LengthMap& _edge_weight) : 
+	G(_G), edge_weight(_edge_weight), 
+	tree_edge(_G,INVALID), min_weight(_G), reach(_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() {
+	NodeIt _r;	
+	G.first(_r);
+	run(_r);
       }
 
 
-      void run() {
+      void run(Node r) {
+
+	NodeIt u;
+	for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
+	  tree_edge.set(u,INVALID);
+	  min_weight.set(u,0);
+	  reach.set(u,false);
+	}
+
 
 	typename Graph::NodeMap<bool> scanned(G, false);
 	typename Graph::NodeMap<int> heap_map(G,-1);
@@ -83,43 +84,43 @@
 	Heap heap(heap_map);
 
 	heap.push(r,0); 
-	reached.set(r, true);
+	reach.set(r, true);
 
 	while ( !heap.empty() ) {
 
-	  NodeIt v=heap.top(); 
+	  Node 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); 
+	  for( G.first(e,v); G.valid(e); G.next(e)) {
+	    Node w=G.head(e); 
 	    
-	    if ( !scanned.get(w) ) {
-	      if ( !reached.get(w) ) {
-		reached.set(w,true);
-		heap.push(w, edge_weight.get(e)); 
+	    if ( !scanned[w] ) {
+	      if ( !reach[w] ) {
+		reach.set(w,true);
+		heap.push(w, edge_weight[e]); 
 		tree_edge.set(w,e);
-	      } else if ( edge_weight.get(e) < heap.get(w) ) {
+	      } else if ( edge_weight[e] < heap.get(w) ) {
 		tree_edge.set(w,e);
-		heap.decrease(w, edge_weight.get(e)); 
+		heap.decrease(w, edge_weight[e]); 
 	      }
 	    }
 	  }
 
 	  InEdgeIt f;
-	  for( G.getFirst(f,v); G.valid(f); G.next(f)) {
-	    NodeIt w=G.tail(f); 
+	  for( G.first(f,v); G.valid(f); G.next(f)) {
+	    Node w=G.tail(f); 
 	    
-	    if ( !scanned.get(w) ) {
-	      if ( !reached.get(w) ) {
-		reached.set(w,true);
-		heap.push(w, edge_weight.get(f)); 
+	    if ( !scanned[w] ) {
+	      if ( !reach[w] ) {
+		reach.set(w,true);
+		heap.push(w, edge_weight[f]); 
 		tree_edge.set(w,f);
-	      } else if ( edge_weight.get(f) < heap.get(w) ) {
+	      } else if ( edge_weight[f] < heap.get(w) ) {
 		tree_edge.set(w,f);
-		heap.decrease(w, edge_weight.get(f)); 
+		heap.decrease(w, edge_weight[f]); 
 	      }
 	    }
 	  }
@@ -129,22 +130,22 @@
 
       T weight() {
 	T w=0;
-	EachNodeIt u;
-	for ( G.getFirst(u) ; G.valid(u) ; G.next(u) ) w+=min_weight.get(u);
+	NodeIt u;
+	for ( G.first(u) ; G.valid(u) ; G.next(u) ) w+=min_weight[u];
 	return w;
       }
      
 
-      EdgeIt tree(NodeIt v) {
-	return tree_edge.get(v);
+      Edge tree(Node v) {
+	return tree_edge[v];
       } 
 
 
       bool conn() {
 	bool c=true;
-	EachNodeIt u;
-	for ( G.getFirst(u) ; G.valid(u) ; G.next(u) ) 
-	  if ( !reached.get(u) ) { 
+	NodeIt u;
+	for ( G.first(u) ; G.valid(u) ; G.next(u) ) 
+	  if ( !reached[u] ) { 
 	    c=false;
 	    break;
 	  }
@@ -152,12 +153,12 @@
       }
 
 
-      bool reach(NodeIt v) {
-	return reached.get(v);
+      bool reached(Node v) {
+	return reached[v];
       }
 
 
-      NodeIt root() {
+      Node root() {
 	return r;
       }