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