1.1 --- a/lemon/belmann_ford.h Wed Nov 02 15:26:04 2005 +0000
1.2 +++ b/lemon/belmann_ford.h Wed Nov 02 15:27:38 2005 +0000
1.3 @@ -141,7 +141,7 @@
1.4
1.5 };
1.6
1.7 - /// \brief BelmannFord algorithm class.
1.8 + /// \brief %BelmannFord algorithm class.
1.9 ///
1.10 /// \ingroup flowalgs
1.11 /// This class provides an efficient implementation of \c Belmann-Ford
1.12 @@ -151,7 +151,7 @@
1.13 ///
1.14 /// The Belmann-Ford algorithm solves the shortest path from one node
1.15 /// problem when the edges can have negative length but the graph should
1.16 - /// not contain circle with negative sum of length. If we can assume
1.17 + /// not contain cycles with negative sum of length. If we can assume
1.18 /// that all edge is non-negative in the graph then the dijkstra algorithm
1.19 /// should be used rather.
1.20 ///
1.21 @@ -428,11 +428,11 @@
1.22 }
1.23 }
1.24
1.25 - /// \brief Executes the algorithm and checks the negative circles.
1.26 + /// \brief Executes the algorithm and checks the negative cycles.
1.27 ///
1.28 /// \pre init() must be called and at least one node should be added
1.29 /// with addSource() before using this function. If there is
1.30 - /// a negative circle in the graph it gives back false.
1.31 + /// a negative cycles in the graph it gives back false.
1.32 ///
1.33 /// This method runs the %BelmannFord algorithm from the root node(s)
1.34 /// in order to compute the shortest path to each node. The algorithm
2.1 --- a/lemon/floyd_warshall.h Wed Nov 02 15:26:04 2005 +0000
2.2 +++ b/lemon/floyd_warshall.h Wed Nov 02 15:27:38 2005 +0000
2.3 @@ -142,20 +142,20 @@
2.4
2.5 };
2.6
2.7 - /// \brief FloydWarshall algorithm class.
2.8 + /// \brief %FloydWarshall algorithm class.
2.9 ///
2.10 /// \ingroup flowalgs
2.11 - /// This class provides an efficient implementation of \c FloydWarshall
2.12 + /// This class provides an efficient implementation of \c Floyd-Warshall
2.13 /// algorithm. The edge lengths are passed to the algorithm using a
2.14 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
2.15 /// kind of length.
2.16 ///
2.17 /// The algorithm solves the shortest path problem for each pairs
2.18 /// of node when the edges can have negative length but the graph should
2.19 - /// not contain circle with negative sum of length. If we can assume
2.20 + /// not contain cycles with negative sum of length. If we can assume
2.21 /// that all edge is non-negative in the graph then the dijkstra algorithm
2.22 /// should be used from each node rather and if the graph is sparse and
2.23 - /// there are negative circles then the johson algorithm.
2.24 + /// there are negative circles then the johnson algorithm.
2.25 ///
2.26 /// The complexity of this algorithm is O(n^3 + e).
2.27 ///
2.28 @@ -428,10 +428,10 @@
2.29 }
2.30 }
2.31
2.32 - /// \brief Executes the algorithm and checks the negative circles.
2.33 + /// \brief Executes the algorithm and checks the negative cycles.
2.34 ///
2.35 /// This method runs the %FloydWarshall algorithm in order to compute
2.36 - /// the shortest path to each node pairs. If there is a negative circle
2.37 + /// the shortest path to each node pairs. If there is a negative cycle
2.38 /// in the graph it gives back false.
2.39 /// The algorithm computes
2.40 /// - The shortest path tree for each node.
3.1 --- a/lemon/johnson.h Wed Nov 02 15:26:04 2005 +0000
3.2 +++ b/lemon/johnson.h Wed Nov 02 15:27:38 2005 +0000
3.3 @@ -175,17 +175,17 @@
3.4
3.5 };
3.6
3.7 - /// \brief Johnson algorithm class.
3.8 + /// \brief %Johnson algorithm class.
3.9 ///
3.10 /// \ingroup flowalgs
3.11 - /// This class provides an efficient implementation of \c Johnson
3.12 + /// This class provides an efficient implementation of \c %Johnson
3.13 /// algorithm. The edge lengths are passed to the algorithm using a
3.14 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
3.15 /// kind of length.
3.16 ///
3.17 /// The algorithm solves the shortest path problem for each pairs
3.18 /// of node when the edges can have negative length but the graph should
3.19 - /// not contain circle with negative sum of length. If we can assume
3.20 + /// not contain cycles with negative sum of length. If we can assume
3.21 /// that all edge is non-negative in the graph then the dijkstra algorithm
3.22 /// should be used from each node.
3.23 ///
3.24 @@ -377,8 +377,8 @@
3.25 throw UninitializedParameter();
3.26 }
3.27 };
3.28 - ///\ref named-templ-param "Named parameter" for setting heap and cross
3.29 - ///reference type
3.30 + ///\brief \ref named-templ-param "Named parameter" for setting heap and
3.31 + ///cross reference type
3.32
3.33 ///\ref named-templ-param "Named parameter" for setting heap and cross
3.34 ///reference type
3.35 @@ -487,18 +487,14 @@
3.36
3.37 protected:
3.38
3.39 - typedef typename BelmannFord<Graph, LengthMap>::
3.40 - template DefOperationTraits<OperationTraits>::
3.41 - template DefPredMap<NullMap<Node, Edge> >::
3.42 - Create BelmannFordType;
3.43 -
3.44 - void shiftedRun(const BelmannFordType& belmannford) {
3.45 + template <typename PotentialMap>
3.46 + void shiftedRun(const PotentialMap& potential) {
3.47
3.48 typename Graph::template EdgeMap<Value> shiftlen(*graph);
3.49 for (EdgeIt it(*graph); it != INVALID; ++it) {
3.50 shiftlen[it] = (*length)[it]
3.51 - + belmannford.dist(graph->source(it))
3.52 - - belmannford.dist(graph->target(it));
3.53 + + potential[graph->source(it)]
3.54 + - potential[graph->target(it)];
3.55 }
3.56
3.57 typename Dijkstra<Graph, typename Graph::template EdgeMap<Value> >::
3.58 @@ -512,7 +508,7 @@
3.59 for (NodeIt jt(*graph); jt != INVALID; ++jt) {
3.60 if (dijkstra.reached(jt)) {
3.61 _dist->set(it, jt, dijkstra.dist(jt) +
3.62 - belmannford.dist(jt) - belmannford.dist(it));
3.63 + potential[jt] - potential[it]);
3.64 _pred->set(it, jt, dijkstra.pred(jt));
3.65 } else {
3.66 _dist->set(it, jt, OperationTraits::infinity());
3.67 @@ -550,6 +546,11 @@
3.68 /// - The distance between each node pairs.
3.69 void start() {
3.70
3.71 + typedef typename BelmannFord<Graph, LengthMap>::
3.72 + template DefOperationTraits<OperationTraits>::
3.73 + template DefPredMap<NullMap<Node, Edge> >::
3.74 + Create BelmannFordType;
3.75 +
3.76 BelmannFordType belmannford(*graph, *length);
3.77
3.78 NullMap<Node, Edge> predMap;
3.79 @@ -559,18 +560,23 @@
3.80 belmannford.init(OperationTraits::zero());
3.81 belmannford.start();
3.82
3.83 - shiftedRun(belmannford);
3.84 + shiftedRun(belmannford.distMap());
3.85 }
3.86
3.87 - /// \brief Executes the algorithm and checks the negatvie circles.
3.88 + /// \brief Executes the algorithm and checks the negatvie cycles.
3.89 ///
3.90 /// This method runs the %Johnson algorithm in order to compute
3.91 /// the shortest path to each node pairs. If the graph contains
3.92 - /// negative circle it gives back false. The algorithm
3.93 + /// negative cycle it gives back false. The algorithm
3.94 /// computes
3.95 /// - The shortest path tree for each node.
3.96 /// - The distance between each node pairs.
3.97 bool checkedStart() {
3.98 +
3.99 + typedef typename BelmannFord<Graph, LengthMap>::
3.100 + template DefOperationTraits<OperationTraits>::
3.101 + template DefPredMap<NullMap<Node, Edge> >::
3.102 + Create BelmannFordType;
3.103
3.104 BelmannFordType belmannford(*graph, *length);
3.105
3.106 @@ -581,7 +587,7 @@
3.107 belmannford.init(OperationTraits::zero());
3.108 if (!belmannford.checkedStart()) return false;
3.109
3.110 - shiftedRun(belmannford);
3.111 + shiftedRun(belmannford.distMap());
3.112 return true;
3.113 }
3.114