# HG changeset patch
# User marci
# Date 1084305021 0
# Node ID b6b31b75b522ab982c882d440bc25a9a0d8eb10e
# Parent  75cf1d52eee588491ffb3d52bf1a688642b49f1c
docs, max_flow improvments

diff -r 75cf1d52eee5 -r b6b31b75b522 src/work/Doxyfile
--- a/src/work/Doxyfile	Tue May 11 19:38:00 2004 +0000
+++ b/src/work/Doxyfile	Tue May 11 19:50:21 2004 +0000
@@ -394,7 +394,6 @@
 INPUT                  = ../hugo \
                          ../hugo/skeletons \
                          ../test/test_tools.h \
-                         athos/minlengthpaths.h \
                          klao/path.h \
                          jacint/max_flow.h \
                          jacint/max_matching.h \ 
diff -r 75cf1d52eee5 -r b6b31b75b522 src/work/jacint/max_flow.h
--- a/src/work/jacint/max_flow.h	Tue May 11 19:38:00 2004 +0000
+++ b/src/work/jacint/max_flow.h	Tue May 11 19:50:21 2004 +0000
@@ -1,19 +1,19 @@
 // -*- C++ -*-
 
 /*
-  Heuristics: 
+  Heuristics:
   2 phase
   gap
   list 'level_list' on the nodes on level i implemented by hand
   stack 'active' on the active nodes on level i
   runs heuristic 'highest label' for H1*n relabels
   runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label'
- 
+
   Parameters H0 and H1 are initialized to 20 and 1.
 
   Constructors:
 
-  Preflow(Graph, Node, Node, CapMap, FlowMap, bool) : bool must be false if 
+  Preflow(Graph, Node, Node, CapMap, FlowMap, bool) : bool must be false if
   FlowMap is not constant zero, and should be true if it is
 
   Members:
@@ -22,13 +22,13 @@
 
   Num flowValue() : returns the value of a maximum flow
 
-  void minMinCut(CutMap& M) : sets M to the characteristic vector of the 
+  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. ??Is it OK?
 
-  void maxMinCut(CutMap& M) : sets M to the characteristic vector of the 
+  void maxMinCut(CutMap& M) : sets M to the characteristic vector of the
   maximum min cut. M should be a map of bools initialized to false.
 
-  void minCut(CutMap& M) : sets M to the characteristic vector of 
+  void minCut(CutMap& M) : sets M to the characteristic vector of
   a min cut. M should be a map of bools initialized to false.
 
 */
@@ -36,9 +36,6 @@
 #ifndef HUGO_MAX_FLOW_H
 #define HUGO_MAX_FLOW_H
 
-#define H0 20
-#define H1 1
-
 #include <vector>
 #include <queue>
 #include <stack>
@@ -50,18 +47,20 @@
 #include <for_each_macros.h>
 
 /// \file
