// -*- 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