Index: src/work/jacint/max_flow.h
===================================================================
--- src/work/jacint/max_flow.h	(revision 615)
+++ src/work/jacint/max_flow.h	(revision 631)
@@ -1,37 +1,3 @@
 // -*- C++ -*-
-
-/*
-  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
-  FlowMap is not constant zero, and should be true if it is
-
-  Members:
-
-  void run()
-
-  Num 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. ??Is it OK?
-
-  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
-  a min cut. M should be a map of bools initialized to false.
-
-*/
-
 #ifndef HUGO_MAX_FLOW_H
 #define HUGO_MAX_FLOW_H
@@ -48,13 +14,33 @@
 
 /// \file
-/// \brief Maximum flows.
+/// \brief Maximum flow algorithms.
 /// \ingroup galgs
 
 namespace hugo {
 
-
-  //  ///\author Marton Makai, Jacint Szabo
-  /// A class for computing max flows and related quantities.
-  /// \ingroup galgs
+  /// \addtogroup galgs
+  /// @{                                                                                                                                        
+  ///Maximum flow algorithms class.
+
+  ///This class provides various algorithms for finding a flow of
+  ///maximum value in a directed graph. The \e source node, the \e
+  ///target node, the \e capacity of the edges and the \e starting \e
+  ///flow value of the edges can be passed to the algorithm through the
+  ///constructor. It is possible to change these quantities using the
+  ///functions \ref resetSource, \ref resetTarget, \ref resetCap and
+  ///\ref resetFlow. Before any subsequent runs of any algorithm of
+  ///the class \ref resetFlow should be called, otherwise it will
+  ///start from a maximum flow.                                                                                                                 
+  ///After running an algorithm of the class, the maximum value of a
+  ///value can be obtained by calling \ref flowValue(). The minimum
+  ///value cut can be written into a \c node map of \c bools by
+  ///calling \ref minCut. (\ref minMinCut and \ref maxMinCut writes
+  ///the inclusionwise minimum and maximum of the minimum value
+  ///cuts, resp.)                                                                                                                               
+  ///\param Graph The undirected graph type the algorithm runs on.
+  ///\param Num The number type of the capacities and the flow values.
+  ///\param CapMap The type of the capacity map.
+  ///\param FlowMap The type of the flow map.                                                                                                           
+  ///\author Marton Makai, Jacint Szabo 
   template <typename Graph, typename Num,
 	    typename CapMap=typename Graph::template EdgeMap<Num>,
@@ -64,4 +50,5 @@
     typedef typename Graph::Node Node;
     typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::EdgeIt EdgeIt;
     typedef typename Graph::OutEdgeIt OutEdgeIt;
     typedef typename Graph::InEdgeIt InEdgeIt;
@@ -82,11 +69,16 @@
     //typedef typename ResGW::template NodeMap<bool> ReachedMap;
     typedef typename Graph::template NodeMap<int> ReachedMap;
+
+
+    //level works as a bool map in augmenting path algorithms and is
+    //used by bfs for storing reached information.  In preflow, it
+    //shows the levels of nodes.     
     ReachedMap level;
-    //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;
+
+    //excess is needed only in preflow
     typename Graph::template NodeMap<Num> excess;
-    //   protected:
+
+    //fixme    
+//   protected:
     //     MaxFlow() { }
     //     void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
@@ -109,10 +101,15 @@
   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 PRE_FLOW is something different.
+    ///Indicates the property of the starting flow.
+
+    ///Indicates the property of the starting flow. The meanings are as follows:
+    ///- \c ZERO_FLOW: constant zero flow
+    ///- \c GEN_FLOW: any flow, i.e. the sum of the in-flows equals to
+    ///the sum of the out-flows in every node except the \e source and
+    ///the \e target.
+    ///- \c PRE_FLOW: any preflow, i.e. the sum of the in-flows is at 
+    ///least the sum of the out-flows in every node except the \e source.
+    ///- \c NO_FLOW: indicates an unspecified edge map. \ref flow will be 
+    ///set to the constant zero flow in the beginning of the algorithm in this case.
     enum flowEnum{
       ZERO_FLOW,
@@ -127,28 +124,64 @@
       flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {}
 
-    /// A max flow algorithm is run.
-    /// \pre The flow have to satisfy the requirements
-    /// stated in fe.
+    ///Runs a maximum flow algorithm.
+
+    ///Runs a preflow algorithm, which is the fastest maximum flow
+    ///algorithm up-to-date. The default for \c fe is ZERO_FLOW.
+    ///\pre The starting flow must be
+    /// - a constant zero flow if \c fe is \c ZERO_FLOW,
+    /// - an arbitary flow if \c fe is \c GEN_FLOW,
+    /// - an arbitary preflow if \c fe is \c PRE_FLOW,
+    /// - any map if \c fe is NO_FLOW.
     void run(flowEnum fe=ZERO_FLOW) {
       preflow(fe);
     }
 
-    /// 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,
-    /// a pre-flow if fe is \c PRE_FLOW and
-    /// anything if fe is NO_FLOW.
+                                                                                             
+    ///Runs a preflow algorithm.  
+
+    ///Runs a preflow algorithm. The preflow algorithms provide the
+    ///fastest way to compute a maximum flow in a directed graph.
+    ///\pre The starting flow must be
+    /// - a constant zero flow if \c fe is \c ZERO_FLOW,
+    /// - an arbitary flow if \c fe is \c GEN_FLOW,
+    /// - an arbitary preflow if \c fe is \c PRE_FLOW,
+    /// - any map if \c 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, of from undefined value according to \c fe.
-    void preflowPhase0(flowEnum fe);
-
-    /// Second phase of preflow.
-    void preflowPhase1();
+      preflowPhase1(fe);
+      preflowPhase2();
+    }
+    // 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.
+
+    ///Runs the first phase of the preflow algorithm.
+
+    ///The preflow algorithm consists of two phases, this method runs the
+    ///first phase. After the first phase the maximum flow value and a
+    ///minimum value cut can already be computed, though a maximum flow
+    ///is net yet obtained. So after calling this method \ref flowValue
+    ///and \ref actMinCut gives proper results.
+    ///\warning: \ref minCut, \ref minMinCut and \ref maxMinCut do not
+    ///give minimum value cuts unless calling \ref preflowPhase2.
+    ///\pre The starting flow must be
+    /// - a constant zero flow if \c fe is \c ZERO_FLOW,
+    /// - an arbitary flow if \c fe is \c GEN_FLOW,
+    /// - an arbitary preflow if \c fe is \c PRE_FLOW,
+    /// - any map if \c fe is NO_FLOW.
+    void preflowPhase1( flowEnum fe );
+
+    ///Runs the second phase of the preflow algorithm.
+
+    ///The preflow algorithm consists of two phases, this method runs
+    ///the second phase. After calling \ref preflowPhase1 and then
+    ///\ref preflowPhase2 the methods \ref flowValue, \ref minCut,
+    ///\ref minMinCut and \ref maxMinCut give proper results.
+    ///\pre \ref preflowPhase1 must be called before.
+    void preflowPhase2();
 
     /// Starting from a flow, this method searches for an augmenting path
@@ -170,7 +203,9 @@
     bool augmentOnBlockingFlow2();
 
-    /// Returns the actual flow value.
-    /// More precisely, it returns the negative excess of s, thus
-    /// this works also for preflows.
+    /// Returns the maximum value of a flow.
+
+    /// Returns the maximum value of a flow, by counting the 
+    /// over-flow of the target node \ref t.
+    /// It can be called already after running \ref preflowPhase1.
     Num flowValue() {
       Num a=0;
@@ -178,7 +213,15 @@
       FOR_EACH_INC_LOC(OutEdgeIt, e, *g, t) a-=(*flow)[e];
       return a;
-    }
-
-    /// Should be used between preflowPhase0 and preflowPhase1.
+      //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan   
+    }
+
+    ///Returns a minimum value cut after calling \ref preflowPhase1.
+
+    ///After the first phase of the preflow algorithm the maximum flow
+    ///value and a minimum value cut can already be computed. This
+    ///method can be called after running \ref preflowPhase1 for
+    ///obtaining a minimum value cut.
+    /// \warning Gives proper result only right after calling \ref
+    /// preflowPhase1.
     /// \todo We have to make some status variable which shows the
     /// actual state