-/// \brief Dimacs file format reader.
+/// \brief Maximum flows.
+/// \ingroup galgs
 
 namespace hugo {
 
 
   //  ///\author Marton Makai, Jacint Szabo
   /// A class for computing max flows and related quantities.
-  template <typename Graph, typename Num, 
-	    typename CapMap=typename Graph::template EdgeMap<Num>, 
+  /// \ingroup galgs
+  template <typename Graph, typename Num,
+	    typename CapMap=typename Graph::template EdgeMap<Num>,
             typename FlowMap=typename Graph::template EdgeMap<Num> >
   class MaxFlow {
-    
+  protected:
     typedef typename Graph::Node Node;
     typedef typename Graph::NodeIt NodeIt;
     typedef typename Graph::OutEdgeIt OutEdgeIt;
@@ -74,7 +73,7 @@
     const Graph* g;
     Node s;
     Node t;
-    const CapMap* capacity;  
+    const CapMap* capacity;
     FlowMap* flow;
     int n;      //the number of nodes of G
     typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
@@ -83,98 +82,107 @@
     //typedef typename ResGW::template NodeMap<bool> ReachedMap;
     typedef typename Graph::template NodeMap<int> ReachedMap;
     ReachedMap level;
-    //level works as a bool map in augmenting path algorithms 
+    //level works as a bool map in augmenting path algorithms
     //and is used by bfs for storing reached information.
     //In preflow, it shows levels of nodes.
-    //typename Graph::template NodeMap<int> level;    
-    typename Graph::template NodeMap<Num> excess; 
+    //typename Graph::template NodeMap<int> level;
+    typename Graph::template NodeMap<Num> excess;
     //   protected:
     //     MaxFlow() { }
-    //     void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, 
-    // 	     FlowMap& _flow) 
+    //     void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
+    // 	     FlowMap& _flow)
     //       {
-    // 	g=&_G; 
-    // 	s=_s; 
-    // 	t=_t; 
+    // 	g=&_G;
+    // 	s=_s;
+    // 	t=_t;
     // 	capacity=&_capacity;
     // 	flow=&_flow;
     // 	n=_G.nodeNum;
-    // 	level.set (_G); //kellene vmi ilyesmi fv 
+    // 	level.set (_G); //kellene vmi ilyesmi fv
     // 	excess(_G,0); //itt is
     //       }
 
+    // constants used for heuristics
+    static const int H0=20;
+    static const int H1=1;
+
   public:
- 
+
     ///\todo Document this.
     ///\todo Maybe, it should be PRE_FLOW instead.
+    ///- \c NO_FLOW means nothing,
     ///- \c ZERO_FLOW means something,
     ///- \c GEN_FLOW means something else,
-    ///- \c PREFLOW is something different.
+    ///- \c PRE_FLOW is something different.
     enum flowEnum{
-      ZERO_FLOW=0,
-      GEN_FLOW=1,
-      PREFLOW=2
+      ZERO_FLOW,
+      GEN_FLOW,
+      PRE_FLOW,
+      NO_FLOW
     };
 
-    MaxFlow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, 
+    MaxFlow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
 	    FlowMap& _flow) :
-      g(&_G), s(_s), t(_t), capacity(&_capacity), 
+      g(&_G), s(_s), t(_t), capacity(&_capacity),
       flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {}
 
     /// A max flow algorithm is run.
-    ///\pre the flow have to be 0 at the beginning.
-    void run() {
-      preflow(ZERO_FLOW);
+    /// \pre The flow have to satisfy the requirements
+    /// stated in fe.
+    void run(flowEnum fe=ZERO_FLOW) {
+      preflow(fe);
     }
-    
-    /// A preflow algorithm is run. 
-    ///\pre The initial edge-map have to be a 
+
+    /// A preflow algorithm is run.
+    /// \pre The initial edge-map have to be a
     /// zero flow if \c fe is \c ZERO_FLOW,
-    /// a flow if \c fe is \c GEN_FLOW, 
-    /// and a pre-flow it is \c PREFLOW.
+    /// a flow if \c fe is \c GEN_FLOW,
+    /// a pre-flow if fe is \c PRE_FLOW and
+    /// anything if fe is NO_FLOW.
     void preflow(flowEnum fe) {
       preflowPhase0(fe);
       preflowPhase1();
     }
 
-    /// Run the first phase of preflow, starting from a 0 flow, from a flow, 
-    /// or from a preflow, according to \c fe.
-    void preflowPhase0( flowEnum fe );
+    /// Run the first phase of preflow, starting from a 0 flow, from a flow,
+    /// or from a preflow, of from undefined value according to \c fe.
+    void preflowPhase0(flowEnum fe);
 
     /// Second phase of preflow.
     void preflowPhase1();
 
-    /// Starting from a flow, this method searches for an augmenting path 
-    /// according to the Edmonds-Karp algorithm 
-    /// and augments the flow on if any. 
+    /// Starting from a flow, this method searches for an augmenting path
+    /// according to the Edmonds-Karp algorithm
+    /// and augments the flow on if any.
     /// The return value shows if the augmentation was succesful.
     bool augmentOnShortestPath();
 
-    /// Starting from a flow, this method searches for an augmenting blockin 
-    /// flow according to Dinits' algorithm and augments the flow on if any. 
-    /// The blocking flow is computed in a physically constructed 
+    /// Starting from a flow, this method searches for an augmenting blocking
+    /// flow according to Dinits' algorithm and augments the flow on if any.
+    /// The blocking flow is computed in a physically constructed
     /// residual graph of type \c Mutablegraph.
     /// The return value show sif the augmentation was succesful.
     template<typename MutableGraph> bool augmentOnBlockingFlow();
 
-    /// The same as \c augmentOnBlockingFlow<MutableGraph> but the 
+    /// The same as \c augmentOnBlockingFlow<MutableGraph> but the
     /// residual graph is not constructed physically.
     /// The return value shows if the augmentation was succesful.
     bool augmentOnBlockingFlow2();
 
     /// Returns the actual flow value.
-    /// More precisely, it returns the negative excess of s, thus 
+    /// More precisely, it returns the negative excess of s, thus
     /// this works also for preflows.
-    Num flowValue() { 
+    Num flowValue() {
       Num a=0;
-      FOR_EACH_INC_LOC(OutEdgeIt, e, *g, s) a+=(*flow)[e];
-      FOR_EACH_INC_LOC(InEdgeIt, e, *g, s) a-=(*flow)[e];
+      FOR_EACH_INC_LOC(InEdgeIt, e, *g, t) a+=(*flow)[e];
+      FOR_EACH_INC_LOC(OutEdgeIt, e, *g, t) a-=(*flow)[e];
       return a;
     }
 
     /// Should be used between preflowPhase0 and preflowPhase1.
-    ///\todo We have to make some status variable which shows the actual state 
-    /// of the class. This enables us to determine which methods are valid 
+    /// \todo We have to make some status variable which shows the
+    /// actual state
+    /// of the class. This enables us to determine which methods are valid
     /// for MinCut computation
     template<typename _CutMap>
     void actMinCut(_CutMap& M) {
@@ -188,15 +196,15 @@
       }
     }
 
-    /// The unique inclusionwise minimum cut is computed by 
+    /// The unique inclusionwise minimum cut is computed by
     /// processing a bfs from s in the residual graph.
-    ///\pre flow have to be a max flow otherwise it will the whole node-set.
+    /// \pre flow have to be a max flow otherwise it will the whole node-set.
     template<typename _CutMap>
     void minMinCut(_CutMap& M) {
-    
+
       std::queue<Node> queue;
-      
-      M.set(s,true);      
+
+      M.set(s,true);
       queue.push(s);
 
       while (!queue.empty()) {
@@ -210,7 +218,7 @@
 	    queue.push(v);
 	    M.set(v, true);
 	  }
-	} 
+	}
 
 	InEdgeIt f;
 	for(g->first(f,w) ; g->valid(f); g->next(f)) {
@@ -219,14 +227,14 @@
 	    queue.push(v);
 	    M.set(v, true);
 	  }
-	} 
+	}
       }
     }
 
 
-    /// The unique inclusionwise maximum cut is computed by 
+    /// The unique inclusionwise maximum cut is computed by
     /// processing a reverse bfs from t in the residual graph.
-    ///\pre flow have to be a max flow otherwise it will be empty.
+    /// \pre flow have to be a max flow otherwise it will be empty.
     template<typename _CutMap>
     void maxMinCut(_CutMap& M) {
 
@@ -236,15 +244,14 @@
       }
 
       std::queue<Node> queue;
-      
-      M.set(t,false);        
+
+      M.set(t,false);
       queue.push(t);
 
       while (!queue.empty()) {
         Node w=queue.front();
 	queue.pop();
 
-
 	InEdgeIt e;
 	for(g->first(e,w) ; g->valid(e); g->next(e)) {
 	  Node v=g->tail(e);
@@ -253,7 +260,7 @@
 	    M.set(v, false);
 	  }
 	}
