COIN-OR::LEMON - Graph Library

Changeset 373:259ea2d741a2 in lemon-0.x for src/include/dijkstra.h


Ignore:
Timestamp:
04/22/04 16:50:24 (17 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@503
Message:

Changes in the documentation.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/include/dijkstra.h

    r335 r373  
    11// -*- C++ -*-
    2 
    3 /*
    4  *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
    5  *
    6  *Constructor:
    7  *
    8  *Dijkstra(Graph G, LengthMap length)
    9  *
    10  *
    11  *Methods:
    12  *
    13  *void run(Node s)
    14  *
    15  *T dist(Node v) : After run(s) was run, it returns the distance from s to v.
    16  *   Returns T() if v is not reachable from s.
    17  *
    18  *Edge pred(Node v) : After run(s) was run, it returns the last
    19  *   edge of a shortest s-v path. It is INVALID for s and for
    20  *   the nodes not reachable from s.
    21  *
    22  *bool reached(Node v) : After run(s) was run, it is true iff v is
    23  *   reachable from s
    24  *
    25  */
    262
    273#ifndef HUGO_DIJKSTRA_H
     
    3713namespace hugo {
    3814 
    39   //Alpar: Changed the order of the parameters
    40  
    4115  ///%Dijkstra algorithm class.
    4216
     
    5024  ///It is also possible to change the underlying priority heap.
    5125  ///
    52   ///\param Graph The graph type the algorithm runs on.
    53   ///\param LengthMap This read-only
    54   ///EdgeMap
    55   ///determines the
    56   ///lengths of the edges. It is read once for each edge, so the map
    57   ///may involve in relatively time consuming process to compute the edge
    58   ///length if it is necessary. The default map type is
    59   ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
    60   ///\param Heap The heap type used by the %Dijkstra
    61   ///algorithm. The default
    62   ///is using \ref BinHeap "binary heap".
     26  ///\param Graph The graph type the algorithm runs on. 
     27  ///\param LengthMap This read-only EdgeMap determines the lengths of
     28  ///the edges. It is read once for each edge, so the map may involve
     29  ///in relatively time consuming process to compute the edge length
     30  ///if it is necessary. The default map type is \ref
     31  ///GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
     32  ///\param Heap The heap type used by the %Dijkstra algorithm. The
     33  ///default is using \ref BinHeap "binary heap".
    6334 
    6435#ifdef DOXYGEN
     
    10475    ///of this funcion is undefined.
    10576    ValueType dist(Node v) const { return distance[v]; }
     77
    10678    ///Returns the edges of the shortest path tree.
    10779
     
    11183    ///\pre \ref run() must be called before using this function.
    11284    Edge pred(Node v) const { return predecessor[v]; }
     85
    11386    ///Returns the nodes of the shortest paths.
    11487
     
    12497    ///
    12598    const DistMap &distMap() const { return distance;}
     99   
    126100    ///Returns a reference to the shortest path tree map.
    127101
     
    130104    ///\pre \ref run() must be called before using this function.
    131105    const PredMap &predMap() const { return predecessor;}
     106   
    132107    ///Returns a reference to the map of nodes of  shortest paths.
    133108
     
    143118    ///\todo Is this what we want?
    144119    ///\pre \ref run() must be called before using this function.
    145     ///
    146120    bool reached(Node v) { return G.valid(predecessor[v]); }
    147121   
     
    153127  // **********************************************************************
    154128
    155   ///Runs %Dijkstra algorithm from node the source.
     129  ///Runs %Dijkstra algorithm from source node \c s.
    156130
    157131  ///This method runs the %Dijkstra algorithm from a source node \c s
    158   ///in order to
    159   ///compute the
    160   ///shortest path to each node. The algorithm computes
    161   ///- The shortest path tree.
    162   ///- The distance of each node from the source.
     132  ///in order to compute the shortest path to each node. The algorithm
     133  ///computes - The shortest path tree.  - The distance of each node
     134  ///from the source.
    163135  template <typename Graph, typename LengthMap,
    164136            template<class,class,class> class Heap >
     
    169141      predecessor.set(u,INVALID);
    170142      pred_node.set(u,INVALID);
    171       // If a node is unreacheable, then why should be the dist=0?
    172       // distance.set(u,0);
    173       //      reach.set(u,false);
    174143    }
    175144   
     
    177146   
    178147    Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map);
    179    
    180148    heap.push(s,0);
    181149   
    182       while ( !heap.empty() ) {
     150    while ( !heap.empty() ) {
     151     
     152      Node v=heap.top();
     153      ValueType oldvalue=heap[v];
     154      heap.pop();
     155      distance.set(v, oldvalue);
    183156       
    184         Node v=heap.top();
    185         ValueType oldvalue=heap[v];
    186         heap.pop();
    187         distance.set(v, oldvalue);
    188        
    189         { //FIXME this bracket is for e to be local
    190           OutEdgeIt e;
    191         for(G.first(e, v);
    192             G.valid(e); G.next(e)) {
     157      { //FIXME this bracket is for e to be local
     158        OutEdgeIt e;
     159        for(G.first(e, v); G.valid(e); G.next(e)) {
    193160          Node w=G.head(e);
    194161         
     
    210177          }
    211178        }
    212       } //FIXME tis bracket
    213       }
     179      } //FIXME this bracket
     180    }
    214181  }
    215182 
Note: See TracChangeset for help on using the changeset viewer.