@@ -197,7 +240,11 @@
     }
 
-    /// 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.
+    ///Returns the inclusionwise minimum of the minimum value cuts.
+
+    ///Sets \c M to the characteristic vector of the minimum value cut
+    ///which is inclusionwise minimum. It is computed by processing
+    ///a bfs from the source node \c s in the residual graph.
+    ///\pre M should be a node map of bools initialized to false.
+    ///\pre \c flow must be a maximum flow.
     template<typename _CutMap>
     void minMinCut(_CutMap& M) {
@@ -232,8 +279,11 @@
     }
 
-
-    /// 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.
+    ///Returns the inclusionwise maximum of the minimum value cuts.
+
+    ///Sets \c M to the characteristic vector of the minimum value cut
+    ///which is inclusionwise maximum. It is computed by processing a
+    ///backward bfs from the target node \c t in the residual graph.
+    ///\pre M should be a node map of bools initialized to false.
+    ///\pre \c flow must be a maximum flow. 
     template<typename _CutMap>
     void maxMinCut(_CutMap& M) {
@@ -273,18 +323,34 @@
     }
 
-
-    /// A minimum cut is computed.
+    ///Returns a minimum value cut.
+
+    ///Sets \c M to the characteristic vector of a minimum value cut.
+    ///\pre M should be a node map of bools initialized to false.
+    ///\pre \c flow must be a maximum flow.    
     template<typename CutMap>
     void minCut(CutMap& M) { minMinCut(M); }
 
