COIN-OR::LEMON - Graph Library

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


Ignore:
Timestamp:
11/27/07 16:41:43 (12 years ago)
Author:
Balazs Dezso
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

Legend:

Unmodified
Added
Removed
  • lemon/dinitz_sleator_tarjan.h

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

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

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

    r2518 r2522  
    7373    /// \sa Elevator
    7474    /// \sa LinkedElevator
    75     typedef LinkedElevator<Graph, typename Graph::Node> Elevator;
     75    typedef Elevator<Graph, typename Graph::Node> Elevator;
    7676   
    7777    /// \brief Instantiates an Elevator.
     
    101101  /// flow algorithms. The current implementation use a mixture of the
    102102  /// \e "highest label" and the \e "bound decrease" heuristics.
    103   /// The worst case time complexity of the algorithm is \f$O(n^3)\f$.
     103  /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
    104104  ///
    105105  /// The algorithm consists from two phases. After the first phase
     
    408408      reached.set(_target, true);
    409409      while (!queue.empty()) {
     410        _level->initNewLevel();
    410411        std::vector<Node> nqueue;
    411412        for (int i = 0; i < int(queue.size()); ++i) {
     
    864865
    865866    /// \name Query Functions
    866     /// The result of the %Dijkstra algorithm can be obtained using these
     867    /// The result of the %Preflow algorithm can be obtained using these
    867868    /// functions.\n
    868869    /// Before the use of these functions,
Note: See TracChangeset for help on using the changeset viewer.