-	
+
 	OutEdgeIt f;
 	for(g->first(f,w) ; g->valid(f); g->next(f)) {
 	  Node v=g->head(f);
@@ -274,112 +281,111 @@
     void resetSource(Node _s) { s=_s; }
     ///
     void resetTarget(Node _t) { t=_t; }
-   
+
     /// capacity-map is changed.
     void resetCap(const CapMap& _cap) { capacity=&_cap; }
-    
-    /// flow-map is changed. 
+
+    /// flow-map is changed.
     void resetFlow(FlowMap& _flow) { flow=&_flow; }
 
 
   private:
 
     int push(Node w, VecStack& active) {
-      
+
       int lev=level[w];
       Num exc=excess[w];
       int newlevel=n;       //bound on the next level of w
-	  
+
       OutEdgeIt e;
       for(g->first(e,w); g->valid(e); g->next(e)) {
-	    
-	if ( (*flow)[e] >= (*capacity)[e] ) continue; 
-	Node v=g->head(e);            
-	    
+
+	if ( (*flow)[e] >= (*capacity)[e] ) continue;
+	Node v=g->head(e);
+
 	if( lev > level[v] ) { //Push is allowed now
-	  
+
 	  if ( excess[v]<=0 && v!=t && v!=s ) {
 	    int lev_v=level[v];
 	    active[lev_v].push(v);
 	  }
-	  
+
 	  Num cap=(*capacity)[e];
 	  Num flo=(*flow)[e];
 	  Num remcap=cap-flo;
-	  
+
 	  if ( remcap >= exc ) { //A nonsaturating push.
-	    
+
 	    flow->set(e, flo+exc);
 	    excess.set(v, excess[v]+exc);
 	    exc=0;
-	    break; 
-	    
+	    break;
+
 	  } else { //A saturating push.
 	    flow->set(e, cap);
 	    excess.set(v, excess[v]+remcap);
 	    exc-=remcap;
 	  }
 	} else if ( newlevel > level[v] ) newlevel = level[v];
-      } //for out edges wv 
-      
-      if ( exc > 0 ) {	
+      } //for out edges wv
+
+      if ( exc > 0 ) {
 	InEdgeIt e;
 	for(g->first(e,w); g->valid(e); g->next(e)) {
-	  
-	  if( (*flow)[e] <= 0 ) continue; 
-	  Node v=g->tail(e); 
-	  
+
+	  if( (*flow)[e] <= 0 ) continue;
+	  Node v=g->tail(e);
+
 	  if( lev > level[v] ) { //Push is allowed now
-	    
+
 	    if ( excess[v]<=0 && v!=t && v!=s ) {
 	      int lev_v=level[v];
 	      active[lev_v].push(v);
 	    }
-	    
+
 	    Num flo=(*flow)[e];
-	    
+
 	    if ( flo >= exc ) { //A nonsaturating push.
-	      
+
 	      flow->set(e, flo-exc);
 	      excess.set(v, excess[v]+exc);
 	      exc=0;
-	      break; 
+	      break;
 	    } else {  //A saturating push.
-	      
+
 	      excess.set(v, excess[v]+flo);
 	      exc-=flo;
 	      flow->set(e,0);
-	    }  
+	    }
 	  } else if ( newlevel > level[v] ) newlevel = level[v];
 	} //for in edges vw
-	
+
       } // if w still has excess after the out edge for cycle
-      
+
       excess.set(w, exc);
-      
+
       return newlevel;
     }
 
 
-    void preflowPreproc ( flowEnum fe, VecStack& active, 
-			  VecNode& level_list, NNMap& left, NNMap& right ) 
+    void preflowPreproc(flowEnum fe, VecStack& active,
+			VecNode& level_list, NNMap& left, NNMap& right)
     {
+      std::queue<Node> bfs_queue;
 
-      std::queue<Node> bfs_queue;
-      
-      switch ( fe ) {
-      case ZERO_FLOW: 
+      switch (fe) {
+      case ZERO_FLOW:
 	{
 	  //Reverse_bfs from t, to find the starting level.
 	  level.set(t,0);
 	  bfs_queue.push(t);
-	
+
 	  while (!bfs_queue.empty()) {
-	    
-	    Node v=bfs_queue.front();	
+
+	    Node v=bfs_queue.front();
 	    bfs_queue.pop();
 	    int l=level[v]+1;
-	    
+
 	    InEdgeIt e;
 	    for(g->first(e,v); g->valid(e); g->next(e)) {
 	      Node w=g->tail(e);
@@ -393,37 +399,37 @@
 	      }
 	    }
 	  }
-	  
+
 	  //the starting flow
 	  OutEdgeIt e;
-	  for(g->first(e,s); g->valid(e); g->next(e)) 
+	  for(g->first(e,s); g->valid(e); g->next(e))
 	    {
 	      Num c=(*capacity)[e];
 	      if ( c <= 0 ) continue;
 	      Node w=g->head(e);
-	      if ( level[w] < n ) {	  
+	      if ( level[w] < n ) {
 		if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
-		flow->set(e, c); 
+		flow->set(e, c);
 		excess.set(w, excess[w]+c);
 	      }
 	    }
 	  break;
 	}
-	
+
       case GEN_FLOW:
-      case PREFLOW:
+      case PRE_FLOW:
 	{
-	  //Reverse_bfs from t in the residual graph, 
+	  //Reverse_bfs from t in the residual graph,
 	  //to find the starting level.
 	  level.set(t,0);
 	  bfs_queue.push(t);
-	  
+
 	  while (!bfs_queue.empty()) {
-	    
-	    Node v=bfs_queue.front();	
+
+	    Node v=bfs_queue.front();
 	    bfs_queue.pop();
 	    int l=level[v]+1;
-	    
+
 	    InEdgeIt e;
 	    for(g->first(e,v); g->valid(e); g->next(e)) {
 	      if ( (*capacity)[e] <= (*flow)[e] ) continue;
@@ -437,7 +443,7 @@
 		level.set(w, l);
 	      }
 	    }
-	    
+
 	    OutEdgeIt f;
 	    for(g->first(f,v); g->valid(f); g->next(f)) {
 	      if ( 0 >= (*flow)[f] ) continue;
@@ -452,70 +458,70 @@
 	      }
 	    }
 	  }
-	  
-	  
+
+
 	  //the starting flow
 	  OutEdgeIt e;
-	  for(g->first(e,s); g->valid(e); g->next(e)) 
+	  for(g->first(e,s); g->valid(e); g->next(e))
 	    {
 	      Num rem=(*capacity)[e]-(*flow)[e];
 	      if ( rem <= 0 ) continue;
 	      Node w=g->head(e);
-	      if ( level[w] < n ) {	  
+	      if ( level[w] < n ) {
 		if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
-		flow->set(e, (*capacity)[e]); 
+		flow->set(e, (*capacity)[e]);
 		excess.set(w, excess[w]+rem);
 	      }
 	    }
-	  
+
 	  InEdgeIt f;
-	  for(g->first(f,s); g->valid(f); g->next(f)) 
+	  for(g->first(f,s); g->valid(f); g->next(f))
 	    {
 	      if ( (*flow)[f] <= 0 ) continue;
 	      Node w=g->tail(f);
-	      if ( level[w] < n ) {	  
+	      if ( level[w] < n ) {
 		if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
 		excess.set(w, excess[w]+(*flow)[f]);
-		flow->set(f, 0); 
+		flow->set(f, 0);
 	      }
-	    }  
+	    }
 	  break;
-	} //case PREFLOW
+	} //case PRE_FLOW
       }
     } //preflowPreproc
 
 
 
