# Changeset 694:2d87cefb35b2 in lemon-0.x for src/hugo/dijkstra.h

Ignore:
Timestamp:
07/06/04 12:07:48 (17 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@944
Message:

I moved run() into the body of class Dijkstra, because Doxygen handles
external member function definitions very poorly.

File:
1 edited

Unmodified
Removed
• ## src/hugo/dijkstra.h

 r693 ///Initialize maps ///\todo Error if \c G or are \c NULL. What about \c length ///\todo Error if \c G or are \c NULL. What about \c length? ///\todo Better memory allocation (instead of new). void init_maps() } void run(Node s); ///The distance of a node from the root. ///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 root the return value ///of this funcion is undefined. ValueType dist(Node v) const { return (*distance)[v]; } ///Returns the 'previous edge' of the shortest path tree. ///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 \ref 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 'previous node' of the shortest path tree. ///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. ///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 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 root. ///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]); } }; // ********************************************************************** //  IMPLEMENTATIONS // ********************************************************************** ///Runs %Dijkstra algorithm from node the root. ///Runs %Dijkstra algorithm from node \c s. ///This method runs the %Dijkstra algorithm from a root node \c s ///- The shortest path tree. ///- The distance of each node from the root. template class Heap > void Dijkstra::run(Node s) { init_maps(); for ( NodeIt u(*G) ; G->valid(u) ; G->next(u) ) { predecessor->set(u,INVALID); pred_node->set(u,INVALID); } typename GR::template NodeMap heap_map(*G,-1); typedef Heap, void run(Node s) { init_maps(); for ( NodeIt u(*G) ; G->valid(u) ; G->next(u) ) { predecessor->set(u,INVALID); pred_node->set(u,INVALID); } typename GR::template NodeMap heap_map(*G,-1); typedef Heap, std::less > HeapType; HeapType heap(heap_map); heap.push(s,0); HeapType heap(heap_map); heap.push(s,0); while ( !heap.empty() ) { distance->set(v, oldvalue); for(OutEdgeIt e(*G,v); G->valid(e); G->next(e)) { Node w=G->bNode(e); } } } } ///The distance of a node from the root. ///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 root the return value ///of this funcion is undefined. ValueType dist(Node v) const { return (*distance)[v]; } ///Returns the 'previous edge' of the shortest path tree. ///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 \ref 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 'previous node' of the shortest path tree. ///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. ///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 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 root. ///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]); } }; // ********************************************************************** //  IMPLEMENTATIONS // ********************************************************************** /// @}
Note: See TracChangeset for help on using the changeset viewer.