src/hugo/dijkstra.h
changeset 638 2153dd45937a
parent 570 eec0a62979c9
child 688 bdc429a557f2
equal deleted inserted replaced
2:cd349f9b4084 3:af710a7f2b42
    23   ///
    23   ///
    24   ///The type of the length is determined by the \c ValueType of the length map.
    24   ///The type of the length is determined by the \c ValueType of the length map.
    25   ///
    25   ///
    26   ///It is also possible to change the underlying priority heap.
    26   ///It is also possible to change the underlying priority heap.
    27   ///
    27   ///
    28   ///\param Graph The graph type the algorithm runs on.
    28   ///\param GR The graph type the algorithm runs on.
    29   ///\param LengthMap This read-only
    29   ///\param LM This read-only
    30   ///EdgeMap
    30   ///EdgeMap
    31   ///determines the
    31   ///determines the
    32   ///lengths of the edges. It is read once for each edge, so the map
    32   ///lengths of the edges. It is read once for each edge, so the map
    33   ///may involve in relatively time consuming process to compute the edge
    33   ///may involve in relatively time consuming process to compute the edge
    34   ///length if it is necessary. The default map type is
    34   ///length if it is necessary. The default map type is
    36   ///\param Heap The heap type used by the %Dijkstra
    36   ///\param Heap The heap type used by the %Dijkstra
    37   ///algorithm. The default
    37   ///algorithm. The default
    38   ///is using \ref BinHeap "binary heap".
    38   ///is using \ref BinHeap "binary heap".
    39   ///
    39   ///
    40   ///\author Jacint Szabo
    40   ///\author Jacint Szabo
    41   ///\todo We need a LengthMap typedef
    41   ///\todo We need a typedef-names should be standardized.
       
    42 
    42 #ifdef DOXYGEN
    43 #ifdef DOXYGEN
    43   template <typename Graph,
    44   template <typename GR,
    44 	    typename LengthMap,
    45 	    typename LM,
    45 	    typename Heap>
    46 	    typename Heap>
    46 #else
    47 #else
    47   template <typename Graph,
    48   template <typename GR,
    48 	    typename LengthMap=typename Graph::template EdgeMap<int>,
    49 	    typename LM=typename GR::template EdgeMap<int>,
    49 	    template <class,class,class,class> class Heap = BinHeap >
    50 	    template <class,class,class,class> class Heap = BinHeap >
    50 #endif
    51 #endif
    51   class Dijkstra{
    52   class Dijkstra{
    52   public:
    53   public:
       
    54     ///The type of the underlying graph.
       
    55     typedef GR Graph;
    53     typedef typename Graph::Node Node;
    56     typedef typename Graph::Node Node;
    54     typedef typename Graph::NodeIt NodeIt;
    57     typedef typename Graph::NodeIt NodeIt;
    55     typedef typename Graph::Edge Edge;
    58     typedef typename Graph::Edge Edge;
    56     typedef typename Graph::OutEdgeIt OutEdgeIt;
    59     typedef typename Graph::OutEdgeIt OutEdgeIt;
    57     
    60     
    58     typedef typename LengthMap::ValueType ValueType;
    61     ///The type of the length of the edges.
       
    62     typedef typename LM::ValueType ValueType;
       
    63     ///The the type of the map that stores the edge lengths.
       
    64     typedef LM LengthMap;
       
    65     ///\brief The the type of the map that stores the last
       
    66     ///edges of the shortest paths.
    59     typedef typename Graph::template NodeMap<Edge> PredMap;
    67     typedef typename Graph::template NodeMap<Edge> PredMap;
       
    68     ///\brief The the type of the map that stores the last but one
       
    69     ///nodes of the shortest paths.
    60     typedef typename Graph::template NodeMap<Node> PredNodeMap;
    70     typedef typename Graph::template NodeMap<Node> PredNodeMap;
       
    71     ///The the type of the map that stores the dists of the nodes.
    61     typedef typename Graph::template NodeMap<ValueType> DistMap;
    72     typedef typename Graph::template NodeMap<ValueType> DistMap;
    62 
    73 
    63   private:
    74   private:
    64     const Graph& G;
    75     const Graph& G;
    65     const LengthMap& length;
    76     const LM& length;
    66     PredMap predecessor;
    77     PredMap predecessor;
    67     PredNodeMap pred_node;
    78     PredNodeMap pred_node;
    68     DistMap distance;
    79     DistMap distance;
    69     
    80     
    70   public :
    81   public :
    71     
    82     
    72     Dijkstra(const Graph& _G, const LengthMap& _length) :
    83     Dijkstra(const Graph& _G, const LM& _length) :
    73       G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { }
    84       G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { }
    74     
    85     
    75     void run(Node s);
    86     void run(Node s);
    76     
    87     
    77     ///The distance of a node from the root.
    88     ///The distance of a node from the root.
    80     ///\pre \ref run() must be called before using this function.
    91     ///\pre \ref run() must be called before using this function.
    81     ///\warning If node \c v in unreachable from the root the return value
    92     ///\warning If node \c v in unreachable from the root the return value
    82     ///of this funcion is undefined.
    93     ///of this funcion is undefined.
    83     ValueType dist(Node v) const { return distance[v]; }
    94     ValueType dist(Node v) const { return distance[v]; }
    84 
    95 
    85     ///Returns the previous edge of the shortest path tree.
    96     ///Returns the 'previous edge' of the shortest path tree.
    86 
    97 
    87     ///For a node \c v it returns the previous edge of the shortest path tree,
    98     ///For a node \c v it returns the 'previous edge' of the shortest path tree,
    88     ///i.e. it returns the last edge from a shortest path from the root to \c
    99     ///i.e. it returns the last edge from a shortest path from the root to \c
    89     ///v. It is INVALID if \c v is unreachable from the root or if \c v=s. The
   100     ///v. It is INVALID if \c v is unreachable from the root or if \c v=s. The
    90     ///shortest path tree used here is equal to the shortest path tree used in
   101     ///shortest path tree used here is equal to the shortest path tree used in
    91     ///\ref predNode(Node v).  \pre \ref run() must be called before using
   102     ///\ref predNode(Node v).  \pre \ref run() must be called before using
    92     ///this function.
   103     ///this function.
    93     Edge pred(Node v) const { return predecessor[v]; }
   104     Edge pred(Node v) const { return predecessor[v]; }
    94 
   105 
    95     ///Returns the previous node of the shortest path tree.
   106     ///Returns the 'previous node' of the shortest path tree.
    96 
   107 
    97     ///For a node \c v it returns the previous node of the shortest path tree,
   108     ///For a node \c v it returns the 'previous node' of the shortest path tree,
    98     ///i.e. it returns the last but one node from a shortest path from the
   109     ///i.e. it returns the last but one node from a shortest path from the
    99     ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
   110     ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
   100     ///\c v=s. The shortest path tree used here is equal to the shortest path
   111     ///\c v=s. The shortest path tree used here is equal to the shortest path
   101     ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
   112     ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
   102     ///using this function.
   113     ///using this function.
   144   ///in order to
   155   ///in order to
   145   ///compute the
   156   ///compute the
   146   ///shortest path to each node. The algorithm computes
   157   ///shortest path to each node. The algorithm computes
   147   ///- The shortest path tree.
   158   ///- The shortest path tree.
   148   ///- The distance of each node from the root.
   159   ///- The distance of each node from the root.
   149   template <typename Graph, typename LengthMap,
   160   template <typename GR, typename LM,
   150 	    template<class,class,class,class> class Heap >
   161 	    template<class,class,class,class> class Heap >
   151   void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
   162   void Dijkstra<GR,LM,Heap>::run(Node s) {
   152     
   163     
   153     NodeIt u;
   164     NodeIt u;
   154     for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
   165     for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
   155       predecessor.set(u,INVALID);
   166       predecessor.set(u,INVALID);
   156       pred_node.set(u,INVALID);
   167       pred_node.set(u,INVALID);
   157     }
   168     }
   158     
   169     
   159     typename Graph::template NodeMap<int> heap_map(G,-1);
   170     typename GR::template NodeMap<int> heap_map(G,-1);
   160     
   171     
   161     typedef Heap<Node, ValueType, typename Graph::template NodeMap<int>,
   172     typedef Heap<Node, ValueType, typename GR::template NodeMap<int>,
   162       std::less<ValueType> > 
   173       std::less<ValueType> > 
   163       HeapType;
   174       HeapType;
   164     
   175     
   165     HeapType heap(heap_map);
   176     HeapType heap(heap_map);
   166     
   177