# HG changeset patch # User alpar # Date 1079881191 0 # Node ID 5bc1c83257f83ad14091a7063f724aa332a5e633 # Parent 02948c4c68e1e4ce300f8b242d9b7113f8aed8f6 Some doc added diff -r 02948c4c68e1 -r 5bc1c83257f8 src/work/alpar/dijkstra/bin_heap.hh --- a/src/work/alpar/dijkstra/bin_heap.hh Sun Mar 21 14:58:48 2004 +0000 +++ b/src/work/alpar/dijkstra/bin_heap.hh Sun Mar 21 14:59:51 2004 +0000 @@ -65,6 +65,7 @@ namespace hugo { + /// A Binary Heap implementation. template > class BinHeap { diff -r 02948c4c68e1 -r 5bc1c83257f8 src/work/alpar/dijkstra/dijkstra.h --- a/src/work/alpar/dijkstra/dijkstra.h Sun Mar 21 14:58:48 2004 +0000 +++ b/src/work/alpar/dijkstra/dijkstra.h Sun Mar 21 14:59:51 2004 +0000 @@ -32,14 +32,37 @@ namespace hugo { //Alpar: Changed the order of the parameters + + ///Dijkstra algorithm class. + + ///This class provides an efficient implementation of Dijkstra algorithm. + ///The edge lengths are passed to the algorithm using a + ///\ref ReadMapSkeleton "readable map", + ///so it is easy to change it to any kind of length. + /// + ///The type of the length is determined by the \c ValueType of the length map. + /// + ///It is also posible to change the underlying priority heap. + /// + ///\param Graph The graph type the algorithm runs on. + ///\param LengthMap This read-only EdgeMap determines the + ///lengths of the edges. It is read once for each edge, so the map + ///may involve in relatively time consuming process to compute the edge + ///length if it is necessary. + ///\param Heap The heap type used by the Dijkstra + ///algorithm. The default + ///is using \ref BinHeap "binary heap". template , - typename Heap=FibHeap > > class Dijkstra{ public: typedef typename LengthMap::ValueType ValueType; + typedef typename Graph::NodeMap PredMap; + typedef typename Graph::NodeMap PredNodeMap; + typedef typename Graph::NodeMap DistMap; private: typedef typename Graph::Node Node; @@ -49,12 +72,9 @@ const Graph& G; const LengthMap& length; - typedef typename Graph::NodeMap PredMap; PredMap predecessor; //In place of reach: - typedef typename Graph::NodeMap PredNodeMap; PredNodeMap pred_node; - typedef typename Graph::NodeMap DistMap; DistMap distance; //I don't like this: // //FIXME: @@ -72,30 +92,76 @@ void run(Node s); + ///The distance of a node from the source. + + ///Returns the distance of a node from the source. + ///\pre \ref run() must be called before using this function. + ///\warning If node \c v in unreachable from \c s the return value + ///of this funcion is undefined. ValueType dist(Node v) const { return distance[v]; } + ///Returns the edges of the shortest path tree. + + ///For a node \c v it returns the last edge of the shortest path + ///from \c s to \c v or INVALID if \c v is unreachable from \c s. + ///\pre \ref run() must be called before using this function. Edge pred(Node v) const { return predecessor[v]; } + ///Returns the nodes of the shortest paths. + + ///For a node \c v it returns the last but one node of the shortest path + ///from \c s to \c v or INVALID if \c v is unreachable from \c s. + ///\pre \ref run() must be called before using this function. Node predNode(Node v) const { return pred_node[v]; } + ///Returns a reference to the NodeMap of distances. + + ///\pre \ref run() must be called before using this function. + /// const DistMap &distMap() const { return distance;} + ///Returns a reference to the shortest path tree map. + + ///Returns a reference to the NodeMap of the edges of the + ///shortest path tree. + ///\pre \ref run() must be called before using this function. const PredMap &predMap() const { return predecessor;} + ///Returns a reference to the map of nodes of shortest paths. + + ///Returns a reference to the NodeMap of the last but one nodes of the + ///shortest paths. + ///\pre \ref run() must be called before using this function. const PredNodeMap &predNodeMap() const { return pred_node;} // bool reached(Node v) { return reach[v]; } - ///\warning \c s is not reached! + + ///Chech if a node is reachable from \c s. + + ///Returns \c true if \c v is reachable from \c s. + ///\warning \c s is reported to be unreached! + ///\todo Is this what we want? + ///\pre \ref run() must be called before using this function. /// bool reached(Node v) { return G.valid(predecessor[v]); } }; - // IMPLEMENTATIONS + // ********************************************************************** + // IMPLEMENTATIONS + // ********************************************************************** + ///Runs Dijkstra algorithm from node \c s. + + ///This method runs the Dijkstra algorithm from node \c s in order to + ///compute the + ///shortest path to each node. The algorithm computes + ///- The shortest path tree. + ///- The distance of each node. template void Dijkstra::run(Node s) { NodeIt u; for ( G.first(u) ; G.valid(u) ; G.next(u) ) { predecessor.set(u,INVALID); + pred_node.set(u,INVALID); // If a node is unreacheable, then why should be the dist=0? // distance.set(u,0); // reach.set(u,false); diff -r 02948c4c68e1 -r 5bc1c83257f8 src/work/alpar/dijkstra/fib_heap.h --- a/src/work/alpar/dijkstra/fib_heap.h Sun Mar 21 14:58:48 2004 +0000 +++ b/src/work/alpar/dijkstra/fib_heap.h Sun Mar 21 14:59:51 2004 +0000 @@ -57,11 +57,11 @@ namespace hugo { + /// A Fibonacci Heap implementation. template > - + typename Compare = std::less > class FibHeap { - + typedef Prio PrioType; class store;