1.1 --- a/src/hugo/dijkstra.h	Sat May 08 15:56:00 2004 +0000
     1.2 +++ b/src/hugo/dijkstra.h	Sat May 08 15:58:34 2004 +0000
     1.3 @@ -25,8 +25,8 @@
     1.4    ///
     1.5    ///It is also possible to change the underlying priority heap.
     1.6    ///
     1.7 -  ///\param Graph The graph type the algorithm runs on.
     1.8 -  ///\param LengthMap This read-only
     1.9 +  ///\param GR The graph type the algorithm runs on.
    1.10 +  ///\param LM This read-only
    1.11    ///EdgeMap
    1.12    ///determines the
    1.13    ///lengths of the edges. It is read once for each edge, so the map
    1.14 @@ -38,38 +38,49 @@
    1.15    ///is using \ref BinHeap "binary heap".
    1.16    ///
    1.17    ///\author Jacint Szabo
    1.18 -  ///\todo We need a LengthMap typedef
    1.19 +  ///\todo We need a typedef-names should be standardized.
    1.20 +
    1.21  #ifdef DOXYGEN
    1.22 -  template <typename Graph,
    1.23 -	    typename LengthMap,
    1.24 +  template <typename GR,
    1.25 +	    typename LM,
    1.26  	    typename Heap>
    1.27  #else
    1.28 -  template <typename Graph,
    1.29 -	    typename LengthMap=typename Graph::template EdgeMap<int>,
    1.30 +  template <typename GR,
    1.31 +	    typename LM=typename GR::template EdgeMap<int>,
    1.32  	    template <class,class,class,class> class Heap = BinHeap >
    1.33  #endif
    1.34    class Dijkstra{
    1.35    public:
    1.36 +    ///The type of the underlying graph.
    1.37 +    typedef GR Graph;
    1.38      typedef typename Graph::Node Node;
    1.39      typedef typename Graph::NodeIt NodeIt;
    1.40      typedef typename Graph::Edge Edge;
    1.41      typedef typename Graph::OutEdgeIt OutEdgeIt;
    1.42      
    1.43 -    typedef typename LengthMap::ValueType ValueType;
    1.44 +    ///The type of the length of the edges.
    1.45 +    typedef typename LM::ValueType ValueType;
    1.46 +    ///The the type of the map that stores the edge lengths.
    1.47 +    typedef LM LengthMap;
    1.48 +    ///\brief The the type of the map that stores the last
    1.49 +    ///edges of the shortest paths.
    1.50      typedef typename Graph::template NodeMap<Edge> PredMap;
    1.51 +    ///\brief The the type of the map that stores the last but one
    1.52 +    ///nodes of the shortest paths.
    1.53      typedef typename Graph::template NodeMap<Node> PredNodeMap;
    1.54 +    ///The the type of the map that stores the dists of the nodes.
    1.55      typedef typename Graph::template NodeMap<ValueType> DistMap;
    1.56  
    1.57    private:
    1.58      const Graph& G;
    1.59 -    const LengthMap& length;
    1.60 +    const LM& length;
    1.61      PredMap predecessor;
    1.62      PredNodeMap pred_node;
    1.63      DistMap distance;
    1.64      
    1.65    public :
    1.66      
    1.67 -    Dijkstra(const Graph& _G, const LengthMap& _length) :
    1.68 +    Dijkstra(const Graph& _G, const LM& _length) :
    1.69        G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { }
    1.70      
    1.71      void run(Node s);
    1.72 @@ -82,9 +93,9 @@
    1.73      ///of this funcion is undefined.
    1.74      ValueType dist(Node v) const { return distance[v]; }
    1.75  
    1.76 -    ///Returns the previous edge of the shortest path tree.
    1.77 +    ///Returns the 'previous edge' of the shortest path tree.
    1.78  
    1.79 -    ///For a node \c v it returns the previous edge of the shortest path tree,
    1.80 +    ///For a node \c v it returns the 'previous edge' of the shortest path tree,
    1.81      ///i.e. it returns the last edge from a shortest path from the root to \c
    1.82      ///v. It is INVALID if \c v is unreachable from the root or if \c v=s. The
    1.83      ///shortest path tree used here is equal to the shortest path tree used in
    1.84 @@ -92,9 +103,9 @@
    1.85      ///this function.
    1.86      Edge pred(Node v) const { return predecessor[v]; }
    1.87  
    1.88 -    ///Returns the previous node of the shortest path tree.
    1.89 +    ///Returns the 'previous node' of the shortest path tree.
    1.90  
    1.91 -    ///For a node \c v it returns the previous node of the shortest path tree,
    1.92 +    ///For a node \c v it returns the 'previous node' of the shortest path tree,
    1.93      ///i.e. it returns the last but one node from a shortest path from the
    1.94      ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
    1.95      ///\c v=s. The shortest path tree used here is equal to the shortest path
    1.96 @@ -146,9 +157,9 @@
    1.97    ///shortest path to each node. The algorithm computes
    1.98    ///- The shortest path tree.
    1.99    ///- The distance of each node from the root.
   1.100 -  template <typename Graph, typename LengthMap,
   1.101 +  template <typename GR, typename LM,
   1.102  	    template<class,class,class,class> class Heap >
   1.103 -  void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
   1.104 +  void Dijkstra<GR,LM,Heap>::run(Node s) {
   1.105      
   1.106      NodeIt u;
   1.107      for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
   1.108 @@ -156,9 +167,9 @@
   1.109        pred_node.set(u,INVALID);
   1.110      }
   1.111      
   1.112 -    typename Graph::template NodeMap<int> heap_map(G,-1);
   1.113 +    typename GR::template NodeMap<int> heap_map(G,-1);
   1.114      
   1.115 -    typedef Heap<Node, ValueType, typename Graph::template NodeMap<int>,
   1.116 +    typedef Heap<Node, ValueType, typename GR::template NodeMap<int>,
   1.117        std::less<ValueType> > 
   1.118        HeapType;
   1.119