# Changeset 2522:616c019215c4 in lemon-0.x

Ignore:
Timestamp:
11/27/07 16:41:43 (12 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3398
Message:

Performance bug in Preflow
The initial relabeling moved each node to the lowest level
Doc bug fix

Location:
lemon
Files:
4 edited

Unmodified
Removed
• ## lemon/dinitz_sleator_tarjan.h

 r2519 /// @} /// \name Query Functions /// The result of the %Dijkstra algorithm can be obtained using these /// functions.\n /// \name Query Functions /// The result of the Dinitz-Sleator-Tarjan algorithm can be /// obtained using these functions. /// \n /// Before the use of these functions, /// either run() or start() must be called.
• ## lemon/edmonds_karp.h

 r2514 /// \name Query Functions /// The result of the %Dijkstra algorithm can be obtained using these /// The result of the Edmonds-Karp algorithm can be obtained using these /// functions.\n /// Before the use of these functions,
• ## lemon/goldberg_tarjan.h

 r2518 /// DynamicTree "dynamic tree" data structure of Sleator and Tarjan. /// /// The original preflow algorithm with \e "highest label" or \e /// FIFO heuristic has \f$O(n^3)\f$ time complexity. The current /// algorithm improved this complexity to /// \f$O(nm\log(\frac{n^2}{m}))\f$. The algorithm builds limited /// size dynamic trees on the residual graph, which can be used to /// make multilevel push operations and gives a better bound on the /// number of non-saturating pushes. /// The original preflow algorithm with \e highest \e label /// heuristic has \f$O(n^2\sqrt{e})\f$ or with \e FIFO heuristic has /// \f$O(n^3)\f$ time complexity. The current algorithm improved /// this complexity to \f$O(nm\log(\frac{n^2}{m}))\f$. The algorithm /// builds limited size dynamic trees on the residual graph, which /// can be used to make multilevel push operations and gives a /// better bound on the number of non-saturating pushes. /// /// \param Graph The directed graph type the algorithm runs on. /// @} /// \name Query Functions /// The result of the %Dijkstra algorithm can be obtained using these /// functions.\n /// Before the use of these functions, /// either run() or start() must be called. /// \name Query Functions /// The result of the Goldberg-Tarjan algorithm can be obtained /// using these functions. /// \n /// Before the use of these functions, either run() or start() must /// be called. ///@{
• ## lemon/preflow.h

 r2518 /// \sa Elevator /// \sa LinkedElevator typedef LinkedElevator Elevator; typedef Elevator Elevator; /// \brief Instantiates an Elevator. /// flow algorithms. The current implementation use 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^3)\f$. /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$. /// /// The algorithm consists from two phases. After the first phase reached.set(_target, true); while (!queue.empty()) { _level->initNewLevel(); std::vector nqueue; for (int i = 0; i < int(queue.size()); ++i) { /// \name Query Functions /// The result of the %Dijkstra algorithm can be obtained using these /// The result of the %Preflow algorithm can be obtained using these /// functions.\n /// Before the use of these functions,
Note: See TracChangeset for help on using the changeset viewer.