-    ///
+    ///Resets the source node to \c _s.
+
+    ///Resets the source node to \c _s.
+    /// 
     void resetSource(Node _s) { s=_s; }
+
+    ///Resets the target node to \c _t.
+
+    ///Resets the target node to \c _t.
     ///
     void resetTarget(Node _t) { t=_t; }
 
-    /// capacity-map is changed.
+    /// Resets the edge map of the capacities to _cap.
+
+    /// Resets the edge map of the capacities to _cap.
+    /// 
     void resetCap(const CapMap& _cap) { capacity=&_cap; }
 
-    /// flow-map is changed.
+    /// Resets the edge map of the flows to _flow.
+
+    /// Resets the edge map of the flows to _flow.
+    /// 
     void resetFlow(FlowMap& _flow) { flow=&_flow; }
 
@@ -375,4 +441,5 @@
 
       switch (fe) {
+      case NO_FLOW:   //flow is already set to const zero in this case
       case ZERO_FLOW:
 	{
@@ -587,5 +654,5 @@
 
   template <typename Graph, typename Num, typename CapMap, typename FlowMap>
-  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe )
+  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1( flowEnum fe )
   {
 
@@ -616,8 +683,12 @@
     //setting each node to level n
 
-    switch (fe) {
+    if ( fe == NO_FLOW ) {
+      EdgeIt e;
+      for(g->first(e); g->valid(e); g->next(e)) flow->set(e,0);
+    }
+
+    switch (fe) { //computing the excess
     case PRE_FLOW:
       {
-	//computing the excess
 	NodeIt v;
 	for(g->first(v); g->valid(v); g->next(v)) {
@@ -639,17 +710,22 @@
     case GEN_FLOW:
       {
-	//computing the excess of t
+	NodeIt v;
+	for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
+
 	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);
-
 	break;
       }
-    default:;
+    case ZERO_FLOW:
+    case NO_FLOW:
+      {
+	NodeIt v;
+        for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
+	break;
+      }
     }
 
@@ -696,5 +772,5 @@
 
   template <typename Graph, typename Num, typename CapMap, typename FlowMap>
-  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1()
+  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase2()
   {
 
