jacint@173: // -*- C++ -*-
jacint@173: 
jacint@173: //kell hogy tree_edge invalid elekbol alljon, Szep 
jacint@173: //lenne ha az elejen a konstrualas ilyet adna, de
jacint@173: //ugy fest nem igy lesz, ekkor invalidalni kell
jacint@173: 
jacint@173: /* 
jacint@173:  *template <Graph, T, Heap=FibHeap>
jacint@173:  *
jacint@173:  *Constructor: 
jacint@173:  *
jacint@173:  *Prim(Graph G, Graph::EdgeMap<T> weight, NodeIt root=[G.first()])
jacint@173:  *
jacint@173:  *
jacint@173:  *Methods:
jacint@173:  *
jacint@173:  *void run()
jacint@173:  *
jacint@173:  *  The followings functions should be used after run() was already run.
jacint@173:  *
jacint@173:  *T weight() : returns the minimum weight of a spanning tree of the
jacint@173:  *   component of the root. 
jacint@173:  *
jacint@173:  *EdgeIt tree(NodeIt v) : returns the first edge in the path from v
jacint@173:  *   to the root. Returns an invalid iterator if v=s or v is 
jacint@173:  *   not reachable from the root.
jacint@173:  *
jacint@173:  *bool conn() : true iff G is connected
jacint@173:  *
jacint@173:  *bool reach(NodeIt v) : true iff v is in the same component as the root
jacint@173:  *
jacint@173:  *NodeIt root() : returns the root
jacint@173:  *
jacint@173:  */
jacint@173: 
jacint@173: #ifndef PRIM_H
jacint@173: #define PRIM_H
jacint@173: 
jacint@173: #include <fib_heap.h>
jacint@173: 
jacint@173: #include <iostream>
jacint@173: 
jacint@173: namespace hugo {
jacint@173: 
jacint@173:   template <typename Graph, typename T, 
jacint@173:     typename Heap=FibHeap<typename Graph::NodeIt, T, 
jacint@173:     typename Graph::NodeMap<int> > >
jacint@173:     class Prim{
jacint@173:       typedef typename Graph::NodeIt NodeIt;
jacint@173:       typedef typename Graph::EachNodeIt EachNodeIt;
jacint@173:       typedef typename Graph::EdgeIt EdgeIt;
jacint@173:       typedef typename Graph::OutEdgeIt OutEdgeIt;
jacint@173:       typedef typename Graph::InEdgeIt InEdgeIt;  
jacint@173: 
jacint@173:       Graph& G;
jacint@173:       NodeIt r;
jacint@173:       typename Graph::NodeMap<EdgeIt> tree_edge;
jacint@173:       typename Graph::NodeMap<T> min_weight;
jacint@173:       typename Graph::EdgeMap<T>& edge_weight;
jacint@173:       typename Graph::NodeMap<bool> reached;
jacint@173:           
jacint@173:   public :
jacint@173: 
jacint@173:       Prim(Graph& _G, typename Graph::EdgeMap<T>& _edge_weight, 
jacint@173: 	   NodeIt const _r) : 
jacint@173:       G(_G), r(_r), tree_edge(G), min_weight(G), 
jacint@173:       edge_weight(_edge_weight), reached(G, false) { }
jacint@173: 
jacint@173:       Prim(Graph& _G, typename Graph::EdgeMap<T>& _edge_weight) : 
jacint@173:       G(_G), tree_edge(G), min_weight(G), edge_weight(_edge_weight), reached(G, false)
jacint@173:       { 
jacint@173: 	EachNodeIt _r;	   //FIXME
jacint@173: 	G.getFirst(_r);
jacint@173: 	r=_r;
jacint@173:       }
jacint@173: 
jacint@173: 
jacint@173:       void run() {
jacint@173: 
jacint@173: 	typename Graph::NodeMap<bool> scanned(G, false);
jacint@173: 	typename Graph::NodeMap<int> heap_map(G,-1);
jacint@173: 	
jacint@173: 	Heap heap(heap_map);
jacint@173: 
jacint@173: 	heap.push(r,0); 
jacint@173: 	reached.set(r, true);
jacint@173: 
jacint@173: 	while ( !heap.empty() ) {
jacint@173: 
jacint@173: 	  NodeIt v=heap.top(); 
jacint@173: 	  min_weight.set(v, heap.get(v));
jacint@173: 	  heap.pop();
jacint@173: 	  scanned.set(v,true);
jacint@173: 
jacint@173: 	  OutEdgeIt e;
jacint@173: 	  for( G.getFirst(e,v); G.valid(e); G.next(e)) {
jacint@173: 	    NodeIt w=G.head(e); 
jacint@173: 	    
jacint@173: 	    if ( !scanned.get(w) ) {
jacint@173: 	      if ( !reached.get(w) ) {
jacint@173: 		reached.set(w,true);
jacint@173: 		heap.push(w, edge_weight.get(e)); 
jacint@173: 		tree_edge.set(w,e);
jacint@173: 	      } else if ( edge_weight.get(e) < heap.get(w) ) {
jacint@173: 		tree_edge.set(w,e);
jacint@173: 		heap.decrease(w, edge_weight.get(e)); 
jacint@173: 	      }
jacint@173: 	    }
jacint@173: 	  }
jacint@173: 
jacint@173: 	  InEdgeIt f;
jacint@173: 	  for( G.getFirst(f,v); G.valid(f); G.next(f)) {
jacint@173: 	    NodeIt w=G.tail(f); 
jacint@173: 	    
jacint@173: 	    if ( !scanned.get(w) ) {
jacint@173: 	      if ( !reached.get(w) ) {
jacint@173: 		reached.set(w,true);
jacint@173: 		heap.push(w, edge_weight.get(f)); 
jacint@173: 		tree_edge.set(w,f);
jacint@173: 	      } else if ( edge_weight.get(f) < heap.get(w) ) {
jacint@173: 		tree_edge.set(w,f);
jacint@173: 		heap.decrease(w, edge_weight.get(f)); 
jacint@173: 	      }
jacint@173: 	    }
jacint@173: 	  }
jacint@173: 	}
jacint@173:       } 
jacint@173:  
jacint@173: 
jacint@173:       T weight() {
jacint@173: 	T w=0;
jacint@173: 	EachNodeIt u;
jacint@173: 	for ( G.getFirst(u) ; G.valid(u) ; G.next(u) ) w+=min_weight.get(u);
jacint@173: 	return w;
jacint@173:       }
jacint@173:      
jacint@173: 
jacint@173:       EdgeIt tree(NodeIt v) {
jacint@173: 	return tree_edge.get(v);
jacint@173:       } 
jacint@173: 
jacint@173: 
jacint@173:       bool conn() {
jacint@173: 	bool c=true;
jacint@173: 	EachNodeIt u;
jacint@173: 	for ( G.getFirst(u) ; G.valid(u) ; G.next(u) ) 
jacint@173: 	  if ( !reached.get(u) ) { 
jacint@173: 	    c=false;
jacint@173: 	    break;
jacint@173: 	  }
jacint@173: 	return c;
jacint@173:       }
jacint@173: 
jacint@173: 
jacint@173:       bool reach(NodeIt v) {
jacint@173: 	return reached.get(v);
jacint@173:       }
jacint@173: 
jacint@173: 
jacint@173:       NodeIt root() {
jacint@173: 	return r;
jacint@173:       }
jacint@173: 
jacint@173:     };
jacint@173: 
jacint@173: }
jacint@173: 
jacint@173: #endif
jacint@173: 
jacint@173: