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 ,
@@ 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 ReachedMap;
typedef typename Graph::template NodeMap 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 level;
+
+ //excess is needed only in preflow
typename Graph::template NodeMap 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 inflows equals to
+ ///the sum of the outflows in every node except the \e source and
+ ///the \e target.
+ /// \c PRE_FLOW: any preflow, i.e. the sum of the inflows is at
+ ///least the sum of the outflows 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 uptodate. 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 edgemap have to be a
 /// zero flow if \c fe is \c ZERO_FLOW,
 /// a flow if \c fe is \c GEN_FLOW,
 /// a preflow 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
+ /// overflow 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 nodeset.
+ ///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
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
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
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; }
 /// capacitymap 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; }
 /// flowmap 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
 void MaxFlow::preflowPhase0( flowEnum fe )
+ void MaxFlow::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
 void MaxFlow::preflowPhase1()
+ void MaxFlow::preflowPhase2()
{