COIN-OR::LEMON - Graph Library

Changeset 372:e6a156fc186d in lemon-0.x for src/work/jacint/dijkstra.h


Ignore:
Timestamp:
04/22/04 16:11:28 (17 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@502
Message:
 
File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/jacint/dijkstra.h

    r220 r372  
    11// -*- C++ -*-
     2
    23/*
    34 *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
     
    2728#define HUGO_DIJKSTRA_H
    2829
     30///\file
     31///\brief Dijkstra algorithm.
     32
    2933#include <fib_heap.h>
     34#include <bin_heap.h>
    3035#include <invalid.h>
    3136
    3237namespace hugo {
    3338 
    34   template <typename Graph, typename T,
    35     typename Heap=FibHeap<typename Graph::Node, T,
    36     typename Graph::NodeMap<int> >,
    37     typename LengthMap=typename Graph::EdgeMap<T> >
     39  //Alpar: Changed the order of the parameters
     40 
     41  ///%Dijkstra algorithm class.
     42
     43  ///This class provides an efficient implementation of %Dijkstra algorithm.
     44  ///The edge lengths are passed to the algorithm using a
     45  ///\ref ReadMapSkeleton "readable map",
     46  ///so it is easy to change it to any kind of length.
     47  ///
     48  ///The type of the length is determined by the \c ValueType of the length map.
     49  ///
     50  ///It is also possible to change the underlying priority heap.
     51  ///
     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".
     63 
     64#ifdef DOXYGEN
     65  template <typename Graph,
     66            typename LengthMap,
     67            typename Heap>
     68#else
     69  template <typename Graph,
     70            typename LengthMap=typename Graph::EdgeMap<int>,
     71            template <class,class,class> class Heap = BinHeap >
     72#endif
    3873  class Dijkstra{
     74  public:
    3975    typedef typename Graph::Node Node;
    4076    typedef typename Graph::NodeIt NodeIt;
     
    4278    typedef typename Graph::OutEdgeIt OutEdgeIt;
    4379   
     80    typedef typename LengthMap::ValueType ValueType;
     81    typedef typename Graph::NodeMap<Edge> PredMap;
     82    typedef typename Graph::NodeMap<Node> PredNodeMap;
     83    typedef typename Graph::NodeMap<ValueType> DistMap;
     84
     85  private:
    4486    const Graph& G;
    4587    const LengthMap& length;
    46     typename Graph::NodeMap<Edge> predecessor;
    47     typename Graph::NodeMap<T> distance;
    48     //FIXME:
    49     typename Graph::NodeMap<bool> reach;
    50     //typename Graph::NodeMap<int> reach;
     88    PredMap predecessor;
     89    PredNodeMap pred_node;
     90    DistMap distance;
    5191   
    5292  public :
    5393   
    54     /*
    55       The distance of the nodes is 0.
    56     */
    57     Dijkstra(Graph& _G, LengthMap& _length) : G(_G),
    58       length(_length), predecessor(_G), distance(_G), reach(_G) { }
    59    
    60 
    61     void run(Node s) {
    62      
    63       NodeIt u;
    64       for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
    65         predecessor.set(u,INVALID);
    66         distance.set(u,0);
    67         reach.set(u,false);
    68       }
    69      
    70       //FIXME:
    71       typename Graph::NodeMap<bool> scanned(G,false);
    72       //typename Graph::NodeMap<int> scanned(G,false);
    73       typename Graph::NodeMap<int> heap_map(G,-1);
    74      
    75       Heap heap(heap_map);
    76 
    77       heap.push(s,0);
    78       reach.set(s, true);
    79 
     94    Dijkstra(Graph& _G, LengthMap& _length) :
     95      G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { }
     96   
     97    void run(Node s);
     98   
     99    ///The distance of a node from the source.
     100
     101    ///Returns the distance of a node from the source.
     102    ///\pre \ref run() must be called before using this function.
     103    ///\warning If node \c v in unreachable from the source the return value
     104    ///of this funcion is undefined.
     105    ValueType dist(Node v) const { return distance[v]; }
     106    ///Returns the edges of the shortest path tree.
     107
     108    ///For a node \c v it returns the last edge of the shortest path
     109    ///from the source to \c v or INVALID if \c v is unreachable
     110    ///from the source.
     111    ///\pre \ref run() must be called before using this function.
     112    Edge pred(Node v) const { return predecessor[v]; }
     113    ///Returns the nodes of the shortest paths.
     114
     115    ///For a node \c v it returns the last but one node of the shortest path
     116    ///from the source to \c v or INVALID if \c v is unreachable
     117    ///from the source.
     118    ///\pre \ref run() must be called before using this function.
     119    Node predNode(Node v) const { return pred_node[v]; }
     120   
     121    ///Returns a reference to the NodeMap of distances.
     122
     123    ///\pre \ref run() must be called before using this function.
     124    ///
     125    const DistMap &distMap() const { return distance;}
     126    ///Returns a reference to the shortest path tree map.
     127
     128    ///Returns a reference to the NodeMap of the edges of the
     129    ///shortest path tree.
     130    ///\pre \ref run() must be called before using this function.
     131    const PredMap &predMap() const { return predecessor;}
     132    ///Returns a reference to the map of nodes of  shortest paths.
     133
     134    ///Returns a reference to the NodeMap of the last but one nodes of the
     135    ///shortest paths.
     136    ///\pre \ref run() must be called before using this function.
     137    const PredNodeMap &predNodeMap() const { return pred_node;}
     138
     139    ///Checks if a node is reachable from the source.
     140
     141    ///Returns \c true if \c v is reachable from the source.
     142    ///\warning the source node is reported to be unreached!
     143    ///\todo Is this what we want?
     144    ///\pre \ref run() must be called before using this function.
     145    ///
     146    bool reached(Node v) { return G.valid(predecessor[v]); }
     147   
     148  };
     149 
     150
     151  // **********************************************************************
     152  //  IMPLEMENTATIONS
     153  // **********************************************************************
     154
     155  ///Runs %Dijkstra algorithm from node the source.
     156
     157  ///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.
     163  template <typename Graph, typename LengthMap,
     164            template<class,class,class> class Heap >
     165  void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
     166   
     167    NodeIt u;
     168    for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
     169      predecessor.set(u,INVALID);
     170      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);
     174    }
     175   
     176    typename Graph::NodeMap<int> heap_map(G,-1);
     177   
     178    Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map);
     179   
     180    heap.push(s,0);
     181   
    80182      while ( !heap.empty() ) {
    81183       
    82184        Node v=heap.top();
    83         T oldvalue=heap.get(v);
     185        ValueType oldvalue=heap[v];
    84186        heap.pop();
    85187        distance.set(v, oldvalue);
    86         scanned.set(v,true);
    87 
    88         OutEdgeIt e;
    89         for( G.first(e,v); G.valid(e); G.next(e)) {
     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)) {
    90193          Node w=G.head(e);
    91            
    92           if ( !scanned[w] ) {
    93             if ( !reach[w] ) {
    94               reach.set(w,true);
    95               heap.push(w,oldvalue+length[e]);
     194         
     195          switch(heap.state(w)) {
     196          case heap.PRE_HEAP:
     197            heap.push(w,oldvalue+length[e]);
     198            predecessor.set(w,e);
     199            pred_node.set(w,v);
     200            break;
     201          case heap.IN_HEAP:
     202            if ( oldvalue+length[e] < heap[w] ) {
     203              heap.decrease(w, oldvalue+length[e]);
    96204              predecessor.set(w,e);
    97             } else if ( oldvalue+length[e] < heap.get(w) ) {
    98               predecessor.set(w,e);
    99               heap.decrease(w, oldvalue+length[e]);
     205              pred_node.set(w,v);
    100206            }
     207            break;
     208          case heap.POST_HEAP:
     209            break;
    101210          }
    102211        }
     212      } //FIXME tis bracket
    103213      }
    104     }
    105    
    106     T dist(Node v) {
    107       return distance[v];
    108     }
    109 
    110     Edge pred(Node v) {
    111       return predecessor[v];
    112     }
    113      
    114     bool reached(Node v) {
    115       return reach[v];
    116     }
    117    
    118   };
    119  
    120 }
     214  }
     215 
     216} //END OF NAMESPACE HUGO
    121217
    122218#endif
Note: See TracChangeset for help on using the changeset viewer.