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