COIN-OR::LEMON - Graph Library

Changeset 224:5bc1c83257f8 in lemon-0.x


Ignore:
Timestamp:
03/21/04 15:59:51 (20 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@321
Message:

Some doc added

Location:
src/work/alpar/dijkstra
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • src/work/alpar/dijkstra/bin_heap.hh

    r222 r224  
    6666namespace hugo {
    6767
     68  /// A Binary Heap implementation.
    6869  template <typename Key, typename Val, typename KeyIntMap,
    6970            typename Compare = std::less<Val> >
  • src/work/alpar/dijkstra/dijkstra.h

    r222 r224  
    3333 
    3434  //Alpar: Changed the order of the parameters
     35 
     36  ///Dijkstra algorithm class.
     37
     38  ///This class provides an efficient implementation of Dijkstra algorithm.
     39  ///The edge lengths are passed to the algorithm using a
     40  ///\ref ReadMapSkeleton "readable map",
     41  ///so it is easy to change it to any kind of length.
     42  ///
     43  ///The type of the length is determined by the \c ValueType of the length map.
     44  ///
     45  ///It is also posible to change the underlying priority heap.
     46  ///
     47  ///\param Graph The graph type the algorithm runs on.
     48  ///\param LengthMap This read-only EdgeMap determines the
     49  ///lengths of the edges. It is read once for each edge, so the map
     50  ///may involve in relatively time consuming process to compute the edge
     51  ///length if it is necessary.
     52  ///\param Heap The heap type used by the Dijkstra
     53  ///algorithm. The default
     54  ///is using \ref BinHeap "binary heap".
    3555  template <typename Graph,
    3656            typename LengthMap=typename Graph::EdgeMap<int>,
    37             typename Heap=FibHeap<typename Graph::Node,
     57            typename Heap=BinHeap<typename Graph::Node,
    3858                                  typename LengthMap::ValueType,
    3959                                  typename Graph::NodeMap<int> > >
     
    4161  public:
    4262    typedef typename LengthMap::ValueType ValueType;
     63    typedef typename Graph::NodeMap<Edge> PredMap;
     64    typedef typename Graph::NodeMap<Node> PredNodeMap;
     65    typedef typename Graph::NodeMap<ValueType> DistMap;
    4366
    4467  private:
     
    5073    const Graph& G;
    5174    const LengthMap& length;
    52     typedef typename Graph::NodeMap<Edge> PredMap;
    5375    PredMap predecessor;
    5476    //In place of reach:
    55     typedef typename Graph::NodeMap<Node> PredNodeMap;
    5677    PredNodeMap pred_node;
    57     typedef typename Graph::NodeMap<ValueType> DistMap;
    5878    DistMap distance;
    5979    //I don't like this:
     
    7393    void run(Node s);
    7494   
     95    ///The distance of a node from the source.
     96
     97    ///Returns the distance of a node from the source.
     98    ///\pre \ref run() must be called before using this function.
     99    ///\warning If node \c v in unreachable from \c s the return value
     100    ///of this funcion is undefined.
    75101    ValueType dist(Node v) const { return distance[v]; }
     102    ///Returns the edges of the shortest path tree.
     103
     104    ///For a node \c v it returns the last edge of the shortest path
     105    ///from \c s to \c v or INVALID if \c v is unreachable from \c s.
     106    ///\pre \ref run() must be called before using this function.
    76107    Edge pred(Node v) const { return predecessor[v]; }
     108    ///Returns the nodes of the shortest paths.
     109
     110    ///For a node \c v it returns the last but one node of the shortest path
     111    ///from \c s to \c v or INVALID if \c v is unreachable from \c s.
     112    ///\pre \ref run() must be called before using this function.
    77113    Node predNode(Node v) const { return pred_node[v]; }
    78114   
     115    ///Returns a reference to the NodeMap of distances.
     116
     117    ///\pre \ref run() must be called before using this function.
     118    ///
    79119    const DistMap &distMap() const { return distance;}
     120    ///Returns a reference to the shortest path tree map.
     121
     122    ///Returns a reference to the NodeMap of the edges of the
     123    ///shortest path tree.
     124    ///\pre \ref run() must be called before using this function.
    80125    const PredMap &predMap() const { return predecessor;}
     126    ///Returns a reference to the map of nodes of  shortest paths.
     127
     128    ///Returns a reference to the NodeMap of the last but one nodes of the
     129    ///shortest paths.
     130    ///\pre \ref run() must be called before using this function.
    81131    const PredNodeMap &predNodeMap() const { return pred_node;}
    82132
    83133    //    bool reached(Node v) { return reach[v]; }
    84     ///\warning \c s is not reached!
     134
     135    ///Chech if a node is reachable from \c s.
     136
     137    ///Returns \c true if \c v is reachable from \c s.
     138    ///\warning \c s is reported to be unreached!
     139    ///\todo Is this what we want?
     140    ///\pre \ref run() must be called before using this function.
    85141    ///
    86142    bool reached(Node v) { return G.valid(predecessor[v]); }
     
    89145 
    90146
    91   // IMPLEMENTATIONS
    92 
     147  // **********************************************************************
     148  //  IMPLEMENTATIONS
     149  // **********************************************************************
     150
     151  ///Runs Dijkstra algorithm from node \c s.
     152
     153  ///This method runs the Dijkstra algorithm from node \c s in order to
     154  ///compute the
     155  ///shortest path to each node. The algorithm computes
     156  ///- The shortest path tree.
     157  ///- The distance of each node.
    93158  template <typename Graph, typename LengthMap, typename Heap >
    94159  void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
     
    97162    for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
    98163      predecessor.set(u,INVALID);
     164      pred_node.set(u,INVALID);
    99165      // If a node is unreacheable, then why should be the dist=0?
    100166      // distance.set(u,0);
  • src/work/alpar/dijkstra/fib_heap.h

    r222 r224  
    5858namespace hugo {
    5959 
     60  /// A Fibonacci Heap implementation.
    6061  template <typename Item, typename Prio, typename ItemIntMap,
    61     typename Compare = std::less<Prio> >
    62  
     62            typename Compare = std::less<Prio> >
    6363  class FibHeap {
    64  
     64   
    6565    typedef Prio PrioType;
    6666   
Note: See TracChangeset for help on using the changeset viewer.