diff -r 741f3108a90f -r e997802b855c src/work/marci/experiment/edmonds_karp_1.h --- a/src/work/marci/experiment/edmonds_karp_1.h Sat Nov 13 12:24:01 2004 +0000 +++ b/src/work/marci/experiment/edmonds_karp_1.h Sat Nov 13 12:53:28 2004 +0000 @@ -41,7 +41,7 @@ Edge() { } //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { } Number free() const { - if (resG->G.aNode(sym)==resG->G.tail(sym)) { + if (resG->G.aNode(sym)==resG->G.source(sym)) { return (resG->capacity.get(sym)-resG->flow.get(sym)); } else { return (resG->flow.get(sym)); @@ -49,7 +49,7 @@ } bool valid() const { return sym.valid(); } void augment(Number a) const { - if (resG->G.aNode(sym)==resG->G.tail(sym)) { + if (resG->G.aNode(sym)==resG->G.source(sym)) { resG->flow.set(sym, resG->flow.get(sym)+a); //resG->flow[sym]+=a; } else { @@ -97,8 +97,8 @@ return e; } - Node tail(Edge e) const { return G.aNode(e.sym); } - Node head(Edge e) const { return G.bNode(e.sym); } + Node source(Edge e) const { return G.aNode(e.sym); } + Node target(Edge e) const { return G.bNode(e.sym); } Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); } Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); } @@ -224,9 +224,9 @@ return e; } - Node tail(Edge e) const { + Node source(Edge e) const { return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } - Node head(Edge e) const { + Node target(Edge e) const { return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } Node aNode(OutEdgeIt e) const { @@ -286,15 +286,15 @@ while ( !bfs.finished() ) { ResGWOutEdgeIt e=bfs; if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { - Node v=res_graph.tail(e); - Node w=res_graph.head(e); + Node v=res_graph.source(e); + Node w=res_graph.target(e); pred.set(w, e); if (res_graph.valid(pred.get(v))) { free.set(w, std::min(free.get(v), res_graph.resCap(e))); } else { free.set(w, res_graph.resCap(e)); } - if (res_graph.head(e)==t) { _augment=true; break; } + if (res_graph.target(e)==t) { _augment=true; break; } } ++bfs; @@ -306,7 +306,7 @@ while (res_graph.valid(pred.get(n))) { ResGWEdge e=pred.get(n); res_graph.augment(e, augment_value); - n=res_graph.tail(e); + n=res_graph.source(e); } } @@ -323,7 +323,7 @@ void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; } int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; } bool get(const typename MapGraphWrapper::Edge& e) const { - return (dist.get(g->tail(e))head(e))); + return (dist.get(g->source(e))target(e))); } }; @@ -342,7 +342,7 @@ while ( !bfs.finished() ) { ResGWOutEdgeIt e=bfs; if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { - dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); + dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); } ++bfs; } //computing distances from s in the residual graph @@ -368,8 +368,8 @@ { typename FilterResGW::EdgeIt e; for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) { - //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { - typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); + //if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { + typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); original_edge.update(); original_edge.set(f, e); residual_capacity.update(); @@ -422,7 +422,7 @@ while (F.valid(pred.get(n))) { typename MG::Edge e=pred.get(n); res_graph.augment(original_edge.get(e), augment_value); - n=F.tail(e); + n=F.source(e); if (residual_capacity.get(e)==augment_value) F.erase(e); else @@ -467,15 +467,15 @@ ResGWOutEdgeIt e=bfs; if (res_graph.valid(e)) { if (bfs.isBNodeNewlyReached()) { - dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); - typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); + dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); + typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); original_edge.update(); original_edge.set(f, e); residual_capacity.update(); residual_capacity.set(f, res_graph.resCap(e)); } else { - if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) { - typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); + if (dist.get(res_graph.target(e))==(dist.get(res_graph.source(e))+1)) { + typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); original_edge.update(); original_edge.set(f, e); residual_capacity.update(); @@ -530,7 +530,7 @@ while (F.valid(pred.get(n))) { typename MG::Edge e=pred.get(n); res_graph.augment(original_edge.get(e), augment_value); - n=F.tail(e); + n=F.source(e); if (residual_capacity.get(e)==augment_value) F.erase(e); else @@ -556,7 +556,7 @@ while ( !bfs.finished() ) { ResGWOutEdgeIt e=bfs; if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { - dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); + dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); } ++bfs; } //computing distances from s in the residual graph @@ -632,7 +632,7 @@ while (erasing_res_graph.valid(pred.get(n))) { typename ErasingResGW::OutEdgeIt e=pred.get(n); res_graph.augment(e, augment_value); - n=erasing_res_graph.tail(e); + n=erasing_res_graph.source(e); if (res_graph.resCap(e)==0) erasing_res_graph.erase(e); } @@ -727,15 +727,15 @@ // while ( !bfs.finished() ) { // AugOutEdgeIt e=bfs; // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { -// Node v=res_graph.tail(e); -// Node w=res_graph.head(e); +// Node v=res_graph.source(e); +// Node w=res_graph.target(e); // pred.set(w, e); // if (res_graph.valid(pred.get(v))) { // free.set(w, std::min(free.get(v), res_graph.free(e))); // } else { // free.set(w, res_graph.free(e)); // } -// n=res_graph.head(e); +// n=res_graph.target(e); // if (T->get(n) && (used.get(n)<1) ) { // //Number u=0; // //for(InEdgeIt f=G->template first(n); G->valid(f); G->next(f)) @@ -757,7 +757,7 @@ // while (res_graph.valid(pred.get(n))) { // AugEdge e=pred.get(n); // res_graph.augment(e, augment_value); -// n=res_graph.tail(e); +// n=res_graph.source(e); // } // used.set(n, 1); //mind2 vegen jav // } @@ -798,7 +798,7 @@ // // while ( !bfs.finished() ) { // // AugOutEdgeIt e=bfs; // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { -// // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); +// // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); // // } // // ++bfs; @@ -820,8 +820,8 @@ // // //Making F to the graph containing the edges of the residual graph // // //which are in some shortest paths // // for(typename AugGraph::EdgeIt e=res_graph.template first(); res_graph.valid(e); res_graph.next(e)) { -// // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { -// // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); +// // if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { +// // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); // // original_edge.update(); // // original_edge.set(f, e); // // residual_capacity.update(); @@ -873,7 +873,7 @@ // // while (F.valid(pred.get(n))) { // // typename MutableGraph::Edge e=pred.get(n); // // res_graph.augment(original_edge.get(e), augment_value); -// // n=F.tail(e); +// // n=F.source(e); // // if (residual_capacity.get(e)==augment_value) // // F.erase(e); // // else @@ -924,7 +924,7 @@ // while ( !bfs.finished() ) { // typename ErasingResGraphWrapper::OutEdgeIt e=bfs; // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { -// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); +// dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); // } // ++bfs; // } //computing distances from s in the residual graph @@ -1001,7 +1001,7 @@ // while (res_graph.valid(pred.get(n))) { // EAugEdge e=pred.get(n); // res_graph.augment(e, augment_value); -// n=res_graph.tail(e); +// n=res_graph.source(e); // if (res_graph.free(e)==0) // res_graph.erase(e); // } @@ -1094,17 +1094,17 @@ // // while ( !bfs.finished() ) { // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); // // if (e.valid() && bfs.isBNodeNewlyReached()) { -// // Node v=res_graph.tail(e); -// // Node w=res_graph.head(e); +// // Node v=res_graph.source(e); +// // Node w=res_graph.target(e); // // pred.set(w, e); // // if (pred.get(v).valid()) { // // free.set(w, std::min(free.get(v), e.free())); // // } else { // // free.set(w, e.free()); // // } -// // if (TMap.get(res_graph.head(e))) { +// // if (TMap.get(res_graph.target(e))) { // // _augment=true; -// // reached_t_node=res_graph.head(e); +// // reached_t_node=res_graph.target(e); // // break; // // } // // } @@ -1118,7 +1118,7 @@ // // while (pred.get(n).valid()) { // // AugEdge e=pred.get(n); // // e.augment(augment_value); -// // n=res_graph.tail(e); +// // n=res_graph.source(e); // // } // // }