Changeset 211:9222a9b8b323 in lemon0.x for src/work/jacint/prim.h
 Timestamp:
 03/19/04 23:16:05 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@306
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/jacint/prim.h
r173 r211 1 1 // * C++ * 2 3 //kell hogy tree_edge invalid elekbol alljon, Szep4 //lenne ha az elejen a konstrualas ilyet adna, de5 //ugy fest nem igy lesz, ekkor invalidalni kell6 7 2 /* 8 *template <Graph, T, Heap=FibHeap >3 *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> > 9 4 * 10 5 *Constructor: 11 6 * 12 *Prim(Graph G, Graph::EdgeMap<T> weight, NodeIt root=[G.first()])7 *Prim(Graph G, LengthMap weight) 13 8 * 14 9 * 15 10 *Methods: 16 11 * 17 *void run() 12 *void run() : Runs the Primalgorithm from a random node 18 13 * 19 * The followings functions should be used after run() was already run.14 *void run(Node r) : Runs the Primalgorithm from node s 20 15 * 21 *T weight() : returns the minimum weight of a spanning tree of the22 * component of the root.16 *T weight() : After run(r) was run, it returns the minimum 17 * weight of a spanning tree of the component of the root. 23 18 * 24 *Edge It tree(NodeIt v) : returns the first edge in the path from v25 * to the root. Returns an invalid iterator if v=s or v is26 * not reachable from the root.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. 27 22 * 28 *bool conn() : true iff G is connected23 *bool conn() : After run(r) was run, it is true iff G is connected 29 24 * 30 *bool reach(NodeIt v) : true iff v is in the same component as the root 25 *bool reached(Node v) : After run(r) was run, it is true 26 * iff v is in the same component as the root 31 27 * 32 *Node Itroot() : returns the root28 *Node root() : returns the root 33 29 * 34 30 */ 35 31 36 #ifndef PRIM_H37 #define PRIM_H32 #ifndef HUGO_PRIM_H 33 #define HUGO_PRIM_H 38 34 39 35 #include <fib_heap.h> 40 41 #include <iostream> 36 #include <invalid.h> 42 37 43 38 namespace hugo { 44 39 45 40 template <typename Graph, typename T, 46 typename Heap=FibHeap<typename Graph::NodeIt, T, 47 typename Graph::NodeMap<int> > > 41 typename Heap=FibHeap<typename Graph::Node, T, 42 typename Graph::NodeMap<int> >, 43 typename LengthMap=typename Graph::EdgeMap<T> > 48 44 class Prim{ 45 typedef typename Graph::Node Node; 49 46 typedef typename Graph::NodeIt NodeIt; 50 typedef typename Graph::EachNodeIt EachNodeIt; 51 typedef typename Graph::EdgeIt EdgeIt; 47 typedef typename Graph::Edge Edge; 52 48 typedef typename Graph::OutEdgeIt OutEdgeIt; 53 49 typedef typename Graph::InEdgeIt InEdgeIt; 54 50 55 Graph& G;56 NodeIt r;57 typename Graph::NodeMap<Edge It> tree_edge;51 const Graph& G; 52 const LengthMap& edge_weight; 53 typename Graph::NodeMap<Edge> tree_edge; 58 54 typename Graph::NodeMap<T> min_weight; 59 typename Graph::EdgeMap<T>& edge_weight; 60 typename Graph::NodeMap<bool> reached; 55 typename Graph::NodeMap<bool> reach; 61 56 62 57 public : 63 58 64 Prim(Graph& _G, typename Graph::EdgeMap<T>& _edge_weight, 65 NodeIt const _r) : 66 G(_G), r(_r), tree_edge(G), min_weight(G), 67 edge_weight(_edge_weight), reached(G, false) { } 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) { } 68 62 69 Prim(Graph& _G, typename Graph::EdgeMap<T>& _edge_weight) : 70 G(_G), tree_edge(G), min_weight(G), edge_weight(_edge_weight), reached(G, false) 71 { 72 EachNodeIt _r; //FIXME 73 G.getFirst(_r); 74 r=_r; 63 64 void run() { 65 NodeIt _r; 66 G.first(_r); 67 run(_r); 75 68 } 76 69 77 70 78 void run() { 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 79 80 80 81 typename Graph::NodeMap<bool> scanned(G, false); … … 84 85 85 86 heap.push(r,0); 86 reach ed.set(r, true);87 reach.set(r, true); 87 88 88 89 while ( !heap.empty() ) { 89 90 90 Node Itv=heap.top();91 Node v=heap.top(); 91 92 min_weight.set(v, heap.get(v)); 92 93 heap.pop(); … … 94 95 95 96 OutEdgeIt e; 96 for( G. getFirst(e,v); G.valid(e); G.next(e)) {97 Node Itw=G.head(e);97 for( G.first(e,v); G.valid(e); G.next(e)) { 98 Node w=G.head(e); 98 99 99 if ( !scanned .get(w)) {100 if ( !reach ed.get(w)) {101 reach ed.set(w,true);102 heap.push(w, edge_weight .get(e));100 if ( !scanned[w] ) { 101 if ( !reach[w] ) { 102 reach.set(w,true); 103 heap.push(w, edge_weight[e]); 103 104 tree_edge.set(w,e); 104 } else if ( edge_weight .get(e)< heap.get(w) ) {105 } else if ( edge_weight[e] < heap.get(w) ) { 105 106 tree_edge.set(w,e); 106 heap.decrease(w, edge_weight .get(e));107 heap.decrease(w, edge_weight[e]); 107 108 } 108 109 } … … 110 111 111 112 InEdgeIt f; 112 for( G. getFirst(f,v); G.valid(f); G.next(f)) {113 Node Itw=G.tail(f);113 for( G.first(f,v); G.valid(f); G.next(f)) { 114 Node w=G.tail(f); 114 115 115 if ( !scanned .get(w)) {116 if ( !reach ed.get(w)) {117 reach ed.set(w,true);118 heap.push(w, edge_weight .get(f));116 if ( !scanned[w] ) { 117 if ( !reach[w] ) { 118 reach.set(w,true); 119 heap.push(w, edge_weight[f]); 119 120 tree_edge.set(w,f); 120 } else if ( edge_weight .get(f)< heap.get(w) ) {121 } else if ( edge_weight[f] < heap.get(w) ) { 121 122 tree_edge.set(w,f); 122 heap.decrease(w, edge_weight .get(f));123 heap.decrease(w, edge_weight[f]); 123 124 } 124 125 } … … 130 131 T weight() { 131 132 T w=0; 132 EachNodeIt u;133 for ( G. getFirst(u) ; G.valid(u) ; G.next(u) ) w+=min_weight.get(u);133 NodeIt u; 134 for ( G.first(u) ; G.valid(u) ; G.next(u) ) w+=min_weight[u]; 134 135 return w; 135 136 } 136 137 137 138 138 Edge It tree(NodeItv) {139 return tree_edge .get(v);139 Edge tree(Node v) { 140 return tree_edge[v]; 140 141 } 141 142 … … 143 144 bool conn() { 144 145 bool c=true; 145 EachNodeIt u;146 for ( G. getFirst(u) ; G.valid(u) ; G.next(u) )147 if ( !reached .get(u)) {146 NodeIt u; 147 for ( G.first(u) ; G.valid(u) ; G.next(u) ) 148 if ( !reached[u] ) { 148 149 c=false; 149 150 break; … … 153 154 154 155 155 bool reach (NodeItv) {156 return reached .get(v);156 bool reached(Node v) { 157 return reached[v]; 157 158 } 158 159 159 160 160 Node Itroot() {161 Node root() { 161 162 return r; 162 163 }
Note: See TracChangeset
for help on using the changeset viewer.