-    void relabel(Node w, int newlevel, VecStack& active,  
-		 VecNode& level_list, NNMap& left, 
-		 NNMap& right, int& b, int& k, bool what_heur ) 
+    void relabel(Node w, int newlevel, VecStack& active,
+		 VecNode& level_list, NNMap& left,
+		 NNMap& right, int& b, int& k, bool what_heur )
     {
 
-      Num lev=level[w];	
-      
+      Num lev=level[w];
+
       Node right_n=right[w];
       Node left_n=left[w];
-      
+
       //unlacing starts
       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;   
+	  level_list[lev]=right_n;
 	  left.set(right_n, INVALID);
-	} 
+	}
       } else {
 	if ( g->valid(left_n) ) {
 	  right.set(left_n, INVALID);
-	} else { 
-	  level_list[lev]=INVALID;   
-	} 
-      } 
+	} else {
+	  level_list[lev]=INVALID;
+	}
+      }
       //unlacing ends
-		
+
       if ( !g->valid(level_list[lev]) ) {
-	      
+
 	//gapping starts
 	for (int i=lev; i!=k ; ) {
 	  Node v=level_list[++i];
@@ -528,17 +534,17 @@
 	    while ( !active[i].empty() ) {
 	      active[i].pop();    //FIXME: ezt szebben kene
 	    }
-	  }	     
+	  }
 	}
-	
+
 	level.set(w,n);
 	b=lev-1;
 	k=b;
 	//gapping ends
-	
+
       } else {
-	
-	if ( newlevel == n ) level.set(w,n); 
+
+	if ( newlevel == n ) level.set(w,n);
 	else {
 	  level.set(w,++newlevel);
 	  active[newlevel].push(w);
@@ -551,54 +557,55 @@
 	  level_list[newlevel]=w;
 	}
       }
-      
+
     } //relabel
 
 
-    template<typename MapGraphWrapper> 
+    template<typename MapGraphWrapper>
     class DistanceMap {
     protected:
       const MapGraphWrapper* g;
-      typename MapGraphWrapper::template NodeMap<int> dist; 
+      typename MapGraphWrapper::template NodeMap<int> dist;
     public:
       DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { }
-      void set(const typename MapGraphWrapper::Node& n, int a) { 
-	dist.set(n, a); 
+      void set(const typename MapGraphWrapper::Node& n, int a) {
+	dist.set(n, a);
       }
-      int operator[](const typename MapGraphWrapper::Node& n) 
+      int operator[](const typename MapGraphWrapper::Node& n)
       { return dist[n]; }
-      //       int get(const typename MapGraphWrapper::Node& n) const { 
+      //       int get(const typename MapGraphWrapper::Node& n) const {
       // 	return dist[n]; }
-      //       bool get(const typename MapGraphWrapper::Edge& e) const { 
+      //       bool get(const typename MapGraphWrapper::Edge& e) const {
       // 	return (dist.get(g->tail(e))<dist.get(g->head(e))); }
-      bool operator[](const typename MapGraphWrapper::Edge& e) const { 
-	return (dist[g->tail(e)]<dist[g->head(e)]); 
+      bool operator[](const typename MapGraphWrapper::Edge& e) const {
+	return (dist[g->tail(e)]<dist[g->head(e)]);
       }
     };
-    
+
   };
 
 
   template <typename Graph, typename Num, typename CapMap, typename FlowMap>
-  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe ) 
+  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe )
   {
-      
-    int heur0=(int)(H0*n);  //time while running 'bound decrease' 
+
+    int heur0=(int)(H0*n);  //time while running 'bound decrease'
     int heur1=(int)(H1*n);  //time while running 'highest label'
     int heur=heur1;         //starting time interval (#of relabels)
     int numrelabel=0;
-     
-    bool what_heur=1;       
+
+    bool what_heur=1;
     //It is 0 in case 'bound decrease' and 1 in case 'highest label'
 
-    bool end=false;     
-    //Needed for 'bound decrease', true means no active nodes are above bound b.
+    bool end=false;
+    //Needed for 'bound decrease', true means no active nodes are above bound
+    //b.
 
     int k=n-2;  //bound on the highest level under n containing a node
     int b=k;    //bound on the highest level under n of an active node
-      
+
     VecStack active(n);
-      
+
     NNMap left(*g, INVALID);
     NNMap right(*g, INVALID);
     VecNode level_list(n,INVALID);
@@ -607,22 +614,22 @@
     NodeIt v;
     for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
     //setting each node to level n
-      
-    switch ( fe ) {
-    case PREFLOW:
+
+    switch (fe) {
+    case PRE_FLOW:
       {
-	//counting the excess
+	//computing the excess
 	NodeIt v;
 	for(g->first(v); g->valid(v); g->next(v)) {
 	  Num exc=0;
-	  
+
 	  InEdgeIt e;
 	  for(g->first(e,v); g->valid(e); g->next(e)) exc+=(*flow)[e];
 	  OutEdgeIt f;
 	  for(g->first(f,v); g->valid(f); g->next(f)) exc-=(*flow)[f];
-	    
-	  excess.set(v,exc);	  
-	    
+
+	  excess.set(v,exc);
+
 	  //putting the active nodes into the stack
 	  int lev=level[v];
 	  if ( exc > 0 && lev < n && v != t ) active[lev].push(v);
@@ -631,26 +638,25 @@
       }
     case GEN_FLOW:
       {
-	//Counting the excess of t
+	//computing the excess of t
 	Num exc=0;
-	  
+
 	InEdgeIt e;
 	for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
 	OutEdgeIt f;
 	for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
-	  
-	excess.set(t,exc);	
-	  
+
+	excess.set(t,exc);
+
 	break;
       }
-    default:
-      break;
+    default:;
     }
-      
-    preflowPreproc( fe, active, level_list, left, right );
-    //End of preprocessing 
-      
-      
+
+    preflowPreproc(fe, active, level_list, left, right);
+    //End of preprocessing
+
+
     //Push/relabel on the highest level active nodes.
     while ( true ) {
       if ( b == 0 ) {
@@ -659,17 +665,17 @@
 	  end=true;
 	} else break;
       }
-	
-      if ( active[b].empty() ) --b; 
+
+      if ( active[b].empty() ) --b;
       else {
-	end=false;  
+	end=false;
 	Node w=active[b].top();
 	active[b].pop();
 	int newlevel=push(w,active);
-	if ( excess[w] > 0 ) relabel(w, newlevel, active, level_list, 
+	if ( excess[w] > 0 ) relabel(w, newlevel, active, level_list,
 				     left, right, b, k, what_heur);
-	  
-	++numrelabel; 
+
+	++numrelabel;
 	if ( numrelabel >= heur ) {
 	  numrelabel=0;
 	  if ( what_heur ) {
@@ -679,49 +685,49 @@
 	  } else {
 	    what_heur=1;
 	    heur=heur1;
-	    b=k; 
+	    b=k;
 	  }
 	}
-      } 
-    } 
+      }
+    }
   }
 
 
 
   template <typename Graph, typename Num, typename CapMap, typename FlowMap>
