jacint@159: // -*- C++ -*-
jacint@159: /* 
jacint@211:  *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
jacint@159:  *
jacint@159:  *Constructor: 
jacint@159:  *
jacint@211:  *Dijkstra(Graph G, LengthMap length)
jacint@159:  *
jacint@159:  *
jacint@211:  *Methods:
jacint@159:  *
jacint@211:  *void run(Node s)
jacint@159:  *
jacint@211:  *T dist(Node v) : After run(s) was run, it returns the distance from s to v. 
jacint@211:  *   Returns T() if v is not reachable from s.
jacint@159:  *
jacint@211:  *Edge pred(Node v) : After run(s) was run, it returns the last 
jacint@211:  *   edge of a shortest s-v path. It is INVALID for s and for 
jacint@211:  *   the nodes not reachable from s.
jacint@159:  *
jacint@211:  *bool reached(Node v) : After run(s) was run, it is true iff v is 
jacint@211:  *   reachable from s
jacint@159:  *
jacint@159:  */
jacint@159: 
jacint@211: #ifndef HUGO_DIJKSTRA_H
jacint@211: #define HUGO_DIJKSTRA_H
jacint@159: 
jacint@159: #include <fib_heap.h>
jacint@211: #include <invalid.h>
jacint@159: 
jacint@159: namespace hugo {
jacint@211:   
jacint@159:   template <typename Graph, typename T, 
jacint@211:     typename Heap=FibHeap<typename Graph::Node, T, 
jacint@211:     typename Graph::NodeMap<int> >, 
jacint@211:     typename LengthMap=typename Graph::EdgeMap<T> >
jacint@211:   class Dijkstra{
jacint@211:     typedef typename Graph::Node Node;
jacint@211:     typedef typename Graph::NodeIt NodeIt;
jacint@211:     typedef typename Graph::Edge Edge;
jacint@211:     typedef typename Graph::OutEdgeIt OutEdgeIt;
jacint@211:     
jacint@211:     const Graph& G;
jacint@211:     const LengthMap& length;
jacint@211:     typename Graph::NodeMap<Edge> predecessor;
jacint@211:     typename Graph::NodeMap<T> distance;
alpar@217:     //FIXME:
jacint@211:     typename Graph::NodeMap<bool> reach;
alpar@217:     //typename Graph::NodeMap<int> reach;
jacint@211:     
jacint@159:   public :
jacint@211:     
jacint@159:     /*
jacint@159:       The distance of the nodes is 0.
jacint@159:     */
jacint@211:     Dijkstra(Graph& _G, LengthMap& _length) : G(_G), 
jacint@211:       length(_length), predecessor(_G), distance(_G), reach(_G) { }
jacint@159:     
jacint@211: 
jacint@211:     void run(Node s) {
jacint@159:       
jacint@211:       NodeIt u;
jacint@211:       for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
jacint@211: 	predecessor.set(u,INVALID);
jacint@211: 	distance.set(u,0);
jacint@211: 	reach.set(u,false);
jacint@211:       }
jacint@211:      
alpar@217:       //FIXME:
jacint@211:       typename Graph::NodeMap<bool> scanned(G,false);
alpar@217:       //typename Graph::NodeMap<int> scanned(G,false);
jacint@211:       typename Graph::NodeMap<int> heap_map(G,-1);
jacint@211:       
jacint@211:       Heap heap(heap_map);
jacint@211: 
jacint@211:       heap.push(s,0); 
jacint@211:       reach.set(s, true);
jacint@211: 
jacint@211:       while ( !heap.empty() ) {
jacint@159: 	
jacint@211: 	Node v=heap.top(); 
jacint@220: 	T oldvalue=heap.get(v);
jacint@211: 	heap.pop();
jacint@211: 	distance.set(v, oldvalue);
jacint@211: 	scanned.set(v,true);
jacint@159: 
jacint@211: 	OutEdgeIt e;
jacint@211: 	for( G.first(e,v); G.valid(e); G.next(e)) {
jacint@211: 	  Node w=G.head(e); 
jacint@159: 	    
jacint@211: 	  if ( !scanned[w] ) {
jacint@211: 	    if ( !reach[w] ) {
jacint@211: 	      reach.set(w,true);
jacint@211: 	      heap.push(w,oldvalue+length[e]); 
jacint@211: 	      predecessor.set(w,e);
jacint@220: 	    } else if ( oldvalue+length[e] < heap.get(w) ) {
jacint@211: 	      predecessor.set(w,e);
jacint@211: 	      heap.decrease(w, oldvalue+length[e]); 
jacint@159: 	    }
jacint@159: 	  }
jacint@159: 	}
jacint@211:       }
alpar@217:     }
jacint@211:     
jacint@211:     T dist(Node v) {
jacint@211:       return distance[v];
jacint@211:     }
jacint@159: 
jacint@211:     Edge pred(Node v) {
jacint@211:       return predecessor[v];
jacint@211:     }
jacint@159:      
jacint@211:     bool reached(Node v) {
jacint@211:       return reach[v];
jacint@211:     }
jacint@211:     
jacint@211:   };
jacint@167:   
jacint@159: }
jacint@159: 
jacint@159: #endif
jacint@159: 
jacint@159: