Changeset 1710:f531c16dd923 in lemon-0.x for lemon/johnson.h
- Timestamp:
- 10/06/05 11:37:53 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2237
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/johnson.h
r1699 r1710 25 25 #include <lemon/list_graph.h> 26 26 #include <lemon/graph_utils.h> 27 #include <lemon/dfs.h>28 27 #include <lemon/dijkstra.h> 29 28 #include <lemon/belmann_ford.h> … … 173 172 /// \author Balazs Dezso 174 173 174 #ifdef DOXYGEN 175 template <typename _Graph, typename _LengthMap, typename _Traits> 176 #else 175 177 template <typename _Graph=ListGraph, 176 178 typename _LengthMap=typename _Graph::template EdgeMap<int>, 177 179 typename _Traits=JohnsonDefaultTraits<_Graph,_LengthMap> > 180 #endif 178 181 class Johnson { 179 182 public: … … 258 261 /// 259 262 template <class T> 260 class DefPredMap 261 : public Johnson< Graph, LengthMap, DefPredMapTraits<T> > {}; 263 struct DefPredMap 264 : public Johnson< Graph, LengthMap, DefPredMapTraits<T> > { 265 typedef Johnson< Graph, LengthMap, DefPredMapTraits<T> > Create; 266 }; 262 267 263 268 template <class T> … … 274 279 /// 275 280 template <class T> 276 class DefDistMap 277 : public Johnson< Graph, LengthMap, DefDistMapTraits<T> > {}; 281 struct DefDistMap 282 : public Johnson< Graph, LengthMap, DefDistMapTraits<T> > { 283 typedef Johnson< Graph, LengthMap, DefDistMapTraits<T> > Create; 284 }; 278 285 279 286 template <class T> … … 285 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 296 template <class T> 289 class DefOperationTraits 290 : public Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > {}; 297 struct DefOperationTraits 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 308 public: … … 375 389 /// - The distance between each node pairs. 376 390 void start() { 377 type name BelmannFord<Graph, LengthMap>::391 typedef typename BelmannFord<Graph, LengthMap>:: 378 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(); 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 402 belmannford.init(OperationTraits::zero()); 406 403 belmannford.start(); 407 404 408 405 for (NodeIt it(*graph); it != INVALID; ++it) { 409 406 typedef PotentialDifferenceMap<Graph, 410 typename BelmannFord <Graph, LengthMap>::DistMap> PotDiffMap;407 typename BelmannFordType::DistMap> PotDiffMap; 411 408 PotDiffMap potdiff(*graph, belmannford.distMap()); 412 409 typedef SubMap<LengthMap, PotDiffMap> ShiftLengthMap;
Note: See TracChangeset
for help on using the changeset viewer.