/*

  *dijkstra

  *by jacint

  *Performs Dijkstra's algorithm from node s. 

  *

  *Constructor: 

  *

  *dijkstra(graph_type& G, node_iterator s, edge_property_vector& distance)

  *

  *

  *

  *Member functions:

  *

  *void run()

  *

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

  *

  *

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

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

  *

  *

  *edge_iterator pred(node_iterator 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(node_iterator 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 <marci_property_vector.hh>

 namespace std {

   namespace marci {

     template <typename graph_type, typename T>

     class dijkstra{

       typedef typename graph_traits<graph_type>::node_iterator node_iterator;

       typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;

       typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;

       typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;

       typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;

       graph_type& G;

       node_iterator s;

       node_property_vector<graph_type, edge_iterator> predecessor;

       node_property_vector<graph_type, T> distance;

       edge_property_vector<graph_type, T> length;

       node_property_vector<graph_type, bool> reached;

   public :

     /*

       The distance of all the nodes is 0.

     */

     dijkstra(graph_type& _G, node_iterator _s, edge_property_vector<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

       {

 	node_property_vector<graph_type, T> &d;

 	node_dist_comp(node_property_vector<graph_type, T> &_d) : d(_d) {} 

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

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

       };

       void run() {

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

 	std::priority_queue<node_iterator, vector<node_iterator>, node_dist_comp> 

 	  heap(( node_dist_comp(distance) ));

 	heap.push(s);

 	reached.put(s, true);

 	while (!heap.empty()) {

 	  node_iterator v=heap.top();	

 	  heap.pop();

 	  if (!scanned.get(v)) {

 	    for(out_edge_iterator e=G.first_out_edge(v); e.valid(); ++e) {

 	      node_iterator 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(node_iterator 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.

        */      

       edge_iterator pred(node_iterator v) {

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

 	else {return edge_iterator();}

       }

       bool reach(node_iterator v) {

 	return reached.get(v);

       }

     };// class dijkstra

   } // namespace marci

 }

 #endif //DIJKSTRA_HH