COIN-OR::LEMON - Graph Library

Changeset 902:79fab87ee483 in lemon-1.2


Ignore:
Timestamp:
02/28/11 09:58:07 (13 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
1.2
Parents:
900:1861d5dcf312 (diff), 901:30d5f950aa5f (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 bugfix #414 to branch 1.2

Files:
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/preflow.h

    r895 r902  
    544544          _flow->set(e, (*_capacity)[e]);
    545545          (*_excess)[u] += rem;
    546           if (u != _target && !_level->active(u)) {
    547             _level->activate(u);
    548           }
    549546        }
    550547      }
     
    556553          _flow->set(e, 0);
    557554          (*_excess)[v] += rem;
    558           if (v != _target && !_level->active(v)) {
    559             _level->activate(v);
    560           }
    561         }
    562       }
     555        }
     556      }
     557      for (NodeIt n(_graph); n != INVALID; ++n)
     558        if(n!=_source && n!=_target && _tolerance.positive((*_excess)[n]))
     559          _level->activate(n);
     560         
    563561      return true;
    564562    }
  • lemon/preflow.h

    r901 r902  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    5353    /// The type of the map that stores the flow values.
    5454    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     55#ifdef DOXYGEN
     56    typedef GR::ArcMap<Value> FlowMap;
     57#else
    5558    typedef typename Digraph::template ArcMap<Value> FlowMap;
     59#endif
    5660
    5761    /// \brief Instantiates a FlowMap.
     
    6872    /// The elevator type used by Preflow algorithm.
    6973    ///
    70     /// \sa Elevator
    71     /// \sa LinkedElevator
    72     typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator;
     74    /// \sa Elevator, LinkedElevator
     75#ifdef DOXYGEN
     76    typedef lemon::Elevator<GR, GR::Node> Elevator;
     77#else
     78    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
     79#endif
    7380
    7481    /// \brief Instantiates an Elevator.
     
    96103  /// This class provides an implementation of Goldberg-Tarjan's \e preflow
    97104  /// \e push-relabel algorithm producing a \ref max_flow
    98   /// "flow of maximum value" in a digraph.
     105  /// "flow of maximum value" in a digraph \ref clrs01algorithms,
     106  /// \ref amo93networkflows, \ref goldberg88newapproach.
    99107  /// The preflow algorithms are the fastest known maximum
    100   /// flow algorithms. The current implementation use a mixture of the
     108  /// flow algorithms. The current implementation uses a mixture of the
    101109  /// \e "highest label" and the \e "bound decrease" heuristics.
    102110  /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
     
    106114  /// second phase constructs a feasible maximum flow on each arc.
    107115  ///
     116  /// \warning This implementation cannot handle infinite or very large
     117  /// capacities (e.g. the maximum value of \c CAP::Value).
     118  ///
    108119  /// \tparam GR The type of the digraph the algorithm runs on.
    109120  /// \tparam CAP The type of the capacity map. The default map
    110121  /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
     122  /// \tparam TR The traits class that defines various types used by the
     123  /// algorithm. By default, it is \ref PreflowDefaultTraits
     124  /// "PreflowDefaultTraits<GR, CAP>".
     125  /// In most cases, this parameter should not be set directly,
     126  /// consider to use the named template parameters instead.
    111127#ifdef DOXYGEN
    112128  template <typename GR, typename CAP, typename TR>
     
    258274    /// able to automatically created by the algorithm (i.e. the
    259275    /// digraph and the maximum level should be passed to it).
    260     /// However an external elevator object could also be passed to the
     276    /// However, an external elevator object could also be passed to the
    261277    /// algorithm with the \ref elevator(Elevator&) "elevator()" function
    262278    /// before calling \ref run() or \ref init().
     
    372388    }
    373389
    374     /// \brief Sets the tolerance used by algorithm.
    375     ///
    376     /// Sets the tolerance used by algorithm.
     390    /// \brief Sets the tolerance used by the algorithm.
     391    ///
     392    /// Sets the tolerance object used by the algorithm.
     393    /// \return <tt>(*this)</tt>
    377394    Preflow& tolerance(const Tolerance& tolerance) {
    378395      _tolerance = tolerance;
     
    382399    /// \brief Returns a const reference to the tolerance.
    383400    ///
    384     /// Returns a const reference to the tolerance.
     401    /// Returns a const reference to the tolerance object used by
     402    /// the algorithm.
    385403    const Tolerance& tolerance() const {
    386404      return _tolerance;
     
    390408    /// The simplest way to execute the preflow algorithm is to use
    391409    /// \ref run() or \ref runMinCut().\n
    392     /// If you need more control on the initial solution or the execution,
    393     /// first you have to call one of the \ref init() functions, then
     410    /// If you need better control on the initial solution or the execution,
     411    /// you have to call one of the \ref init() functions first, then
    394412    /// \ref startFirstPhase() and if you need it \ref startSecondPhase().
    395413
  • test/preflow_test.cc

    r877 r902  
    157157}
    158158
     159void initFlowTest()
     160{
     161  DIGRAPH_TYPEDEFS(SmartDigraph);
     162 
     163  SmartDigraph g;
     164  SmartDigraph::ArcMap<int> cap(g),iflow(g);
     165  Node s=g.addNode(); Node t=g.addNode();
     166  Node n1=g.addNode(); Node n2=g.addNode();
     167  Arc a;
     168  a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;
     169  a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;
     170  a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;
     171
     172  Preflow<SmartDigraph> pre(g,cap,s,t);
     173  pre.init(iflow);
     174  pre.startFirstPhase();
     175  check(pre.flowValue() == 10, "The incorrect max flow value.");
     176  check(pre.minCut(s), "Wrong min cut (Node s).");
     177  check(pre.minCut(n1), "Wrong min cut (Node n1).");
     178  check(!pre.minCut(n2), "Wrong min cut (Node n2).");
     179  check(!pre.minCut(t), "Wrong min cut (Node t).");
     180}
     181
     182
    159183int main() {
    160184
     
    247271        "The max flow value or the three min cut values are incorrect.");
    248272
     273  initFlowTest();
     274 
    249275  return 0;
    250276}
  • test/preflow_test.cc

    r901 r902  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9696  const PreflowType& const_preflow_test = preflow_test;
    9797
     98  const PreflowType::Elevator& elev = const_preflow_test.elevator();
     99  preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev));
     100  PreflowType::Tolerance tol = const_preflow_test.tolerance();
     101  preflow_test.tolerance(tol);
     102
    98103  preflow_test
    99104    .capacityMap(cap)
     
    114119  b = const_preflow_test.minCut(n);
    115120  const_preflow_test.minCutMap(cut);
    116  
     121
    117122  ignore_unused_variable_warning(fm);
    118123}
Note: See TracChangeset for help on using the changeset viewer.