-  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1() 
+  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1()
   {
-      
+
     int k=n-2;  //bound on the highest level under n containing a node
     int b=k;    //bound on the highest level under n of an active node
-      
+
     VecStack active(n);
     level.set(s,0);
     std::queue<Node> bfs_queue;
     bfs_queue.push(s);
-	    
+
     while (!bfs_queue.empty()) {
-	
-      Node v=bfs_queue.front();	
+
+      Node v=bfs_queue.front();
       bfs_queue.pop();
       int l=level[v]+1;
-	      
+
       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 ) { 
+	if ( level[u] >= n ) {
 	  bfs_queue.push(u);
 	  level.set(u, l);
 	  if ( excess[u] > 0 ) active[l].push(u);
 	}
       }
-	
+
       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 ) { 
+	if ( level[u] >= n ) {
 	  bfs_queue.push(u);
 	  level.set(u, l);
 	  if ( excess[u] > 0 ) active[l].push(u);
@@ -731,14 +737,14 @@
     b=n-2;
 
     while ( true ) {
-	
+
       if ( b == 0 ) break;
 
-      if ( active[b].empty() ) --b; 
+      if ( active[b].empty() ) --b;
       else {
 	Node w=active[b].top();
 	active[b].pop();
-	int newlevel=push(w,active);	  
+	int newlevel=push(w,active);
 
 	//relabel
 	if ( excess[w] > 0 ) {
@@ -753,23 +759,23 @@
 
 
   template <typename Graph, typename Num, typename CapMap, typename FlowMap>
-  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath() 
+  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath()
   {
     ResGW res_graph(*g, *capacity, *flow);
     bool _augment=false;
-      
+
     //ReachedMap level(res_graph);
     FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
     BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
     bfs.pushAndSetReached(s);
-	
-    typename ResGW::template NodeMap<ResGWEdge> pred(res_graph); 
+
+    typename ResGW::template NodeMap<ResGWEdge> pred(res_graph);
     pred.set(s, INVALID);
-      
+
     typename ResGW::template NodeMap<Num> free(res_graph);
-	
+
     //searching for augmenting path
-    while ( !bfs.finished() ) { 
+    while ( !bfs.finished() ) {
       ResGWOutEdgeIt e=bfs;
       if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
 	Node v=res_graph.tail(e);
@@ -778,20 +784,20 @@
 	if (res_graph.valid(pred[v])) {
 	  free.set(w, std::min(free[v], res_graph.resCap(e)));
 	} else {
-	  free.set(w, res_graph.resCap(e)); 
+	  free.set(w, res_graph.resCap(e));
 	}
 	if (res_graph.head(e)==t) { _augment=true; break; }
       }
-	
+
       ++bfs;
     } //end of searching augmenting path
 
     if (_augment) {
       Node n=t;
       Num augment_value=free[t];
-      while (res_graph.valid(pred[n])) { 
+      while (res_graph.valid(pred[n])) {
 	ResGWEdge e=pred[n];
-	res_graph.augment(e, augment_value); 
+	res_graph.augment(e, augment_value);
 	n=res_graph.tail(e);
       }
     }
@@ -805,12 +811,10 @@
 
 
 
-
-
   template <typename Graph, typename Num, typename CapMap, typename FlowMap>
-  template<typename MutableGraph> 
-  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow() 
-  {      
+  template<typename MutableGraph>
+  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow()
+  {
     typedef MutableGraph MG;
     bool _augment=false;
 
@@ -821,13 +825,13 @@
     FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
     BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
     bfs.pushAndSetReached(s);
-    typename ResGW::template NodeMap<int> 
+    typename ResGW::template NodeMap<int>
       dist(res_graph); //filled up with 0's
 
     //F will contain the physical copy of the residual graph
     //with the set of edges which are on shortest paths
     MG F;
-    typename ResGW::template NodeMap<typename MG::Node> 
+    typename ResGW::template NodeMap<typename MG::Node>
       res_graph_to_F(res_graph);
     {
       typename ResGW::NodeIt n;
@@ -841,19 +845,21 @@
     typename MG::template EdgeMap<ResGWEdge> original_edge(F);
     typename MG::template EdgeMap<Num> residual_capacity(F);
 
-    while ( !bfs.finished() ) { 
+    while ( !bfs.finished() ) {
       ResGWOutEdgeIt e=bfs;
       if (res_graph.valid(e)) {
 	if (bfs.isBNodeNewlyReached()) {
 	  dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
-	  typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
+	  typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)],
+					res_graph_to_F[res_graph.head(e)]);
 	  original_edge.update();
 	  original_edge.set(f, e);
 	  residual_capacity.update();
 	  residual_capacity.set(f, res_graph.resCap(e));
 	} else {
 	  if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) {
-	    typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
+	    typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)],
+					  res_graph_to_F[res_graph.head(e)]);
 	    original_edge.update();
 	    original_edge.set(f, e);
 	    residual_capacity.update();
@@ -876,7 +882,7 @@
 
       typename MG::template NodeMap<Num> free(F);
 
-      dfs.pushAndSetReached(sF);      
+      dfs.pushAndSetReached(sF);
       while (!dfs.finished()) {
 	++dfs;
 	if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
@@ -887,58 +893,56 @@
 	    if (F.valid(pred[v])) {
 	      free.set(w, std::min(free[v], residual_capacity[dfs]));
 	    } else {
-	      free.set(w, residual_capacity[dfs]); 
+	      free.set(w, residual_capacity[dfs]);
 	    }
-	    if (w==tF) { 
-	      __augment=true; 
+	    if (w==tF) {
+	      __augment=true;
 	      _augment=true;
-	      break; 
+	      break;
 	    }
-	      
+
 	  } else {
 	    F.erase(/*typename MG::OutEdgeIt*/(dfs));
 	  }
-	} 
+	}
       }
 
       if (__augment) {
 	typename MG::Node n=tF;
 	Num augment_value=free[tF];
-	while (F.valid(pred[n])) { 
+	while (F.valid(pred[n])) {
 	  typename MG::Edge e=pred[n];
-	  res_graph.augment(original_edge[e], augment_value); 
+	  res_graph.augment(original_edge[e], augment_value);
 	  n=F.tail(e);
-	  if (residual_capacity[e]==augment_value) 
-	    F.erase(e); 
-	  else 
+	  if (residual_capacity[e]==augment_value)
+	    F.erase(e);
+	  else
 	    residual_capacity.set(e, residual_capacity[e]-augment_value);
 	}
       }
-	
+
     }
-            
+
     return _augment;
   }
 
 
 
 
-
-
   template <typename Graph, typename Num, typename CapMap, typename FlowMap>
-  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2() 
+  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2()
   {
     bool _augment=false;
 
     ResGW res_graph(*g, *capacity, *flow);
-      
+
     //ReachedMap level(res_graph);
     FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
     BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
 
     bfs.pushAndSetReached(s);
     DistanceMap<ResGW> dist(res_graph);
-    while ( !bfs.finished() ) { 
+    while ( !bfs.finished() ) {
       ResGWOutEdgeIt e=bfs;
       if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
 	dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
@@ -948,17 +952,17 @@
 
       //Subgraph containing the edges on some shortest paths
     ConstMap<typename ResGW::Node, bool> true_map(true);
-    typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>, 
+    typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
       DistanceMap<ResGW> > FilterResGW;
     FilterResGW filter_res_graph(res_graph, true_map, dist);
 
-    //Subgraph, which is able to delete edges which are already 
+    //Subgraph, which is able to delete edges which are already
     //met by the dfs
-    typename FilterResGW::template NodeMap<typename FilterResGW::OutEdgeIt> 
+    typename FilterResGW::template NodeMap<typename FilterResGW::OutEdgeIt>
       first_out_edges(filter_res_graph);
     typename FilterResGW::NodeIt v;
-    for(filter_res_graph.first(v); filter_res_graph.valid(v); 
-	filter_res_graph.next(v)) 
+    for(filter_res_graph.first(v); filter_res_graph.valid(v);
+	filter_res_graph.next(v))
       {
  	typename FilterResGW::OutEdgeIt e;
  	filter_res_graph.first(e, v);
@@ -974,57 +978,60 @@
 
       __augment=false;
       //computing blocking flow with dfs
-      DfsIterator< ErasingResGW, 
-	typename ErasingResGW::template NodeMap<bool> > 
+      DfsIterator< ErasingResGW,
+	typename ErasingResGW::template NodeMap<bool> >
 	dfs(erasing_res_graph);
       typename ErasingResGW::
-	template NodeMap<typename ErasingResGW::OutEdgeIt> 
-	pred(erasing_res_graph); 
+	template NodeMap<typename ErasingResGW::OutEdgeIt>
+	pred(erasing_res_graph);
       pred.set(s, INVALID);
       //invalid iterators for sources
 
-      typename ErasingResGW::template NodeMap<Num> 
+      typename ErasingResGW::template NodeMap<Num>
 	free1(erasing_res_graph);
 
-      dfs.pushAndSetReached(
-			    typename ErasingResGW::Node(
-							typename FilterResGW::Node(
-										   typename ResGW::Node(s)
-										   )
-							)
-			    );
+      dfs.pushAndSetReached
+	///\bug hugo 0.2
+	(typename ErasingResGW::Node
+	 (typename FilterResGW::Node
+	  (typename ResGW::Node(s)
+	   )
+	  )
+	 );
       while (!dfs.finished()) {
 	++dfs;
-	if (erasing_res_graph.valid(
-				    typename ErasingResGW::OutEdgeIt(dfs))) 
- 	  { 
+	if (erasing_res_graph.valid(typename ErasingResGW::OutEdgeIt(dfs)))
+ 	  {
   	    if (dfs.isBNodeNewlyReached()) {
-	  
+
  	      typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);
  	      typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
 
  	      pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
  	      if (erasing_res_graph.valid(pred[v])) {
- 		free1.set(w, std::min(free1[v], res_graph.resCap(
-								 typename ErasingResGW::OutEdgeIt(dfs))));
+ 		free1.set
+		  (w, std::min(free1[v], res_graph.resCap
+			       (typename ErasingResGW::OutEdgeIt(dfs))));
  	      } else {
- 		free1.set(w, res_graph.resCap(
-					      typename ErasingResGW::OutEdgeIt(dfs))); 
+ 		free1.set
+		  (w, res_graph.resCap
+		   (typename ErasingResGW::OutEdgeIt(dfs)));
  	      }
-	      
- 	      if (w==t) { 
- 		__augment=true; 
+
+ 	      if (w==t) {
+ 		__augment=true;
  		_augment=true;
- 		break; 
+ 		break;
  	      }
  	    } else {
  	      erasing_res_graph.erase(dfs);
 	    }
 	  }
-      }	
+      }
 
       if (__augment) {
-	typename ErasingResGW::Node n=typename FilterResGW::Node(typename ResGW::Node(t));
+	typename ErasingResGW::Node
+	  n=typename FilterResGW::Node(typename ResGW::Node(t));
 	// 	  typename ResGW::NodeMap<Num> a(res_graph);
 	// 	  typename ResGW::Node b;
 	// 	  Num j=a[b];
@@ -1035,7 +1042,7 @@
 	// 	  typename ErasingResGW::Node b2;
 	// 	  Num j2=a2[b2];
 	Num augment_value=free1[n];
-	while (erasing_res_graph.valid(pred[n])) { 
+	while (erasing_res_graph.valid(pred[n])) {
 	  typename ErasingResGW::OutEdgeIt e=pred[n];
 	  res_graph.augment(e, augment_value);
 	  n=erasing_res_graph.tail(e);
@@ -1043,15 +1050,13 @@
 	    erasing_res_graph.erase(e);
 	}
       }
-      
-    } //while (__augment) 
-            
+
+    } //while (__augment)
+
     return _augment;
   }
 
 
-
-
 } //namespace hugo
 
 #endif //HUGO_MAX_FLOW_H
diff -r 75cf1d52eee5 -r b6b31b75b522 src/work/marci/bfs_dfs.h
--- a/src/work/marci/bfs_dfs.h	Tue May 11 19:38:00 2004 +0000
+++ b/src/work/marci/bfs_dfs.h	Tue May 11 19:50:21 2004 +0000
@@ -2,13 +2,13 @@
 #ifndef HUGO_BFS_DFS_H
 #define HUGO_BFS_DFS_H
 
-// ///\ingroup gwrappers
-///\file
-///\brief Bfs and dfs iterators.
+/// \ingroup galgs
+/// \file
+/// \brief Bfs and dfs iterators.
 ///
-///This file contains bfs and dfs iterator classes.
+/// This file contains bfs and dfs iterator classes.
 ///
-// ///\author Marton Makai
+// /// \author Marton Makai
 
 #include <queue>
 #include <stack>
@@ -21,6 +21,7 @@
   /// Bfs searches for the nodes wich are not marked in 
   /// \c reached_map
   /// Reached have to work as read-write bool Node-map.
+  /// \ingroup galgs
   template <typename Graph, /*typename OutEdgeIt,*/ 
 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
   class BfsIterator {
@@ -105,33 +106,32 @@
       }
       return *this;
     }
-    ///
+    /// Guess what?
     bool finished() const { return bfs_queue.empty(); }
     /// The conversion operator makes for converting the bfs-iterator 
     /// to an \c out-edge-iterator.
     ///\bug Edge have to be in HUGO 0.2
     operator OutEdgeIt() const { return actual_edge; }
-    ///
+    /// Guess what?
     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
-    ///
+    /// Guess what?
     bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
-    ///
+    /// Guess what?
     Node aNode() const { return bfs_queue.front(); }
-    ///
+    /// Guess what?
     Node bNode() const { return graph->bNode(actual_edge); }
-    ///
+    /// Guess what?
     const ReachedMap& getReachedMap() const { return reached; }
-    ///
+    /// Guess what?
     const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
-  };  
+  };
 
   /// Bfs searches for the nodes wich are not marked in 
   /// \c reached_map
   /// Reached have to work as a read-write bool Node-map, 
   /// Pred is a write Edge Node-map and
-  /// Dist is a read-write int Node-map, have to be. 
-  ///\todo In fact onsly simple operations requirement are needed for 
-  /// Dist::Value.
+  /// Dist is a read-write Node-map of integral value, have to be. 
+  /// \ingroup galgs
   template <typename Graph, 
 	    typename ReachedMap=typename Graph::template NodeMap<bool>, 
 	    typename PredMap
@@ -178,15 +178,16 @@
       }
       return *this;
     }
-    ///
+    /// Guess what?
     const PredMap& getPredMap() const { return pred; }
-    ///
+    /// Guess what?
     const DistMap& getDistMap() const { return dist; }
   };
 
   /// Dfs searches for the nodes wich are not marked in 
   /// \c reached_map
   /// Reached have to be a read-write bool Node-map.
