src/work/jacint/prim.h
author deba
Wed, 08 Sep 2004 12:06:45 +0000 (2004-09-08)
changeset 822 88226d9fe821
parent 173 de9849252e78
child 921 818510fa3d99
permissions -rw-r--r--
The MapFactories have been removed from the code because
if we use macros then they increases only the complexity.

The pair iterators of the maps are separeted from the maps.

Some macros and comments has been changed.
     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 HUGO_PRIM_H
    33 #define HUGO_PRIM_H
    34 
    35 #include <fib_heap.h>
    36 #include <invalid.h>
    37 
    38 namespace hugo {
    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.head(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.tail(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