# Changeset 2059:ebf3b2962554 in lemon-0.x for lemon

Ignore:
Timestamp:
04/18/06 09:02:32 (14 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2703
Message:

Doc fix

Location:
lemon
Files:
2 edited

### Legend:

Unmodified
 r2042 /// \brief Executes one round from the bellman ford algorithm. /// /// If the algoritm calculated the distances in the previous round /// strictly for all at most k length paths then it will calculate the /// distances strictly for all at most k + 1 length paths. With k /// iteration this function calculates the at most k length paths. /// \return %True when the algorithm have not found more shorter paths. /// If the algoritm calculated the distances in the previous round /// exactly for all at most \f$k \f$ length path lengths then it will /// calculate the distances exactly for all at most \f$k + 1 \f$ /// length path lengths. With \f$k \f$ iteration this function /// calculates the at most \f$k \f$ length path lengths. /// /// \warning The paths with limited edge number cannot be retrieved /// easily with \ref getPath() or \ref predEdge() functions. If you /// need the shortest path and not just the distance you should store /// after each iteration the \ref predEdgeMap() map and manually build /// the path. /// /// \return %True when the algorithm have not found more shorter /// paths. bool processNextRound() { for (int i = 0; i < (int)_process.size(); ++i) { /// with addSource() before using this function. /// /// This method runs the %BellmanFord algorithm from the root node(s) /// in order to compute the shortest path with at most \c length edge /// long paths to each node. The algorithm computes /// - The shortest path tree. /// This method runs the %BellmanFord algorithm from the root /// node(s) in order to compute the shortest path lengths with at /// most \c num edge. /// /// \warning The paths with limited edge number cannot be retrieved /// easily with \ref getPath() or \ref predEdge() functions. If you /// need the shortest path and not just the distance you should store /// after each iteration the \ref predEdgeMap() map and manually build /// the path. /// /// The algorithm computes /// - The predecessor edge from each node. /// - The limited distance of each node from the root(s). void limitedStart(int length) { for (int i = 0; i < length; ++i) { void limitedStart(int num) { for (int i = 0; i < num; ++i) { if (processNextRound()) break; }
 r2037 /// constructor. /// /// The time complexity of the algorithm is O(n * e^2) in worst case. /// Always try the preflow algorithm instead of this if you does not /// have some additional reason than to compute the optimal flow which /// has O(n^3) time complexity. /// The time complexity of the algorithm is \f$O(n * e^2) \f$ in /// worst case.  Always try the preflow algorithm instead of this if /// you does not have some additional reason than to compute the /// optimal flow which has \f$O(n^3) \f$ time complexity. /// /// \param _Graph The directed graph type the algorithm runs on. /// /// \author Balazs Dezso #ifdef DOXYGEN template #else template , typename _FlowMap = typename _Graph::template EdgeMap<_Number>, typename _Tolerance = Tolerance<_Number> > #endif class EdmondsKarp { public: /// \param flow The flow of the edges. /// \param tolerance Tolerance class. /// Except the graph, all of these parameters can be reset by /// calling \ref source, \ref target, \ref capacityMap and \ref /// flowMap, resp. EdmondsKarp(const Graph& graph, Node source, Node target, const CapacityMap& capacity, FlowMap& flow, /// /// It is just a shorthand for: /// \code /// ///\code /// ek.init(); /// ek.start(); /// \endcode ///\endcode void run() { init();