|
1 // -*- C++ -*- |
|
2 |
|
3 //kell hogy tree_edge invalid elekbol alljon, Szep |
|
4 //lenne ha az elejen a konstrualas ilyet adna, de |
|
5 //ugy fest nem igy lesz, ekkor invalidalni kell |
|
6 |
|
7 /* |
|
8 *template <Graph, T, Heap=FibHeap> |
|
9 * |
|
10 *Constructor: |
|
11 * |
|
12 *Prim(Graph G, Graph::EdgeMap<T> weight, NodeIt root=[G.first()]) |
|
13 * |
|
14 * |
|
15 *Methods: |
|
16 * |
|
17 *void run() |
|
18 * |
|
19 * The followings functions should be used after run() was already run. |
|
20 * |
|
21 *T weight() : returns the minimum weight of a spanning tree of the |
|
22 * component of the root. |
|
23 * |
|
24 *EdgeIt tree(NodeIt v) : returns the first edge in the path from v |
|
25 * to the root. Returns an invalid iterator if v=s or v is |
|
26 * not reachable from the root. |
|
27 * |
|
28 *bool conn() : true iff G is connected |
|
29 * |
|
30 *bool reach(NodeIt v) : true iff v is in the same component as the root |
|
31 * |
|
32 *NodeIt root() : returns the root |
|
33 * |
|
34 */ |
|
35 |
|
36 #ifndef PRIM_H |
|
37 #define PRIM_H |
|
38 |
|
39 #include <fib_heap.h> |
|
40 |
|
41 #include <iostream> |
|
42 |
|
43 namespace hugo { |
|
44 |
|
45 template <typename Graph, typename T, |
|
46 typename Heap=FibHeap<typename Graph::NodeIt, T, |
|
47 typename Graph::NodeMap<int> > > |
|
48 class Prim{ |
|
49 typedef typename Graph::NodeIt NodeIt; |
|
50 typedef typename Graph::EachNodeIt EachNodeIt; |
|
51 typedef typename Graph::EdgeIt EdgeIt; |
|
52 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
53 typedef typename Graph::InEdgeIt InEdgeIt; |
|
54 |
|
55 Graph& G; |
|
56 NodeIt r; |
|
57 typename Graph::NodeMap<EdgeIt> tree_edge; |
|
58 typename Graph::NodeMap<T> min_weight; |
|
59 typename Graph::EdgeMap<T>& edge_weight; |
|
60 typename Graph::NodeMap<bool> reached; |
|
61 |
|
62 public : |
|
63 |
|
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) { } |
|
68 |
|
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; |
|
75 } |
|
76 |
|
77 |
|
78 void run() { |
|
79 |
|
80 typename Graph::NodeMap<bool> scanned(G, false); |
|
81 typename Graph::NodeMap<int> heap_map(G,-1); |
|
82 |
|
83 Heap heap(heap_map); |
|
84 |
|
85 heap.push(r,0); |
|
86 reached.set(r, true); |
|
87 |
|
88 while ( !heap.empty() ) { |
|
89 |
|
90 NodeIt v=heap.top(); |
|
91 min_weight.set(v, heap.get(v)); |
|
92 heap.pop(); |
|
93 scanned.set(v,true); |
|
94 |
|
95 OutEdgeIt e; |
|
96 for( G.getFirst(e,v); G.valid(e); G.next(e)) { |
|
97 NodeIt w=G.head(e); |
|
98 |
|
99 if ( !scanned.get(w) ) { |
|
100 if ( !reached.get(w) ) { |
|
101 reached.set(w,true); |
|
102 heap.push(w, edge_weight.get(e)); |
|
103 tree_edge.set(w,e); |
|
104 } else if ( edge_weight.get(e) < heap.get(w) ) { |
|
105 tree_edge.set(w,e); |
|
106 heap.decrease(w, edge_weight.get(e)); |
|
107 } |
|
108 } |
|
109 } |
|
110 |
|
111 InEdgeIt f; |
|
112 for( G.getFirst(f,v); G.valid(f); G.next(f)) { |
|
113 NodeIt w=G.tail(f); |
|
114 |
|
115 if ( !scanned.get(w) ) { |
|
116 if ( !reached.get(w) ) { |
|
117 reached.set(w,true); |
|
118 heap.push(w, edge_weight.get(f)); |
|
119 tree_edge.set(w,f); |
|
120 } else if ( edge_weight.get(f) < heap.get(w) ) { |
|
121 tree_edge.set(w,f); |
|
122 heap.decrease(w, edge_weight.get(f)); |
|
123 } |
|
124 } |
|
125 } |
|
126 } |
|
127 } |
|
128 |
|
129 |
|
130 T weight() { |
|
131 T w=0; |
|
132 EachNodeIt u; |
|
133 for ( G.getFirst(u) ; G.valid(u) ; G.next(u) ) w+=min_weight.get(u); |
|
134 return w; |
|
135 } |
|
136 |
|
137 |
|
138 EdgeIt tree(NodeIt v) { |
|
139 return tree_edge.get(v); |
|
140 } |
|
141 |
|
142 |
|
143 bool conn() { |
|
144 bool c=true; |
|
145 EachNodeIt u; |
|
146 for ( G.getFirst(u) ; G.valid(u) ; G.next(u) ) |
|
147 if ( !reached.get(u) ) { |
|
148 c=false; |
|
149 break; |
|
150 } |
|
151 return c; |
|
152 } |
|
153 |
|
154 |
|
155 bool reach(NodeIt v) { |
|
156 return reached.get(v); |
|
157 } |
|
158 |
|
159 |
|
160 NodeIt root() { |
|
161 return r; |
|
162 } |
|
163 |
|
164 }; |
|
165 |
|
166 } |
|
167 |
|
168 #endif |
|
169 |
|
170 |