Context Navigation

← Previous Change
Next Change →

Changeset 631:26819ef1611f in lemon-0.x for src/work

Timestamp:

05/13/04 12:30:20 (21 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@822

Message:

Almost full documentation added, NO_FLOW incorporated, Phase0(1) changed to Phase1(2)

File:

: 1 edited

src/work/jacint/max_flow.h (modified) (16 diffs)

Legend:

: Unmodified
: Added
: Removed

src/work/jacint/max_flow.h

-                      r615
+                      r631
 // -*- C++ -*-
-/*
-  Heuristics:
-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
 …
 /// \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>,
 …
     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;
 …
     //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,
 …
   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,
 …
       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
 …
     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;
 …
       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
 …
+    }
+    /// 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) {
 …
+    }
+    /// 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) {
 …
+    }
+    /// 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; }
 …
       switch (fe) {
+      case NO_FLOW:   //flow is already set to const zero in this case
       case ZERO_FLOW:
+        {
 …
   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 )
+  {
 …
     //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)) {
 …
     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;
+      }
+    }
 …
   template <typename Graph, typename Num, typename CapMap, typename FlowMap>
   void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1()
+  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase2()
+  {

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset 631:26819ef1611f in lemon-0.x for src/work

Legend:

src/work/jacint/max_flow.h

Download in other formats: