equal
deleted
inserted
replaced
9 |
9 |
10 #include <hugo/dijkstra.h> |
10 #include <hugo/dijkstra.h> |
11 #include <hugo/graph_wrapper.h> |
11 #include <hugo/graph_wrapper.h> |
12 #include <hugo/maps.h> |
12 #include <hugo/maps.h> |
13 #include <vector> |
13 #include <vector> |
14 #include <hugo/for_each_macros.h> |
|
15 |
14 |
16 namespace hugo { |
15 namespace hugo { |
17 |
16 |
18 /// \addtogroup flowalgs |
17 /// \addtogroup flowalgs |
19 /// @{ |
18 /// @{ |
114 int run(Node s, Node t, int k) { |
113 int run(Node s, Node t, int k) { |
115 |
114 |
116 //Resetting variables from previous runs |
115 //Resetting variables from previous runs |
117 total_length = 0; |
116 total_length = 0; |
118 |
117 |
119 for(typename Graph::EdgeIt e=loopFirst(typename Graph::EdgeIt(), (G)); e!=INVALID; ++e){ |
118 for (typename Graph::EdgeIt e(G); e!=INVALID; ++e) flow.set(e, 0); |
120 flow.set(e,0); |
|
121 } |
|
122 |
119 |
123 //Initialize the potential to zero |
120 //Initialize the potential to zero |
124 for(typename Graph::NodeIt n=loopFirst(typename Graph::NodeIt(), (G)); n!=INVALID; ++n){ |
121 for (typename Graph::NodeIt n(G); n!=INVALID; ++n) potential.set(n, 0); |
125 potential.set(n,0); |
122 |
126 } |
|
127 |
|
128 |
|
129 |
123 |
130 //We need a residual graph |
124 //We need a residual graph |
131 ResGraphType res_graph(G, capacity, flow); |
125 ResGraphType res_graph(G, capacity, flow); |
132 |
126 |
133 |
127 |
142 //There are no k paths from s to t |
136 //There are no k paths from s to t |
143 break; |
137 break; |
144 }; |
138 }; |
145 |
139 |
146 //We have to change the potential |
140 //We have to change the potential |
147 //#define FOR_EACH_LOC(Ittype, e, g) for(Ittype e=loopFirst(Ittype(), (g)); (g).valid(e); (g).next(e)) |
141 for(typename ResGraphType::NodeIt n(res_graph); n!=INVALID; ++n) |
148 //FOR_EACH_LOC(typename ResGraphType::NodeIt, n, res_graph){ |
|
149 for(typename ResGraphType::NodeIt n=loopFirst(typename ResGraphType::NodeIt(), (res_graph)); n!=INVALID; ++n){ |
|
150 potential[n] += dijkstra.distMap()[n]; |
142 potential[n] += dijkstra.distMap()[n]; |
151 } |
|
152 |
143 |
153 |
144 |
154 //Augmenting on the sortest path |
145 //Augmenting on the sortest path |
155 Node n=t; |
146 Node n=t; |
156 ResGraphEdge e; |
147 ResGraphEdge e; |
195 /// |
186 /// |
196 ///\todo Is this OK here? |
187 ///\todo Is this OK here? |
197 bool checkComplementarySlackness(){ |
188 bool checkComplementarySlackness(){ |
198 Length mod_pot; |
189 Length mod_pot; |
199 Length fl_e; |
190 Length fl_e; |
200 //#define FOR_EACH_LOC(Ittype, e, g) for(Ittype e=loopFirst(Ittype(), (g)); (g).valid(e); (g).next(e)) |
191 for(typename Graph::EdgeIt e(G); e!=INVALID; ++e) { |
201 //FOR_EACH_LOC(typename Graph::EdgeIt, e, G){ |
|
202 for(typename Graph::EdgeIt e=loopFirst(typename Graph::EdgeIt(), (G)); e!=INVALID; ++e){ |
|
203 //C^{\Pi}_{i,j} |
192 //C^{\Pi}_{i,j} |
204 mod_pot = length[e]-potential[G.head(e)]+potential[G.tail(e)]; |
193 mod_pot = length[e]-potential[G.head(e)]+potential[G.tail(e)]; |
205 fl_e = flow[e]; |
194 fl_e = flow[e]; |
206 // std::cout << fl_e << std::endl; |
195 // std::cout << fl_e << std::endl; |
207 if (0<fl_e && fl_e<capacity[e]){ |
196 if (0<fl_e && fl_e<capacity[e]){ |