COIN-OR::LEMON - Graph Library

Changeset 694:2d87cefb35b2 in lemon-0.x


Ignore:
Timestamp:
07/06/04 12:07:48 (20 years ago)
Author:
Alpar Juttner
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

Legend:

Unmodified
Added
Removed
  • src/hugo/dijkstra.h

    r693 r694  
    8585    ///Initialize maps
    8686   
    87     ///\todo Error if \c G or are \c NULL. What about \c length
     87    ///\todo Error if \c G or are \c NULL. What about \c length?
    8888    ///\todo Better memory allocation (instead of new).
    8989    void init_maps()
     
    197197    }
    198198   
    199     void run(Node s);
    200    
    201     ///The distance of a node from the root.
    202 
    203     ///Returns the distance of a node from the root.
    204     ///\pre \ref run() must be called before using this function.
    205     ///\warning If node \c v in unreachable from the root the return value
    206     ///of this funcion is undefined.
    207     ValueType dist(Node v) const { return (*distance)[v]; }
    208 
    209     ///Returns the 'previous edge' of the shortest path tree.
    210 
    211     ///For a node \c v it returns the 'previous edge' of the shortest path tree,
    212     ///i.e. it returns the last edge from a shortest path from the root to \c
    213     ///v. It is \ref INVALID
    214     ///if \c v is unreachable from the root or if \c v=s. The
    215     ///shortest path tree used here is equal to the shortest path tree used in
    216     ///\ref predNode(Node v).  \pre \ref run() must be called before using
    217     ///this function.
    218     Edge pred(Node v) const { return (*predecessor)[v]; }
    219 
    220     ///Returns the 'previous node' of the shortest path tree.
    221 
    222     ///For a node \c v it returns the 'previous node' of the shortest path tree,
    223     ///i.e. it returns the last but one node from a shortest path from the
    224     ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
    225     ///\c v=s. The shortest path tree used here is equal to the shortest path
    226     ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
    227     ///using this function.
    228     Node predNode(Node v) const { return (*pred_node)[v]; }
    229    
    230     ///Returns a reference to the NodeMap of distances.
    231 
    232     ///Returns a reference to the NodeMap of distances. \pre \ref run() must
    233     ///be called before using this function.
    234     const DistMap &distMap() const { return *distance;}
    235  
    236     ///Returns a reference to the shortest path tree map.
    237 
    238     ///Returns a reference to the NodeMap of the edges of the
    239     ///shortest path tree.
    240     ///\pre \ref run() must be called before using this function.
    241     const PredMap &predMap() const { return *predecessor;}
    242  
    243     ///Returns a reference to the map of nodes of shortest paths.
    244 
    245     ///Returns a reference to the NodeMap of the last but one nodes of the
    246     ///shortest path tree.
    247     ///\pre \ref run() must be called before using this function.
    248     const PredNodeMap &predNodeMap() const { return *pred_node;}
    249 
    250     ///Checks if a node is reachable from the root.
    251 
    252     ///Returns \c true if \c v is reachable from the root.
    253     ///\warning the root node is reported to be unreached!
    254     ///\todo Is this what we want?
    255     ///\pre \ref run() must be called before using this function.
    256     ///
    257     bool reached(Node v) { return G->valid((*predecessor)[v]); }
    258    
    259   };
    260  
    261 
    262   // **********************************************************************
    263   //  IMPLEMENTATIONS
    264   // **********************************************************************
    265 
    266   ///Runs %Dijkstra algorithm from node the root.
     199  ///Runs %Dijkstra algorithm from node \c s.
    267200
    268201  ///This method runs the %Dijkstra algorithm from a root node \c s
     
    272205  ///- The shortest path tree.
    273206  ///- The distance of each node from the root.
    274   template <typename GR, typename LM,
    275             template<class,class,class,class> class Heap >
    276   void Dijkstra<GR,LM,Heap>::run(Node s) {
    277 
    278     init_maps();
    279 
    280     for ( NodeIt u(*G) ; G->valid(u) ; G->next(u) ) {
    281       predecessor->set(u,INVALID);
    282       pred_node->set(u,INVALID);
    283     }
    284    
    285     typename GR::template NodeMap<int> heap_map(*G,-1);
    286    
    287     typedef Heap<Node, ValueType, typename GR::template NodeMap<int>,
     207   
     208    void run(Node s) {
     209     
     210      init_maps();
     211     
     212      for ( NodeIt u(*G) ; G->valid(u) ; G->next(u) ) {
     213        predecessor->set(u,INVALID);
     214        pred_node->set(u,INVALID);
     215      }
     216     
     217      typename GR::template NodeMap<int> heap_map(*G,-1);
     218     
     219      typedef Heap<Node, ValueType, typename GR::template NodeMap<int>,
    288220      std::less<ValueType> >
    289221      HeapType;
    290    
    291     HeapType heap(heap_map);
    292    
    293     heap.push(s,0);
    294    
     222     
     223      HeapType heap(heap_map);
     224     
     225      heap.push(s,0);
     226     
    295227      while ( !heap.empty() ) {
    296228       
     
    300232        distance->set(v, oldvalue);
    301233       
    302          
     234       
    303235        for(OutEdgeIt e(*G,v); G->valid(e); G->next(e)) {
    304236          Node w=G->bNode(e);
     
    322254        }
    323255      }
    324   }
     256    }
     257   
     258    ///The distance of a node from the root.
     259
     260    ///Returns the distance of a node from the root.
     261    ///\pre \ref run() must be called before using this function.
     262    ///\warning If node \c v in unreachable from the root the return value
     263    ///of this funcion is undefined.
     264    ValueType dist(Node v) const { return (*distance)[v]; }
     265
     266    ///Returns the 'previous edge' of the shortest path tree.
     267
     268    ///For a node \c v it returns the 'previous edge' of the shortest path tree,
     269    ///i.e. it returns the last edge from a shortest path from the root to \c
     270    ///v. It is \ref INVALID
     271    ///if \c v is unreachable from the root or if \c v=s. The
     272    ///shortest path tree used here is equal to the shortest path tree used in
     273    ///\ref predNode(Node v).  \pre \ref run() must be called before using
     274    ///this function.
     275    Edge pred(Node v) const { return (*predecessor)[v]; }
     276
     277    ///Returns the 'previous node' of the shortest path tree.
     278
     279    ///For a node \c v it returns the 'previous node' of the shortest path tree,
     280    ///i.e. it returns the last but one node from a shortest path from the
     281    ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
     282    ///\c v=s. The shortest path tree used here is equal to the shortest path
     283    ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
     284    ///using this function.
     285    Node predNode(Node v) const { return (*pred_node)[v]; }
     286   
     287    ///Returns a reference to the NodeMap of distances.
     288
     289    ///Returns a reference to the NodeMap of distances. \pre \ref run() must
     290    ///be called before using this function.
     291    const DistMap &distMap() const { return *distance;}
     292 
     293    ///Returns a reference to the shortest path tree map.
     294
     295    ///Returns a reference to the NodeMap of the edges of the
     296    ///shortest path tree.
     297    ///\pre \ref run() must be called before using this function.
     298    const PredMap &predMap() const { return *predecessor;}
     299 
     300    ///Returns a reference to the map of nodes of shortest paths.
     301
     302    ///Returns a reference to the NodeMap of the last but one nodes of the
     303    ///shortest path tree.
     304    ///\pre \ref run() must be called before using this function.
     305    const PredNodeMap &predNodeMap() const { return *pred_node;}
     306
     307    ///Checks if a node is reachable from the root.
     308
     309    ///Returns \c true if \c v is reachable from the root.
     310    ///\warning the root node is reported to be unreached!
     311    ///\todo Is this what we want?
     312    ///\pre \ref run() must be called before using this function.
     313    ///
     314    bool reached(Node v) { return G->valid((*predecessor)[v]); }
     315   
     316  };
     317 
     318
     319  // **********************************************************************
     320  //  IMPLEMENTATIONS
     321  // **********************************************************************
    325322
    326323/// @}
Note: See TracChangeset for help on using the changeset viewer.