Changeset 385:d7ebbae96025 in lemon-0.x for src

Ignore:
Timestamp:
04/23/04 21:04:05 (16 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@515
Message:

Some changes in the documentation.

File:
1 edited

Unmodified
Added
Removed
• src/include/dijkstra.h

 r373 // -*- C++ -*- #ifndef HUGO_DIJKSTRA_H #define HUGO_DIJKSTRA_H ///\brief Dijkstra algorithm. #include #include #include namespace hugo { ///%Dijkstra algorithm class. ///It is also possible 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. The default map type is \ref ///GraphSkeleton::EdgeMap "Graph::EdgeMap" ///\param Heap The heap type used by the %Dijkstra algorithm. The ///default is using \ref BinHeap "binary 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. The default map type is ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap" ///\param Heap The heap type used by the %Dijkstra ///algorithm. The default ///is using \ref BinHeap "binary heap". #ifdef DOXYGEN void run(Node s); ///The distance of a node from the source. ///The distance of a node from the root. ///Returns the distance of a node from the source. ///Returns the distance of a node from the root. ///\pre \ref run() must be called before using this function. ///\warning If node \c v in unreachable from the source the return value ///\warning If node \c v in unreachable from the root the return value ///of this funcion is undefined. ValueType dist(Node v) const { return distance[v]; } ///Returns the edges of the shortest path tree. ///Returns the previous edge of the shortest path tree. ///For a node \c v it returns the last edge of the shortest path ///from the source to \c v or INVALID if \c v is unreachable ///from the source. ///\pre \ref run() must be called before using this function. ///For a node \c v it returns the previous edge of the shortest path tree, ///i.e. it returns the last edge from a shortest path from the root to \c ///v. It is INVALID if \c v is unreachable from the root or if \c v=s. The ///shortest path tree used here is equal to the shortest path tree used in ///\ref predNode(Node v).  \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. ///Returns the previous node of the shortest path tree. ///For a node \c v it returns the last but one node of the shortest path ///from the source to \c v or INVALID if \c v is unreachable ///from the source. ///\pre \ref run() must be called before using this function. ///For a node \c v it returns the previous node of the shortest path tree, ///i.e. it returns the last but one node from a shortest path from the ///root to \c /v. It is INVALID if \c v is unreachable from the root or if ///\c v=s. The shortest path tree used here is equal to the shortest path ///tree used in \ref pred(Node v).  \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. /// ///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. ///\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 map of nodes of shortest paths. ///Returns a reference to the NodeMap of the last but one nodes of the ///shortest paths. ///shortest path tree. ///\pre \ref run() must be called before using this function. const PredNodeMap &predNodeMap() const { return pred_node;} ///Checks if a node is reachable from the source. ///Checks if a node is reachable from the root. ///Returns \c true if \c v is reachable from the source. ///\warning the source node is reported to be unreached! ///Returns \c true if \c v is reachable from the root. ///\warning the root node 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]); } // ********************************************************************** ///Runs %Dijkstra algorithm from source node \c s. ///Runs %Dijkstra algorithm from node the root. ///This method runs the %Dijkstra algorithm from a source 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 ///from the source. ///This method runs the %Dijkstra algorithm from a root 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 from the root. template class Heap > Heap > heap(heap_map); heap.push(s,0); while ( !heap.empty() ) { Node v=heap.top(); ValueType oldvalue=heap[v]; heap.pop(); distance.set(v, oldvalue); while ( !heap.empty() ) { { //FIXME this bracket is for e to be local OutEdgeIt e; for(G.first(e, v); G.valid(e); G.next(e)) { Node v=heap.top(); ValueType oldvalue=heap[v]; heap.pop(); distance.set(v, oldvalue); { //FIXME this bracket is for e to be local OutEdgeIt e; for(G.first(e, v); G.valid(e); G.next(e)) { Node w=G.head(e); } } } //FIXME this bracket } } //FIXME tis bracket } }
Note: See TracChangeset for help on using the changeset viewer.