1.1 --- a/lemon/belmann_ford.h Fri Oct 14 10:53:35 2005 +0000
1.2 +++ b/lemon/belmann_ford.h Fri Oct 14 10:53:51 2005 +0000
1.3 @@ -144,11 +144,19 @@
1.4 /// \brief BelmannFord algorithm class.
1.5 ///
1.6 /// \ingroup flowalgs
1.7 - /// This class provides an efficient implementation of \c BelmannFord
1.8 + /// This class provides an efficient implementation of \c Belmann-Ford
1.9 /// algorithm. The edge lengths are passed to the algorithm using a
1.10 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
1.11 /// kind of length.
1.12 ///
1.13 + /// The Belmann-Ford algorithm solves the shortest path from one node
1.14 + /// problem when the edges can have negative length but the graph should
1.15 + /// not contain circle with negative sum of length. If we can assume
1.16 + /// that all edge is non-negative in the graph then the dijkstra algorithm
1.17 + /// should be used rather.
1.18 + ///
1.19 + /// The complexity of the algorithm is O(n * e).
1.20 + ///
1.21 /// The type of the length is determined by the
1.22 /// \ref concept::ReadMap::Value "Value" of the length map.
1.23 ///
1.24 @@ -402,9 +410,9 @@
1.25 /// - The shortest path tree.
1.26 /// - The distance of each node from the root(s).
1.27 void start() {
1.28 - bool ready = false;
1.29 - while (!ready) {
1.30 - ready = true;
1.31 + int num = countNodes(*graph) - 1;
1.32 + for (int i = 0; i < num; ++i) {
1.33 + bool ready = true;
1.34 for (EdgeIt it(*graph); it != INVALID; ++it) {
1.35 Node source = graph->source(it);
1.36 Node target = graph->target(it);
1.37 @@ -416,8 +424,40 @@
1.38 ready = false;
1.39 }
1.40 }
1.41 + if (ready) return;
1.42 }
1.43 }
1.44 +
1.45 + /// \brief Executes the algorithm and check the negative circles.
1.46 + ///
1.47 + /// \pre init() must be called and at least one node should be added
1.48 + /// with addSource() before using this function. If there is
1.49 + /// a negative circle in the graph it gives back false.
1.50 + ///
1.51 + /// This method runs the %BelmannFord algorithm from the root node(s)
1.52 + /// in order to compute the shortest path to each node. The algorithm
1.53 + /// computes
1.54 + /// - The shortest path tree.
1.55 + /// - The distance of each node from the root(s).
1.56 + bool checkedStart() {
1.57 + int num = countNodes(*graph);
1.58 + for (int i = 0; i < num; ++i) {
1.59 + bool ready = true;
1.60 + for (EdgeIt it(*graph); it != INVALID; ++it) {
1.61 + Node source = graph->source(it);
1.62 + Node target = graph->target(it);
1.63 + Value relaxed =
1.64 + OperationTraits::plus((*_dist)[source], (*length)[it]);
1.65 + if (OperationTraits::less(relaxed, (*_dist)[target])) {
1.66 + _pred->set(target, it);
1.67 + _dist->set(target, relaxed);
1.68 + ready = false;
1.69 + }
1.70 + }
1.71 + if (ready) return true;
1.72 + }
1.73 + return false;
1.74 + }
1.75
1.76 /// \brief Runs %BelmannFord algorithm from node \c s.
1.77 ///
2.1 --- a/lemon/floyd_warshall.h Fri Oct 14 10:53:35 2005 +0000
2.2 +++ b/lemon/floyd_warshall.h Fri Oct 14 10:53:51 2005 +0000
2.3 @@ -27,6 +27,7 @@
2.4 #include <lemon/graph_utils.h>
2.5 #include <lemon/invalid.h>
2.6 #include <lemon/error.h>
2.7 +#include <lemon/matrix_maps.h>
2.8 #include <lemon/maps.h>
2.9
2.10 #include <limits>
2.11 @@ -105,14 +106,14 @@
2.12 /// \see FloydWarshallDefaultOperationTraits
2.13 typedef FloydWarshallDefaultOperationTraits<Value> OperationTraits;
2.14
2.15 - /// \brief The type of the map that stores the last edges of the
2.16 + /// \brief The type of the matrix map that stores the last edges of the
2.17 /// shortest paths.
2.18 ///
2.19 - /// The type of the map that stores the last
2.20 - /// edges of the shortest paths.
2.21 + /// The type of the map that stores the last edges of the shortest paths.
2.22 /// It must be a matrix map with \c Graph::Edge value type.
2.23 ///
2.24 - typedef NodeMatrixMap<Graph, typename Graph::Edge> PredMap;
2.25 + typedef DynamicMatrixMap<Graph, typename Graph::Node,
2.26 + typename Graph::Edge> PredMap;
2.27
2.28 /// \brief Instantiates a PredMap.
2.29 ///
2.30 @@ -126,9 +127,9 @@
2.31 /// \brief The type of the map that stores the dists of the nodes.
2.32 ///
2.33 /// The type of the map that stores the dists of the nodes.
2.34 - /// It must meet the \ref concept::WriteMap "WriteMap" concept.
2.35 + /// It must meet the \ref concept::WriteMatrixMap "WriteMatrixMap" concept.
2.36 ///
2.37 - typedef NodeMatrixMap<Graph, Value> DistMap;
2.38 + typedef DynamicMatrixMap<Graph, typename Graph::Node, Value> DistMap;
2.39
2.40 /// \brief Instantiates a DistMap.
2.41 ///
2.42 @@ -149,6 +150,15 @@
2.43 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
2.44 /// kind of length.
2.45 ///
2.46 + /// The algorithm solves the shortest path problem for each pairs
2.47 + /// of node when the edges can have negative length but the graph should
2.48 + /// not contain circle with negative sum of length. If we can assume
2.49 + /// that all edge is non-negative in the graph then the dijkstra algorithm
2.50 + /// should be used from each node rather and if the graph is sparse and
2.51 + /// there are negative circles then the johson algorithm.
2.52 + ///
2.53 + /// The complexity of this algorithm is O(n^3 + e).
2.54 + ///
2.55 /// The type of the length is determined by the
2.56 /// \ref concept::ReadMap::Value "Value" of the length map.
2.57 ///
3.1 --- a/lemon/johnson.h Fri Oct 14 10:53:35 2005 +0000
3.2 +++ b/lemon/johnson.h Fri Oct 14 10:53:51 2005 +0000
3.3 @@ -29,6 +29,7 @@
3.4 #include <lemon/invalid.h>
3.5 #include <lemon/error.h>
3.6 #include <lemon/maps.h>
3.7 +#include <lemon/matrix_maps.h>
3.8
3.9 #include <limits>
3.10
3.11 @@ -106,14 +107,14 @@
3.12 /// \see JohnsonDefaultOperationTraits
3.13 typedef JohnsonDefaultOperationTraits<Value> OperationTraits;
3.14
3.15 - /// \brief The type of the map that stores the last edges of the
3.16 + /// \brief The type of the matrix map that stores the last edges of the
3.17 /// shortest paths.
3.18 ///
3.19 - /// The type of the map that stores the last
3.20 - /// edges of the shortest paths.
3.21 + /// The type of the map that stores the last edges of the shortest paths.
3.22 /// It must be a matrix map with \c Graph::Edge value type.
3.23 ///
3.24 - typedef NodeMatrixMap<Graph, typename Graph::Edge> PredMap;
3.25 + typedef DynamicMatrixMap<Graph, typename Graph::Node,
3.26 + typename Graph::Edge> PredMap;
3.27
3.28 /// \brief Instantiates a PredMap.
3.29 ///
3.30 @@ -124,13 +125,13 @@
3.31 return new PredMap(graph);
3.32 }
3.33
3.34 - /// \brief The type of the map that stores the dists of the nodes.
3.35 + /// \brief The type of the matrix map that stores the dists of the nodes.
3.36 ///
3.37 - /// The type of the map that stores the dists of the nodes.
3.38 - /// It must meet the \ref concept::WriteMap "WriteMap" concept.
3.39 + /// The type of the matrix map that stores the dists of the nodes.
3.40 + /// It must meet the \ref concept::WriteMatrixMap "WriteMatrixMap" concept.
3.41 ///
3.42 - typedef NodeMatrixMap<Graph, Value> DistMap;
3.43 -
3.44 + typedef DynamicMatrixMap<Graph, typename Graph::Node, Value> DistMap;
3.45 +
3.46 /// \brief Instantiates a DistMap.
3.47 ///
3.48 /// This function instantiates a \ref DistMap.
3.49 @@ -150,6 +151,15 @@
3.50 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
3.51 /// kind of length.
3.52 ///
3.53 + /// The algorithm solves the shortest path problem for each pairs
3.54 + /// of node when the edges can have negative length but the graph should
3.55 + /// not contain circle with negative sum of length. If we can assume
3.56 + /// that all edge is non-negative in the graph then the dijkstra algorithm
3.57 + /// should be used from each node.
3.58 + ///
3.59 + /// The complexity of this algorithm is $O(n^2 * log(n) + n * log(n) * e)$ or
3.60 + /// with fibonacci heap O(n^2 * log(n) + n * e).
3.61 + ///
3.62 /// The type of the length is determined by the
3.63 /// \ref concept::ReadMap::Value "Value" of the length map.
3.64 ///