# HG changeset patch # User deba # Date 1130945258 0 # Node ID 4bf5ceb49023d25aa67c5473062030c6805c6d44 # Parent 98d83dd56c1dc44b769a8eea08a637fe04b51e4d Documentation modified diff -r 98d83dd56c1d -r 4bf5ceb49023 lemon/belmann_ford.h --- a/lemon/belmann_ford.h Wed Nov 02 15:26:04 2005 +0000 +++ b/lemon/belmann_ford.h Wed Nov 02 15:27:38 2005 +0000 @@ -141,7 +141,7 @@ }; - /// \brief BelmannFord algorithm class. + /// \brief %BelmannFord algorithm class. /// /// \ingroup flowalgs /// This class provides an efficient implementation of \c Belmann-Ford @@ -151,7 +151,7 @@ /// /// The Belmann-Ford algorithm solves the shortest path from one node /// problem when the edges can have negative length but the graph should - /// not contain circle with negative sum of length. If we can assume + /// not contain cycles with negative sum of length. If we can assume /// that all edge is non-negative in the graph then the dijkstra algorithm /// should be used rather. /// @@ -428,11 +428,11 @@ } } - /// \brief Executes the algorithm and checks the negative circles. + /// \brief Executes the algorithm and checks the negative cycles. /// /// \pre init() must be called and at least one node should be added /// with addSource() before using this function. If there is - /// a negative circle in the graph it gives back false. + /// a negative cycles in the graph it gives back false. /// /// This method runs the %BelmannFord algorithm from the root node(s) /// in order to compute the shortest path to each node. The algorithm diff -r 98d83dd56c1d -r 4bf5ceb49023 lemon/floyd_warshall.h --- a/lemon/floyd_warshall.h Wed Nov 02 15:26:04 2005 +0000 +++ b/lemon/floyd_warshall.h Wed Nov 02 15:27:38 2005 +0000 @@ -142,20 +142,20 @@ }; - /// \brief FloydWarshall algorithm class. + /// \brief %FloydWarshall algorithm class. /// /// \ingroup flowalgs - /// This class provides an efficient implementation of \c FloydWarshall + /// This class provides an efficient implementation of \c Floyd-Warshall /// algorithm. The edge lengths are passed to the algorithm using a /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any /// kind of length. /// /// The algorithm solves the shortest path problem for each pairs /// of node when the edges can have negative length but the graph should - /// not contain circle with negative sum of length. If we can assume + /// not contain cycles with negative sum of length. If we can assume /// that all edge is non-negative in the graph then the dijkstra algorithm /// should be used from each node rather and if the graph is sparse and - /// there are negative circles then the johson algorithm. + /// there are negative circles then the johnson algorithm. /// /// The complexity of this algorithm is O(n^3 + e). /// @@ -428,10 +428,10 @@ } } - /// \brief Executes the algorithm and checks the negative circles. + /// \brief Executes the algorithm and checks the negative cycles. /// /// This method runs the %FloydWarshall algorithm in order to compute - /// the shortest path to each node pairs. If there is a negative circle + /// the shortest path to each node pairs. If there is a negative cycle /// in the graph it gives back false. /// The algorithm computes /// - The shortest path tree for each node. diff -r 98d83dd56c1d -r 4bf5ceb49023 lemon/johnson.h --- a/lemon/johnson.h Wed Nov 02 15:26:04 2005 +0000 +++ b/lemon/johnson.h Wed Nov 02 15:27:38 2005 +0000 @@ -175,17 +175,17 @@ }; - /// \brief Johnson algorithm class. + /// \brief %Johnson algorithm class. /// /// \ingroup flowalgs - /// This class provides an efficient implementation of \c Johnson + /// This class provides an efficient implementation of \c %Johnson /// algorithm. The edge lengths are passed to the algorithm using a /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any /// kind of length. /// /// The algorithm solves the shortest path problem for each pairs /// of node when the edges can have negative length but the graph should - /// not contain circle with negative sum of length. If we can assume + /// not contain cycles with negative sum of length. If we can assume /// that all edge is non-negative in the graph then the dijkstra algorithm /// should be used from each node. /// @@ -377,8 +377,8 @@ throw UninitializedParameter(); } }; - ///\ref named-templ-param "Named parameter" for setting heap and cross - ///reference type + ///\brief \ref named-templ-param "Named parameter" for setting heap and + ///cross reference type ///\ref named-templ-param "Named parameter" for setting heap and cross ///reference type @@ -487,18 +487,14 @@ protected: - typedef typename BelmannFord:: - template DefOperationTraits:: - template DefPredMap >:: - Create BelmannFordType; - - void shiftedRun(const BelmannFordType& belmannford) { + template + void shiftedRun(const PotentialMap& potential) { typename Graph::template EdgeMap shiftlen(*graph); for (EdgeIt it(*graph); it != INVALID; ++it) { shiftlen[it] = (*length)[it] - + belmannford.dist(graph->source(it)) - - belmannford.dist(graph->target(it)); + + potential[graph->source(it)] + - potential[graph->target(it)]; } typename Dijkstra >:: @@ -512,7 +508,7 @@ for (NodeIt jt(*graph); jt != INVALID; ++jt) { if (dijkstra.reached(jt)) { _dist->set(it, jt, dijkstra.dist(jt) + - belmannford.dist(jt) - belmannford.dist(it)); + potential[jt] - potential[it]); _pred->set(it, jt, dijkstra.pred(jt)); } else { _dist->set(it, jt, OperationTraits::infinity()); @@ -550,6 +546,11 @@ /// - The distance between each node pairs. void start() { + typedef typename BelmannFord:: + template DefOperationTraits:: + template DefPredMap >:: + Create BelmannFordType; + BelmannFordType belmannford(*graph, *length); NullMap predMap; @@ -559,18 +560,23 @@ belmannford.init(OperationTraits::zero()); belmannford.start(); - shiftedRun(belmannford); + shiftedRun(belmannford.distMap()); } - /// \brief Executes the algorithm and checks the negatvie circles. + /// \brief Executes the algorithm and checks the negatvie cycles. /// /// This method runs the %Johnson algorithm in order to compute /// the shortest path to each node pairs. If the graph contains - /// negative circle it gives back false. The algorithm + /// negative cycle it gives back false. The algorithm /// computes /// - The shortest path tree for each node. /// - The distance between each node pairs. bool checkedStart() { + + typedef typename BelmannFord:: + template DefOperationTraits:: + template DefPredMap >:: + Create BelmannFordType; BelmannFordType belmannford(*graph, *length); @@ -581,7 +587,7 @@ belmannford.init(OperationTraits::zero()); if (!belmannford.checkedStart()) return false; - shiftedRun(belmannford); + shiftedRun(belmannford.distMap()); return true; }