1.1 --- a/src/work/marci/experiment/edmonds_karp_1.h Sat Nov 13 12:24:01 2004 +0000
1.2 +++ b/src/work/marci/experiment/edmonds_karp_1.h Sat Nov 13 12:53:28 2004 +0000
1.3 @@ -41,7 +41,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 @@ -49,7 +49,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 @@ -97,8 +97,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 @@ -224,9 +224,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 @@ -286,15 +286,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 @@ -306,7 +306,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 @@ -323,7 +323,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(g->tail(e))<dist.get(g->head(e)));
1.77 + return (dist.get(g->source(e))<dist.get(g->target(e)));
1.78 }
1.79 };
1.80
1.81 @@ -342,7 +342,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 @@ -368,8 +368,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 @@ -422,7 +422,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 @@ -467,15 +467,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 @@ -530,7 +530,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 @@ -556,7 +556,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 @@ -632,7 +632,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 @@ -727,15 +727,15 @@
1.158 // while ( !bfs.finished() ) {
1.159 // AugOutEdgeIt e=bfs;
1.160 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.161 -// Node v=res_graph.tail(e);
1.162 -// Node w=res_graph.head(e);
1.163 +// Node v=res_graph.source(e);
1.164 +// Node w=res_graph.target(e);
1.165 // pred.set(w, e);
1.166 // if (res_graph.valid(pred.get(v))) {
1.167 // free.set(w, std::min(free.get(v), res_graph.free(e)));
1.168 // } else {
1.169 // free.set(w, res_graph.free(e));
1.170 // }
1.171 -// n=res_graph.head(e);
1.172 +// n=res_graph.target(e);
1.173 // if (T->get(n) && (used.get(n)<1) ) {
1.174 // //Number u=0;
1.175 // //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
1.176 @@ -757,7 +757,7 @@
1.177 // while (res_graph.valid(pred.get(n))) {
1.178 // AugEdge e=pred.get(n);
1.179 // res_graph.augment(e, augment_value);
1.180 -// n=res_graph.tail(e);
1.181 +// n=res_graph.source(e);
1.182 // }
1.183 // used.set(n, 1); //mind2 vegen jav
1.184 // }
1.185 @@ -798,7 +798,7 @@
1.186 // // while ( !bfs.finished() ) {
1.187 // // AugOutEdgeIt e=bfs;
1.188 // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.189 -// // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.190 +// // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1);
1.191 // // }
1.192
1.193 // // ++bfs;
1.194 @@ -820,8 +820,8 @@
1.195 // // //Making F to the graph containing the edges of the residual graph
1.196 // // //which are in some shortest paths
1.197 // // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
1.198 -// // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
1.199 -// // 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.200 +// // if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) {
1.201 +// // 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.202 // // original_edge.update();
1.203 // // original_edge.set(f, e);
1.204 // // residual_capacity.update();
1.205 @@ -873,7 +873,7 @@
1.206 // // while (F.valid(pred.get(n))) {
1.207 // // typename MutableGraph::Edge e=pred.get(n);
1.208 // // res_graph.augment(original_edge.get(e), augment_value);
1.209 -// // n=F.tail(e);
1.210 +// // n=F.source(e);
1.211 // // if (residual_capacity.get(e)==augment_value)
1.212 // // F.erase(e);
1.213 // // else
1.214 @@ -924,7 +924,7 @@
1.215 // while ( !bfs.finished() ) {
1.216 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
1.217 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.218 -// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.219 +// dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1);
1.220 // }
1.221 // ++bfs;
1.222 // } //computing distances from s in the residual graph
1.223 @@ -1001,7 +1001,7 @@
1.224 // while (res_graph.valid(pred.get(n))) {
1.225 // EAugEdge e=pred.get(n);
1.226 // res_graph.augment(e, augment_value);
1.227 -// n=res_graph.tail(e);
1.228 +// n=res_graph.source(e);
1.229 // if (res_graph.free(e)==0)
1.230 // res_graph.erase(e);
1.231 // }
1.232 @@ -1094,17 +1094,17 @@
1.233 // // while ( !bfs.finished() ) {
1.234 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
1.235 // // if (e.valid() && bfs.isBNodeNewlyReached()) {
1.236 -// // Node v=res_graph.tail(e);
1.237 -// // Node w=res_graph.head(e);
1.238 +// // Node v=res_graph.source(e);
1.239 +// // Node w=res_graph.target(e);
1.240 // // pred.set(w, e);
1.241 // // if (pred.get(v).valid()) {
1.242 // // free.set(w, std::min(free.get(v), e.free()));
1.243 // // } else {
1.244 // // free.set(w, e.free());
1.245 // // }
1.246 -// // if (TMap.get(res_graph.head(e))) {
1.247 +// // if (TMap.get(res_graph.target(e))) {
1.248 // // _augment=true;
1.249 -// // reached_t_node=res_graph.head(e);
1.250 +// // reached_t_node=res_graph.target(e);
1.251 // // break;
1.252 // // }
1.253 // // }
1.254 @@ -1118,7 +1118,7 @@
1.255 // // while (pred.get(n).valid()) {
1.256 // // AugEdge e=pred.get(n);
1.257 // // e.augment(augment_value);
1.258 -// // n=res_graph.tail(e);
1.259 +// // n=res_graph.source(e);
1.260 // // }
1.261 // // }
1.262