+  /// \ingroup galgs
   template <typename Graph, /*typename OutEdgeIt,*/ 
 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
   class DfsIterator {
@@ -248,21 +249,21 @@
       }
       return *this;
     }
-    ///
+    /// Guess what?
     bool finished() const { return dfs_stack.empty(); }
-    ///
+    /// Guess what?
     operator OutEdgeIt() const { return actual_edge; }
-    ///
+    /// Guess what?
     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
-    ///
+    /// Guess what?
     bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
-    ///
+    /// Guess what?
     Node aNode() const { return actual_node; /*FIXME*/}
-    ///
+    /// Guess what?
     Node bNode() const { return graph->bNode(actual_edge); }
-    ///
+    /// Guess what?
     const ReachedMap& getReachedMap() const { return reached; }
-    ///
+    /// Guess what?
     const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
   };
 
@@ -270,6 +271,7 @@
   /// \c reached_map
   /// Reached is a read-write bool Node-map, 
   /// Pred is a write Node-map, have to be.
+  /// \ingroup galgs
   template <typename Graph, 
 	    typename ReachedMap=typename Graph::template NodeMap<bool>, 
 	    typename PredMap
@@ -312,7 +314,7 @@
       }
       return *this;
     }
-    ///
+    /// Guess what?
     const PredMap& getPredMap() const { return pred; }
   };
 
