src/work/jacint/prim.h
author athos
Wed, 23 Mar 2005 11:51:40 +0000
changeset 1247 60708e1475ae
parent 921 818510fa3d99
permissions -rw-r--r--
Completions.
     1 // -*- C++ -*-
     2 /* 
     3  *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
     4  *
     5  *Constructor: 
     6  *
     7  *Prim(Graph G, LengthMap weight)
     8  *
     9  *
    10  *Methods:
    11  *
    12  *void run() : Runs the Prim-algorithm from a random node
    13  *
    14  *void run(Node r) : Runs the Prim-algorithm from node s
    15  *
    16  *T weight() : After run(r) was run, it returns the minimum 
    17  *   weight of a spanning tree of the component of the root. 
    18  *
    19  *Edge tree(Node v) : After run(r) was run, it returns the 
    20  *   first edge in the path from v to the root. Returns 
    21  *   INVALID if v=r or v is not reachable from the root.
    22  *
    23  *bool conn() : After run(r) was run, it is true iff G is connected
    24  *
    25  *bool reached(Node v) : After run(r) was run, it is true 
    26  *   iff v is in the same component as the root
    27  *
    28  *Node root() : returns the root
    29  *
    30  */
    31 
    32 #ifndef LEMON_PRIM_H
    33 #define LEMON_PRIM_H
    34 
    35 #include <fib_heap.h>
    36 #include <invalid.h>
    37 
    38 namespace lemon {
    39 
    40   template <typename Graph, typename T, 
    41     typename Heap=FibHeap<typename Graph::Node, T, 
    42     typename Graph::NodeMap<int> >, 
    43     typename LengthMap=typename Graph::EdgeMap<T> >
    44     class Prim{
    45       typedef typename Graph::Node Node;
    46       typedef typename Graph::NodeIt NodeIt;
    47       typedef typename Graph::Edge Edge;
    48       typedef typename Graph::OutEdgeIt OutEdgeIt;
    49       typedef typename Graph::InEdgeIt InEdgeIt;  
    50 
    51       const Graph& G;
    52       const LengthMap& edge_weight;
    53       typename Graph::NodeMap<Edge> tree_edge;
    54       typename Graph::NodeMap<T> min_weight;
    55       typename Graph::NodeMap<bool> reach;
    56           
    57   public :
    58 
    59       Prim(Graph& _G, LengthMap& _edge_weight) : 
    60 	G(_G), edge_weight(_edge_weight), 
    61 	tree_edge(_G,INVALID), min_weight(_G), reach(_G, false) { }
    62 
    63 
    64       void run() {
    65 	NodeIt _r;	
    66 	G.first(_r);
    67 	run(_r);
    68       }
    69 
    70 
    71       void run(Node r) {
    72 
    73 	NodeIt u;
    74 	for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
    75 	  tree_edge.set(u,INVALID);
    76 	  min_weight.set(u,0);
    77 	  reach.set(u,false);
    78 	}
    79 
    80 
    81 	typename Graph::NodeMap<bool> scanned(G, false);
    82 	typename Graph::NodeMap<int> heap_map(G,-1);
    83 	
    84 	Heap heap(heap_map);
    85 
    86 	heap.push(r,0); 
    87 	reach.set(r, true);
    88 
    89 	while ( !heap.empty() ) {
    90 
    91 	  Node v=heap.top(); 
    92 	  min_weight.set(v, heap.get(v));
    93 	  heap.pop();
    94 	  scanned.set(v,true);
    95 
    96 	  OutEdgeIt e;
    97 	  for( G.first(e,v); G.valid(e); G.next(e)) {
    98 	    Node w=G.target(e); 
    99 	    
   100 	    if ( !scanned[w] ) {
   101 	      if ( !reach[w] ) {
   102 		reach.set(w,true);
   103 		heap.push(w, edge_weight[e]); 
   104 		tree_edge.set(w,e);
   105 	      } else if ( edge_weight[e] < heap.get(w) ) {
   106 		tree_edge.set(w,e);
   107 		heap.decrease(w, edge_weight[e]); 
   108 	      }
   109 	    }
   110 	  }
   111 
   112 	  InEdgeIt f;
   113 	  for( G.first(f,v); G.valid(f); G.next(f)) {
   114 	    Node w=G.source(f); 
   115 	    
   116 	    if ( !scanned[w] ) {
   117 	      if ( !reach[w] ) {
   118 		reach.set(w,true);
   119 		heap.push(w, edge_weight[f]); 
   120 		tree_edge.set(w,f);
   121 	      } else if ( edge_weight[f] < heap.get(w) ) {
   122 		tree_edge.set(w,f);
   123 		heap.decrease(w, edge_weight[f]); 
   124 	      }
   125 	    }
   126 	  }
   127 	}
   128       } 
   129  
   130 
   131       T weight() {
   132 	T w=0;
   133 	NodeIt u;
   134 	for ( G.first(u) ; G.valid(u) ; G.next(u) ) w+=min_weight[u];
   135 	return w;
   136       }
   137      
   138 
   139       Edge tree(Node v) {
   140 	return tree_edge[v];
   141       } 
   142 
   143 
   144       bool conn() {
   145 	bool c=true;
   146 	NodeIt u;
   147 	for ( G.first(u) ; G.valid(u) ; G.next(u) ) 
   148 	  if ( !reached[u] ) { 
   149 	    c=false;
   150 	    break;
   151 	  }
   152 	return c;
   153       }
   154 
   155 
   156       bool reached(Node v) {
   157 	return reached[v];
   158       }
   159 
   160 
   161       Node root() {
   162 	return r;
   163       }
   164 
   165     };
   166 
   167 }
   168 
   169 #endif
   170 
   171