1 // -*- C++ -*- |
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 /* |
2 /* |
8 *template <Graph, T, Heap=FibHeap> |
3 *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> > |
9 * |
4 * |
10 *Constructor: |
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 *Methods: |
10 *Methods: |
16 * |
11 * |
17 *void run() |
12 *void run() : Runs the Prim-algorithm 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 Prim-algorithm from node s |
20 * |
15 * |
21 *T weight() : returns the minimum weight of a spanning tree of the |
16 *T weight() : After run(r) was run, it returns the minimum |
22 * component of the root. |
17 * weight of a spanning tree of the component of the root. |
23 * |
18 * |
24 *EdgeIt tree(NodeIt v) : returns the first edge in the path from v |
19 *Edge tree(Node v) : After run(r) was run, it returns the |
25 * to the root. Returns an invalid iterator if v=s or v is |
20 * first edge in the path from v to the root. Returns |
26 * not reachable from the root. |
21 * INVALID if v=r or v is not reachable from the root. |
27 * |
22 * |
28 *bool conn() : true iff G is connected |
23 *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 *NodeIt root() : returns the root |
28 *Node root() : returns the root |
33 * |
29 * |
34 */ |
30 */ |
35 |
31 |
36 #ifndef PRIM_H |
32 #ifndef HUGO_PRIM_H |
37 #define PRIM_H |
33 #define HUGO_PRIM_H |
38 |
34 |
39 #include <fib_heap.h> |
35 #include <fib_heap.h> |
40 |
36 #include <invalid.h> |
41 #include <iostream> |
|
42 |
37 |
43 namespace hugo { |
38 namespace hugo { |
44 |
39 |
45 template <typename Graph, typename T, |
40 template <typename Graph, typename T, |
46 typename Heap=FibHeap<typename Graph::NodeIt, T, |
41 typename Heap=FibHeap<typename Graph::Node, T, |
47 typename Graph::NodeMap<int> > > |
42 typename Graph::NodeMap<int> >, |
|
43 typename LengthMap=typename Graph::EdgeMap<T> > |
48 class Prim{ |
44 class Prim{ |
|
45 typedef typename Graph::Node Node; |
49 typedef typename Graph::NodeIt NodeIt; |
46 typedef typename Graph::NodeIt NodeIt; |
50 typedef typename Graph::EachNodeIt EachNodeIt; |
47 typedef typename Graph::Edge Edge; |
51 typedef typename Graph::EdgeIt EdgeIt; |
|
52 typedef typename Graph::OutEdgeIt OutEdgeIt; |
48 typedef typename Graph::OutEdgeIt OutEdgeIt; |
53 typedef typename Graph::InEdgeIt InEdgeIt; |
49 typedef typename Graph::InEdgeIt InEdgeIt; |
54 |
50 |
55 Graph& G; |
51 const Graph& G; |
56 NodeIt r; |
52 const LengthMap& edge_weight; |
57 typename Graph::NodeMap<EdgeIt> tree_edge; |
53 typename Graph::NodeMap<Edge> tree_edge; |
58 typename Graph::NodeMap<T> min_weight; |
54 typename Graph::NodeMap<T> min_weight; |
59 typename Graph::EdgeMap<T>& edge_weight; |
55 typename Graph::NodeMap<bool> reach; |
60 typename Graph::NodeMap<bool> reached; |
|
61 |
56 |
62 public : |
57 public : |
63 |
58 |
64 Prim(Graph& _G, typename Graph::EdgeMap<T>& _edge_weight, |
59 Prim(Graph& _G, LengthMap& _edge_weight) : |
65 NodeIt const _r) : |
60 G(_G), edge_weight(_edge_weight), |
66 G(_G), r(_r), tree_edge(G), min_weight(G), |
61 tree_edge(_G,INVALID), min_weight(_G), reach(_G, false) { } |
67 edge_weight(_edge_weight), reached(G, false) { } |
|
68 |
62 |
69 Prim(Graph& _G, typename Graph::EdgeMap<T>& _edge_weight) : |
63 |
70 G(_G), tree_edge(G), min_weight(G), edge_weight(_edge_weight), reached(G, false) |
64 void run() { |
71 { |
65 NodeIt _r; |
72 EachNodeIt _r; //FIXME |
66 G.first(_r); |
73 G.getFirst(_r); |
67 run(_r); |
74 r=_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 typename Graph::NodeMap<bool> scanned(G, false); |
81 typename Graph::NodeMap<bool> scanned(G, false); |
81 typename Graph::NodeMap<int> heap_map(G,-1); |
82 typename Graph::NodeMap<int> heap_map(G,-1); |
82 |
83 |
83 Heap heap(heap_map); |
84 Heap heap(heap_map); |
84 |
85 |
85 heap.push(r,0); |
86 heap.push(r,0); |
86 reached.set(r, true); |
87 reach.set(r, true); |
87 |
88 |
88 while ( !heap.empty() ) { |
89 while ( !heap.empty() ) { |
89 |
90 |
90 NodeIt v=heap.top(); |
91 Node v=heap.top(); |
91 min_weight.set(v, heap.get(v)); |
92 min_weight.set(v, heap.get(v)); |
92 heap.pop(); |
93 heap.pop(); |
93 scanned.set(v,true); |
94 scanned.set(v,true); |
94 |
95 |
95 OutEdgeIt e; |
96 OutEdgeIt e; |
96 for( G.getFirst(e,v); G.valid(e); G.next(e)) { |
97 for( G.first(e,v); G.valid(e); G.next(e)) { |
97 NodeIt w=G.head(e); |
98 Node w=G.head(e); |
98 |
99 |
99 if ( !scanned.get(w) ) { |
100 if ( !scanned[w] ) { |
100 if ( !reached.get(w) ) { |
101 if ( !reach[w] ) { |
101 reached.set(w,true); |
102 reach.set(w,true); |
102 heap.push(w, edge_weight.get(e)); |
103 heap.push(w, edge_weight[e]); |
103 tree_edge.set(w,e); |
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 tree_edge.set(w,e); |
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 } |
109 } |
110 } |
110 |
111 |
111 InEdgeIt f; |
112 InEdgeIt f; |
112 for( G.getFirst(f,v); G.valid(f); G.next(f)) { |
113 for( G.first(f,v); G.valid(f); G.next(f)) { |
113 NodeIt w=G.tail(f); |
114 Node w=G.tail(f); |
114 |
115 |
115 if ( !scanned.get(w) ) { |
116 if ( !scanned[w] ) { |
116 if ( !reached.get(w) ) { |
117 if ( !reach[w] ) { |
117 reached.set(w,true); |
118 reach.set(w,true); |
118 heap.push(w, edge_weight.get(f)); |
119 heap.push(w, edge_weight[f]); |
119 tree_edge.set(w,f); |
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 tree_edge.set(w,f); |
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 } |
125 } |
126 } |
126 } |
127 } |
127 } |
128 } |
128 |
129 |
129 |
130 |
130 T weight() { |
131 T weight() { |
131 T w=0; |
132 T w=0; |
132 EachNodeIt u; |
133 NodeIt u; |
133 for ( G.getFirst(u) ; G.valid(u) ; G.next(u) ) w+=min_weight.get(u); |
134 for ( G.first(u) ; G.valid(u) ; G.next(u) ) w+=min_weight[u]; |
134 return w; |
135 return w; |
135 } |
136 } |
136 |
137 |
137 |
138 |
138 EdgeIt tree(NodeIt v) { |
139 Edge tree(Node v) { |
139 return tree_edge.get(v); |
140 return tree_edge[v]; |
140 } |
141 } |
141 |
142 |
142 |
143 |
143 bool conn() { |
144 bool conn() { |
144 bool c=true; |
145 bool c=true; |
145 EachNodeIt u; |
146 NodeIt u; |
146 for ( G.getFirst(u) ; G.valid(u) ; G.next(u) ) |
147 for ( G.first(u) ; G.valid(u) ; G.next(u) ) |
147 if ( !reached.get(u) ) { |
148 if ( !reached[u] ) { |
148 c=false; |
149 c=false; |
149 break; |
150 break; |
150 } |
151 } |
151 return c; |
152 return c; |
152 } |
153 } |
153 |
154 |
154 |
155 |
155 bool reach(NodeIt v) { |
156 bool reached(Node v) { |
156 return reached.get(v); |
157 return reached[v]; |
157 } |
158 } |
158 |
159 |
159 |
160 |
160 NodeIt root() { |
161 Node root() { |
161 return r; |
162 return r; |
162 } |
163 } |
163 |
164 |
164 }; |
165 }; |
165 |
166 |