/*

  *dijkstra

  *by jacint

  *Performs Dijkstra's algorithm from Node s. 

  *

  *Constructor: 

  *

  *dijkstra(graph_type& G, NodeIt s, EdgeMap& distance)

  *

  *

  *

  *Member functions:

  *

  *void run()

  *

  *  The following function should be used after run() was already run.

  *

  *

  *T dist(NodeIt v) : returns the distance from s to v. 

  *   It is 0 if v is not reachable from s.

  *

  *

  *EdgeIt pred(NodeIt v)

  *   Returns the last Edge of a shortest s-v path. 

  *   Returns an invalid iterator if v=s or v is not

  *   reachable from s.

  *

  *

  *bool reach(NodeIt v) : true if v is reachable from s

  *

  *

  *

  *

  *

  *Problems: 

  * 

  *Heap implementation is needed, because the priority queue of stl

  *does not have a mathod for key-decrease, so we had to use here a 

  *g\'any solution.

  * 

  *The implementation of infinity would be desirable, see after line 100. 

  */

 #ifndef DIJKSTRA_HH

 #define DIJKSTRA_HH

 #include <queue>

 #include <algorithm>

 #include <marci_graph_traits.hh>

 #include <marciMap.hh>

 namespace std {

   namespace hugo {

     template <typename graph_type, typename T>

     class dijkstra{

       typedef typename graph_traits<graph_type>::NodeIt NodeIt;

       typedef typename graph_traits<graph_type>::EdgeIt EdgeIt;

       typedef typename graph_traits<graph_type>::EachNodeIt EachNodeIt;

       typedef typename graph_traits<graph_type>::InEdgeIt InEdgeIt;

       typedef typename graph_traits<graph_type>::OutEdgeIt OutEdgeIt;

       graph_type& G;

       NodeIt s;

       NodeMap<graph_type, EdgeIt> predecessor;

       NodeMap<graph_type, T> distance;

       EdgeMap<graph_type, T> length;

       NodeMap<graph_type, bool> reached;

   public :

     /*

       The distance of all the Nodes is 0.

     */

     dijkstra(graph_type& _G, NodeIt _s, EdgeMap<graph_type, T>& _length) : 

       G(_G), s(_s), predecessor(G, 0), distance(G, 0), length(_length), reached(G, false) { }

       /*By Misi.*/

       struct Node_dist_comp

       {

 	NodeMap<graph_type, T> &d;

 	Node_dist_comp(NodeMap<graph_type, T> &_d) : d(_d) {} 

 	bool operator()(const NodeIt& u, const NodeIt& v) const 

 	{ return d.get(u) < d.get(v); }

       };

       void run() {

 	NodeMap<graph_type, bool> scanned(G, false);

 	std::priority_queue<NodeIt, vector<NodeIt>, Node_dist_comp> 

 	  heap(( Node_dist_comp(distance) ));

 	heap.push(s);

 	reached.put(s, true);

 	while (!heap.empty()) {

 	  NodeIt v=heap.top();	

 	  heap.pop();

 	  if (!scanned.get(v)) {

 	    for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) {

 	      NodeIt w=G.head(e);

 	      if (!scanned.get(w)) {

 		if (!reached.get(w)) {

 		  reached.put(w,true);

 		  distance.put(w, distance.get(v)-length.get(e));

 		  predecessor.put(w,e);

 		} else if (distance.get(v)-length.get(e)>distance.get(w)) {

 		  distance.put(w, distance.get(v)-length.get(e));

 		  predecessor.put(w,e);

 		}

 		heap.push(w);

 	      } 

 	    } 

 	    scanned.put(v,true);

 	  } // if (!scanned.get(v))

 	} // while (!heap.empty())

       } //void run()

       /*

        *Returns the distance of the Node v.

        *It is 0 for the root and for the Nodes not

        *reachable form the root.

        */      

       T dist(NodeIt v) {

 	return -distance.get(v);

       }

       /*

        *  Returns the last Edge of a shortest s-v path. 

        *  Returns an invalid iterator if v=root or v is not

        *  reachable from the root.

        */      

       EdgeIt pred(NodeIt v) {

 	if (v!=s) { return predecessor.get(v);}

 	else {return EdgeIt();}

       }

       bool reach(NodeIt v) {

 	return reached.get(v);

       }

     };// class dijkstra

   } // namespace hugo

 }

 #endif //DIJKSTRA_HH