1.1 --- a/lemon/johnson.h Mon Oct 24 17:03:02 2005 +0000
1.2 +++ b/lemon/johnson.h Wed Oct 26 10:50:47 2005 +0000
1.3 @@ -106,6 +106,38 @@
1.4 /// and the used operation.
1.5 /// \see JohnsonDefaultOperationTraits
1.6 typedef JohnsonDefaultOperationTraits<Value> OperationTraits;
1.7 +
1.8 + /// The cross reference type used by heap.
1.9 +
1.10 + /// The cross reference type used by heap.
1.11 + /// Usually it is \c Graph::NodeMap<int>.
1.12 + typedef typename Graph::template NodeMap<int> HeapCrossRef;
1.13 +
1.14 + ///Instantiates a HeapCrossRef.
1.15 +
1.16 + ///This function instantiates a \ref HeapCrossRef.
1.17 + /// \param graph is the graph, to which we would like to define the
1.18 + /// HeapCrossRef.
1.19 + static HeapCrossRef *createHeapCrossRef(const Graph& graph) {
1.20 + return new HeapCrossRef(graph);
1.21 + }
1.22 +
1.23 + ///The heap type used by Dijkstra algorithm.
1.24 +
1.25 + ///The heap type used by Dijkstra algorithm.
1.26 + ///
1.27 + ///\sa BinHeap
1.28 + ///\sa Dijkstra
1.29 + typedef BinHeap<typename Graph::Node, typename LengthMap::Value,
1.30 + HeapCrossRef, std::less<Value> > Heap;
1.31 +
1.32 + ///Instantiates a Heap.
1.33 +
1.34 + ///This function instantiates a \ref Heap.
1.35 + /// \param crossRef The cross reference for the heap.
1.36 + static Heap *createHeap(HeapCrossRef& crossRef) {
1.37 + return new Heap(crossRef);
1.38 + }
1.39
1.40 /// \brief The type of the matrix map that stores the last edges of the
1.41 /// shortest paths.
1.42 @@ -121,7 +153,7 @@
1.43 /// This function instantiates a \ref PredMap.
1.44 /// \param G is the graph, to which we would like to define the PredMap.
1.45 /// \todo The graph alone may be insufficient for the initialization
1.46 - static PredMap *createPredMap(const _Graph& graph) {
1.47 + static PredMap *createPredMap(const Graph& graph) {
1.48 return new PredMap(graph);
1.49 }
1.50
1.51 @@ -158,7 +190,9 @@
1.52 /// should be used from each node.
1.53 ///
1.54 /// The complexity of this algorithm is $O(n^2 * log(n) + n * log(n) * e)$ or
1.55 - /// with fibonacci heap O(n^2 * log(n) + n * e).
1.56 + /// with fibonacci heap O(n^2 * log(n) + n * e). Usually the fibonacci heap
1.57 + /// implementation is slower than either binary heap implementation or the
1.58 + /// Floyd-Warshall algorithm.
1.59 ///
1.60 /// The type of the length is determined by the
1.61 /// \ref concept::ReadMap::Value "Value" of the length map.
1.62 @@ -225,6 +259,10 @@
1.63 typedef typename _Traits::DistMap DistMap;
1.64 /// \brief The operation traits.
1.65 typedef typename _Traits::OperationTraits OperationTraits;
1.66 + ///The cross reference type used for the current heap.
1.67 + typedef typename _Traits::HeapCrossRef HeapCrossRef;
1.68 + ///The heap type used by the dijkstra algorithm.
1.69 + typedef typename _Traits::Heap Heap;
1.70 private:
1.71 /// Pointer to the underlying graph.
1.72 const Graph *graph;
1.73 @@ -238,6 +276,14 @@
1.74 DistMap *_dist;
1.75 ///Indicates if \ref _dist is locally allocated (\c true) or not.
1.76 bool local_dist;
1.77 + ///Pointer to the heap cross references.
1.78 + HeapCrossRef *_heap_cross_ref;
1.79 + ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
1.80 + bool local_heap_cross_ref;
1.81 + ///Pointer to the heap.
1.82 + Heap *_heap;
1.83 + ///Indicates if \ref _heap is locally allocated (\c true) or not.
1.84 + bool local_heap;
1.85
1.86 /// Creates the maps if necessary.
1.87 void create_maps() {
1.88 @@ -249,9 +295,19 @@
1.89 local_dist = true;
1.90 _dist = Traits::createDistMap(*graph);
1.91 }
1.92 + if (!_heap_cross_ref) {
1.93 + local_heap_cross_ref = true;
1.94 + _heap_cross_ref = Traits::createHeapCrossRef(*graph);
1.95 + }
1.96 + if (!_heap) {
1.97 + local_heap = true;
1.98 + _heap = Traits::createHeap(*_heap_cross_ref);
1.99 + }
1.100 }
1.101 -
1.102 +
1.103 public :
1.104 +
1.105 + typedef Johnson Create;
1.106
1.107 /// \name Named template parameters
1.108
1.109 @@ -308,6 +364,56 @@
1.110 : public Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > {
1.111 typedef Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > Create;
1.112 };
1.113 +
1.114 + template <class H, class CR>
1.115 + struct DefHeapTraits : public Traits {
1.116 + typedef CR HeapCrossRef;
1.117 + typedef H Heap;
1.118 + static HeapCrossRef *createHeapCrossRef(const Graph &) {
1.119 + throw UninitializedParameter();
1.120 + }
1.121 + static Heap *createHeap(HeapCrossRef &)
1.122 + {
1.123 + throw UninitializedParameter();
1.124 + }
1.125 + };
1.126 + ///\ref named-templ-param "Named parameter" for setting heap and cross
1.127 + ///reference type
1.128 +
1.129 + ///\ref named-templ-param "Named parameter" for setting heap and cross
1.130 + ///reference type
1.131 + ///
1.132 + template <class H, class CR = typename Graph::template NodeMap<int> >
1.133 + struct DefHeap
1.134 + : public Johnson< Graph, LengthMap, DefHeapTraits<H, CR> > {
1.135 + typedef Johnson< Graph, LengthMap, DefHeapTraits<H, CR> > Create;
1.136 + };
1.137 +
1.138 + template <class H, class CR>
1.139 + struct DefStandardHeapTraits : public Traits {
1.140 + typedef CR HeapCrossRef;
1.141 + typedef H Heap;
1.142 + static HeapCrossRef *createHeapCrossRef(const Graph &G) {
1.143 + return new HeapCrossRef(G);
1.144 + }
1.145 + static Heap *createHeap(HeapCrossRef &R)
1.146 + {
1.147 + return new Heap(R);
1.148 + }
1.149 + };
1.150 + ///\ref named-templ-param "Named parameter" for setting heap and cross
1.151 + ///reference type with automatic allocation
1.152 +
1.153 + ///\ref named-templ-param "Named parameter" for setting heap and cross
1.154 + ///reference type. It can allocate the heap and the cross reference
1.155 + ///object if the cross reference's constructor waits for the graph as
1.156 + ///parameter and the heap's constructor waits for the cross reference.
1.157 + template <class H, class CR = typename Graph::template NodeMap<int> >
1.158 + struct DefStandardHeap
1.159 + : public Johnson< Graph, LengthMap, DefStandardHeapTraits<H, CR> > {
1.160 + typedef Johnson< Graph, LengthMap, DefStandardHeapTraits<H, CR> >
1.161 + Create;
1.162 + };
1.163
1.164 ///@}
1.165
1.166 @@ -316,6 +422,8 @@
1.167 Johnson() {}
1.168
1.169 public:
1.170 +
1.171 + typedef Johnson Create;
1.172
1.173 /// \brief Constructor.
1.174 ///
1.175 @@ -324,12 +432,16 @@
1.176 Johnson(const Graph& _graph, const LengthMap& _length) :
1.177 graph(&_graph), length(&_length),
1.178 _pred(0), local_pred(false),
1.179 - _dist(0), local_dist(false) {}
1.180 + _dist(0), local_dist(false),
1.181 + _heap_cross_ref(0), local_heap_cross_ref(false),
1.182 + _heap(0), local_heap(false) {}
1.183
1.184 ///Destructor.
1.185 ~Johnson() {
1.186 - if(local_pred) delete _pred;
1.187 - if(local_dist) delete _dist;
1.188 + if (local_pred) delete _pred;
1.189 + if (local_dist) delete _dist;
1.190 + if (local_heap_cross_ref) delete _heap_cross_ref;
1.191 + if (local_heap) delete _heap;
1.192 }
1.193
1.194 /// \brief Sets the length map.
1.195 @@ -373,6 +485,43 @@
1.196 return *this;
1.197 }
1.198
1.199 + protected:
1.200 +
1.201 + typedef typename BelmannFord<Graph, LengthMap>::
1.202 + template DefOperationTraits<OperationTraits>::
1.203 + template DefPredMap<NullMap<Node, Edge> >::
1.204 + Create BelmannFordType;
1.205 +
1.206 + void shiftedRun(const BelmannFordType& belmannford) {
1.207 +
1.208 + typedef PotentialDifferenceMap<Graph,
1.209 + typename BelmannFordType::DistMap> PotDiffMap;
1.210 + PotDiffMap potdiff(*graph, belmannford.distMap());
1.211 + typedef SubMap<LengthMap, PotDiffMap> ShiftLengthMap;
1.212 + ShiftLengthMap shiftlen(*length, potdiff);
1.213 +
1.214 + typename Dijkstra<Graph, ShiftLengthMap>::
1.215 + template DefHeap<Heap, HeapCrossRef>::Create dijkstra(*graph, shiftlen);
1.216 +
1.217 + dijkstra.heap(*_heap, *_heap_cross_ref);
1.218 +
1.219 + for (NodeIt it(*graph); it != INVALID; ++it) {
1.220 + dijkstra.run(it);
1.221 + for (NodeIt jt(*graph); jt != INVALID; ++jt) {
1.222 + if (dijkstra.reached(jt)) {
1.223 + _dist->set(it, jt, dijkstra.dist(jt) +
1.224 + belmannford.dist(jt) - belmannford.dist(it));
1.225 + _pred->set(it, jt, dijkstra.pred(jt));
1.226 + } else {
1.227 + _dist->set(it, jt, OperationTraits::infinity());
1.228 + _pred->set(it, jt, INVALID);
1.229 + }
1.230 + }
1.231 + }
1.232 + }
1.233 +
1.234 + public:
1.235 +
1.236 ///\name Execution control
1.237 /// The simplest way to execute the algorithm is to use
1.238 /// one of the member functions called \c run(...).
1.239 @@ -389,7 +538,7 @@
1.240 void init() {
1.241 create_maps();
1.242 }
1.243 -
1.244 +
1.245 /// \brief Executes the algorithm.
1.246 ///
1.247 /// This method runs the %Johnson algorithm in order to compute
1.248 @@ -398,10 +547,6 @@
1.249 /// - The shortest path tree for each node.
1.250 /// - The distance between each node pairs.
1.251 void start() {
1.252 - typedef typename BelmannFord<Graph, LengthMap>::
1.253 - template DefOperationTraits<OperationTraits>::
1.254 - template DefPredMap<NullMap<Node, Edge> >::
1.255 - Create BelmannFordType;
1.256
1.257 BelmannFordType belmannford(*graph, *length);
1.258
1.259 @@ -412,26 +557,32 @@
1.260 belmannford.init(OperationTraits::zero());
1.261 belmannford.start();
1.262
1.263 - for (NodeIt it(*graph); it != INVALID; ++it) {
1.264 - typedef PotentialDifferenceMap<Graph,
1.265 - typename BelmannFordType::DistMap> PotDiffMap;
1.266 - PotDiffMap potdiff(*graph, belmannford.distMap());
1.267 - typedef SubMap<LengthMap, PotDiffMap> ShiftLengthMap;
1.268 - ShiftLengthMap shiftlen(*length, potdiff);
1.269 - Dijkstra<Graph, ShiftLengthMap> dijkstra(*graph, shiftlen);
1.270 - dijkstra.run(it);
1.271 - for (NodeIt jt(*graph); jt != INVALID; ++jt) {
1.272 - if (dijkstra.reached(jt)) {
1.273 - _dist->set(it, jt, dijkstra.dist(jt) +
1.274 - belmannford.dist(jt) - belmannford.dist(it));
1.275 - _pred->set(it, jt, dijkstra.pred(jt));
1.276 - } else {
1.277 - _dist->set(it, jt, OperationTraits::infinity());
1.278 - _pred->set(it, jt, INVALID);
1.279 - }
1.280 - }
1.281 - }
1.282 + shiftedRun(belmannford);
1.283 }
1.284 +
1.285 + /// \brief Executes the algorithm and checks the negatvie circles.
1.286 + ///
1.287 + /// This method runs the %Johnson algorithm in order to compute
1.288 + /// the shortest path to each node pairs. If the graph contains
1.289 + /// negative circle it gives back false. The algorithm
1.290 + /// computes
1.291 + /// - The shortest path tree for each node.
1.292 + /// - The distance between each node pairs.
1.293 + bool checkedStart() {
1.294 +
1.295 + BelmannFordType belmannford(*graph, *length);
1.296 +
1.297 + NullMap<Node, Edge> predMap;
1.298 +
1.299 + belmannford.predMap(predMap);
1.300 +
1.301 + belmannford.init(OperationTraits::zero());
1.302 + if (!belmannford.checkedStart()) return false;
1.303 +
1.304 + shiftedRun(belmannford);
1.305 + return true;
1.306 + }
1.307 +
1.308
1.309 /// \brief Runs %Johnson algorithm.
1.310 ///