1.1 --- a/src/work/marci/edmonds_karp.h Thu Apr 29 10:16:46 2004 +0000
1.2 +++ b/src/work/marci/edmonds_karp.h Thu Apr 29 10:29:51 2004 +0000
1.3 @@ -14,8 +14,8 @@
1.4
1.5 namespace hugo {
1.6
1.7 - template <typename Graph, typename Number,
1.8 - typename CapacityMap, typename FlowMap>
1.9 + template <typename Graph, typename Num,
1.10 + typename CapMap, typename FlowMap>
1.11 class MaxFlow {
1.12 protected:
1.13 typedef typename Graph::Node Node;
1.14 @@ -26,9 +26,9 @@
1.15 const Graph* g;
1.16 Node s;
1.17 Node t;
1.18 - const CapacityMap* capacity;
1.19 + const CapMap* capacity;
1.20 FlowMap* flow;
1.21 - typedef ResGraphWrapper<const Graph, Number, CapacityMap, FlowMap> ResGW;
1.22 + typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
1.23 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
1.24 typedef typename ResGW::Edge ResGWEdge;
1.25 //typedef typename ResGW::template NodeMap<bool> ReachedMap;
1.26 @@ -37,7 +37,7 @@
1.27 //reached is called level because of compatibility with preflow
1.28 public:
1.29
1.30 - MaxFlow(const Graph& _g, Node _s, Node _t, const CapacityMap& _capacity,
1.31 + MaxFlow(const Graph& _g, Node _s, Node _t, const CapMap& _capacity,
1.32 FlowMap& _flow) :
1.33 g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow), level(_g) { }
1.34
1.35 @@ -53,7 +53,7 @@
1.36 typename ResGW::template NodeMap<ResGWEdge> pred(res_graph);
1.37 pred.set(s, INVALID);
1.38
1.39 - typename ResGW::template NodeMap<Number> free(res_graph);
1.40 + typename ResGW::template NodeMap<Num> free(res_graph);
1.41
1.42 //searching for augmenting path
1.43 while ( !bfs.finished() ) {
1.44 @@ -75,7 +75,7 @@
1.45
1.46 if (_augment) {
1.47 Node n=t;
1.48 - Number augment_value=free[t];
1.49 + Num augment_value=free[t];
1.50 while (res_graph.valid(pred[n])) {
1.51 ResGWEdge e=pred[n];
1.52 res_graph.augment(e, augment_value);
1.53 @@ -145,7 +145,7 @@
1.54 typename MG::Node sF=res_graph_to_F[s];
1.55 typename MG::Node tF=res_graph_to_F[t];
1.56 typename MG::template EdgeMap<ResGWEdge> original_edge(F);
1.57 - typename MG::template EdgeMap<Number> residual_capacity(F);
1.58 + typename MG::template EdgeMap<Num> residual_capacity(F);
1.59
1.60 //Making F to the graph containing the edges of the residual graph
1.61 //which are in some shortest paths
1.62 @@ -173,7 +173,7 @@
1.63 pred.set(sF, INVALID);
1.64 //invalid iterators for sources
1.65
1.66 - typename MG::template NodeMap<Number> free(F);
1.67 + typename MG::template NodeMap<Num> free(F);
1.68
1.69 dfs.pushAndSetReached(sF);
1.70 while (!dfs.finished()) {
1.71 @@ -202,7 +202,7 @@
1.72
1.73 if (__augment) {
1.74 typename MG::Node n=tF;
1.75 - Number augment_value=free[tF];
1.76 + Num augment_value=free[tF];
1.77 while (F.valid(pred[n])) {
1.78 typename MG::Edge e=pred[n];
1.79 res_graph.augment(original_edge[e], augment_value);
1.80 @@ -248,7 +248,7 @@
1.81 typename MG::Node sF=res_graph_to_F[s];
1.82 typename MG::Node tF=res_graph_to_F[t];
1.83 typename MG::template EdgeMap<ResGWEdge> original_edge(F);
1.84 - typename MG::template EdgeMap<Number> residual_capacity(F);
1.85 + typename MG::template EdgeMap<Num> residual_capacity(F);
1.86
1.87 while ( !bfs.finished() ) {
1.88 ResGWOutEdgeIt e=bfs;
1.89 @@ -283,7 +283,7 @@
1.90 pred.set(sF, INVALID);
1.91 //invalid iterators for sources
1.92
1.93 - typename MG::template NodeMap<Number> free(F);
1.94 + typename MG::template NodeMap<Num> free(F);
1.95
1.96 dfs.pushAndSetReached(sF);
1.97 while (!dfs.finished()) {
1.98 @@ -312,7 +312,7 @@
1.99
1.100 if (__augment) {
1.101 typename MG::Node n=tF;
1.102 - Number augment_value=free[tF];
1.103 + Num augment_value=free[tF];
1.104 while (F.valid(pred[n])) {
1.105 typename MG::Edge e=pred[n];
1.106 res_graph.augment(original_edge[e], augment_value);
1.107 @@ -385,7 +385,7 @@
1.108 pred.set(s, INVALID);
1.109 //invalid iterators for sources
1.110
1.111 - typename ErasingResGW::template NodeMap<Number>
1.112 + typename ErasingResGW::template NodeMap<Num>
1.113 free1(erasing_res_graph);
1.114
1.115 dfs.pushAndSetReached(
1.116 @@ -427,16 +427,16 @@
1.117
1.118 if (__augment) {
1.119 typename ErasingResGW::Node n=typename FilterResGW::Node(typename ResGW::Node(t));
1.120 -// typename ResGW::NodeMap<Number> a(res_graph);
1.121 +// typename ResGW::NodeMap<Num> a(res_graph);
1.122 // typename ResGW::Node b;
1.123 -// Number j=a[b];
1.124 -// typename FilterResGW::NodeMap<Number> a1(filter_res_graph);
1.125 +// Num j=a[b];
1.126 +// typename FilterResGW::NodeMap<Num> a1(filter_res_graph);
1.127 // typename FilterResGW::Node b1;
1.128 -// Number j1=a1[b1];
1.129 -// typename ErasingResGW::NodeMap<Number> a2(erasing_res_graph);
1.130 +// Num j1=a1[b1];
1.131 +// typename ErasingResGW::NodeMap<Num> a2(erasing_res_graph);
1.132 // typename ErasingResGW::Node b2;
1.133 -// Number j2=a2[b2];
1.134 - Number augment_value=free1[n];
1.135 +// Num j2=a2[b2];
1.136 + Num augment_value=free1[n];
1.137 while (erasing_res_graph.valid(pred[n])) {
1.138 typename ErasingResGW::OutEdgeIt e=pred[n];
1.139 res_graph.augment(e, augment_value);
1.140 @@ -469,8 +469,8 @@
1.141 }
1.142 }
1.143
1.144 - Number flowValue() {
1.145 - Number a=0;
1.146 + Num flowValue() {
1.147 + Num a=0;
1.148 OutEdgeIt e;
1.149 for(g->first(e, s); g->valid(e); g->next(e)) {
1.150 a+=(*flow)[e];
1.151 @@ -481,7 +481,7 @@
1.152 };
1.153
1.154
1.155 -// template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.156 +// template <typename Graph, typename Num, typename FlowMap, typename CapMap>
1.157 // class MaxMatching {
1.158 // public:
1.159 // typedef typename Graph::Node Node;
1.160 @@ -500,14 +500,14 @@
1.161 // //Node s;
1.162 // //Node t;
1.163 // FlowMap* flow;
1.164 -// const CapacityMap* capacity;
1.165 -// typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
1.166 +// const CapMap* capacity;
1.167 +// typedef ResGraphWrapper<Graph, Num, FlowMap, CapMap > AugGraph;
1.168 // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1.169 // typedef typename AugGraph::Edge AugEdge;
1.170 // typename Graph::NodeMap<int> used; //0
1.171
1.172 // public:
1.173 -// MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :
1.174 +// MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapMap& _capacity) :
1.175 // G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
1.176 // bool augmentOnShortestPath() {
1.177 // AugGraph res_graph(*G, *flow, *capacity);
1.178 @@ -518,7 +518,7 @@
1.179 // typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.180 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.181 // if ((S->get(s)) && (used.get(s)<1) ) {
1.182 -// //Number u=0;
1.183 +// //Num u=0;
1.184 // //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.185 // //u+=flow->get(e);
1.186 // //if (u<1) {
1.187 @@ -528,7 +528,7 @@
1.188 // }
1.189 // }
1.190
1.191 -// typename AugGraph::NodeMap<Number> free(res_graph);
1.192 +// typename AugGraph::NodeMap<Num> free(res_graph);
1.193
1.194 // Node n;
1.195 // //searching for augmenting path
1.196 @@ -545,7 +545,7 @@
1.197 // }
1.198 // n=res_graph.head(e);
1.199 // if (T->get(n) && (used.get(n)<1) ) {
1.200 -// //Number u=0;
1.201 +// //Num u=0;
1.202 // //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
1.203 // //u+=flow->get(f);
1.204 // //if (u<1) {
1.205 @@ -561,7 +561,7 @@
1.206 // if (_augment) {
1.207 // //Node n=t;
1.208 // used.set(n, 1); //mind2 vegen jav
1.209 -// Number augment_value=free.get(n);
1.210 +// Num augment_value=free.get(n);
1.211 // while (res_graph.valid(pred.get(n))) {
1.212 // AugEdge e=pred.get(n);
1.213 // res_graph.augment(e, augment_value);
1.214 @@ -588,7 +588,7 @@
1.215 // // //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.216 // // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.217 // // if (S->get(s)) {
1.218 -// // Number u=0;
1.219 +// // Num u=0;
1.220 // // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.221 // // u+=flow->get(e);
1.222 // // if (u<1) {
1.223 @@ -623,7 +623,7 @@
1.224 // // typename MutableGraph::Node tF=res_graph_to_F.get(t);
1.225
1.226 // // typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
1.227 -// // typename MutableGraph::EdgeMap<Number> residual_capacity(F);
1.228 +// // typename MutableGraph::EdgeMap<Num> residual_capacity(F);
1.229
1.230 // // //Making F to the graph containing the edges of the residual graph
1.231 // // //which are in some shortest paths
1.232 @@ -648,7 +648,7 @@
1.233 // // pred.set(sF, typename MutableGraph::Edge(INVALID));
1.234 // // //invalid iterators for sources
1.235
1.236 -// // typename MutableGraph::NodeMap<Number> free(F);
1.237 +// // typename MutableGraph::NodeMap<Num> free(F);
1.238
1.239 // // dfs.pushAndSetReached(sF);
1.240 // // while (!dfs.finished()) {
1.241 @@ -677,7 +677,7 @@
1.242
1.243 // // if (__augment) {
1.244 // // typename MutableGraph::Node n=tF;
1.245 -// // Number augment_value=free.get(tF);
1.246 +// // Num augment_value=free.get(tF);
1.247 // // while (F.valid(pred.get(n))) {
1.248 // // typename MutableGraph::Edge e=pred.get(n);
1.249 // // res_graph.augment(original_edge.get(e), augment_value);
1.250 @@ -696,8 +696,8 @@
1.251 // bool augmentOnBlockingFlow2() {
1.252 // bool _augment=false;
1.253
1.254 -// //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
1.255 -// typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
1.256 +// //typedef ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap> EAugGraph;
1.257 +// typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap> > EAugGraph;
1.258 // typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
1.259 // typedef typename EAugGraph::Edge EAugEdge;
1.260
1.261 @@ -705,15 +705,15 @@
1.262
1.263 // //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
1.264 // BfsIterator<
1.265 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
1.266 -// /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
1.267 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
1.268 +// ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>,
1.269 +// /*typename ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::OutEdgeIt,*/
1.270 +// ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::NodeMap<bool> > bfs(res_graph);
1.271
1.272
1.273 // //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.274 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.275 // if (S->get(s)) {
1.276 -// Number u=0;
1.277 +// Num u=0;
1.278 // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.279 // u+=flow->get(e);
1.280 // if (u<1) {
1.281 @@ -726,11 +726,11 @@
1.282
1.283 // //bfs.pushAndSetReached(s);
1.284
1.285 -// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
1.286 +// typename ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::
1.287 // NodeMap<int>& dist=res_graph.dist;
1.288
1.289 // while ( !bfs.finished() ) {
1.290 -// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
1.291 +// typename ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::OutEdgeIt e=bfs;
1.292 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.293 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.294 // }
1.295 @@ -750,13 +750,13 @@
1.296 // //pred.set(s, EAugEdge(INVALID));
1.297 // //invalid iterators for sources
1.298
1.299 -// typename EAugGraph::NodeMap<Number> free(res_graph);
1.300 +// typename EAugGraph::NodeMap<Num> free(res_graph);
1.301
1.302
1.303 // //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.304 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.305 // if (S->get(s)) {
1.306 -// Number u=0;
1.307 +// Num u=0;
1.308 // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.309 // u+=flow->get(e);
1.310 // if (u<1) {
1.311 @@ -787,7 +787,7 @@
1.312
1.313 // n=w;
1.314 // if (T->get(w)) {
1.315 -// Number u=0;
1.316 +// Num u=0;
1.317 // for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
1.318 // u+=flow->get(f);
1.319 // if (u<1) {
1.320 @@ -805,7 +805,7 @@
1.321
1.322 // if (__augment) {
1.323 // // typename EAugGraph::Node n=t;
1.324 -// Number augment_value=free.get(n);
1.325 +// Num augment_value=free.get(n);
1.326 // while (res_graph.valid(pred.get(n))) {
1.327 // EAugEdge e=pred.get(n);
1.328 // res_graph.augment(e, augment_value);
1.329 @@ -835,8 +835,8 @@
1.330 // // //std::cout<<std::endl;
1.331 // // }
1.332 // // }
1.333 -// Number flowValue() {
1.334 -// Number a=0;
1.335 +// Num flowValue() {
1.336 +// Num a=0;
1.337 // EdgeIt e;
1.338 // for(G->/*getF*/first(e); G->valid(e); G->next(e)) {
1.339 // a+=flow->get(e);
1.340 @@ -850,7 +850,7 @@
1.341
1.342
1.343
1.344 -// // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.345 +// // template <typename Graph, typename Num, typename FlowMap, typename CapMap>
1.346 // // class MaxFlow2 {
1.347 // // public:
1.348 // // typedef typename Graph::Node Node;
1.349 @@ -863,14 +863,14 @@
1.350 // // std::list<Node>& S;
1.351 // // std::list<Node>& T;
1.352 // // FlowMap& flow;
1.353 -// // const CapacityMap& capacity;
1.354 -// // typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
1.355 +// // const CapMap& capacity;
1.356 +// // typedef ResGraphWrapper<Graph, Num, FlowMap, CapMap > AugGraph;
1.357 // // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1.358 // // typedef typename AugGraph::Edge AugEdge;
1.359 // // typename Graph::NodeMap<bool> SMap;
1.360 // // typename Graph::NodeMap<bool> TMap;
1.361 // // public:
1.362 -// // MaxFlow2(const Graph& _G, std::list<Node>& _S, std::list<Node>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {
1.363 +// // MaxFlow2(const Graph& _G, std::list<Node>& _S, std::list<Node>& _T, FlowMap& _flow, const CapMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {
1.364 // // for(typename std::list<Node>::const_iterator i=S.begin();
1.365 // // i!=S.end(); ++i) {
1.366 // // SMap.set(*i, true);
1.367 @@ -896,7 +896,7 @@
1.368 // // typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.369 // // //filled up with invalid iterators
1.370
1.371 -// // typename AugGraph::NodeMap<Number> free(res_graph);
1.372 +// // typename AugGraph::NodeMap<Num> free(res_graph);
1.373
1.374 // // //searching for augmenting path
1.375 // // while ( !bfs.finished() ) {
1.376 @@ -922,7 +922,7 @@
1.377
1.378 // // if (_augment) {
1.379 // // Node n=reached_t_node;
1.380 -// // Number augment_value=free.get(reached_t_node);
1.381 +// // Num augment_value=free.get(reached_t_node);
1.382 // // while (pred.get(n).valid()) {
1.383 // // AugEdge e=pred.get(n);
1.384 // // e.augment(augment_value);
1.385 @@ -935,8 +935,8 @@
1.386 // // void run() {
1.387 // // while (augment()) { }
1.388 // // }
1.389 -// // Number flowValue() {
1.390 -// // Number a=0;
1.391 +// // Num flowValue() {
1.392 +// // Num a=0;
1.393 // // for(typename std::list<Node>::const_iterator i=S.begin();
1.394 // // i!=S.end(); ++i) {
1.395 // // for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {