22 /// \brief Johnson algorithm. |
22 /// \brief Johnson algorithm. |
23 /// |
23 /// |
24 |
24 |
25 #include <lemon/list_graph.h> |
25 #include <lemon/list_graph.h> |
26 #include <lemon/graph_utils.h> |
26 #include <lemon/graph_utils.h> |
27 #include <lemon/dfs.h> |
|
28 #include <lemon/dijkstra.h> |
27 #include <lemon/dijkstra.h> |
29 #include <lemon/belmann_ford.h> |
28 #include <lemon/belmann_ford.h> |
30 #include <lemon/invalid.h> |
29 #include <lemon/invalid.h> |
31 #include <lemon/error.h> |
30 #include <lemon/error.h> |
32 #include <lemon/maps.h> |
31 #include <lemon/maps.h> |
170 /// JohnsonDefaultTraits for the documentation of a Johnson traits |
169 /// JohnsonDefaultTraits for the documentation of a Johnson traits |
171 /// class. |
170 /// class. |
172 /// |
171 /// |
173 /// \author Balazs Dezso |
172 /// \author Balazs Dezso |
174 |
173 |
|
174 #ifdef DOXYGEN |
|
175 template <typename _Graph, typename _LengthMap, typename _Traits> |
|
176 #else |
175 template <typename _Graph=ListGraph, |
177 template <typename _Graph=ListGraph, |
176 typename _LengthMap=typename _Graph::template EdgeMap<int>, |
178 typename _LengthMap=typename _Graph::template EdgeMap<int>, |
177 typename _Traits=JohnsonDefaultTraits<_Graph,_LengthMap> > |
179 typename _Traits=JohnsonDefaultTraits<_Graph,_LengthMap> > |
|
180 #endif |
178 class Johnson { |
181 class Johnson { |
179 public: |
182 public: |
180 |
183 |
181 /// \brief \ref Exception for uninitialized parameters. |
184 /// \brief \ref Exception for uninitialized parameters. |
182 /// |
185 /// |
255 /// \brief \ref named-templ-param "Named parameter" for setting PredMap |
258 /// \brief \ref named-templ-param "Named parameter" for setting PredMap |
256 /// type |
259 /// type |
257 /// \ref named-templ-param "Named parameter" for setting PredMap type |
260 /// \ref named-templ-param "Named parameter" for setting PredMap type |
258 /// |
261 /// |
259 template <class T> |
262 template <class T> |
260 class DefPredMap |
263 struct DefPredMap |
261 : public Johnson< Graph, LengthMap, DefPredMapTraits<T> > {}; |
264 : public Johnson< Graph, LengthMap, DefPredMapTraits<T> > { |
|
265 typedef Johnson< Graph, LengthMap, DefPredMapTraits<T> > Create; |
|
266 }; |
262 |
267 |
263 template <class T> |
268 template <class T> |
264 struct DefDistMapTraits : public Traits { |
269 struct DefDistMapTraits : public Traits { |
265 typedef T DistMap; |
270 typedef T DistMap; |
266 static DistMap *createDistMap(const Graph& graph) { |
271 static DistMap *createDistMap(const Graph& graph) { |
271 /// type |
276 /// type |
272 /// |
277 /// |
273 /// \ref named-templ-param "Named parameter" for setting DistMap type |
278 /// \ref named-templ-param "Named parameter" for setting DistMap type |
274 /// |
279 /// |
275 template <class T> |
280 template <class T> |
276 class DefDistMap |
281 struct DefDistMap |
277 : public Johnson< Graph, LengthMap, DefDistMapTraits<T> > {}; |
282 : public Johnson< Graph, LengthMap, DefDistMapTraits<T> > { |
|
283 typedef Johnson< Graph, LengthMap, DefDistMapTraits<T> > Create; |
|
284 }; |
278 |
285 |
279 template <class T> |
286 template <class T> |
280 struct DefOperationTraitsTraits : public Traits { |
287 struct DefOperationTraitsTraits : public Traits { |
281 typedef T OperationTraits; |
288 typedef T OperationTraits; |
282 }; |
289 }; |
283 |
290 |
284 /// \brief \ref named-templ-param "Named parameter" for setting |
291 /// \brief \ref named-templ-param "Named parameter" for setting |
285 /// OperationTraits type |
292 /// OperationTraits type |
286 /// |
293 /// |
287 /// \ref named-templ-param "Named parameter" for setting PredMap type |
294 /// \ref named-templ-param "Named parameter" for setting |
|
295 /// OperationTraits type |
288 template <class T> |
296 template <class T> |
289 class DefOperationTraits |
297 struct DefOperationTraits |
290 : public Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > {}; |
298 : public Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > { |
|
299 typedef Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > Create; |
|
300 }; |
291 |
301 |
292 ///@} |
302 ///@} |
|
303 |
|
304 protected: |
|
305 |
|
306 Johnson() {} |
293 |
307 |
294 public: |
308 public: |
295 |
309 |
296 /// \brief Constructor. |
310 /// \brief Constructor. |
297 /// |
311 /// |
372 /// the shortest path to each node pairs. The algorithm |
386 /// the shortest path to each node pairs. The algorithm |
373 /// computes |
387 /// computes |
374 /// - The shortest path tree for each node. |
388 /// - The shortest path tree for each node. |
375 /// - The distance between each node pairs. |
389 /// - The distance between each node pairs. |
376 void start() { |
390 void start() { |
377 typename BelmannFord<Graph, LengthMap>:: |
391 typedef typename BelmannFord<Graph, LengthMap>:: |
378 template DefOperationTraits<OperationTraits>:: |
392 template DefOperationTraits<OperationTraits>:: |
379 BelmannFord belmannford(*graph, *length); |
393 template DefPredMap<NullMap<Node, Edge> >:: |
|
394 Create BelmannFordType; |
|
395 |
|
396 BelmannFordType belmannford(*graph, *length); |
|
397 |
|
398 NullMap<Node, Edge> predMap; |
|
399 |
|
400 belmannford.predMap(predMap); |
380 |
401 |
381 belmannford.init(); |
402 belmannford.init(OperationTraits::zero()); |
382 |
|
383 typename Graph::template NodeMap<bool> initial(*graph, false); |
|
384 |
|
385 { |
|
386 Dfs<Graph> dfs(*graph); |
|
387 |
|
388 dfs.init(); |
|
389 for (NodeIt it(*graph); it != INVALID; ++it) { |
|
390 if (!dfs.reached(it)) { |
|
391 dfs.addSource(it); |
|
392 while (!dfs.emptyQueue()) { |
|
393 Edge edge = dfs.processNextEdge(); |
|
394 initial.set(graph->target(edge), false); |
|
395 } |
|
396 initial.set(it, true); |
|
397 } |
|
398 } |
|
399 for (NodeIt it(*graph); it != INVALID; ++it) { |
|
400 if (initial[it]) { |
|
401 belmannford.addSource(it); |
|
402 } |
|
403 } |
|
404 } |
|
405 |
|
406 belmannford.start(); |
403 belmannford.start(); |
407 |
404 |
408 for (NodeIt it(*graph); it != INVALID; ++it) { |
405 for (NodeIt it(*graph); it != INVALID; ++it) { |
409 typedef PotentialDifferenceMap<Graph, |
406 typedef PotentialDifferenceMap<Graph, |
410 typename BelmannFord<Graph, LengthMap>::DistMap> PotDiffMap; |
407 typename BelmannFordType::DistMap> PotDiffMap; |
411 PotDiffMap potdiff(*graph, belmannford.distMap()); |
408 PotDiffMap potdiff(*graph, belmannford.distMap()); |
412 typedef SubMap<LengthMap, PotDiffMap> ShiftLengthMap; |
409 typedef SubMap<LengthMap, PotDiffMap> ShiftLengthMap; |
413 ShiftLengthMap shiftlen(*length, potdiff); |
410 ShiftLengthMap shiftlen(*length, potdiff); |
414 Dijkstra<Graph, ShiftLengthMap> dijkstra(*graph, shiftlen); |
411 Dijkstra<Graph, ShiftLengthMap> dijkstra(*graph, shiftlen); |
415 dijkstra.run(it); |
412 dijkstra.run(it); |