diff -r 75cf1d52eee5 -r b6b31b75b522 src/work/marci/bfs_dfs_misc.h
--- a/src/work/marci/bfs_dfs_misc.h	Tue May 11 19:38:00 2004 +0000
+++ b/src/work/marci/bfs_dfs_misc.h	Tue May 11 19:50:21 2004 +0000
@@ -2,11 +2,11 @@
 #ifndef HUGO_BFS_DFS_MISC_H
 #define HUGO_BFS_DFS_MISC_H
 
-// ///\ingroup gwrappers
-///\file
-///\brief Miscellaneous algorithms using bfs and dfs.
+/// \ingroup galgs
+/// \file
+/// \brief Miscellaneous algorithms using bfs and dfs.
 ///
-///This file contains several algorithms using bfs and dfs.
+/// This file contains several algorithms using bfs and dfs.
 ///
 // ///\author Marton Makai
 
@@ -15,10 +15,11 @@
 
 namespace hugo {
 
-  /// This function eat a read-write \c BoolMap& bool_map, 
+  /// This function eats a read-write \c BoolMap& bool_map, 
   /// which have to work well up 
   /// to its \c set and \c operator[]() method. Thus we have to deal 
   /// very carefully with an uninitialized \c IterableBoolMap.
+  /// \ingroup galgs
   template<typename Graph, typename BoolMap> 
   bool isBipartite(const Graph& g, BoolMap& bool_map) {
     typedef typename Graph::template NodeMap<bool> ReachedMap;
@@ -52,6 +53,7 @@
   /// If the graph is directed and not acyclic, 
   /// then going back from the returned node via the pred information, a 
   /// cycle is obtained.
+  /// \ingroup galgs
   template<typename Graph, typename PredMap> 
   typename Graph::Node 
   topSort(const Graph& g, std::list<typename Graph::Node>& l, 
@@ -89,6 +91,7 @@
     }
     return INVALID;
   }
+
 } //namespace hugo
 
 #endif //HUGO_BFS_DFS_MISC_H
