COIN-OR::LEMON - Graph Library

Changeset 647:19dd325da0e8 in lemon-0.x


Ignore:
Timestamp:
05/19/04 18:09:38 (17 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@847
Message:

the same

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/jacint/max_flow.h

    r640 r647  
    2626  ///maximum value in a directed graph. The \e source node, the \e
    2727  ///target node, the \e capacity of the edges and the \e starting \e
    28   ///flow value of the edges can be passed to the algorithm through the
     28  ///flow value of the edges should be passed to the algorithm through the
    2929  ///constructor. It is possible to change these quantities using the
    3030  ///functions \ref resetSource, \ref resetTarget, \ref resetCap and
    3131  ///\ref resetFlow. Before any subsequent runs of any algorithm of
    32   ///the class \ref resetFlow should be called, otherwise it will
    33   ///start from a maximum flow.                                                                                                                 
    34   ///After running an algorithm of the class, the maximum value of a
    35   ///value can be obtained by calling \ref flowValue(). The minimum
     32  ///the class \ref resetFlow should be called.
     33
     34  ///After running an algorithm of the class, the actual flow value
     35  ///can be obtained by calling \ref flowValue(). The minimum
    3636  ///value cut can be written into a \c node map of \c bools by
    3737  ///calling \ref minCut. (\ref minMinCut and \ref maxMinCut writes
     
    4040  ///\param Graph The directed graph type the algorithm runs on.
    4141  ///\param Num The number type of the capacities and the flow values.
    42   ///\param CapMap The type of the capacity map.
    43   ///\param FlowMap The type of the flow map.                                                                                                           
     42  ///\param CapMap The capacity map type.
     43  ///\param FlowMap The flow map type.                                                                                                           
    4444  ///\author Marton Makai, Jacint Szabo
    4545  template <typename Graph, typename Num,
     
    112112    ///- \c NO_FLOW: indicates an unspecified edge map. \ref flow will be
    113113    ///set to the constant zero flow in the beginning of the algorithm in this case.
    114     enum flowEnum{
     114    enum FlowEnum{
    115115      ZERO_FLOW,
    116116      GEN_FLOW,
     
    119119    };
    120120
     121    enum StatusEnum {
     122      AFTER_NOTHING,
     123      AFTER_AUGMENTING,
     124      AFTER_PRE_FLOW_PHASE_1,     
     125      AFTER_PRE_FLOW_PHASE_2
     126    };
     127
     128    /// Don not needle this flag only if necessary.
     129    StatusEnum status;
     130    int number_of_augmentations;
     131
     132
     133    template<typename IntMap>
     134    class TrickyReachedMap {
     135    protected:
     136      IntMap* map;
     137      int* number_of_augmentations;
     138    public:
     139      TrickyReachedMap(IntMap& _map, int& _number_of_augmentations) :
     140        map(&_map), number_of_augmentations(&_number_of_augmentations) { }
     141      void set(const Node& n, bool b) {
     142        map->set(n, *number_of_augmentations);
     143      }
     144      bool operator[](const Node& n) const {
     145        return (*map)[n]==*number_of_augmentations;
     146      }
     147    };
     148   
    121149    MaxFlow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
    122150            FlowMap& _flow) :
    123151      g(&_G), s(_s), t(_t), capacity(&_capacity),
    124       flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {}
     152      flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0),
     153      status(AFTER_NOTHING), number_of_augmentations(0) { }
    125154
    126155    ///Runs a maximum flow algorithm.
     
    133162    /// - an arbitary preflow if \c fe is \c PRE_FLOW,
    134163    /// - any map if \c fe is NO_FLOW.
    135     void run(flowEnum fe=ZERO_FLOW) {
     164    void run(FlowEnum fe=ZERO_FLOW) {
    136165      preflow(fe);
    137166    }
    138167
    139                                                                                              
     168                                                                             
    140169    ///Runs a preflow algorithm. 
    141170
     
    147176    /// - an arbitary preflow if \c fe is \c PRE_FLOW,
    148177    /// - any map if \c fe is NO_FLOW.
    149     void preflow(flowEnum fe) {
     178    void preflow(FlowEnum fe) {
    150179      preflowPhase1(fe);
    151180      preflowPhase2();
     
    174203    /// - an arbitary preflow if \c fe is \c PRE_FLOW,
    175204    /// - any map if \c fe is NO_FLOW.
    176     void preflowPhase1( flowEnum fe );
     205    void preflowPhase1(FlowEnum fe);
    177206
    178207    ///Runs the second phase of the preflow algorithm.
     
    190219    /// The return value shows if the augmentation was succesful.
    191220    bool augmentOnShortestPath();
     221    bool augmentOnShortestPath2();
    192222
    193223    /// Starting from a flow, this method searches for an augmenting blocking
     
    208238    /// over-flow of the target node \ref t.
    209239    /// It can be called already after running \ref preflowPhase1.
    210     Num flowValue() {
     240    Num flowValue() const {
    211241      Num a=0;
    212242      FOR_EACH_INC_LOC(InEdgeIt, e, *g, t) a+=(*flow)[e];
     
    229259    /// for MinCut computation
    230260    template<typename _CutMap>
    231     void actMinCut(_CutMap& M) {
     261    void actMinCut(_CutMap& M) const {
    232262      NodeIt v;
    233       for(g->first(v); g->valid(v); g->next(v)) {
    234         if ( level[v] < n ) {
    235           M.set(v,false);
    236         } else {
    237           M.set(v,true);
    238         }
     263      switch (status) {
     264        case AFTER_PRE_FLOW_PHASE_1:
     265        for(g->first(v); g->valid(v); g->next(v)) {
     266          if (level[v] < n) {
     267            M.set(v, false);
     268          } else {
     269            M.set(v, true);
     270          }
     271        }
     272        break;
     273        case AFTER_PRE_FLOW_PHASE_2:
     274        case AFTER_NOTHING:
     275        minMinCut(M);
     276        break;
     277        case AFTER_AUGMENTING:
     278        for(g->first(v); g->valid(v); g->next(v)) {
     279          if (level[v]) {
     280            M.set(v, true);
     281          } else {
     282            M.set(v, false);
     283          }
     284        }
     285        break;
    239286      }
    240287    }
     
    248295    ///\pre \c flow must be a maximum flow.
    249296    template<typename _CutMap>
    250     void minMinCut(_CutMap& M) {
    251 
     297    void minMinCut(_CutMap& M) const {
    252298      std::queue<Node> queue;
    253299
     
    287333    ///\pre \c flow must be a maximum flow.
    288334    template<typename _CutMap>
    289     void maxMinCut(_CutMap& M) {
     335    void maxMinCut(_CutMap& M) const {
    290336
    291337      NodeIt v;
     
    329375    ///\pre \c flow must be a maximum flow.   
    330376    template<typename CutMap>
    331     void minCut(CutMap& M) { minMinCut(M); }
     377    void minCut(CutMap& M) const { minMinCut(M); }
    332378
    333379    ///Resets the source node to \c _s.
     
    335381    ///Resets the source node to \c _s.
    336382    ///
    337     void resetSource(Node _s) { s=_s; }
     383    void resetSource(Node _s) { s=_s; status=AFTER_NOTHING; }
    338384
    339385    ///Resets the target node to \c _t.
     
    341387    ///Resets the target node to \c _t.
    342388    ///
    343     void resetTarget(Node _t) { t=_t; }
     389    void resetTarget(Node _t) { t=_t; status=AFTER_NOTHING; }
    344390
    345391    /// Resets the edge map of the capacities to _cap.
     
    347393    /// Resets the edge map of the capacities to _cap.
    348394    ///
    349     void resetCap(const CapMap& _cap) { capacity=&_cap; }
     395    void resetCap(const CapMap& _cap) { capacity=&_cap; status=AFTER_NOTHING; }
    350396
    351397    /// Resets the edge map of the flows to _flow.
     
    353399    /// Resets the edge map of the flows to _flow.
    354400    ///
    355     void resetFlow(FlowMap& _flow) { flow=&_flow; }
     401    void resetFlow(FlowMap& _flow) { flow=&_flow; status=AFTER_NOTHING; }
    356402
    357403
     
    435481
    436482
    437     void preflowPreproc(flowEnum fe, VecStack& active,
     483    void preflowPreproc(FlowEnum fe, VecStack& active,
    438484                        VecNode& level_list, NNMap& left, NNMap& right)
    439485    {
     
    639685        dist.set(n, a);
    640686      }
    641       int operator[](const typename MapGraphWrapper::Node& n)
    642       { return dist[n]; }
     687      int operator[](const typename MapGraphWrapper::Node& n) const {
     688        return dist[n];
     689      }
    643690      //       int get(const typename MapGraphWrapper::Node& n) const {
    644691      //        return dist[n]; }
     
    654701
    655702  template <typename Graph, typename Num, typename CapMap, typename FlowMap>
    656   void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1( flowEnum fe )
     703  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1(FlowEnum fe)
    657704  {
    658705
     
    767814      }
    768815    }
     816
     817    status=AFTER_PRE_FLOW_PHASE_1;
    769818  }
    770819
     
    831880      }  // if stack[b] is nonempty
    832881    } // while(true)
     882
     883    status=AFTER_PRE_FLOW_PHASE_2;
    833884  }
    834885
     
    879930    }
    880931
     932    status=AFTER_AUGMENTING;
    881933    return _augment;
    882934  }
    883935
    884936
    885 
    886 
    887 
     937  template <typename Graph, typename Num, typename CapMap, typename FlowMap>
     938  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath2()
     939  {
     940    ResGW res_graph(*g, *capacity, *flow);
     941    bool _augment=false;
     942
     943    if (status!=AFTER_AUGMENTING) {
     944      FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, -1);
     945      number_of_augmentations=0;
     946    } else {
     947      ++number_of_augmentations;
     948    }
     949    TrickyReachedMap<ReachedMap>
     950      tricky_reached_map(level, number_of_augmentations);
     951    //ReachedMap level(res_graph);
     952//    FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
     953    BfsIterator<ResGW, TrickyReachedMap<ReachedMap> >
     954      bfs(res_graph, tricky_reached_map);
     955    bfs.pushAndSetReached(s);
     956
     957    typename ResGW::template NodeMap<ResGWEdge> pred(res_graph);
     958    pred.set(s, INVALID);
     959
     960    typename ResGW::template NodeMap<Num> free(res_graph);
     961
     962    //searching for augmenting path
     963    while ( !bfs.finished() ) {
     964      ResGWOutEdgeIt e=bfs;
     965      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
     966        Node v=res_graph.tail(e);
     967        Node w=res_graph.head(e);
     968        pred.set(w, e);
     969        if (res_graph.valid(pred[v])) {
     970          free.set(w, std::min(free[v], res_graph.resCap(e)));
     971        } else {
     972          free.set(w, res_graph.resCap(e));
     973        }
     974        if (res_graph.head(e)==t) { _augment=true; break; }
     975      }
     976
     977      ++bfs;
     978    } //end of searching augmenting path
     979
     980    if (_augment) {
     981      Node n=t;
     982      Num augment_value=free[t];
     983      while (res_graph.valid(pred[n])) {
     984        ResGWEdge e=pred[n];
     985        res_graph.augment(e, augment_value);
     986        n=res_graph.tail(e);
     987      }
     988    }
     989
     990    status=AFTER_AUGMENTING;
     991    return _augment;
     992  }
    888993
    889994
     
    10001105    }
    10011106
     1107    status=AFTER_AUGMENTING;
    10021108    return _augment;
    10031109  }
     
    11301236    } //while (__augment)
    11311237
     1238    status=AFTER_AUGMENTING;
    11321239    return _augment;
    11331240  }
Note: See TracChangeset for help on using the changeset viewer.