Changeset 209:765619b7cbb2 in lemon-main for lemon/dijkstra.h

Timestamp:

07/13/08 20:51:02 (16 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Phase:

public

Message:

Apply unify-sources.sh to the source tree

File:

• lemon/dijkstra.h (modified) (74 diffs)

lemon/dijkstra.h

@@ -1 @@
-/* -*- C++ -*-
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
  *
- * This file is a part of LEMON, a generic C++ optimization library
+ * This file is a part of LEMON, a generic C++ optimization library.
  *
  * Copyright (C) 2003-2008
@@ -35 +35 @@
 
   /// \brief Default OperationTraits for the Dijkstra algorithm class.
-  ///  
+  ///
   /// It defines all computational operations and constants which are
   /// used in the Dijkstra algorithm.
@@ -55 +55 @@
 
   /// \brief Widest path OperationTraits for the Dijkstra algorithm class.
-  ///  
+  ///
   /// It defines all computational operations and constants which are
   /// used in the Dijkstra algorithm for widest path computation.
@@ -73 +73 @@
     }
   };
-  
+
   ///Default traits class of Dijkstra class.
 
@@ -82 +82 @@
   struct DijkstraDefaultTraits
   {
-    ///The digraph type the algorithm runs on. 
+    ///The digraph type the algorithm runs on.
     typedef GR Digraph;
     ///The type of the map that stores the arc lengths.
@@ -104 +104 @@
     ///Instantiates a HeapCrossRef.
 
-    ///This function instantiates a \c HeapCrossRef. 
-    /// \param G is the digraph, to which we would like to define the 
+    ///This function instantiates a \c HeapCrossRef.
+    /// \param G is the digraph, to which we would like to define the
     /// HeapCrossRef.
-    static HeapCrossRef *createHeapCrossRef(const GR &G) 
+    static HeapCrossRef *createHeapCrossRef(const GR &G)
     {
       return new HeapCrossRef(G);
     }
-    
+
     ///The heap type used by Dijkstra algorithm.
 
@@ -120 +120 @@
     typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
 
-    static Heap *createHeap(HeapCrossRef& R) 
+    static Heap *createHeap(HeapCrossRef& R)
     {
       return new Heap(R);
@@ -127 +127 @@
     ///\brief The type of the map that stores the last
     ///arcs of the shortest paths.
-    /// 
+    ///
     ///The type of the map that stores the last
     ///arcs of the shortest paths.
@@ -134 +134 @@
     typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
     ///Instantiates a PredMap.
- 
-    ///This function instantiates a \c PredMap. 
+
+    ///This function instantiates a \c PredMap.
     ///\param G is the digraph, to which we would like to define the PredMap.
     ///\todo The digraph alone may be insufficient for the initialization
-    static PredMap *createPredMap(const GR &G) 
+    static PredMap *createPredMap(const GR &G)
     {
       return new PredMap(G);
@@ -144 +144 @@
 
     ///The type of the map that stores whether a nodes is processed.
- 
+
     ///The type of the map that stores whether a nodes is processed.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
@@ -153 +153 @@
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     ///Instantiates a ProcessedMap.
- 
-    ///This function instantiates a \c ProcessedMap. 
+
+    ///This function instantiates a \c ProcessedMap.
     ///\param g is the digraph, to which
     ///we would like to define the \c ProcessedMap
@@ -166 +166 @@
     }
     ///The type of the map that stores the dists of the nodes.
- 
+
     ///The type of the map that stores the dists of the nodes.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
@@ -172 +172 @@
     typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
     ///Instantiates a DistMap.
- 
-    ///This function instantiates a \ref DistMap. 
+
+    ///This function instantiates a \ref DistMap.
     ///\param G is the digraph, to which we would like to define the \ref DistMap
     static DistMap *createDistMap(const GR &G)
@@ -180 +180 @@
     }
   };
-  
+
   ///%Dijkstra algorithm class.
-  
+
   /// \ingroup shortest_path
   ///This class provides an efficient implementation of %Dijkstra algorithm.
@@ -203 +203 @@
   ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".  The value
   ///of LM is not used directly by Dijkstra, it is only passed to \ref
-  ///DijkstraDefaultTraits.  
+  ///DijkstraDefaultTraits.
   ///\tparam TR Traits class to set
   ///various data types used by the algorithm.  The default traits
@@ -215 +215 @@
 #else
   template <typename GR=ListDigraph,
-            typename LM=typename GR::template ArcMap<int>,
-            typename TR=DijkstraDefaultTraits<GR,LM> >
+            typename LM=typename GR::template ArcMap<int>,
+            typename TR=DijkstraDefaultTraits<GR,LM> >
 #endif
   class Dijkstra {
@@ -229 +229 @@
     public:
       virtual const char* what() const throw() {
-        return "lemon::Dijkstra::UninitializedParameter";
+        return "lemon::Dijkstra::UninitializedParameter";
       }
     };
@@ -244 +244 @@
     ///\e
     typedef typename Digraph::OutArcIt OutArcIt;
-    
+
     ///The type of the length of the arcs.
     typedef typename TR::LengthMap::Value Value;
@@ -289 +289 @@
 
     ///Creates the maps if necessary.
-    
+
     ///\todo Better memory allocation (instead of new).
-    void create_maps() 
+    void create_maps()
     {
       if(!_pred) {
-        local_pred = true;
-        _pred = Traits::createPredMap(*G);
+        local_pred = true;
+        _pred = Traits::createPredMap(*G);
       }
       if(!_dist) {
-        local_dist = true;
-        _dist = Traits::createDistMap(*G);
+        local_dist = true;
+        _dist = Traits::createDistMap(*G);
       }
       if(!_processed) {
-        local_processed = true;
-        _processed = Traits::createProcessedMap(*G);
+        local_processed = true;
+        _processed = Traits::createProcessedMap(*G);
       }
       if (!_heap_cross_ref) {
-        local_heap_cross_ref = true;
-        _heap_cross_ref = Traits::createHeapCrossRef(*G);
+        local_heap_cross_ref = true;
+        _heap_cross_ref = Traits::createHeapCrossRef(*G);
       }
       if (!_heap) {
-        local_heap = true;
-        _heap = Traits::createHeap(*_heap_cross_ref);
-      }
-    }
-    
+        local_heap = true;
+        _heap = Traits::createHeap(*_heap_cross_ref);
+      }
+    }
+
   public :
 
     typedef Dijkstra Create;
- 
+
     ///\name Named template parameters
 
@@ -328 +328 @@
       static PredMap *createPredMap(const Digraph &)
       {
-        throw UninitializedParameter();
+        throw UninitializedParameter();
       }
     };
@@ -336 +336 @@
     ///
     template <class T>
-    struct DefPredMap 
-      : public Dijkstra< Digraph,       LengthMap, DefPredMapTraits<T> > {
-      typedef Dijkstra< Digraph,        LengthMap, DefPredMapTraits<T> > Create;
-    };
-    
+    struct DefPredMap
+      : public Dijkstra< Digraph,        LengthMap, DefPredMapTraits<T> > {
+      typedef Dijkstra< Digraph,        LengthMap, DefPredMapTraits<T> > Create;
+    };
+
     template <class T>
     struct DefDistMapTraits : public Traits {
@@ -346 +346 @@
       static DistMap *createDistMap(const Digraph &)
       {
-        throw UninitializedParameter();
+        throw UninitializedParameter();
       }
     };
@@ -354 +354 @@
     ///
     template <class T>
-    struct DefDistMap 
-      : public Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > { 
+    struct DefDistMap
+      : public Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > {
       typedef Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > Create;
     };
-    
+
     template <class T>
     struct DefProcessedMapTraits : public Traits {
       typedef T ProcessedMap;
-      static ProcessedMap *createProcessedMap(const Digraph &G) 
+      static ProcessedMap *createProcessedMap(const Digraph &G)
       {
-        throw UninitializedParameter();
+        throw UninitializedParameter();
       }
     };
@@ -372 +372 @@
     ///
     template <class T>
-    struct DefProcessedMap 
-      : public Dijkstra< Digraph,       LengthMap, DefProcessedMapTraits<T> > { 
-      typedef Dijkstra< Digraph,        LengthMap, DefProcessedMapTraits<T> > Create;
-    };
-    
+    struct DefProcessedMap
+      : public Dijkstra< Digraph,        LengthMap, DefProcessedMapTraits<T> > {
+      typedef Dijkstra< Digraph,        LengthMap, DefProcessedMapTraits<T> > Create;
+    };
+
     struct DefDigraphProcessedMapTraits : public Traits {
       typedef typename Digraph::template NodeMap<bool> ProcessedMap;
-      static ProcessedMap *createProcessedMap(const Digraph &G) 
+      static ProcessedMap *createProcessedMap(const Digraph &G)
       {
-        return new ProcessedMap(G);
+        return new ProcessedMap(G);
       }
     };
@@ -391 +391 @@
     ///If you don't set it explicitely, it will be automatically allocated.
     template <class T>
-    struct DefProcessedMapToBeDefaultMap 
+    struct DefProcessedMapToBeDefaultMap
       : public Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> {
       typedef Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> Create;
@@ -401 +401 @@
       typedef H Heap;
       static HeapCrossRef *createHeapCrossRef(const Digraph &) {
-        throw UninitializedParameter();
-      }
-      static Heap *createHeap(HeapCrossRef &) 
+        throw UninitializedParameter();
+      }
+      static Heap *createHeap(HeapCrossRef &)
       {
-        throw UninitializedParameter();
+        throw UninitializedParameter();
       }
     };
@@ -411 +411 @@
     ///heap and cross reference type
     ///
-    ///\ref named-templ-param "Named parameter" for setting heap and cross 
+    ///\ref named-templ-param "Named parameter" for setting heap and cross
     ///reference type
     ///
     template <class H, class CR = typename Digraph::template NodeMap<int> >
     struct DefHeap
-      : public Dijkstra< Digraph,       LengthMap, DefHeapTraits<H, CR> > { 
-      typedef Dijkstra< Digraph,        LengthMap, DefHeapTraits<H, CR> > Create;
+      : public Dijkstra< Digraph,        LengthMap, DefHeapTraits<H, CR> > {
+      typedef Dijkstra< Digraph,        LengthMap, DefHeapTraits<H, CR> > Create;
     };
 
@@ -425 +425 @@
       typedef H Heap;
       static HeapCrossRef *createHeapCrossRef(const Digraph &G) {
-        return new HeapCrossRef(G);
-      }
-      static Heap *createHeap(HeapCrossRef &R) 
+        return new HeapCrossRef(G);
+      }
+      static Heap *createHeap(HeapCrossRef &R)
       {
-        return new Heap(R);
+        return new Heap(R);
       }
     };
@@ -435 +435 @@
     ///heap and cross reference type with automatic allocation
     ///
-    ///\ref named-templ-param "Named parameter" for setting heap and cross 
-    ///reference type. It can allocate the heap and the cross reference 
-    ///object if the cross reference's constructor waits for the digraph as 
+    ///\ref named-templ-param "Named parameter" for setting heap and cross
+    ///reference type. It can allocate the heap and the cross reference
+    ///object if the cross reference's constructor waits for the digraph as
     ///parameter and the heap's constructor waits for the cross reference.
     template <class H, class CR = typename Digraph::template NodeMap<int> >
     struct DefStandardHeap
-      : public Dijkstra< Digraph,       LengthMap, DefStandardHeapTraits<H, CR> > { 
-      typedef Dijkstra< Digraph,        LengthMap, DefStandardHeapTraits<H, CR> > 
+      : public Dijkstra< Digraph,        LengthMap, DefStandardHeapTraits<H, CR> > {
+      typedef Dijkstra< Digraph,        LengthMap, DefStandardHeapTraits<H, CR> >
       Create;
     };
@@ -450 +450 @@
       typedef T OperationTraits;
     };
-    
-    /// \brief \ref named-templ-param "Named parameter" for setting 
+
+    /// \brief \ref named-templ-param "Named parameter" for setting
     /// OperationTraits type
     ///
@@ -462 +462 @@
       Create;
     };
-    
+
     ///@}
 
@@ -470 +470 @@
     Dijkstra() {}
 
-  public:      
-    
+  public:
+
     ///Constructor.
-    
+
     ///\param _G the digraph the algorithm will run on.
     ///\param _length the length map used by the algorithm.
@@ -484 +484 @@
       _heap(NULL), local_heap(false)
     { }
-    
+
     ///Destructor.
-    ~Dijkstra() 
+    ~Dijkstra()
     {
       if(local_pred) delete _pred;
@@ -499 +499 @@
     ///Sets the length map.
     ///\return <tt> (*this) </tt>
-    Dijkstra &lengthMap(const LengthMap &m) 
+    Dijkstra &lengthMap(const LengthMap &m)
     {
       length = &m;
@@ -512 +512 @@
     ///automatically allocated map, of course.
     ///\return <tt> (*this) </tt>
-    Dijkstra &predMap(PredMap &m) 
+    Dijkstra &predMap(PredMap &m)
     {
       if(local_pred) {
-        delete _pred;
-        local_pred=false;
+        delete _pred;
+        local_pred=false;
       }
       _pred = &m;
@@ -529 +529 @@
     ///automatically allocated map, of course.
     ///\return <tt> (*this) </tt>
-    Dijkstra &distMap(DistMap &m) 
+    Dijkstra &distMap(DistMap &m)
     {
       if(local_dist) {
-        delete _dist;
-        local_dist=false;
+        delete _dist;
+        local_dist=false;
       }
       _dist = &m;
@@ -549 +549 @@
     {
       if(local_heap_cross_ref) {
-        delete _heap_cross_ref;
-        local_heap_cross_ref=false;
+        delete _heap_cross_ref;
+        local_heap_cross_ref=false;
       }
       _heap_cross_ref = &cr;
       if(local_heap) {
-        delete _heap;
-        local_heap=false;
+        delete _heap;
+        local_heap=false;
       }
       _heap = &hp;
@@ -593 +593 @@
       _heap->clear();
       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
-        _pred->set(u,INVALID);
-        _processed->set(u,false);
-        _heap_cross_ref->set(u,Heap::PRE_HEAP);
-      }
-    }
-    
+        _pred->set(u,INVALID);
+        _processed->set(u,false);
+        _heap_cross_ref->set(u,Heap::PRE_HEAP);
+      }
+    }
+
     ///Adds a new source node.
 
@@ -611 +611 @@
     {
       if(_heap->state(s) != Heap::IN_HEAP) {
-        _heap->push(s,dst);
+        _heap->push(s,dst);
       } else if(OperationTraits::less((*_heap)[s], dst)) {
-        _heap->set(s,dst);
-        _pred->set(s,INVALID);
-      }
-    }
-    
+        _heap->set(s,dst);
+        _pred->set(s,INVALID);
+      }
+    }
+
     ///Processes the next node in the priority heap
 
@@ -627 +627 @@
     Node processNextNode()
     {
-      Node v=_heap->top(); 
+      Node v=_heap->top();
       Value oldvalue=_heap->prio();
       _heap->pop();
       finalizeNodeData(v,oldvalue);
-      
+
       for(OutArcIt e(*G,v); e!=INVALID; ++e) {
-        Node w=G->target(e); 
-        switch(_heap->state(w)) {
-        case Heap::PRE_HEAP:
-          _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e])); 
-          _pred->set(w,e);
-          break;
-        case Heap::IN_HEAP:
-          {
-            Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
-            if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
-              _heap->decrease(w, newvalue); 
-              _pred->set(w,e);
-            }
-          }
-          break;
-        case Heap::POST_HEAP:
-          break;
-        }
+        Node w=G->target(e);
+        switch(_heap->state(w)) {
+        case Heap::PRE_HEAP:
+          _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e]));
+          _pred->set(w,e);
+          break;
+        case Heap::IN_HEAP:
+          {
+            Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
+            if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
+              _heap->decrease(w, newvalue);
+              _pred->set(w,e);
+            }
+          }
+          break;
+        case Heap::POST_HEAP:
+          break;
+        }
       }
       return v;
@@ -656 +656 @@
 
     ///Next node to be processed.
-    
+
     ///Next node to be processed.
     ///
@@ -662 +662 @@
     /// is empty.
     Node nextNode()
-    { 
+    {
       return !_heap->empty()?_heap->top():INVALID;
     }
- 
+
     ///\brief Returns \c false if there are nodes
     ///to be processed in the priority heap
@@ -677 +677 @@
     ///
     int queueSize() { return _heap->size(); }
-    
+
     ///Executes the algorithm.
 
@@ -696 +696 @@
       while ( !_heap->empty() ) processNextNode();
     }
-    
+
     ///Executes the algorithm until \c dest is reached.
 
@@ -716 +716 @@
       if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
     }
-    
+
     ///Executes the algorithm until a condition is met.
 
@@ -737 +737 @@
       return _heap->top();
     }
-    
+
     ///Runs %Dijkstra algorithm from node \c s.
-    
+
     ///This method runs the %Dijkstra algorithm from a root node \c s
     ///in order to
@@ -758 +758 @@
       start();
     }
-    
+
     ///Finds the shortest path between \c s and \c t.
-    
+
     ///Finds the shortest path between \c s and \c t.
     ///
@@ -778 +778 @@
       return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t];
     }
-    
+
     ///@}
 
@@ -786 +786 @@
     ///Before the use of these functions,
     ///either run() or start() must be called.
-    
+
     ///@{
 
     ///Gives back the shortest path.
-    
+
     ///Gives back the shortest path.
     ///\pre The \c t should be reachable from the source.
-    Path path(Node t) 
+    Path path(Node t)
     {
       return Path(*G, *_pred, t);
@@ -833 +833 @@
     ///using this function.
     Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
-                                  G->source((*_pred)[v]); }
-    
+                                  G->source((*_pred)[v]); }
+
     ///Returns a reference to the NodeMap of distances.
 
@@ -840 +840 @@
     ///be called before using this function.
     const DistMap &distMap() const { return *_dist;}
- 
+
     ///Returns a reference to the shortest path tree map.
 
@@ -847 +847 @@
     ///\pre \ref run() must be called before using this function.
     const PredMap &predMap() const { return *_pred;}
- 
+
     ///Checks if a node is reachable from the root.
 
@@ -863 +863 @@
     ///
     bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
-    
+
     ///@}
   };
@@ -870 +870 @@
 
 
- 
+
   ///Default traits class of Dijkstra function.
 
@@ -879 +879 @@
   struct DijkstraWizardDefaultTraits
   {
-    ///The digraph type the algorithm runs on. 
+    ///The digraph type the algorithm runs on.
     typedef GR Digraph;
     ///The type of the map that stores the arc lengths.
@@ -902 +902 @@
     ///Instantiates a HeapCrossRef.
 
-    ///This function instantiates a \ref HeapCrossRef. 
-    /// \param G is the digraph, to which we would like to define the 
+    ///This function instantiates a \ref HeapCrossRef.
+    /// \param G is the digraph, to which we would like to define the
     /// HeapCrossRef.
     /// \todo The digraph alone may be insufficient for the initialization
-    static HeapCrossRef *createHeapCrossRef(const GR &G) 
+    static HeapCrossRef *createHeapCrossRef(const GR &G)
     {
       return new HeapCrossRef(G);
     }
-    
+
     ///The heap type used by Dijkstra algorithm.
 
@@ -918 +918 @@
     ///\sa Dijkstra
     typedef BinHeap<typename LM::Value, typename GR::template NodeMap<int>,
-                    std::less<Value> > Heap;
-
-    static Heap *createHeap(HeapCrossRef& R) 
+                    std::less<Value> > Heap;
+
+    static Heap *createHeap(HeapCrossRef& R)
     {
       return new Heap(R);
@@ -927 +927 @@
     ///\brief The type of the map that stores the last
     ///arcs of the shortest paths.
-    /// 
+    ///
     ///The type of the map that stores the last
     ///arcs of the shortest paths.
@@ -934 +934 @@
     typedef NullMap <typename GR::Node,typename GR::Arc> PredMap;
     ///Instantiates a PredMap.
- 
-    ///This function instantiates a \ref PredMap. 
+
+    ///This function instantiates a \ref PredMap.
     ///\param g is the digraph, to which we would like to define the PredMap.
     ///\todo The digraph alone may be insufficient for the initialization
 #ifdef DOXYGEN
-    static PredMap *createPredMap(const GR &g) 
+    static PredMap *createPredMap(const GR &g)
 #else
-    static PredMap *createPredMap(const GR &) 
+    static PredMap *createPredMap(const GR &)
 #endif
     {
@@ -947 +947 @@
     }
     ///The type of the map that stores whether a nodes is processed.
- 
+
     ///The type of the map that stores whether a nodes is processed.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
@@ -956 +956 @@
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     ///Instantiates a ProcessedMap.
- 
-    ///This function instantiates a \ref ProcessedMap. 
+
+    ///This function instantiates a \ref ProcessedMap.
     ///\param g is the digraph, to which
     ///we would like to define the \ref ProcessedMap
@@ -969 +969 @@
     }
     ///The type of the map that stores the dists of the nodes.
- 
+
     ///The type of the map that stores the dists of the nodes.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
@@ -975 +975 @@
     typedef NullMap<typename Digraph::Node,typename LM::Value> DistMap;
     ///Instantiates a DistMap.
- 
-    ///This function instantiates a \ref DistMap. 
+
+    ///This function instantiates a \ref DistMap.
     ///\param g is the digraph, to which we would like to define the \ref DistMap
 #ifdef DOXYGEN
@@ -987 +987 @@
     }
   };
-  
+
   /// Default traits used by \ref DijkstraWizard
 
@@ -1019 +1019 @@
     public:
     /// Constructor.
-    
+
     /// This constructor does not require parameters, therefore it initiates
     /// all of the attributes to default values (0, INVALID).
     DijkstraWizardBase() : _g(0), _length(0), _pred(0),
-                           _dist(0), _source(INVALID) {}
+                           _dist(0), _source(INVALID) {}
 
     /// Constructor.
-    
+
     /// This constructor requires some parameters,
     /// listed in the parameters list.
@@ -1034 +1034 @@
     /// \param s is the initial value of  \ref _source
     DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
-      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), 
-      _length(reinterpret_cast<void*>(const_cast<LM*>(&l))), 
+      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
+      _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
       _pred(0), _dist(0), _source(s) {}
 
   };
-  
+
   /// A class to make the usage of Dijkstra algorithm easier
 
@@ -1057 +1057 @@
   ///
   /// It does not have own \ref run method. When its \ref run method is called
-  /// it initiates a plain \ref Dijkstra class, and calls the \ref 
+  /// it initiates a plain \ref Dijkstra class, and calls the \ref
   /// Dijkstra::run method of it.
   template<class TR>
@@ -1074 +1074 @@
     //\e
     typedef typename Digraph::OutArcIt OutArcIt;
-    
+
     ///The type of the map that stores the arc lengths.
     typedef typename TR::LengthMap LengthMap;
@@ -1103 +1103 @@
 
     ///Runs Dijkstra algorithm from a given node.
-    
+
     ///Runs Dijkstra algorithm from a given node.
     ///The node can be given by the \ref source function.
@@ -1109 +1109 @@
     {
       if(Base::_source==INVALID) throw UninitializedParameter();
-      Dijkstra<Digraph,LengthMap,TR> 
-        dij(*reinterpret_cast<const Digraph*>(Base::_g),
+      Dijkstra<Digraph,LengthMap,TR>
+        dij(*reinterpret_cast<const Digraph*>(Base::_g),
             *reinterpret_cast<const LengthMap*>(Base::_length));
       if(Base::_pred) dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
@@ -1133 +1133 @@
       DefPredMapBase(const TR &b) : TR(b) {}
     };
-    
+
     ///\brief \ref named-templ-param "Named parameter"
     ///function for setting PredMap type
@@ -1141 +1141 @@
     ///
     template<class T>
-    DijkstraWizard<DefPredMapBase<T> > predMap(const T &t) 
+    DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
     {
       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
       return DijkstraWizard<DefPredMapBase<T> >(*this);
     }
-    
+
     template<class T>
     struct DefDistMapBase : public Base {
@@ -1153 +1153 @@
       DefDistMapBase(const TR &b) : TR(b) {}
     };
-    
+
     ///\brief \ref named-templ-param "Named parameter"
     ///function for setting DistMap type
@@ -1161 +1161 @@
     ///
     template<class T>
-    DijkstraWizard<DefDistMapBase<T> > distMap(const T &t) 
+    DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
     {
       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
       return DijkstraWizard<DefDistMapBase<T> >(*this);
     }
-    
+
     /// Sets the source node, from which the Dijkstra algorithm runs.
 
     /// Sets the source node, from which the Dijkstra algorithm runs.
     /// \param s is the source node.
-    DijkstraWizard<TR> &source(Node s) 
+    DijkstraWizard<TR> &source(Node s)
     {
       Base::_source=s;
       return *this;
     }
-    
+
   };
-  
+
   ///Function type interface for Dijkstra algorithm.