diff -r 75cf1d52eee5 -r b6b31b75b522 src/work/marci/makefile
--- a/src/work/marci/makefile	Tue May 11 19:38:00 2004 +0000
+++ b/src/work/marci/makefile	Tue May 11 19:50:21 2004 +0000
@@ -4,7 +4,7 @@
 INCLUDEDIRS ?= -I../.. -I.. -I../{marci,jacint,alpar,klao,akos,athos} -I$(BOOSTROOT)
 
 LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
-BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_3 top_sort_test
+BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_3 top_sort_test max_flow_1
 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
 
 include ../makefile
diff -r 75cf1d52eee5 -r b6b31b75b522 src/work/marci/max_bipartite_matching.h
--- a/src/work/marci/max_bipartite_matching.h	Tue May 11 19:38:00 2004 +0000
+++ b/src/work/marci/max_bipartite_matching.h	Tue May 11 19:50:21 2004 +0000
@@ -2,6 +2,16 @@
 #ifndef HUGO_MAX_BIPARTITE_MATCHING_H
 #define HUGO_MAX_BIPARTITE_MATCHING_H
 
+/// \ingroup galgs
+/// \file
+/// \brief Maximum bipartite matchings, b-matchings and 
+/// capacitated b-matchings.
+///
+/// This file contains a class for bipartite maximum matching, b-matchings 
+/// and capacitated b-matching computations.
+///
+// /// \author Marton Makai
+
 //#include <for_each_macros.h>
 #include <bipartite_graph_wrapper.h>
 //#include <hugo/maps.h>
diff -r 75cf1d52eee5 -r b6b31b75b522 src/work/marci/max_flow_1.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/marci/max_flow_1.cc	Tue May 11 19:50:21 2004 +0000
@@ -0,0 +1,60 @@
+// -*- c++ -*-
+#include <iostream>
+#include <fstream>
+
+#include <list_graph.h>
+#include <hugo/smart_graph.h>
+#include <hugo/dimacs.h>
+#include <hugo/time_measure.h>
+//#include <graph_wrapper.h>
+#include <max_flow.h>
+//#include <preflow_res.h>
+#include <for_each_macros.h>
+
+using namespace hugo;
+
+// Use a DIMACS max flow file as stdin.
+// read_dimacs_demo < dimacs_max_flow_file
+
+
+int main(int, char **) {
+
+  typedef ListGraph MutableGraph;
+
+  typedef SmartGraph Graph;
+  //  typedef ListGraph Graph;
+  typedef Graph::Node Node;
+  typedef Graph::EdgeIt EdgeIt;
+
+
+  Graph g;
+  Node s, t;
+  Graph::EdgeMap<int> cap(g);
+  //readDimacsMaxFlow(std::cin, g, s, t, cap);
+  readDimacs(std::cin, g, cap, s, t);
+  Timer ts;
+  Graph::EdgeMap<int> flow(g); //0 flow
+  MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
+    max_flow_test(g, s, t, cap, flow);
+
+  {
+    std::cout << "preflow ..." << std::endl;
+    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+    ts.reset();
+    max_flow_test.preflowPhase0(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::ZERO_FLOW);
+    std::cout << "elapsed time: " << ts << std::endl;
+    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+  }
+
+  {
+    std::cout << "preflow ..." << std::endl;
+    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+    ts.reset();
+    max_flow_test.preflowPhase0(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::ZERO_FLOW);
+    std::cout << "elapsed time: " << ts << std::endl;
+    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+  }
+
+
+  return 0;
+}