COIN-OR::LEMON - Graph Library

Changeset 611:85cb3aa71cce in lemon-1.2 for lemon/preflow.h


Ignore:
Timestamp:
04/21/09 16:18:54 (11 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
612:0c8e5c688440, 613:b1811c363299, 619:ec817dfc2cb7
Parents:
600:0ba8dfce7259 (diff), 610:dacc2cee2b4c (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge and fix

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/preflow.h

    r581 r611  
    4747
    4848    /// \brief The type of the flow values.
    49     typedef typename CapacityMap::Value Value;
     49    typedef typename CapacityMap::Value Flow;
    5050
    5151    /// \brief The type of the map that stores the flow values.
     
    5353    /// The type of the map that stores the flow values.
    5454    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    55     typedef typename Digraph::template ArcMap<Value> FlowMap;
     55    typedef typename Digraph::template ArcMap<Flow> FlowMap;
    5656
    5757    /// \brief Instantiates a FlowMap.
    5858    ///
    5959    /// This function instantiates a \ref FlowMap.
    60     /// \param digraph The digraph, to which we would like to define
     60    /// \param digraph The digraph for which we would like to define
    6161    /// the flow map.
    6262    static FlowMap* createFlowMap(const Digraph& digraph) {
     
    7575    ///
    7676    /// This function instantiates an \ref Elevator.
    77     /// \param digraph The digraph, to which we would like to define
     77    /// \param digraph The digraph for which we would like to define
    7878    /// the elevator.
    7979    /// \param max_level The maximum level of the elevator.
     
    8585    ///
    8686    /// The tolerance used by the algorithm to handle inexact computation.
    87     typedef lemon::Tolerance<Value> Tolerance;
     87    typedef lemon::Tolerance<Flow> Tolerance;
    8888
    8989  };
     
    126126    typedef typename Traits::CapacityMap CapacityMap;
    127127    ///The type of the flow values.
    128     typedef typename Traits::Value Value;
     128    typedef typename Traits::Flow Flow;
    129129
    130130    ///The type of the flow map.
     
    152152    bool _local_level;
    153153
    154     typedef typename Digraph::template NodeMap<Value> ExcessMap;
     154    typedef typename Digraph::template NodeMap<Flow> ExcessMap;
    155155    ExcessMap* _excess;
    156156
     
    471471
    472472      for (NodeIt n(_graph); n != INVALID; ++n) {
    473         Value excess = 0;
     473        Flow excess = 0;
    474474        for (InArcIt e(_graph, n); e != INVALID; ++e) {
    475475          excess += (*_flow)[e];
     
    520520
    521521      for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
    522         Value rem = (*_capacity)[e] - (*_flow)[e];
     522        Flow rem = (*_capacity)[e] - (*_flow)[e];
    523523        if (_tolerance.positive(rem)) {
    524524          Node u = _graph.target(e);
     
    532532      }
    533533      for (InArcIt e(_graph, _source); e != INVALID; ++e) {
    534         Value rem = (*_flow)[e];
     534        Flow rem = (*_flow)[e];
    535535        if (_tolerance.positive(rem)) {
    536536          Node v = _graph.source(e);
     
    565565
    566566        while (num > 0 && n != INVALID) {
    567           Value excess = (*_excess)[n];
     567          Flow excess = (*_excess)[n];
    568568          int new_level = _level->maxLevel();
    569569
    570570          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
    571             Value rem = (*_capacity)[e] - (*_flow)[e];
     571            Flow rem = (*_capacity)[e] - (*_flow)[e];
    572572            if (!_tolerance.positive(rem)) continue;
    573573            Node v = _graph.target(e);
     
    592592
    593593          for (InArcIt e(_graph, n); e != INVALID; ++e) {
    594             Value rem = (*_flow)[e];
     594            Flow rem = (*_flow)[e];
    595595            if (!_tolerance.positive(rem)) continue;
    596596            Node v = _graph.source(e);
     
    638638        num = _node_num * 20;
    639639        while (num > 0 && n != INVALID) {
    640           Value excess = (*_excess)[n];
     640          Flow excess = (*_excess)[n];
    641641          int new_level = _level->maxLevel();
    642642
    643643          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
    644             Value rem = (*_capacity)[e] - (*_flow)[e];
     644            Flow rem = (*_capacity)[e] - (*_flow)[e];
    645645            if (!_tolerance.positive(rem)) continue;
    646646            Node v = _graph.target(e);
     
    665665
    666666          for (InArcIt e(_graph, n); e != INVALID; ++e) {
    667             Value rem = (*_flow)[e];
     667            Flow rem = (*_flow)[e];
    668668            if (!_tolerance.positive(rem)) continue;
    669669            Node v = _graph.source(e);
     
    779779      Node n;
    780780      while ((n = _level->highestActive()) != INVALID) {
    781         Value excess = (*_excess)[n];
     781        Flow excess = (*_excess)[n];
    782782        int level = _level->highestActiveLevel();
    783783        int new_level = _level->maxLevel();
    784784
    785785        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
    786           Value rem = (*_capacity)[e] - (*_flow)[e];
     786          Flow rem = (*_capacity)[e] - (*_flow)[e];
    787787          if (!_tolerance.positive(rem)) continue;
    788788          Node v = _graph.target(e);
     
    807807
    808808        for (InArcIt e(_graph, n); e != INVALID; ++e) {
    809           Value rem = (*_flow)[e];
     809          Flow rem = (*_flow)[e];
    810810          if (!_tolerance.positive(rem)) continue;
    811811          Node v = _graph.source(e);
     
    898898    /// \pre Either \ref run() or \ref init() must be called before
    899899    /// using this function.
    900     Value flowValue() const {
     900    Flow flowValue() const {
    901901      return (*_excess)[_target];
    902902    }
     
    909909    /// \pre Either \ref run() or \ref init() must be called before
    910910    /// using this function.
    911     Value flow(const Arc& arc) const {
     911    Flow flow(const Arc& arc) const {
    912912      return (*_flow)[arc];
    913913    }
  • lemon/preflow.h

    r610 r611  
    3333  /// Default traits class of Preflow class.
    3434  /// \tparam GR Digraph type.
    35   /// \tparam CM Capacity map type.
    36   template <typename GR, typename CM>
     35  /// \tparam CAP Capacity map type.
     36  template <typename GR, typename CAP>
    3737  struct PreflowDefaultTraits {
    3838
     
    4444    /// The type of the map that stores the arc capacities.
    4545    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    46     typedef CM CapacityMap;
     46    typedef CAP CapacityMap;
    4747
    4848    /// \brief The type of the flow values.
     
    9595  ///
    9696  /// This class provides an implementation of Goldberg-Tarjan's \e preflow
    97   /// \e push-relabel algorithm producing a flow of maximum value in a
    98   /// digraph. The preflow algorithms are the fastest known maximum
     97  /// \e push-relabel algorithm producing a \ref max_flow
     98  /// "flow of maximum value" in a digraph.
     99  /// The preflow algorithms are the fastest known maximum
    99100  /// flow algorithms. The current implementation use a mixture of the
    100101  /// \e "highest label" and the \e "bound decrease" heuristics.
     
    106107  ///
    107108  /// \tparam GR The type of the digraph the algorithm runs on.
    108   /// \tparam CM The type of the capacity map. The default map
     109  /// \tparam CAP The type of the capacity map. The default map
    109110  /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    110111#ifdef DOXYGEN
    111   template <typename GR, typename CM, typename TR>
     112  template <typename GR, typename CAP, typename TR>
    112113#else
    113114  template <typename GR,
    114             typename CM = typename GR::template ArcMap<int>,
    115             typename TR = PreflowDefaultTraits<GR, CM> >
     115            typename CAP = typename GR::template ArcMap<int>,
     116            typename TR = PreflowDefaultTraits<GR, CAP> >
    116117#endif
    117118  class Preflow {
     
    195196    ///@{
    196197
    197     template <typename _FlowMap>
     198    template <typename T>
    198199    struct SetFlowMapTraits : public Traits {
    199       typedef _FlowMap FlowMap;
     200      typedef T FlowMap;
    200201      static FlowMap *createFlowMap(const Digraph&) {
    201202        LEMON_ASSERT(false, "FlowMap is not initialized");
     
    209210    /// \ref named-templ-param "Named parameter" for setting FlowMap
    210211    /// type.
    211     template <typename _FlowMap>
     212    template <typename T>
    212213    struct SetFlowMap
    213       : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<_FlowMap> > {
     214      : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<T> > {
    214215      typedef Preflow<Digraph, CapacityMap,
    215                       SetFlowMapTraits<_FlowMap> > Create;
     216                      SetFlowMapTraits<T> > Create;
    216217    };
    217218
    218     template <typename _Elevator>
     219    template <typename T>
    219220    struct SetElevatorTraits : public Traits {
    220       typedef _Elevator Elevator;
     221      typedef T Elevator;
    221222      static Elevator *createElevator(const Digraph&, int) {
    222223        LEMON_ASSERT(false, "Elevator is not initialized");
     
    234235    /// \ref run() or \ref init().
    235236    /// \sa SetStandardElevator
    236     template <typename _Elevator>
     237    template <typename T>
    237238    struct SetElevator
    238       : public Preflow<Digraph, CapacityMap, SetElevatorTraits<_Elevator> > {
     239      : public Preflow<Digraph, CapacityMap, SetElevatorTraits<T> > {
    239240      typedef Preflow<Digraph, CapacityMap,
    240                       SetElevatorTraits<_Elevator> > Create;
     241                      SetElevatorTraits<T> > Create;
    241242    };
    242243
    243     template <typename _Elevator>
     244    template <typename T>
    244245    struct SetStandardElevatorTraits : public Traits {
    245       typedef _Elevator Elevator;
     246      typedef T Elevator;
    246247      static Elevator *createElevator(const Digraph& digraph, int max_level) {
    247248        return new Elevator(digraph, max_level);
     
    261262    /// before calling \ref run() or \ref init().
    262263    /// \sa SetElevator
    263     template <typename _Elevator>
     264    template <typename T>
    264265    struct SetStandardElevator
    265266      : public Preflow<Digraph, CapacityMap,
    266                        SetStandardElevatorTraits<_Elevator> > {
     267                       SetStandardElevatorTraits<T> > {
    267268      typedef Preflow<Digraph, CapacityMap,
    268                       SetStandardElevatorTraits<_Elevator> > Create;
     269                      SetStandardElevatorTraits<T> > Create;
    269270    };
    270271
     
    404405      _phase = true;
    405406      for (NodeIt n(_graph); n != INVALID; ++n) {
    406         _excess->set(n, 0);
     407        (*_excess)[n] = 0;
    407408      }
    408409
     
    417418
    418419      std::vector<Node> queue;
    419       reached.set(_source, true);
     420      reached[_source] = true;
    420421
    421422      queue.push_back(_target);
    422       reached.set(_target, true);
     423      reached[_target] = true;
    423424      while (!queue.empty()) {
    424425        _level->initNewLevel();
     
    429430            Node u = _graph.source(e);
    430431            if (!reached[u] && _tolerance.positive((*_capacity)[e])) {
    431               reached.set(u, true);
     432              reached[u] = true;
    432433              _level->initAddItem(u);
    433434              nqueue.push_back(u);
     
    444445          if ((*_level)[u] == _level->maxLevel()) continue;
    445446          _flow->set(e, (*_capacity)[e]);
    446           _excess->set(u, (*_excess)[u] + (*_capacity)[e]);
     447          (*_excess)[u] += (*_capacity)[e];
    447448          if (u != _target && !_level->active(u)) {
    448449            _level->activate(u);
     
    478479        }
    479480        if (excess < 0 && n != _source) return false;
    480         _excess->set(n, excess);
     481        (*_excess)[n] = excess;
    481482      }
    482483
     
    487488
    488489      std::vector<Node> queue;
    489       reached.set(_source, true);
     490      reached[_source] = true;
    490491
    491492      queue.push_back(_target);
    492       reached.set(_target, true);
     493      reached[_target] = true;
    493494      while (!queue.empty()) {
    494495        _level->initNewLevel();
     
    500501            if (!reached[u] &&
    501502                _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
    502               reached.set(u, true);
     503              reached[u] = true;
    503504              _level->initAddItem(u);
    504505              nqueue.push_back(u);
     
    508509            Node v = _graph.target(e);
    509510            if (!reached[v] && _tolerance.positive((*_flow)[e])) {
    510               reached.set(v, true);
     511              reached[v] = true;
    511512              _level->initAddItem(v);
    512513              nqueue.push_back(v);
     
    524525          if ((*_level)[u] == _level->maxLevel()) continue;
    525526          _flow->set(e, (*_capacity)[e]);
    526           _excess->set(u, (*_excess)[u] + rem);
     527          (*_excess)[u] += rem;
    527528          if (u != _target && !_level->active(u)) {
    528529            _level->activate(u);
     
    536537          if ((*_level)[v] == _level->maxLevel()) continue;
    537538          _flow->set(e, 0);
    538           _excess->set(v, (*_excess)[v] + rem);
     539          (*_excess)[v] += rem;
    539540          if (v != _target && !_level->active(v)) {
    540541            _level->activate(v);
     
    577578              if (!_tolerance.less(rem, excess)) {
    578579                _flow->set(e, (*_flow)[e] + excess);
    579                 _excess->set(v, (*_excess)[v] + excess);
     580                (*_excess)[v] += excess;
    580581                excess = 0;
    581582                goto no_more_push_1;
    582583              } else {
    583584                excess -= rem;
    584                 _excess->set(v, (*_excess)[v] + rem);
     585                (*_excess)[v] += rem;
    585586                _flow->set(e, (*_capacity)[e]);
    586587              }
     
    600601              if (!_tolerance.less(rem, excess)) {
    601602                _flow->set(e, (*_flow)[e] - excess);
    602                 _excess->set(v, (*_excess)[v] + excess);
     603                (*_excess)[v] += excess;
    603604                excess = 0;
    604605                goto no_more_push_1;
    605606              } else {
    606607                excess -= rem;
    607                 _excess->set(v, (*_excess)[v] + rem);
     608                (*_excess)[v] += rem;
    608609                _flow->set(e, 0);
    609610              }
     
    615616        no_more_push_1:
    616617
    617           _excess->set(n, excess);
     618          (*_excess)[n] = excess;
    618619
    619620          if (excess != 0) {
     
    650651              if (!_tolerance.less(rem, excess)) {
    651652                _flow->set(e, (*_flow)[e] + excess);
    652                 _excess->set(v, (*_excess)[v] + excess);
     653                (*_excess)[v] += excess;
    653654                excess = 0;
    654655                goto no_more_push_2;
    655656              } else {
    656657                excess -= rem;
    657                 _excess->set(v, (*_excess)[v] + rem);
     658                (*_excess)[v] += rem;
    658659                _flow->set(e, (*_capacity)[e]);
    659660              }
     
    673674              if (!_tolerance.less(rem, excess)) {
    674675                _flow->set(e, (*_flow)[e] - excess);
    675                 _excess->set(v, (*_excess)[v] + excess);
     676                (*_excess)[v] += excess;
    676677                excess = 0;
    677678                goto no_more_push_2;
    678679              } else {
    679680                excess -= rem;
    680                 _excess->set(v, (*_excess)[v] + rem);
     681                (*_excess)[v] += rem;
    681682                _flow->set(e, 0);
    682683              }
     
    688689        no_more_push_2:
    689690
    690           _excess->set(n, excess);
     691          (*_excess)[n] = excess;
    691692
    692693          if (excess != 0) {
     
    731732      typename Digraph::template NodeMap<bool> reached(_graph);
    732733      for (NodeIt n(_graph); n != INVALID; ++n) {
    733         reached.set(n, (*_level)[n] < _level->maxLevel());
     734        reached[n] = (*_level)[n] < _level->maxLevel();
    734735      }
    735736
     
    739740      std::vector<Node> queue;
    740741      queue.push_back(_source);
    741       reached.set(_source, true);
     742      reached[_source] = true;
    742743
    743744      while (!queue.empty()) {
     
    749750            Node v = _graph.target(e);
    750751            if (!reached[v] && _tolerance.positive((*_flow)[e])) {
    751               reached.set(v, true);
     752              reached[v] = true;
    752753              _level->initAddItem(v);
    753754              nqueue.push_back(v);
     
    758759            if (!reached[u] &&
    759760                _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
    760               reached.set(u, true);
     761              reached[u] = true;
    761762              _level->initAddItem(u);
    762763              nqueue.push_back(u);
     
    792793            if (!_tolerance.less(rem, excess)) {
    793794              _flow->set(e, (*_flow)[e] + excess);
    794               _excess->set(v, (*_excess)[v] + excess);
     795              (*_excess)[v] += excess;
    795796              excess = 0;
    796797              goto no_more_push;
    797798            } else {
    798799              excess -= rem;
    799               _excess->set(v, (*_excess)[v] + rem);
     800              (*_excess)[v] += rem;
    800801              _flow->set(e, (*_capacity)[e]);
    801802            }
     
    815816            if (!_tolerance.less(rem, excess)) {
    816817              _flow->set(e, (*_flow)[e] - excess);
    817               _excess->set(v, (*_excess)[v] + excess);
     818              (*_excess)[v] += excess;
    818819              excess = 0;
    819820              goto no_more_push;
    820821            } else {
    821822              excess -= rem;
    822               _excess->set(v, (*_excess)[v] + rem);
     823              (*_excess)[v] += rem;
    823824              _flow->set(e, 0);
    824825            }
     
    830831      no_more_push:
    831832
    832         _excess->set(n, excess);
     833        (*_excess)[n] = excess;
    833834
    834835        if (excess != 0) {
     
    947948    ///
    948949    /// \note This function calls \ref minCut() for each node, so it runs in
    949     /// \f$O(n)\f$ time.
     950    /// O(n) time.
    950951    ///
    951952    /// \pre Either \ref run() or \ref init() must be called before
Note: See TracChangeset for help on using the changeset viewer.