diff -r f2994a2b10b2 -r a82713ed19f3 src/work/marci/augmenting_flow.h --- a/src/work/marci/augmenting_flow.h Tue Aug 31 13:40:07 2004 +0000 +++ b/src/work/marci/augmenting_flow.h Tue Aug 31 17:54:22 2004 +0000 @@ -11,7 +11,7 @@ #include #include #include -#include +//#include /// \file /// \brief Maximum flow algorithms. @@ -1082,8 +1082,8 @@ Num flowValue() const { Num a=0; - FOR_EACH_INC_LOC(InEdgeIt, e, *g, t) a+=(*flow)[e]; - FOR_EACH_INC_LOC(OutEdgeIt, e, *g, t) a-=(*flow)[e]; + for (InEdgeIt e(*g, t); e!=INVALID; ++e) a+=(*flow)[e]; + for (OutEdgeIt e(*g, t); e!=INVALID; ++e) a-=(*flow)[e]; return a; //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan } @@ -1121,7 +1121,7 @@ bool _augment=false; //ReachedMap level(res_graph); - FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0); + for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0); BfsIterator bfs(res_graph, level); bfs.pushAndSetReached(s); @@ -1132,7 +1132,7 @@ //searching for augmenting path while ( !bfs.finished() ) { - ResGWOutEdgeIt e=bfs; + ResGWEdge e=bfs; if (e!=INVALID && bfs.isBNodeNewlyReached()) { Node v=res_graph.tail(e); Node w=res_graph.head(e); @@ -1169,7 +1169,7 @@ bool _augment=false; if (status!=AFTER_FAST_AUGMENTING) { - FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0); + for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0); number_of_augmentations=1; } else { ++number_of_augmentations; @@ -1189,7 +1189,7 @@ //searching for augmenting path while ( !bfs.finished() ) { - ResGWOutEdgeIt e=bfs; + ResGWEdge e=bfs; if (e!=INVALID && bfs.isBNodeNewlyReached()) { Node v=res_graph.tail(e); Node w=res_graph.head(e); @@ -1231,7 +1231,7 @@ //bfs for distances on the residual graph //ReachedMap level(res_graph); - FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0); + for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0); BfsIterator bfs(res_graph, level); bfs.pushAndSetReached(s); typename ResGW::template NodeMap @@ -1255,7 +1255,7 @@ typename MG::template EdgeMap residual_capacity(F); while ( !bfs.finished() ) { - ResGWOutEdgeIt e=bfs; + ResGWEdge e=bfs; if (e!=INVALID) { if (bfs.isBNodeNewlyReached()) { dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); @@ -1296,8 +1296,8 @@ ++dfs; if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { if (dfs.isBNodeNewlyReached()) { - typename MG::Node v=F.aNode(dfs); - typename MG::Node w=F.bNode(dfs); + typename MG::Node v=F.tail(dfs); + typename MG::Node w=F.head(dfs); pred.set(w, dfs); if (pred[v]!=INVALID) { free.set(w, std::min(free[v], residual_capacity[dfs])); @@ -1345,20 +1345,20 @@ ResGW res_graph(*g, *capacity, *flow); //ReachedMap level(res_graph); - FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0); + for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0); BfsIterator bfs(res_graph, level); bfs.pushAndSetReached(s); DistanceMap dist(res_graph); while ( !bfs.finished() ) { - ResGWOutEdgeIt e=bfs; + ResGWEdge e=bfs; if (e!=INVALID && bfs.isBNodeNewlyReached()) { dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); } ++bfs; } //computing distances from s in the residual graph - //Subgraph containing the edges on some shortest paths + //Subgraph containing the edges on some shortest paths ConstMap true_map(true); typedef SubGraphWrapper, DistanceMap > FilterResGW; @@ -1366,17 +1366,17 @@ //Subgraph, which is able to delete edges which are already //met by the dfs - typename FilterResGW::template NodeMap + typename FilterResGW::template NodeMap first_out_edges(filter_res_graph); typename FilterResGW::NodeIt v; for(filter_res_graph.first(v); v!=INVALID; ++v) { - typename FilterResGW::OutEdgeIt e; - filter_res_graph.first(e, v); - first_out_edges.set(v, e); + typename FilterResGW::OutEdgeIt e; + filter_res_graph.first(e, v); + first_out_edges.set(v, e); } typedef ErasingFirstGraphWrapper > ErasingResGW; + template NodeMap > ErasingResGW; ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges); bool __augment=true; @@ -1389,8 +1389,7 @@ typename ErasingResGW::template NodeMap > dfs(erasing_res_graph); typename ErasingResGW:: - template NodeMap - pred(erasing_res_graph); + template NodeMap pred(erasing_res_graph); pred.set(s, INVALID); //invalid iterators for sources @@ -1398,31 +1397,32 @@ free1(erasing_res_graph); dfs.pushAndSetReached - ///\bug hugo 0.2 + /// \bug hugo 0.2 (typename ErasingResGW::Node (typename FilterResGW::Node (typename ResGW::Node(s) ) ) ); + while (!dfs.finished()) { ++dfs; - if (erasing_res_graph.valid(typename ErasingResGW::OutEdgeIt(dfs))) + if (typename ErasingResGW::Edge(dfs)!=INVALID) { if (dfs.isBNodeNewlyReached()) { - typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs); - typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs); + typename ErasingResGW::Node v=erasing_res_graph.tail(dfs); + typename ErasingResGW::Node w=erasing_res_graph.head(dfs); - pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs)); + pred.set(w, typename ErasingResGW::Edge(dfs)); if (pred[v]!=INVALID) { free1.set (w, std::min(free1[v], res_graph.resCap - (typename ErasingResGW::OutEdgeIt(dfs)))); + (typename ErasingResGW::Edge(dfs)))); } else { free1.set (w, res_graph.resCap - (typename ErasingResGW::OutEdgeIt(dfs))); + (typename ErasingResGW::Edge(dfs))); } if (w==t) { @@ -1449,8 +1449,8 @@ // typename ErasingResGW::Node b2; // Num j2=a2[b2]; Num augment_value=free1[n]; - while (erasing_res_graph.valid(pred[n])) { - typename ErasingResGW::OutEdgeIt e=pred[n]; + while (pred[n]!=INVALID) { + typename ErasingResGW::Edge e=pred[n]; res_graph.augment(e, augment_value); n=erasing_res_graph.tail(e); if (res_graph.resCap(e)==0)