COIN-OR::LEMON - Graph Library

Changeset 1270:dceba191c00d in lemon for lemon/edmonds_karp.h


Ignore:
Timestamp:
08/09/13 11:28:17 (7 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
1271:fb1c7da561ce, 1381:e0ccc1f0268f
Phase:
public
Message:

Apply unify-sources.sh to the source tree

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/edmonds_karp.h

    r1250 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3737  struct EdmondsKarpDefaultTraits {
    3838
    39     /// \brief The digraph type the algorithm runs on. 
     39    /// \brief The digraph type the algorithm runs on.
    4040    typedef GR Digraph;
    4141
     
    6161    /// \brief Instantiates a FlowMap.
    6262    ///
    63     /// This function instantiates a \ref FlowMap. 
     63    /// This function instantiates a \ref FlowMap.
    6464    /// \param digraph The digraph for which we would like to define
    6565    /// the flow map.
     
    9696  /// \tparam GR The type of the digraph the algorithm runs on.
    9797  /// \tparam CAP The type of the capacity map. The default map
    98   /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 
     98  /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    9999  /// \tparam TR The traits class that defines various types used by the
    100100  /// algorithm. By default, it is \ref EdmondsKarpDefaultTraits
     
    105105#ifdef DOXYGEN
    106106  template <typename GR, typename CAP, typename TR>
    107 #else 
     107#else
    108108  template <typename GR,
    109             typename CAP = typename GR::template ArcMap<int>,
     109            typename CAP = typename GR::template ArcMap<int>,
    110110            typename TR = EdmondsKarpDefaultTraits<GR, CAP> >
    111111#endif
     
    121121    typedef typename Traits::CapacityMap CapacityMap;
    122122    /// The type of the flow values.
    123     typedef typename Traits::Value Value; 
     123    typedef typename Traits::Value Value;
    124124
    125125    /// The type of the flow map.
     
    132132    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    133133    typedef typename Digraph::template NodeMap<Arc> PredMap;
    134    
     134
    135135    const Digraph& _graph;
    136136    const CapacityMap* _capacity;
     
    143143    PredMap* _pred;
    144144    std::vector<Node> _queue;
    145    
     145
    146146    Tolerance _tolerance;
    147147    Value _flow_value;
     
    149149    void createStructures() {
    150150      if (!_flow) {
    151         _flow = Traits::createFlowMap(_graph);
    152         _local_flow = true;
     151        _flow = Traits::createFlowMap(_graph);
     152        _local_flow = true;
    153153      }
    154154      if (!_pred) {
    155         _pred = new PredMap(_graph);
     155        _pred = new PredMap(_graph);
    156156      }
    157157      _queue.resize(countNodes(_graph));
     
    160160    void destroyStructures() {
    161161      if (_local_flow) {
    162         delete _flow;
     162        delete _flow;
    163163      }
    164164      if (_pred) {
    165         delete _pred;
    166       }
    167     }
    168    
     165        delete _pred;
     166      }
     167    }
     168
    169169  public:
    170170
     
    179179      typedef T FlowMap;
    180180      static FlowMap *createFlowMap(const Digraph&) {
    181         LEMON_ASSERT(false, "FlowMap is not initialized");
     181        LEMON_ASSERT(false, "FlowMap is not initialized");
    182182        return 0;
    183183      }
     
    190190    /// type
    191191    template <typename T>
    192     struct SetFlowMap 
     192    struct SetFlowMap
    193193      : public EdmondsKarp<Digraph, CapacityMap, SetFlowMapTraits<T> > {
    194194      typedef EdmondsKarp<Digraph, CapacityMap, SetFlowMapTraits<T> > Create;
     
    198198
    199199  protected:
    200    
     200
    201201    EdmondsKarp() {}
    202202
     
    205205    /// \brief The constructor of the class.
    206206    ///
    207     /// The constructor of the class. 
    208     /// \param digraph The digraph the algorithm runs on. 
    209     /// \param capacity The capacity of the arcs. 
     207    /// The constructor of the class.
     208    /// \param digraph The digraph the algorithm runs on.
     209    /// \param capacity The capacity of the arcs.
    210210    /// \param source The source node.
    211211    /// \param target The target node.
    212212    EdmondsKarp(const Digraph& digraph, const CapacityMap& capacity,
    213                 Node source, Node target)
     213                Node source, Node target)
    214214      : _graph(digraph), _capacity(&capacity), _source(source), _target(target),
    215         _flow(0), _local_flow(false), _pred(0), _tolerance(), _flow_value()
     215        _flow(0), _local_flow(false), _pred(0), _tolerance(), _flow_value()
    216216    {
    217217      LEMON_ASSERT(_source != _target,
     
    245245    EdmondsKarp& flowMap(FlowMap& map) {
    246246      if (_local_flow) {
    247         delete _flow;
    248         _local_flow = false;
     247        delete _flow;
     248        _local_flow = false;
    249249      }
    250250      _flow = &map;
     
    277277      _tolerance = tolerance;
    278278      return *this;
    279     } 
     279    }
    280280
    281281    /// \brief Returns a const reference to the tolerance.
     
    285285    const Tolerance& tolerance() const {
    286286      return _tolerance;
    287     } 
     287    }
    288288
    289289    /// \name Execution control
     
    292292    /// you have to call one of the \ref init() functions first, then
    293293    /// \ref start() or multiple times the \ref augment() function.
    294    
     294
    295295    ///@{
    296296
     
    306306      _flow_value = 0;
    307307    }
    308    
     308
    309309    /// \brief Initializes the algorithm using the given flow map.
    310310    ///
     
    318318      createStructures();
    319319      for (ArcIt e(_graph); e != INVALID; ++e) {
    320         _flow->set(e, flowMap[e]);
     320        _flow->set(e, flowMap[e]);
    321321      }
    322322      _flow_value = 0;
     
    335335    /// contain a feasible flow, i.e. at each node excluding the source
    336336    /// and the target, the incoming flow should be equal to the
    337     /// outgoing flow. 
     337    /// outgoing flow.
    338338    /// \return \c false when the given \c flowMap does not contain a
    339339    /// feasible flow.
     
    342342      createStructures();
    343343      for (ArcIt e(_graph); e != INVALID; ++e) {
    344         _flow->set(e, flowMap[e]);
     344        _flow->set(e, flowMap[e]);
    345345      }
    346346      for (NodeIt it(_graph); it != INVALID; ++it) {
     
    373373
    374374    /// \brief Augments the solution along a shortest path.
    375     /// 
     375    ///
    376376    /// Augments the solution along a shortest path. This function searches a
    377377    /// shortest path between the source and the target
     
    384384    bool augment() {
    385385      for (NodeIt n(_graph); n != INVALID; ++n) {
    386         _pred->set(n, INVALID);
    387       }
    388      
     386        _pred->set(n, INVALID);
     387      }
     388
    389389      int first = 0, last = 1;
    390      
     390
    391391      _queue[0] = _source;
    392392      _pred->set(_source, OutArcIt(_graph, _source));
    393393
    394394      while (first != last && (*_pred)[_target] == INVALID) {
    395         Node n = _queue[first++];
    396        
    397         for (OutArcIt e(_graph, n); e != INVALID; ++e) {
    398           Value rem = (*_capacity)[e] - (*_flow)[e];
    399           Node t = _graph.target(e);
    400           if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) {
    401             _pred->set(t, e);
    402             _queue[last++] = t;
    403           }
    404         }
    405         for (InArcIt e(_graph, n); e != INVALID; ++e) {
    406           Value rem = (*_flow)[e];
    407           Node t = _graph.source(e);
    408           if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) {
    409             _pred->set(t, e);
    410             _queue[last++] = t;
    411           }
    412         }
     395        Node n = _queue[first++];
     396
     397        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
     398          Value rem = (*_capacity)[e] - (*_flow)[e];
     399          Node t = _graph.target(e);
     400          if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) {
     401            _pred->set(t, e);
     402            _queue[last++] = t;
     403          }
     404        }
     405        for (InArcIt e(_graph, n); e != INVALID; ++e) {
     406          Value rem = (*_flow)[e];
     407          Node t = _graph.source(e);
     408          if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) {
     409            _pred->set(t, e);
     410            _queue[last++] = t;
     411          }
     412        }
    413413      }
    414414
    415415      if ((*_pred)[_target] != INVALID) {
    416         Node n = _target;
    417         Arc e = (*_pred)[n];
    418 
    419         Value prem = (*_capacity)[e] - (*_flow)[e];
    420         n = _graph.source(e);
    421         while (n != _source) {
    422           e = (*_pred)[n];
    423           if (_graph.target(e) == n) {
    424             Value rem = (*_capacity)[e] - (*_flow)[e];
    425             if (rem < prem) prem = rem;
    426             n = _graph.source(e);
    427           } else {
    428             Value rem = (*_flow)[e];
    429             if (rem < prem) prem = rem;
    430             n = _graph.target(e);   
    431           }
    432         }
    433 
    434         n = _target;
    435         e = (*_pred)[n];
    436 
    437         _flow->set(e, (*_flow)[e] + prem);
    438         n = _graph.source(e);
    439         while (n != _source) {
    440           e = (*_pred)[n];
    441           if (_graph.target(e) == n) {
    442             _flow->set(e, (*_flow)[e] + prem);
    443             n = _graph.source(e);
    444           } else {
    445             _flow->set(e, (*_flow)[e] - prem);
    446             n = _graph.target(e);   
    447           }
    448         }
    449 
    450         _flow_value += prem;   
    451         return true;
     416        Node n = _target;
     417        Arc e = (*_pred)[n];
     418
     419        Value prem = (*_capacity)[e] - (*_flow)[e];
     420        n = _graph.source(e);
     421        while (n != _source) {
     422          e = (*_pred)[n];
     423          if (_graph.target(e) == n) {
     424            Value rem = (*_capacity)[e] - (*_flow)[e];
     425            if (rem < prem) prem = rem;
     426            n = _graph.source(e);
     427          } else {
     428            Value rem = (*_flow)[e];
     429            if (rem < prem) prem = rem;
     430            n = _graph.target(e);
     431          }
     432        }
     433
     434        n = _target;
     435        e = (*_pred)[n];
     436
     437        _flow->set(e, (*_flow)[e] + prem);
     438        n = _graph.source(e);
     439        while (n != _source) {
     440          e = (*_pred)[n];
     441          if (_graph.target(e) == n) {
     442            _flow->set(e, (*_flow)[e] + prem);
     443            n = _graph.source(e);
     444          } else {
     445            _flow->set(e, (*_flow)[e] - prem);
     446            n = _graph.target(e);
     447          }
     448        }
     449
     450        _flow_value += prem;
     451        return true;
    452452      } else {
    453         return false;
     453        return false;
    454454      }
    455455    }
     
    458458    ///
    459459    /// Executes the algorithm by performing augmenting phases until the
    460     /// optimal solution is reached. 
     460    /// optimal solution is reached.
    461461    /// \pre One of the \ref init() functions must be called before
    462462    /// using this function.
     
    466466
    467467    /// \brief Runs the algorithm.
    468     /// 
     468    ///
    469469    /// Runs the Edmonds-Karp algorithm.
    470470    /// \note ek.run() is just a shortcut of the following code.
    471     ///\code 
     471    ///\code
    472472    /// ek.init();
    473473    /// ek.start();
     
    484484    /// functions.\n
    485485    /// Either \ref run() or \ref start() should be called before using them.
    486    
     486
    487487    ///@{
    488488
     
    543543    void minCutMap(CutMap& cutMap) const {
    544544      for (NodeIt n(_graph); n != INVALID; ++n) {
    545         cutMap.set(n, (*_pred)[n] != INVALID);
     545        cutMap.set(n, (*_pred)[n] != INVALID);
    546546      }
    547547      cutMap.set(_source, true);
    548     }   
     548    }
    549549
    550550    /// @}
Note: See TracChangeset for help on using the changeset viewer.