// -*- C++ -*-

 /* 

  *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >

  *

  *Constructor: 

  *

  *Prim(Graph G, LengthMap weight)

  *

  *

  *Methods:

  *

  *void run() : Runs the Prim-algorithm from a random node

  *

  *void run(Node r) : Runs the Prim-algorithm from node s

  *

  *T weight() : After run(r) was run, it returns the minimum 

  *   weight of a spanning tree of the component of the root. 

  *

  *Edge tree(Node v) : After run(r) was run, it returns the 

  *   first edge in the path from v to the root. Returns 

  *   INVALID if v=r or v is not reachable from the root.

  *

  *bool conn() : After run(r) was run, it is true iff G is connected

  *

  *bool reached(Node v) : After run(r) was run, it is true 

  *   iff v is in the same component as the root

  *

  *Node root() : returns the root

  *

  */

 #ifndef LEMON_PRIM_H

 #define LEMON_PRIM_H

 #include <fib_heap.h>

 #include <invalid.h>

 namespace lemon {

   template <typename Graph, typename T, 

     typename Heap=FibHeap<typename Graph::Node, T, 

     typename Graph::NodeMap<int> >, 

     typename LengthMap=typename Graph::EdgeMap<T> >

     class Prim{

       typedef typename Graph::Node Node;

       typedef typename Graph::NodeIt NodeIt;

       typedef typename Graph::Edge Edge;

       typedef typename Graph::OutEdgeIt OutEdgeIt;

       typedef typename Graph::InEdgeIt InEdgeIt;  

       const Graph& G;

       const LengthMap& edge_weight;

       typename Graph::NodeMap<Edge> tree_edge;

       typename Graph::NodeMap<T> min_weight;

       typename Graph::NodeMap<bool> reach;

   public :

       Prim(Graph& _G, LengthMap& _edge_weight) : 

 	G(_G), edge_weight(_edge_weight), 

 	tree_edge(_G,INVALID), min_weight(_G), reach(_G, false) { }

       void run() {

 	NodeIt _r;	

 	G.first(_r);

 	run(_r);

       }

       void run(Node r) {

 	NodeIt u;

 	for ( G.first(u) ; G.valid(u) ; G.next(u) ) {

 	  tree_edge.set(u,INVALID);

 	  min_weight.set(u,0);

 	  reach.set(u,false);

 	}

 	typename Graph::NodeMap<bool> scanned(G, false);

 	typename Graph::NodeMap<int> heap_map(G,-1);

 	Heap heap(heap_map);

 	heap.push(r,0); 

 	reach.set(r, true);

 	while ( !heap.empty() ) {

 	  Node v=heap.top(); 

 	  min_weight.set(v, heap.get(v));

 	  heap.pop();

 	  scanned.set(v,true);

 	  OutEdgeIt e;

 	  for( G.first(e,v); G.valid(e); G.next(e)) {

 	    Node w=G.head(e); 

 	    if ( !scanned[w] ) {

 	      if ( !reach[w] ) {

 		reach.set(w,true);

 		heap.push(w, edge_weight[e]); 

 		tree_edge.set(w,e);

 	      } else if ( edge_weight[e] < heap.get(w) ) {

 		tree_edge.set(w,e);

 		heap.decrease(w, edge_weight[e]); 

 	      }

 	    }

 	  }

 	  InEdgeIt f;

 	  for( G.first(f,v); G.valid(f); G.next(f)) {

 	    Node w=G.tail(f); 

 	    if ( !scanned[w] ) {

 	      if ( !reach[w] ) {

 		reach.set(w,true);

 		heap.push(w, edge_weight[f]); 

 		tree_edge.set(w,f);

 	      } else if ( edge_weight[f] < heap.get(w) ) {

 		tree_edge.set(w,f);

 		heap.decrease(w, edge_weight[f]); 

 	      }

 	    }

 	  }

 	}

       } 

       T weight() {

 	T w=0;

 	NodeIt u;

 	for ( G.first(u) ; G.valid(u) ; G.next(u) ) w+=min_weight[u];

 	return w;

       }

       Edge tree(Node v) {

 	return tree_edge[v];

       } 

       bool conn() {

 	bool c=true;

 	NodeIt u;

 	for ( G.first(u) ; G.valid(u) ; G.next(u) ) 

 	  if ( !reached[u] ) { 

 	    c=false;

 	    break;

 	  }

 	return c;

       }

       bool reached(Node v) {

 	return reached[v];

       }

       Node root() {

 	return r;

       }

     };

 }

 #endif