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