1.1 --- a/src/work/marci/experiment/edmonds_karp.h Sat Nov 13 12:24:01 2004 +0000
1.2 +++ b/src/work/marci/experiment/edmonds_karp.h Sat Nov 13 12:53:28 2004 +0000
1.3 @@ -40,7 +40,7 @@
1.4 Edge() { }
1.5 //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }
1.6 Number free() const {
1.7 - if (resG->G.aNode(sym)==resG->G.tail(sym)) {
1.8 + if (resG->G.aNode(sym)==resG->G.source(sym)) {
1.9 return (resG->capacity.get(sym)-resG->flow.get(sym));
1.10 } else {
1.11 return (resG->flow.get(sym));
1.12 @@ -48,7 +48,7 @@
1.13 }
1.14 bool valid() const { return sym.valid(); }
1.15 void augment(Number a) const {
1.16 - if (resG->G.aNode(sym)==resG->G.tail(sym)) {
1.17 + if (resG->G.aNode(sym)==resG->G.source(sym)) {
1.18 resG->flow.set(sym, resG->flow.get(sym)+a);
1.19 //resG->flow[sym]+=a;
1.20 } else {
1.21 @@ -96,8 +96,8 @@
1.22 return e;
1.23 }
1.24
1.25 - Node tail(Edge e) const { return G.aNode(e.sym); }
1.26 - Node head(Edge e) const { return G.bNode(e.sym); }
1.27 + Node source(Edge e) const { return G.aNode(e.sym); }
1.28 + Node target(Edge e) const { return G.bNode(e.sym); }
1.29
1.30 Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
1.31 Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
1.32 @@ -223,9 +223,9 @@
1.33 return e;
1.34 }
1.35
1.36 - Node tail(Edge e) const {
1.37 + Node source(Edge e) const {
1.38 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
1.39 - Node head(Edge e) const {
1.40 + Node target(Edge e) const {
1.41 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
1.42
1.43 Node aNode(OutEdgeIt e) const {
1.44 @@ -287,15 +287,15 @@
1.45 while ( !bfs.finished() ) {
1.46 ResGWOutEdgeIt e=bfs;
1.47 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.48 - Node v=res_graph.tail(e);
1.49 - Node w=res_graph.head(e);
1.50 + Node v=res_graph.source(e);
1.51 + Node w=res_graph.target(e);
1.52 pred.set(w, e);
1.53 if (res_graph.valid(pred.get(v))) {
1.54 free.set(w, std::min(free.get(v), res_graph.resCap(e)));
1.55 } else {
1.56 free.set(w, res_graph.resCap(e));
1.57 }
1.58 - if (res_graph.head(e)==t) { _augment=true; break; }
1.59 + if (res_graph.target(e)==t) { _augment=true; break; }
1.60 }
1.61
1.62 ++bfs;
1.63 @@ -307,7 +307,7 @@
1.64 while (res_graph.valid(pred.get(n))) {
1.65 ResGWEdge e=pred.get(n);
1.66 res_graph.augment(e, augment_value);
1.67 - n=res_graph.tail(e);
1.68 + n=res_graph.source(e);
1.69 }
1.70 }
1.71
1.72 @@ -324,7 +324,7 @@
1.73 void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; }
1.74 int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; }
1.75 bool get(const typename MapGraphWrapper::Edge& e) const {
1.76 - return (dist.get(gw.tail(e))<dist.get(gw.head(e)));
1.77 + return (dist.get(gw.source(e))<dist.get(gw.target(e)));
1.78 }
1.79 };
1.80
1.81 @@ -343,7 +343,7 @@
1.82 while ( !bfs.finished() ) {
1.83 ResGWOutEdgeIt e=bfs;
1.84 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.85 - dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.86 + dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1);
1.87 }
1.88 ++bfs;
1.89 } //computing distances from s in the residual graph
1.90 @@ -369,8 +369,8 @@
1.91 {
1.92 typename FilterResGW::EdgeIt e;
1.93 for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) {
1.94 - //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
1.95 - typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
1.96 + //if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) {
1.97 + typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e)));
1.98 original_edge.update();
1.99 original_edge.set(f, e);
1.100 residual_capacity.update();
1.101 @@ -423,7 +423,7 @@
1.102 while (F.valid(pred.get(n))) {
1.103 typename MG::Edge e=pred.get(n);
1.104 res_graph.augment(original_edge.get(e), augment_value);
1.105 - n=F.tail(e);
1.106 + n=F.source(e);
1.107 if (residual_capacity.get(e)==augment_value)
1.108 F.erase(e);
1.109 else
1.110 @@ -468,15 +468,15 @@
1.111 ResGWOutEdgeIt e=bfs;
1.112 if (res_graph.valid(e)) {
1.113 if (bfs.isBNodeNewlyReached()) {
1.114 - dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.115 - typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
1.116 + dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1);
1.117 + typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e)));
1.118 original_edge.update();
1.119 original_edge.set(f, e);
1.120 residual_capacity.update();
1.121 residual_capacity.set(f, res_graph.resCap(e));
1.122 } else {
1.123 - if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
1.124 - typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
1.125 + if (dist.get(res_graph.target(e))==(dist.get(res_graph.source(e))+1)) {
1.126 + typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e)));
1.127 original_edge.update();
1.128 original_edge.set(f, e);
1.129 residual_capacity.update();
1.130 @@ -531,7 +531,7 @@
1.131 while (F.valid(pred.get(n))) {
1.132 typename MG::Edge e=pred.get(n);
1.133 res_graph.augment(original_edge.get(e), augment_value);
1.134 - n=F.tail(e);
1.135 + n=F.source(e);
1.136 if (residual_capacity.get(e)==augment_value)
1.137 F.erase(e);
1.138 else
1.139 @@ -557,7 +557,7 @@
1.140 while ( !bfs.finished() ) {
1.141 ResGWOutEdgeIt e=bfs;
1.142 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.143 - dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.144 + dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1);
1.145 }
1.146 ++bfs;
1.147 } //computing distances from s in the residual graph
1.148 @@ -633,7 +633,7 @@
1.149 while (erasing_res_graph.valid(pred.get(n))) {
1.150 typename ErasingResGW::OutEdgeIt e=pred.get(n);
1.151 res_graph.augment(e, augment_value);
1.152 - n=erasing_res_graph.tail(e);
1.153 + n=erasing_res_graph.source(e);
1.154 if (res_graph.resCap(e)==0)
1.155 erasing_res_graph.erase(e);
1.156 }
1.157 @@ -668,7 +668,7 @@
1.158 // while ( !bfs.finished() ) {
1.159 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
1.160 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.161 -// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.162 +// dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1);
1.163 // }
1.164 // ++bfs;
1.165 // } //computing distances from s in the residual graph
1.166 @@ -722,7 +722,7 @@
1.167 // while (res_graph.valid(pred.get(n))) {
1.168 // EAugEdge e=pred.get(n);
1.169 // res_graph.augment(e, augment_value);
1.170 -// n=res_graph.tail(e);
1.171 +// n=res_graph.source(e);
1.172 // if (res_graph.free(e)==0)
1.173 // res_graph.erase(e);
1.174 // }
1.175 @@ -817,15 +817,15 @@
1.176 // while ( !bfs.finished() ) {
1.177 // AugOutEdgeIt e=bfs;
1.178 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.179 -// Node v=res_graph.tail(e);
1.180 -// Node w=res_graph.head(e);
1.181 +// Node v=res_graph.source(e);
1.182 +// Node w=res_graph.target(e);
1.183 // pred.set(w, e);
1.184 // if (res_graph.valid(pred.get(v))) {
1.185 // free.set(w, std::min(free.get(v), res_graph.free(e)));
1.186 // } else {
1.187 // free.set(w, res_graph.free(e));
1.188 // }
1.189 -// n=res_graph.head(e);
1.190 +// n=res_graph.target(e);
1.191 // if (T->get(n) && (used.get(n)<1) ) {
1.192 // //Number u=0;
1.193 // //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
1.194 @@ -847,7 +847,7 @@
1.195 // while (res_graph.valid(pred.get(n))) {
1.196 // AugEdge e=pred.get(n);
1.197 // res_graph.augment(e, augment_value);
1.198 -// n=res_graph.tail(e);
1.199 +// n=res_graph.source(e);
1.200 // }
1.201 // used.set(n, 1); //mind2 vegen jav
1.202 // }
1.203 @@ -888,7 +888,7 @@
1.204 // // while ( !bfs.finished() ) {
1.205 // // AugOutEdgeIt e=bfs;
1.206 // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.207 -// // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.208 +// // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1);
1.209 // // }
1.210
1.211 // // ++bfs;
1.212 @@ -910,8 +910,8 @@
1.213 // // //Making F to the graph containing the edges of the residual graph
1.214 // // //which are in some shortest paths
1.215 // // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
1.216 -// // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
1.217 -// // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
1.218 +// // if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) {
1.219 +// // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e)));
1.220 // // original_edge.update();
1.221 // // original_edge.set(f, e);
1.222 // // residual_capacity.update();
1.223 @@ -963,7 +963,7 @@
1.224 // // while (F.valid(pred.get(n))) {
1.225 // // typename MutableGraph::Edge e=pred.get(n);
1.226 // // res_graph.augment(original_edge.get(e), augment_value);
1.227 -// // n=F.tail(e);
1.228 +// // n=F.source(e);
1.229 // // if (residual_capacity.get(e)==augment_value)
1.230 // // F.erase(e);
1.231 // // else
1.232 @@ -1014,7 +1014,7 @@
1.233 // while ( !bfs.finished() ) {
1.234 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
1.235 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.236 -// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.237 +// dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1);
1.238 // }
1.239 // ++bfs;
1.240 // } //computing distances from s in the residual graph
1.241 @@ -1091,7 +1091,7 @@
1.242 // while (res_graph.valid(pred.get(n))) {
1.243 // EAugEdge e=pred.get(n);
1.244 // res_graph.augment(e, augment_value);
1.245 -// n=res_graph.tail(e);
1.246 +// n=res_graph.source(e);
1.247 // if (res_graph.free(e)==0)
1.248 // res_graph.erase(e);
1.249 // }
1.250 @@ -1184,17 +1184,17 @@
1.251 // // while ( !bfs.finished() ) {
1.252 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
1.253 // // if (e.valid() && bfs.isBNodeNewlyReached()) {
1.254 -// // Node v=res_graph.tail(e);
1.255 -// // Node w=res_graph.head(e);
1.256 +// // Node v=res_graph.source(e);
1.257 +// // Node w=res_graph.target(e);
1.258 // // pred.set(w, e);
1.259 // // if (pred.get(v).valid()) {
1.260 // // free.set(w, std::min(free.get(v), e.free()));
1.261 // // } else {
1.262 // // free.set(w, e.free());
1.263 // // }
1.264 -// // if (TMap.get(res_graph.head(e))) {
1.265 +// // if (TMap.get(res_graph.target(e))) {
1.266 // // _augment=true;
1.267 -// // reached_t_node=res_graph.head(e);
1.268 +// // reached_t_node=res_graph.target(e);
1.269 // // break;
1.270 // // }
1.271 // // }
1.272 @@ -1208,7 +1208,7 @@
1.273 // // while (pred.get(n).valid()) {
1.274 // // AugEdge e=pred.get(n);
1.275 // // e.augment(augment_value);
1.276 -// // n=res_graph.tail(e);
1.277 +// // n=res_graph.source(e);
1.278 // // }
1.279 // // }
1.280