Changeset 2522:616c019215c4 in lemon-0.x
- Timestamp:
- 11/27/07 16:41:43 (17 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3398
- Location:
- lemon
- Files:
-
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/dinitz_sleator_tarjan.h
r2519 r2522 702 702 /// @} 703 703 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 707 708 /// Before the use of these functions, 708 709 /// either run() or start() must be called. -
lemon/edmonds_karp.h
r2514 r2522 468 468 469 469 /// \name Query Functions 470 /// The result of the %Dijkstraalgorithm can be obtained using these470 /// The result of the Edmonds-Karp algorithm can be obtained using these 471 471 /// functions.\n 472 472 /// Before the use of these functions, -
lemon/goldberg_tarjan.h
r2518 r2522 104 104 /// DynamicTree "dynamic tree" data structure of Sleator and Tarjan. 105 105 /// 106 /// The original preflow algorithm with \e "highest label" or \e107 /// FIFO heuristic has \f$O(n^3)\f$ time complexity. The current108 /// algorithm improved this complexity to109 /// \f$O(nm\log(\frac{n^2}{m}))\f$. The algorithm builds limited110 /// size dynamic trees on the residual graph, which can be used to111 /// make multilevel push operations and gives a better bound on the112 /// 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. 113 113 /// 114 114 /// \param Graph The directed graph type the algorithm runs on. … … 966 966 /// @} 967 967 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. 973 974 974 975 ///@{ -
lemon/preflow.h
r2518 r2522 73 73 /// \sa Elevator 74 74 /// \sa LinkedElevator 75 typedef LinkedElevator<Graph, typename Graph::Node> Elevator;75 typedef Elevator<Graph, typename Graph::Node> Elevator; 76 76 77 77 /// \brief Instantiates an Elevator. … … 101 101 /// flow algorithms. The current implementation use a mixture of the 102 102 /// \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$. 104 104 /// 105 105 /// The algorithm consists from two phases. After the first phase … … 408 408 reached.set(_target, true); 409 409 while (!queue.empty()) { 410 _level->initNewLevel(); 410 411 std::vector<Node> nqueue; 411 412 for (int i = 0; i < int(queue.size()); ++i) { … … 864 865 865 866 /// \name Query Functions 866 /// The result of the % Dijkstraalgorithm can be obtained using these867 /// The result of the %Preflow algorithm can be obtained using these 867 868 /// functions.\n 868 869 /// Before the use of these functions,
Note: See TracChangeset
for help on using the changeset viewer.