Changeset 985:f63fd24c0aea in lemon for lemon/preflow.h

Ignore:
Timestamp:
06/25/10 05:54:56 (12 years ago)
Branch:
1.2
Parents:
978:cbf32bf95954 (diff), 982:bb70ad62c95f (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 #372 to branch 1.2

Files:
2 edited

Unmodified
Added
Removed
• lemon/preflow.h

 r956 _phase = true; Node n = _level->highestActive(); int level = _level->highestActiveLevel(); while (n != INVALID) { while (true) { int num = _node_num; while (num > 0 && n != INVALID) { Node n = INVALID; int level = -1; while (num > 0) { n = _level->highestActive(); if (n == INVALID) goto first_phase_done; level = _level->highestActiveLevel(); --num; Value excess = (*_excess)[n]; int new_level = _level->maxLevel(); _level->deactivate(n); } n = _level->highestActive(); level = _level->highestActiveLevel(); } num = _node_num * 20; while (num > 0) { while (level >= 0 && _level->activeFree(level)) { --level; } if (level == -1) { n = _level->highestActive(); level = _level->highestActiveLevel(); if (n == INVALID) goto first_phase_done; } else { n = _level->activeOn(level); } --num; } num = _node_num * 20; while (num > 0 && n != INVALID) { Value excess = (*_excess)[n]; int new_level = _level->maxLevel(); _level->deactivate(n); } while (level >= 0 && _level->activeFree(level)) { --level; } if (level == -1) { n = _level->highestActive(); level = _level->highestActiveLevel(); } else { n = _level->activeOn(level); } --num; } } } } first_phase_done:; }
• lemon/preflow.h

 r982 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). /// The type of the map that stores the flow values. /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. #ifdef DOXYGEN typedef GR::ArcMap FlowMap; #else typedef typename Digraph::template ArcMap FlowMap; #endif /// \brief Instantiates a FlowMap. /// The elevator type used by Preflow algorithm. /// /// \sa Elevator /// \sa LinkedElevator typedef LinkedElevator Elevator; /// \sa Elevator, LinkedElevator #ifdef DOXYGEN typedef lemon::Elevator Elevator; #else typedef lemon::Elevator Elevator; #endif /// \brief Instantiates an Elevator. /// This class provides an implementation of Goldberg-Tarjan's \e preflow /// \e push-relabel algorithm producing a \ref max_flow /// "flow of maximum value" in a digraph. /// "flow of maximum value" in a digraph \ref clrs01algorithms, /// \ref amo93networkflows, \ref goldberg88newapproach. /// The preflow algorithms are the fastest known maximum /// flow algorithms. The current implementation use a mixture of the /// flow algorithms. The current implementation uses a mixture of the /// \e "highest label" and the \e "bound decrease" heuristics. /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$. /// second phase constructs a feasible maximum flow on each arc. /// /// \warning This implementation cannot handle infinite or very large /// capacities (e.g. the maximum value of \c CAP::Value). /// /// \tparam GR The type of the digraph the algorithm runs on. /// \tparam CAP The type of the capacity map. The default map /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap". /// \tparam TR The traits class that defines various types used by the /// algorithm. By default, it is \ref PreflowDefaultTraits /// "PreflowDefaultTraits". /// In most cases, this parameter should not be set directly, /// consider to use the named template parameters instead. #ifdef DOXYGEN template /// able to automatically created by the algorithm (i.e. the /// digraph and the maximum level should be passed to it). /// However an external elevator object could also be passed to the /// However, an external elevator object could also be passed to the /// algorithm with the \ref elevator(Elevator&) "elevator()" function /// before calling \ref run() or \ref init(). } /// \brief Sets the tolerance used by algorithm. /// /// Sets the tolerance used by algorithm. /// \brief Sets the tolerance used by the algorithm. /// /// Sets the tolerance object used by the algorithm. /// \return (*this) Preflow& tolerance(const Tolerance& tolerance) { _tolerance = tolerance; /// \brief Returns a const reference to the tolerance. /// /// Returns a const reference to the tolerance. /// Returns a const reference to the tolerance object used by /// the algorithm. const Tolerance& tolerance() const { return _tolerance; /// The simplest way to execute the preflow algorithm is to use /// \ref run() or \ref runMinCut().\n /// If you need more control on the initial solution or the execution, /// first you have to call one of the \ref init() functions, then /// If you need better control on the initial solution or the execution, /// you have to call one of the \ref init() functions first, then /// \ref startFirstPhase() and if you need it \ref startSecondPhase().
Note: See TracChangeset for help on using the changeset viewer.