src/work/alpar/dijkstra/dijkstra.h
changeset 240 4a1d2e642552
parent 228 1d5f4cd0342c
child 242 b255f25ad394
equal deleted inserted replaced
2:6c1f93fbabb2 3:4d939553c0a1
    32 
    32 
    33 namespace hugo {
    33 namespace hugo {
    34   
    34   
    35   //Alpar: Changed the order of the parameters
    35   //Alpar: Changed the order of the parameters
    36   
    36   
    37   ///Dijkstra algorithm class.
    37   ///%Dijkstra algorithm class.
    38 
    38 
    39   ///This class provides an efficient implementation of Dijkstra algorithm.
    39   ///This class provides an efficient implementation of %Dijkstra algorithm.
    40   ///The edge lengths are passed to the algorithm using a
    40   ///The edge lengths are passed to the algorithm using a
    41   ///\ref ReadMapSkeleton "readable map",
    41   ///\ref ReadMapSkeleton "readable map",
    42   ///so it is easy to change it to any kind of length.
    42   ///so it is easy to change it to any kind of length.
    43   ///
    43   ///
    44   ///The type of the length is determined by the \c ValueType of the length map.
    44   ///The type of the length is determined by the \c ValueType of the length map.
    48   ///\param Graph The graph type the algorithm runs on.
    48   ///\param Graph The graph type the algorithm runs on.
    49   ///\param LengthMap This read-only EdgeMap determines the
    49   ///\param LengthMap This read-only EdgeMap determines the
    50   ///lengths of the edges. It is read once for each edge, so the map
    50   ///lengths of the edges. It is read once for each edge, so the map
    51   ///may involve in relatively time consuming process to compute the edge
    51   ///may involve in relatively time consuming process to compute the edge
    52   ///length if it is necessary.
    52   ///length if it is necessary.
    53   ///\param Heap The heap type used by the Dijkstra
    53   ///\param Heap The heap type used by the %Dijkstra
    54   ///algorithm. The default
    54   ///algorithm. The default
    55   ///is using \ref BinHeap "binary heap".
    55   ///is using \ref BinHeap "binary heap".
    56   template <typename Graph,
    56   template <typename Graph,
    57 	    typename LengthMap=typename Graph::EdgeMap<int>,
    57 	    typename LengthMap=typename Graph::EdgeMap<int>,
    58 	    typename Heap=BinHeap <typename Graph::Node,
    58 	    typename Heap=BinHeap <typename Graph::Node,
    95     
    95     
    96     ///The distance of a node from the source.
    96     ///The distance of a node from the source.
    97 
    97 
    98     ///Returns the distance of a node from the source.
    98     ///Returns the distance of a node from the source.
    99     ///\pre \ref run() must be called before using this function.
    99     ///\pre \ref run() must be called before using this function.
   100     ///\warning If node \c v in unreachable from \c s the return value
   100     ///\warning If node \c v in unreachable from the source the return value
   101     ///of this funcion is undefined.
   101     ///of this funcion is undefined.
   102     ValueType dist(Node v) const { return distance[v]; }
   102     ValueType dist(Node v) const { return distance[v]; }
   103     ///Returns the edges of the shortest path tree.
   103     ///Returns the edges of the shortest path tree.
   104 
   104 
   105     ///For a node \c v it returns the last edge of the shortest path
   105     ///For a node \c v it returns the last edge of the shortest path
   106     ///from \c s to \c v or INVALID if \c v is unreachable from \c s.
   106     ///from the source to \c v or INVALID if \c v is unreachable
       
   107     ///from the source.
   107     ///\pre \ref run() must be called before using this function.
   108     ///\pre \ref run() must be called before using this function.
   108     Edge pred(Node v) const { return predecessor[v]; }
   109     Edge pred(Node v) const { return predecessor[v]; }
   109     ///Returns the nodes of the shortest paths.
   110     ///Returns the nodes of the shortest paths.
   110 
   111 
   111     ///For a node \c v it returns the last but one node of the shortest path
   112     ///For a node \c v it returns the last but one node of the shortest path
   112     ///from \c s to \c v or INVALID if \c v is unreachable from \c s.
   113     ///from the source to \c v or INVALID if \c v is unreachable
       
   114     ///from the source.
   113     ///\pre \ref run() must be called before using this function.
   115     ///\pre \ref run() must be called before using this function.
   114     Node predNode(Node v) const { return pred_node[v]; }
   116     Node predNode(Node v) const { return pred_node[v]; }
   115     
   117     
   116     ///Returns a reference to the NodeMap of distances.
   118     ///Returns a reference to the NodeMap of distances.
   117 
   119 
   131     ///\pre \ref run() must be called before using this function.
   133     ///\pre \ref run() must be called before using this function.
   132     const PredNodeMap &predNodeMap() const { return pred_node;}
   134     const PredNodeMap &predNodeMap() const { return pred_node;}
   133 
   135 
   134     //    bool reached(Node v) { return reach[v]; }
   136     //    bool reached(Node v) { return reach[v]; }
   135 
   137 
   136     ///Chech if a node is reachable from \c s.
   138     ///Chechs if a node is reachable from the source.
   137 
   139 
   138     ///Returns \c true if \c v is reachable from \c s.
   140     ///Returns \c true if \c v is reachable from the source.
   139     ///\warning \c s is reported to be unreached!
   141     ///\warning the source node is reported to be unreached!
   140     ///\todo Is this what we want?
   142     ///\todo Is this what we want?
   141     ///\pre \ref run() must be called before using this function.
   143     ///\pre \ref run() must be called before using this function.
   142     ///
   144     ///
   143     bool reached(Node v) { return G.valid(predecessor[v]); }
   145     bool reached(Node v) { return G.valid(predecessor[v]); }
   144     
   146     
   147 
   149 
   148   // **********************************************************************
   150   // **********************************************************************
   149   //  IMPLEMENTATIONS
   151   //  IMPLEMENTATIONS
   150   // **********************************************************************
   152   // **********************************************************************
   151 
   153 
   152   ///Runs Dijkstra algorithm from node \c s.
   154   ///Runs %Dijkstra algorithm from node the source.
   153 
   155 
   154   ///This method runs the Dijkstra algorithm from node \c s in order to
   156   ///This method runs the %Dijkstra algorithm from a source node \c s
       
   157   ///in order to
   155   ///compute the
   158   ///compute the
   156   ///shortest path to each node. The algorithm computes
   159   ///shortest path to each node. The algorithm computes
   157   ///- The shortest path tree.
   160   ///- The shortest path tree.
   158   ///- The distance of each node.
   161   ///- The distance of each node from the source.
   159   template <typename Graph, typename LengthMap, typename Heap >
   162   template <typename Graph, typename LengthMap, typename Heap >
   160   void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
   163   void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
   161     
   164     
   162     NodeIt u;
   165     NodeIt u;
   163     for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
   166     for ( G.first(u) ; G.valid(u) ; G.next(u) ) {