1.1 --- a/lemon/belmann_ford.h Mon Oct 24 17:03:02 2005 +0000
1.2 +++ b/lemon/belmann_ford.h Wed Oct 26 10:50:47 2005 +0000
1.3 @@ -412,7 +412,7 @@
1.4 void start() {
1.5 int num = countNodes(*graph) - 1;
1.6 for (int i = 0; i < num; ++i) {
1.7 - bool ready = true;
1.8 + bool done = true;
1.9 for (EdgeIt it(*graph); it != INVALID; ++it) {
1.10 Node source = graph->source(it);
1.11 Node target = graph->target(it);
1.12 @@ -421,14 +421,14 @@
1.13 if (OperationTraits::less(relaxed, (*_dist)[target])) {
1.14 _pred->set(target, it);
1.15 _dist->set(target, relaxed);
1.16 - ready = false;
1.17 + done = false;
1.18 }
1.19 }
1.20 - if (ready) return;
1.21 + if (done) return;
1.22 }
1.23 }
1.24
1.25 - /// \brief Executes the algorithm and check the negative circles.
1.26 + /// \brief Executes the algorithm and checks the negative circles.
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 @@ -442,7 +442,7 @@
1.31 bool checkedStart() {
1.32 int num = countNodes(*graph);
1.33 for (int i = 0; i < num; ++i) {
1.34 - bool ready = true;
1.35 + bool done = true;
1.36 for (EdgeIt it(*graph); it != INVALID; ++it) {
1.37 Node source = graph->source(it);
1.38 Node target = graph->target(it);
1.39 @@ -451,10 +451,10 @@
1.40 if (OperationTraits::less(relaxed, (*_dist)[target])) {
1.41 _pred->set(target, it);
1.42 _dist->set(target, relaxed);
1.43 - ready = false;
1.44 + done = false;
1.45 }
1.46 }
1.47 - if (ready) return true;
1.48 + if (done) return true;
1.49 }
1.50 return false;
1.51 }
2.1 --- a/lemon/dijkstra.h Mon Oct 24 17:03:02 2005 +0000
2.2 +++ b/lemon/dijkstra.h Wed Oct 26 10:50:47 2005 +0000
2.3 @@ -61,7 +61,6 @@
2.4 ///This function instantiates a \ref HeapCrossRef.
2.5 /// \param G is the graph, to which we would like to define the
2.6 /// HeapCrossRef.
2.7 - /// \todo The graph alone may be insufficient for the initialization
2.8 static HeapCrossRef *createHeapCrossRef(const GR &G)
2.9 {
2.10 return new HeapCrossRef(G);
2.11 @@ -74,8 +73,7 @@
2.12 ///\sa BinHeap
2.13 ///\sa Dijkstra
2.14 typedef BinHeap<typename Graph::Node, typename LM::Value,
2.15 - typename GR::template NodeMap<int>,
2.16 - std::less<Value> > Heap;
2.17 + HeapCrossRef, std::less<Value> > Heap;
2.18
2.19 static Heap *createHeap(HeapCrossRef& R)
2.20 {
2.21 @@ -360,12 +358,12 @@
2.22 struct DefHeapTraits : public Traits {
2.23 typedef CR HeapCrossRef;
2.24 typedef H Heap;
2.25 - static HeapCrossRef *createHeapCrossRef(const Graph &G) {
2.26 - return new HeapCrossRef(G);
2.27 + static HeapCrossRef *createHeapCrossRef(const Graph &) {
2.28 + throw UninitializedParameter();
2.29 }
2.30 - static Heap *createHeap(HeapCrossRef &R)
2.31 + static Heap *createHeap(HeapCrossRef &)
2.32 {
2.33 - return new Heap(R);
2.34 + throw UninitializedParameter();
2.35 }
2.36 };
2.37 ///\ref named-templ-param "Named parameter" for setting heap and cross
2.38 @@ -379,6 +377,32 @@
2.39 : public Dijkstra< Graph, LengthMap, DefHeapTraits<H, CR> > {
2.40 typedef Dijkstra< Graph, LengthMap, DefHeapTraits<H, CR> > Create;
2.41 };
2.42 +
2.43 + template <class H, class CR>
2.44 + struct DefStandardHeapTraits : public Traits {
2.45 + typedef CR HeapCrossRef;
2.46 + typedef H Heap;
2.47 + static HeapCrossRef *createHeapCrossRef(const Graph &G) {
2.48 + return new HeapCrossRef(G);
2.49 + }
2.50 + static Heap *createHeap(HeapCrossRef &R)
2.51 + {
2.52 + return new Heap(R);
2.53 + }
2.54 + };
2.55 + ///\ref named-templ-param "Named parameter" for setting heap and cross
2.56 + ///reference type with automatic allocation
2.57 +
2.58 + ///\ref named-templ-param "Named parameter" for setting heap and cross
2.59 + ///reference type. It can allocate the heap and the cross reference
2.60 + ///object if the cross reference's constructor waits for the graph as
2.61 + ///parameter and the heap's constructor waits for the cross reference.
2.62 + template <class H, class CR = typename Graph::template NodeMap<int> >
2.63 + struct DefStandardHeap
2.64 + : public Dijkstra< Graph, LengthMap, DefStandardHeapTraits<H, CR> > {
2.65 + typedef Dijkstra< Graph, LengthMap, DefStandardHeapTraits<H, CR> >
2.66 + Create;
2.67 + };
2.68
2.69 ///@}
2.70
2.71 @@ -456,6 +480,28 @@
2.72 return *this;
2.73 }
2.74
2.75 + ///Sets the heap and the cross reference used by algorithm.
2.76 +
2.77 + ///Sets the heap and the cross reference used by algorithm.
2.78 + ///If you don't use this function before calling \ref run(),
2.79 + ///it will allocate one. The destuctor deallocates this
2.80 + ///automatically allocated map, of course.
2.81 + ///\return <tt> (*this) </tt>
2.82 + Dijkstra &heap(Heap& heap, HeapCrossRef &crossRef)
2.83 + {
2.84 + if(local_heap_cross_ref) {
2.85 + delete _heap_cross_ref;
2.86 + local_heap_cross_ref=false;
2.87 + }
2.88 + _heap_cross_ref = &crossRef;
2.89 + if(local_heap) {
2.90 + delete _heap;
2.91 + local_heap=false;
2.92 + }
2.93 + _heap = &heap;
2.94 + return *this;
2.95 + }
2.96 +
2.97 private:
2.98 void finalizeNodeData(Node v,Value dst)
2.99 {
3.1 --- a/lemon/floyd_warshall.h Mon Oct 24 17:03:02 2005 +0000
3.2 +++ b/lemon/floyd_warshall.h Wed Oct 26 10:50:47 2005 +0000
3.3 @@ -392,9 +392,9 @@
3.4 for (NodeIt it(*graph); it != INVALID; ++it) {
3.5 for (NodeIt jt(*graph); jt != INVALID; ++jt) {
3.6 _pred->set(it, jt, INVALID);
3.7 - _dist->set(it, jt, it == jt ?
3.8 - OperationTraits::zero() : OperationTraits::infinity());
3.9 + _dist->set(it, jt, OperationTraits::infinity());
3.10 }
3.11 + _dist->set(it, it, OperationTraits::zero());
3.12 }
3.13 for (EdgeIt it(*graph); it != INVALID; ++it) {
3.14 Node source = graph->source(it);
3.15 @@ -427,6 +427,24 @@
3.16 }
3.17 }
3.18 }
3.19 +
3.20 + /// \brief Executes the algorithm and checks the negative circles.
3.21 + ///
3.22 + /// This method runs the %FloydWarshall algorithm in order to compute
3.23 + /// the shortest path to each node pairs. If there is a negative circle
3.24 + /// in the graph it gives back false.
3.25 + /// The algorithm computes
3.26 + /// - The shortest path tree for each node.
3.27 + /// - The distance between each node pairs.
3.28 + bool checkedStart() {
3.29 + start();
3.30 + for (NodeIt it(*graph); it != INVALID; ++it) {
3.31 + if (OperationTraits::less((*dist)(it, it), OperationTraits::zero())) {
3.32 + return false;
3.33 + }
3.34 + }
3.35 + return true;
3.36 + }
3.37
3.38 /// \brief Runs %FloydWarshall algorithm.
3.39 ///
4.1 --- a/lemon/johnson.h Mon Oct 24 17:03:02 2005 +0000
4.2 +++ b/lemon/johnson.h Wed Oct 26 10:50:47 2005 +0000
4.3 @@ -106,6 +106,38 @@
4.4 /// and the used operation.
4.5 /// \see JohnsonDefaultOperationTraits
4.6 typedef JohnsonDefaultOperationTraits<Value> OperationTraits;
4.7 +
4.8 + /// The cross reference type used by heap.
4.9 +
4.10 + /// The cross reference type used by heap.
4.11 + /// Usually it is \c Graph::NodeMap<int>.
4.12 + typedef typename Graph::template NodeMap<int> HeapCrossRef;
4.13 +
4.14 + ///Instantiates a HeapCrossRef.
4.15 +
4.16 + ///This function instantiates a \ref HeapCrossRef.
4.17 + /// \param graph is the graph, to which we would like to define the
4.18 + /// HeapCrossRef.
4.19 + static HeapCrossRef *createHeapCrossRef(const Graph& graph) {
4.20 + return new HeapCrossRef(graph);
4.21 + }
4.22 +
4.23 + ///The heap type used by Dijkstra algorithm.
4.24 +
4.25 + ///The heap type used by Dijkstra algorithm.
4.26 + ///
4.27 + ///\sa BinHeap
4.28 + ///\sa Dijkstra
4.29 + typedef BinHeap<typename Graph::Node, typename LengthMap::Value,
4.30 + HeapCrossRef, std::less<Value> > Heap;
4.31 +
4.32 + ///Instantiates a Heap.
4.33 +
4.34 + ///This function instantiates a \ref Heap.
4.35 + /// \param crossRef The cross reference for the heap.
4.36 + static Heap *createHeap(HeapCrossRef& crossRef) {
4.37 + return new Heap(crossRef);
4.38 + }
4.39
4.40 /// \brief The type of the matrix map that stores the last edges of the
4.41 /// shortest paths.
4.42 @@ -121,7 +153,7 @@
4.43 /// This function instantiates a \ref PredMap.
4.44 /// \param G is the graph, to which we would like to define the PredMap.
4.45 /// \todo The graph alone may be insufficient for the initialization
4.46 - static PredMap *createPredMap(const _Graph& graph) {
4.47 + static PredMap *createPredMap(const Graph& graph) {
4.48 return new PredMap(graph);
4.49 }
4.50
4.51 @@ -158,7 +190,9 @@
4.52 /// should be used from each node.
4.53 ///
4.54 /// The complexity of this algorithm is $O(n^2 * log(n) + n * log(n) * e)$ or
4.55 - /// with fibonacci heap O(n^2 * log(n) + n * e).
4.56 + /// with fibonacci heap O(n^2 * log(n) + n * e). Usually the fibonacci heap
4.57 + /// implementation is slower than either binary heap implementation or the
4.58 + /// Floyd-Warshall algorithm.
4.59 ///
4.60 /// The type of the length is determined by the
4.61 /// \ref concept::ReadMap::Value "Value" of the length map.
4.62 @@ -225,6 +259,10 @@
4.63 typedef typename _Traits::DistMap DistMap;
4.64 /// \brief The operation traits.
4.65 typedef typename _Traits::OperationTraits OperationTraits;
4.66 + ///The cross reference type used for the current heap.
4.67 + typedef typename _Traits::HeapCrossRef HeapCrossRef;
4.68 + ///The heap type used by the dijkstra algorithm.
4.69 + typedef typename _Traits::Heap Heap;
4.70 private:
4.71 /// Pointer to the underlying graph.
4.72 const Graph *graph;
4.73 @@ -238,6 +276,14 @@
4.74 DistMap *_dist;
4.75 ///Indicates if \ref _dist is locally allocated (\c true) or not.
4.76 bool local_dist;
4.77 + ///Pointer to the heap cross references.
4.78 + HeapCrossRef *_heap_cross_ref;
4.79 + ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
4.80 + bool local_heap_cross_ref;
4.81 + ///Pointer to the heap.
4.82 + Heap *_heap;
4.83 + ///Indicates if \ref _heap is locally allocated (\c true) or not.
4.84 + bool local_heap;
4.85
4.86 /// Creates the maps if necessary.
4.87 void create_maps() {
4.88 @@ -249,9 +295,19 @@
4.89 local_dist = true;
4.90 _dist = Traits::createDistMap(*graph);
4.91 }
4.92 + if (!_heap_cross_ref) {
4.93 + local_heap_cross_ref = true;
4.94 + _heap_cross_ref = Traits::createHeapCrossRef(*graph);
4.95 + }
4.96 + if (!_heap) {
4.97 + local_heap = true;
4.98 + _heap = Traits::createHeap(*_heap_cross_ref);
4.99 + }
4.100 }
4.101 -
4.102 +
4.103 public :
4.104 +
4.105 + typedef Johnson Create;
4.106
4.107 /// \name Named template parameters
4.108
4.109 @@ -308,6 +364,56 @@
4.110 : public Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > {
4.111 typedef Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > Create;
4.112 };
4.113 +
4.114 + template <class H, class CR>
4.115 + struct DefHeapTraits : public Traits {
4.116 + typedef CR HeapCrossRef;
4.117 + typedef H Heap;
4.118 + static HeapCrossRef *createHeapCrossRef(const Graph &) {
4.119 + throw UninitializedParameter();
4.120 + }
4.121 + static Heap *createHeap(HeapCrossRef &)
4.122 + {
4.123 + throw UninitializedParameter();
4.124 + }
4.125 + };
4.126 + ///\ref named-templ-param "Named parameter" for setting heap and cross
4.127 + ///reference type
4.128 +
4.129 + ///\ref named-templ-param "Named parameter" for setting heap and cross
4.130 + ///reference type
4.131 + ///
4.132 + template <class H, class CR = typename Graph::template NodeMap<int> >
4.133 + struct DefHeap
4.134 + : public Johnson< Graph, LengthMap, DefHeapTraits<H, CR> > {
4.135 + typedef Johnson< Graph, LengthMap, DefHeapTraits<H, CR> > Create;
4.136 + };
4.137 +
4.138 + template <class H, class CR>
4.139 + struct DefStandardHeapTraits : public Traits {
4.140 + typedef CR HeapCrossRef;
4.141 + typedef H Heap;
4.142 + static HeapCrossRef *createHeapCrossRef(const Graph &G) {
4.143 + return new HeapCrossRef(G);
4.144 + }
4.145 + static Heap *createHeap(HeapCrossRef &R)
4.146 + {
4.147 + return new Heap(R);
4.148 + }
4.149 + };
4.150 + ///\ref named-templ-param "Named parameter" for setting heap and cross
4.151 + ///reference type with automatic allocation
4.152 +
4.153 + ///\ref named-templ-param "Named parameter" for setting heap and cross
4.154 + ///reference type. It can allocate the heap and the cross reference
4.155 + ///object if the cross reference's constructor waits for the graph as
4.156 + ///parameter and the heap's constructor waits for the cross reference.
4.157 + template <class H, class CR = typename Graph::template NodeMap<int> >
4.158 + struct DefStandardHeap
4.159 + : public Johnson< Graph, LengthMap, DefStandardHeapTraits<H, CR> > {
4.160 + typedef Johnson< Graph, LengthMap, DefStandardHeapTraits<H, CR> >
4.161 + Create;
4.162 + };
4.163
4.164 ///@}
4.165
4.166 @@ -316,6 +422,8 @@
4.167 Johnson() {}
4.168
4.169 public:
4.170 +
4.171 + typedef Johnson Create;
4.172
4.173 /// \brief Constructor.
4.174 ///
4.175 @@ -324,12 +432,16 @@
4.176 Johnson(const Graph& _graph, const LengthMap& _length) :
4.177 graph(&_graph), length(&_length),
4.178 _pred(0), local_pred(false),
4.179 - _dist(0), local_dist(false) {}
4.180 + _dist(0), local_dist(false),
4.181 + _heap_cross_ref(0), local_heap_cross_ref(false),
4.182 + _heap(0), local_heap(false) {}
4.183
4.184 ///Destructor.
4.185 ~Johnson() {
4.186 - if(local_pred) delete _pred;
4.187 - if(local_dist) delete _dist;
4.188 + if (local_pred) delete _pred;
4.189 + if (local_dist) delete _dist;
4.190 + if (local_heap_cross_ref) delete _heap_cross_ref;
4.191 + if (local_heap) delete _heap;
4.192 }
4.193
4.194 /// \brief Sets the length map.
4.195 @@ -373,6 +485,43 @@
4.196 return *this;
4.197 }
4.198
4.199 + protected:
4.200 +
4.201 + typedef typename BelmannFord<Graph, LengthMap>::
4.202 + template DefOperationTraits<OperationTraits>::
4.203 + template DefPredMap<NullMap<Node, Edge> >::
4.204 + Create BelmannFordType;
4.205 +
4.206 + void shiftedRun(const BelmannFordType& belmannford) {
4.207 +
4.208 + typedef PotentialDifferenceMap<Graph,
4.209 + typename BelmannFordType::DistMap> PotDiffMap;
4.210 + PotDiffMap potdiff(*graph, belmannford.distMap());
4.211 + typedef SubMap<LengthMap, PotDiffMap> ShiftLengthMap;
4.212 + ShiftLengthMap shiftlen(*length, potdiff);
4.213 +
4.214 + typename Dijkstra<Graph, ShiftLengthMap>::
4.215 + template DefHeap<Heap, HeapCrossRef>::Create dijkstra(*graph, shiftlen);
4.216 +
4.217 + dijkstra.heap(*_heap, *_heap_cross_ref);
4.218 +
4.219 + for (NodeIt it(*graph); it != INVALID; ++it) {
4.220 + dijkstra.run(it);
4.221 + for (NodeIt jt(*graph); jt != INVALID; ++jt) {
4.222 + if (dijkstra.reached(jt)) {
4.223 + _dist->set(it, jt, dijkstra.dist(jt) +
4.224 + belmannford.dist(jt) - belmannford.dist(it));
4.225 + _pred->set(it, jt, dijkstra.pred(jt));
4.226 + } else {
4.227 + _dist->set(it, jt, OperationTraits::infinity());
4.228 + _pred->set(it, jt, INVALID);
4.229 + }
4.230 + }
4.231 + }
4.232 + }
4.233 +
4.234 + public:
4.235 +
4.236 ///\name Execution control
4.237 /// The simplest way to execute the algorithm is to use
4.238 /// one of the member functions called \c run(...).
4.239 @@ -389,7 +538,7 @@
4.240 void init() {
4.241 create_maps();
4.242 }
4.243 -
4.244 +
4.245 /// \brief Executes the algorithm.
4.246 ///
4.247 /// This method runs the %Johnson algorithm in order to compute
4.248 @@ -398,10 +547,6 @@
4.249 /// - The shortest path tree for each node.
4.250 /// - The distance between each node pairs.
4.251 void start() {
4.252 - typedef typename BelmannFord<Graph, LengthMap>::
4.253 - template DefOperationTraits<OperationTraits>::
4.254 - template DefPredMap<NullMap<Node, Edge> >::
4.255 - Create BelmannFordType;
4.256
4.257 BelmannFordType belmannford(*graph, *length);
4.258
4.259 @@ -412,26 +557,32 @@
4.260 belmannford.init(OperationTraits::zero());
4.261 belmannford.start();
4.262
4.263 - for (NodeIt it(*graph); it != INVALID; ++it) {
4.264 - typedef PotentialDifferenceMap<Graph,
4.265 - typename BelmannFordType::DistMap> PotDiffMap;
4.266 - PotDiffMap potdiff(*graph, belmannford.distMap());
4.267 - typedef SubMap<LengthMap, PotDiffMap> ShiftLengthMap;
4.268 - ShiftLengthMap shiftlen(*length, potdiff);
4.269 - Dijkstra<Graph, ShiftLengthMap> dijkstra(*graph, shiftlen);
4.270 - dijkstra.run(it);
4.271 - for (NodeIt jt(*graph); jt != INVALID; ++jt) {
4.272 - if (dijkstra.reached(jt)) {
4.273 - _dist->set(it, jt, dijkstra.dist(jt) +
4.274 - belmannford.dist(jt) - belmannford.dist(it));
4.275 - _pred->set(it, jt, dijkstra.pred(jt));
4.276 - } else {
4.277 - _dist->set(it, jt, OperationTraits::infinity());
4.278 - _pred->set(it, jt, INVALID);
4.279 - }
4.280 - }
4.281 - }
4.282 + shiftedRun(belmannford);
4.283 }
4.284 +
4.285 + /// \brief Executes the algorithm and checks the negatvie circles.
4.286 + ///
4.287 + /// This method runs the %Johnson algorithm in order to compute
4.288 + /// the shortest path to each node pairs. If the graph contains
4.289 + /// negative circle it gives back false. The algorithm
4.290 + /// computes
4.291 + /// - The shortest path tree for each node.
4.292 + /// - The distance between each node pairs.
4.293 + bool checkedStart() {
4.294 +
4.295 + BelmannFordType belmannford(*graph, *length);
4.296 +
4.297 + NullMap<Node, Edge> predMap;
4.298 +
4.299 + belmannford.predMap(predMap);
4.300 +
4.301 + belmannford.init(OperationTraits::zero());
4.302 + if (!belmannford.checkedStart()) return false;
4.303 +
4.304 + shiftedRun(belmannford);
4.305 + return true;
4.306 + }
4.307 +
4.308
4.309 /// \brief Runs %Johnson algorithm.
4.310 ///