1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/work/jacint/dijkstra.h	Tue Mar 09 15:32:40 2004 +0000
     1.3 @@ -0,0 +1,124 @@
     1.4 +// -*- C++ -*-
     1.5 +/* 
     1.6 + *template <Graph, T, Heap=FibHeap>
     1.7 + *
     1.8 + *
     1.9 + *Constructor: 
    1.10 + *
    1.11 + *Dijkstra(Graph G, NodeIt s, Graph::EdgeMap<T> length)
    1.12 + *
    1.13 + *
    1.14 + *
    1.15 + *Member functions:
    1.16 + *
    1.17 + *void run()
    1.18 + *
    1.19 + *  The following function should be used after run() was already run.
    1.20 + *
    1.21 + *
    1.22 + *T dist(NodeIt v) : returns the distance from s to v. 
    1.23 + *   It is 0 if v is not reachable from s.
    1.24 + *
    1.25 + *
    1.26 + *EdgeIt pred(NodeIt v) : returns the last edge 
    1.27 + *   of a shortest s-v path. Returns an invalid iterator 
    1.28 + *   if v=s or v is not reachable from s.
    1.29 + *
    1.30 + *
    1.31 + *bool reach(NodeIt v) : true iff v is reachable from s
    1.32 + *
    1.33 + */
    1.34 +
    1.35 +#ifndef DIJKSTRA_HH
    1.36 +#define DIJKSTRA_HH
    1.37 +
    1.38 +#include <fib_heap.h>
    1.39 +
    1.40 +namespace hugo {
    1.41 +
    1.42 +  template <typename Graph, typename T, 
    1.43 +    typename Heap=FibHeap<typename Graph::NodeIt, T, 
    1.44 +    typename Graph::NodeMap<int> > >
    1.45 +    class Dijkstra{
    1.46 +      typedef typename Graph::NodeIt NodeIt;
    1.47 +      typedef typename Graph::EdgeIt EdgeIt;
    1.48 +      typedef typename Graph::OutEdgeIt OutEdgeIt;
    1.49 +      
    1.50 +      Graph& G;
    1.51 +      NodeIt s;
    1.52 +      typename Graph::NodeMap<EdgeIt> predecessor;
    1.53 +      typename Graph::NodeMap<T> distance;
    1.54 +      typename Graph::EdgeMap<T>& length;
    1.55 +      typename Graph::NodeMap<bool> reached;
    1.56 +          
    1.57 +  public :
    1.58 +
    1.59 +    /*
    1.60 +      The distance of the nodes is 0.
    1.61 +    */
    1.62 +    Dijkstra(Graph& _G, NodeIt const _s, 
    1.63 +	     typename Graph::EdgeMap<T>& _length) : 
    1.64 +      G(_G), s(_s), predecessor(G), distance(G), 
    1.65 +      length(_length), reached(G, false) { }
    1.66 +    
    1.67 +      
    1.68 +      void run() {
    1.69 +	
    1.70 +	typename Graph::NodeMap<bool> scanned(G, false);
    1.71 +	typename Graph::NodeMap<int> heap_map(G,-1);
    1.72 +
    1.73 +	Heap heap(heap_map);
    1.74 +
    1.75 +	heap.push(s,0); 
    1.76 +	reached.set(s, true);
    1.77 +
    1.78 +	while ( !heap.empty() ) {
    1.79 +
    1.80 +	  NodeIt v=heap.top(); 
    1.81 +	  T oldvalue=heap.get(v);
    1.82 +	  distance.set(v, oldvalue);
    1.83 +	  heap.pop();
    1.84 +	  
    1.85 +	  OutEdgeIt e;
    1.86 +	  for( G.getFirst(e,v); G.valid(e); G.next(e)) {
    1.87 +	    NodeIt w=G.head(e); 
    1.88 +	    
    1.89 +	    if ( !scanned.get(w) ) {
    1.90 +	      if ( !reached.get(w) ) {
    1.91 +		reached.set(w,true);
    1.92 +		heap.push(w,oldvalue+length.get(e)); 
    1.93 +		predecessor.set(w,e);
    1.94 +
    1.95 +	      } else if ( oldvalue+length.get(e) < heap.get(w) ) {
    1.96 +		predecessor.set(w,e);
    1.97 +		heap.decrease(w, oldvalue+length.get(e)); 
    1.98 +	      }
    1.99 +	    }
   1.100 +	  }
   1.101 +	  scanned.set(v,true);
   1.102 +	}
   1.103 +      } 
   1.104 +      
   1.105 +
   1.106 +      T dist(NodeIt v) {
   1.107 +	return distance.get(v);
   1.108 +      }
   1.109 +
   1.110 +
   1.111 +      EdgeIt pred(NodeIt v) {
   1.112 +	if ( v!=s ) return predecessor.get(v);
   1.113 +	else return EdgeIt();
   1.114 +      }
   1.115 +     
   1.116 +
   1.117 +      bool reach(NodeIt v) {
   1.118 +	return reached.get(v);
   1.119 +      }
   1.120 +
   1.121 +    };
   1.122 +
   1.123 +}
   1.124 +
   1.125 +#endif
   1.126 +
   1.127 +