1.1 --- a/src/work/marci/oldies/edmonds_karp.h Sat Nov 13 12:24:01 2004 +0000
1.2 +++ b/src/work/marci/oldies/edmonds_karp.h Sat Nov 13 12:53:28 2004 +0000
1.3 @@ -59,15 +59,15 @@
1.4 while ( !bfs.finished() ) {
1.5 ResGWOutEdgeIt e=bfs;
1.6 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.7 - Node v=res_graph.tail(e);
1.8 - Node w=res_graph.head(e);
1.9 + Node v=res_graph.source(e);
1.10 + Node w=res_graph.target(e);
1.11 pred.set(w, e);
1.12 if (res_graph.valid(pred[v])) {
1.13 free.set(w, std::min(free[v], res_graph.resCap(e)));
1.14 } else {
1.15 free.set(w, res_graph.resCap(e));
1.16 }
1.17 - if (res_graph.head(e)==t) { _augment=true; break; }
1.18 + if (res_graph.target(e)==t) { _augment=true; break; }
1.19 }
1.20
1.21 ++bfs;
1.22 @@ -79,7 +79,7 @@
1.23 while (res_graph.valid(pred[n])) {
1.24 ResGWEdge e=pred[n];
1.25 res_graph.augment(e, augment_value);
1.26 - n=res_graph.tail(e);
1.27 + n=res_graph.source(e);
1.28 }
1.29 }
1.30
1.31 @@ -101,9 +101,9 @@
1.32 // int get(const typename MapGraphWrapper::Node& n) const {
1.33 // return dist[n]; }
1.34 // bool get(const typename MapGraphWrapper::Edge& e) const {
1.35 -// return (dist.get(g->tail(e))<dist.get(g->head(e))); }
1.36 +// return (dist.get(g->source(e))<dist.get(g->target(e))); }
1.37 bool operator[](const typename MapGraphWrapper::Edge& e) const {
1.38 - return (dist[g->tail(e)]<dist[g->head(e)]);
1.39 + return (dist[g->source(e)]<dist[g->target(e)]);
1.40 }
1.41 };
1.42
1.43 @@ -123,7 +123,7 @@
1.44 while ( !bfs.finished() ) {
1.45 ResGWOutEdgeIt e=bfs;
1.46 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.47 - dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
1.48 + dist.set(res_graph.target(e), dist[res_graph.source(e)]+1);
1.49 }
1.50 ++bfs;
1.51 } //computing distances from s in the residual graph
1.52 @@ -152,8 +152,8 @@
1.53 {
1.54 typename FilterResGW::EdgeIt e;
1.55 for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) {
1.56 - //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
1.57 - typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
1.58 + //if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) {
1.59 + typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]);
1.60 original_edge.update();
1.61 original_edge.set(f, e);
1.62 residual_capacity.update();
1.63 @@ -206,7 +206,7 @@
1.64 while (F.valid(pred[n])) {
1.65 typename MG::Edge e=pred[n];
1.66 res_graph.augment(original_edge[e], augment_value);
1.67 - n=F.tail(e);
1.68 + n=F.source(e);
1.69 if (residual_capacity[e]==augment_value)
1.70 F.erase(e);
1.71 else
1.72 @@ -254,15 +254,15 @@
1.73 ResGWOutEdgeIt e=bfs;
1.74 if (res_graph.valid(e)) {
1.75 if (bfs.isBNodeNewlyReached()) {
1.76 - dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
1.77 - typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
1.78 + dist.set(res_graph.target(e), dist[res_graph.source(e)]+1);
1.79 + typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]);
1.80 original_edge.update();
1.81 original_edge.set(f, e);
1.82 residual_capacity.update();
1.83 residual_capacity.set(f, res_graph.resCap(e));
1.84 } else {
1.85 - if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) {
1.86 - typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
1.87 + if (dist[res_graph.target(e)]==(dist[res_graph.source(e)]+1)) {
1.88 + typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]);
1.89 original_edge.update();
1.90 original_edge.set(f, e);
1.91 residual_capacity.update();
1.92 @@ -316,7 +316,7 @@
1.93 while (F.valid(pred[n])) {
1.94 typename MG::Edge e=pred[n];
1.95 res_graph.augment(original_edge[e], augment_value);
1.96 - n=F.tail(e);
1.97 + n=F.source(e);
1.98 if (residual_capacity[e]==augment_value)
1.99 F.erase(e);
1.100 else
1.101 @@ -343,7 +343,7 @@
1.102 while ( !bfs.finished() ) {
1.103 ResGWOutEdgeIt e=bfs;
1.104 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.105 - dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
1.106 + dist.set(res_graph.target(e), dist[res_graph.source(e)]+1);
1.107 }
1.108 ++bfs;
1.109 } //computing distances from s in the residual graph
1.110 @@ -440,7 +440,7 @@
1.111 while (erasing_res_graph.valid(pred[n])) {
1.112 typename ErasingResGW::OutEdgeIt e=pred[n];
1.113 res_graph.augment(e, augment_value);
1.114 - n=erasing_res_graph.tail(e);
1.115 + n=erasing_res_graph.source(e);
1.116 if (res_graph.resCap(e)==0)
1.117 erasing_res_graph.erase(e);
1.118 }
1.119 @@ -535,15 +535,15 @@
1.120 // while ( !bfs.finished() ) {
1.121 // AugOutEdgeIt e=bfs;
1.122 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.123 -// Node v=res_graph.tail(e);
1.124 -// Node w=res_graph.head(e);
1.125 +// Node v=res_graph.source(e);
1.126 +// Node w=res_graph.target(e);
1.127 // pred.set(w, e);
1.128 // if (res_graph.valid(pred.get(v))) {
1.129 // free.set(w, std::min(free.get(v), res_graph.free(e)));
1.130 // } else {
1.131 // free.set(w, res_graph.free(e));
1.132 // }
1.133 -// n=res_graph.head(e);
1.134 +// n=res_graph.target(e);
1.135 // if (T->get(n) && (used.get(n)<1) ) {
1.136 // //Num u=0;
1.137 // //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
1.138 @@ -565,7 +565,7 @@
1.139 // while (res_graph.valid(pred.get(n))) {
1.140 // AugEdge e=pred.get(n);
1.141 // res_graph.augment(e, augment_value);
1.142 -// n=res_graph.tail(e);
1.143 +// n=res_graph.source(e);
1.144 // }
1.145 // used.set(n, 1); //mind2 vegen jav
1.146 // }
1.147 @@ -606,7 +606,7 @@
1.148 // // while ( !bfs.finished() ) {
1.149 // // AugOutEdgeIt e=bfs;
1.150 // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.151 -// // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.152 +// // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1);
1.153 // // }
1.154
1.155 // // ++bfs;
1.156 @@ -628,8 +628,8 @@
1.157 // // //Making F to the graph containing the edges of the residual graph
1.158 // // //which are in some shortest paths
1.159 // // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
1.160 -// // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
1.161 -// // 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.162 +// // if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) {
1.163 +// // 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.164 // // original_edge.update();
1.165 // // original_edge.set(f, e);
1.166 // // residual_capacity.update();
1.167 @@ -681,7 +681,7 @@
1.168 // // while (F.valid(pred.get(n))) {
1.169 // // typename MutableGraph::Edge e=pred.get(n);
1.170 // // res_graph.augment(original_edge.get(e), augment_value);
1.171 -// // n=F.tail(e);
1.172 +// // n=F.source(e);
1.173 // // if (residual_capacity.get(e)==augment_value)
1.174 // // F.erase(e);
1.175 // // else
1.176 @@ -732,7 +732,7 @@
1.177 // while ( !bfs.finished() ) {
1.178 // typename ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::OutEdgeIt e=bfs;
1.179 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.180 -// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.181 +// dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1);
1.182 // }
1.183 // ++bfs;
1.184 // } //computing distances from s in the residual graph
1.185 @@ -809,7 +809,7 @@
1.186 // while (res_graph.valid(pred.get(n))) {
1.187 // EAugEdge e=pred.get(n);
1.188 // res_graph.augment(e, augment_value);
1.189 -// n=res_graph.tail(e);
1.190 +// n=res_graph.source(e);
1.191 // if (res_graph.free(e)==0)
1.192 // res_graph.erase(e);
1.193 // }
1.194 @@ -902,17 +902,17 @@
1.195 // // while ( !bfs.finished() ) {
1.196 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
1.197 // // if (e.valid() && bfs.isBNodeNewlyReached()) {
1.198 -// // Node v=res_graph.tail(e);
1.199 -// // Node w=res_graph.head(e);
1.200 +// // Node v=res_graph.source(e);
1.201 +// // Node w=res_graph.target(e);
1.202 // // pred.set(w, e);
1.203 // // if (pred.get(v).valid()) {
1.204 // // free.set(w, std::min(free.get(v), e.free()));
1.205 // // } else {
1.206 // // free.set(w, e.free());
1.207 // // }
1.208 -// // if (TMap.get(res_graph.head(e))) {
1.209 +// // if (TMap.get(res_graph.target(e))) {
1.210 // // _augment=true;
1.211 -// // reached_t_node=res_graph.head(e);
1.212 +// // reached_t_node=res_graph.target(e);
1.213 // // break;
1.214 // // }
1.215 // // }
1.216 @@ -926,7 +926,7 @@
1.217 // // while (pred.get(n).valid()) {
1.218 // // AugEdge e=pred.get(n);
1.219 // // e.augment(augment_value);
1.220 -// // n=res_graph.tail(e);
1.221 +// // n=res_graph.source(e);
1.222 // // }
1.223 // // }
1.224