source: lemon-0.x/src/work/jacint/prim.h @ 175:ebccffe4d47b

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