source: lemon-0.x/src/work/jacint/prim.h @ 983:3095ff2b5c18

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