// -*- C++ -*-

 //kell hogy tree_edge invalid elekbol alljon, Szep 

 //lenne ha az elejen a konstrualas ilyet adna, de

 //ugy fest nem igy lesz, ekkor invalidalni kell

 /* 

  *template <Graph, T, Heap=FibHeap>

  *

  *Constructor: 

  *

  *Prim(Graph G, Graph::EdgeMap<T> weight, NodeIt root=[G.first()])

  *

  *

  *Methods:

  *

  *void run()

  *

  *  The followings functions should be used after run() was already run.

  *

  *T weight() : returns the minimum weight of a spanning tree of the

  *   component of the root. 

  *

  *EdgeIt tree(NodeIt v) : returns the first edge in the path from v

  *   to the root. Returns an invalid iterator if v=s or v is 

  *   not reachable from the root.

  *

  *bool conn() : true iff G is connected

  *

  *bool reach(NodeIt v) : true iff v is in the same component as the root

  *

  *NodeIt root() : returns the root

  *

  */

 #ifndef PRIM_H

 #define PRIM_H

 #include <fib_heap.h>

 #include <iostream>

 namespace hugo {

   template <typename Graph, typename T, 

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

     typename Graph::NodeMap<int> > >

     class Prim{

       typedef typename Graph::NodeIt NodeIt;

       typedef typename Graph::EachNodeIt EachNodeIt;

       typedef typename Graph::EdgeIt EdgeIt;

       typedef typename Graph::OutEdgeIt OutEdgeIt;

       typedef typename Graph::InEdgeIt InEdgeIt;  

       Graph& G;

       NodeIt r;

       typename Graph::NodeMap<EdgeIt> tree_edge;

       typename Graph::NodeMap<T> min_weight;

       typename Graph::EdgeMap<T>& edge_weight;

       typename Graph::NodeMap<bool> reached;

   public :

       Prim(Graph& _G, typename Graph::EdgeMap<T>& _edge_weight, 

 	   NodeIt const _r) : 

       G(_G), r(_r), tree_edge(G), min_weight(G), 

       edge_weight(_edge_weight), reached(G, false) { }

       Prim(Graph& _G, typename Graph::EdgeMap<T>& _edge_weight) : 

       G(_G), tree_edge(G), min_weight(G), edge_weight(_edge_weight), reached(G, false)

       { 

 	EachNodeIt _r;	   //FIXME

 	G.getFirst(_r);

 	r=_r;

       }

       void run() {

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

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

 	Heap heap(heap_map);

 	heap.push(r,0); 

 	reached.set(r, true);

 	while ( !heap.empty() ) {

 	  NodeIt v=heap.top(); 

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

 	  heap.pop();

 	  scanned.set(v,true);

 	  OutEdgeIt e;

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

 	    NodeIt w=G.head(e); 

 	    if ( !scanned.get(w) ) {

 	      if ( !reached.get(w) ) {

 		reached.set(w,true);

 		heap.push(w, edge_weight.get(e)); 

 		tree_edge.set(w,e);

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

 		tree_edge.set(w,e);

 		heap.decrease(w, edge_weight.get(e)); 

 	      }

 	    }

 	  }

 	  InEdgeIt f;

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

 	    NodeIt w=G.tail(f); 

 	    if ( !scanned.get(w) ) {

 	      if ( !reached.get(w) ) {

 		reached.set(w,true);

 		heap.push(w, edge_weight.get(f)); 

 		tree_edge.set(w,f);

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

 		tree_edge.set(w,f);

 		heap.decrease(w, edge_weight.get(f)); 

 	      }

 	    }

 	  }

 	}

       } 

       T weight() {

 	T w=0;

 	EachNodeIt u;

 	for ( G.getFirst(u) ; G.valid(u) ; G.next(u) ) w+=min_weight.get(u);

 	return w;

       }

       EdgeIt tree(NodeIt v) {

 	return tree_edge.get(v);

       } 

       bool conn() {

 	bool c=true;

 	EachNodeIt u;

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

 	  if ( !reached.get(u) ) { 

 	    c=false;

 	    break;

 	  }

 	return c;

       }

       bool reach(NodeIt v) {

 	return reached.get(v);

       }

       NodeIt root() {

 	return r;

       }

     };

 }

 #endif