diff -r 1ac27e476e25 -r 0631992fe7a1 src/work/edmonds_karp.hh --- a/src/work/edmonds_karp.hh Thu Feb 26 16:07:40 2004 +0000 +++ b/src/work/edmonds_karp.hh Fri Feb 27 12:39:15 2004 +0000 @@ -6,7 +6,7 @@ #include #include -#include +//#include namespace hugo { @@ -281,6 +281,7 @@ bool out_or_in; //1, iff out public: EdgeIt() : out_or_in(1) { } + //EdgeIt(const EdgeIt& e) : G(e.G), flow(e.flow), capacity(e.capacity), out(e.out), in(e.in), out_or_in(e.out_or_in) { } Number free() const { if (out_or_in) { return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out)); @@ -297,6 +298,23 @@ /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a); } } + void print() { + if (out_or_in) { + std::cout << "out "; + if (out.valid()) + std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out)); + else + std::cout << "invalid"; + } + else { + std::cout << "in "; + if (in.valid()) + std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in)); + else + std::cout << "invalid"; + } + std::cout << std::endl; + } }; class OutEdgeIt : public EdgeIt { @@ -308,11 +326,13 @@ G=&_G; flow=&_flow; capacity=&_capacity; - out=/*resG->*/G->template first(v); + //out=/*resG->*/G->template first(v); + G->getFirst(out, v); while( out.valid() && !(free()>0) ) { ++out; } if (!out.valid()) { out_or_in=0; - in=/*resG->*/G->template first(v); + //in=/*resG->*/G->template first(v); + G->getFirst(in, v); while( in.valid() && !(free()>0) ) { ++in; } } } @@ -324,7 +344,7 @@ while( out.valid() && !(free()>0) ) { ++out; } if (!out.valid()) { out_or_in=0; - in=/*resG->*/G->template first(v); + G->getFirst(in, v); //=/*resG->*/G->template first(v); while( in.valid() && !(free()>0) ) { ++in; } } } else { @@ -335,9 +355,75 @@ } }; + class EachEdgeIt : public EdgeIt { + typename Graph::EachNodeIt v; + public: + EachEdgeIt() { } + //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { } + EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) { + G=&_G; + flow=&_flow; + capacity=&_capacity; + out_or_in=1; + G->getFirst(v); + if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt(); + while (out.valid() && !(free()>0) ) { ++out; } + while (v.valid() && !out.valid()) { + ++v; + if (v.valid()) G->getFirst(out, v); + while (out.valid() && !(free()>0) ) { ++out; } + } + if (!out.valid()) { + out_or_in=0; + G->getFirst(v); + if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt(); + while (in.valid() && !(free()>0) ) { ++in; } + while (v.valid() && !in.valid()) { + ++v; + if (v.valid()) G->getFirst(in, v); + while (in.valid() && !(free()>0) ) { ++in; } + } + } + } + EachEdgeIt& operator++() { + if (out_or_in) { + ++out; + while (out.valid() && !(free()>0) ) { ++out; } + while (v.valid() && !out.valid()) { + ++v; + if (v.valid()) G->getFirst(out, v); + while (out.valid() && !(free()>0) ) { ++out; } + } + if (!out.valid()) { + out_or_in=0; + G->getFirst(v); + if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt(); + while (in.valid() && !(free()>0) ) { ++in; } + while (v.valid() && !in.valid()) { + ++v; + if (v.valid()) G->getFirst(in, v); + while (in.valid() && !(free()>0) ) { ++in; } + } + } + } else { + ++in; + while (in.valid() && !(free()>0) ) { ++in; } + while (v.valid() && !in.valid()) { + ++v; + if (v.valid()) G->getFirst(in, v); + while (in.valid() && !(free()>0) ) { ++in; } + } + } + return *this; + } + }; + void getFirst(OutEdgeIt& e, NodeIt v) const { e=OutEdgeIt(G, v, flow, capacity); } + void getFirst(EachEdgeIt& e) const { + e=EachEdgeIt(G, flow, capacity); + } void getFirst(EachNodeIt& v) const { G.getFirst(v); } template< typename It > @@ -401,13 +487,13 @@ //AugGraph res_graph; //typedef typename AugGraph::NodeMap ReachedMap; //typename AugGraph::NodeMap pred; - //typename AugGraph::NodeMap free; + //typename AugGraph::NodeMap free; public: MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) //, //res_graph(G, flow, capacity), pred(res_graph), free(res_graph) { } - bool augment() { + bool augmentOnShortestPath() { AugGraph res_graph(G, flow, capacity); bool _augment=false; @@ -419,7 +505,7 @@ //filled up with invalid iterators //pred.set(s, AugEdgeIt()); - typename AugGraph::NodeMap free(res_graph); + typename AugGraph::NodeMap free(res_graph); //searching for augmenting path while ( !res_bfs.finished() ) { @@ -451,48 +537,130 @@ return _augment; } - bool augmentWithBlockingFlow() { - BfsIterator4< Graph, OutEdgeIt, typename Graph::NodeMap > bfs(G); + template bool augmentOnBlockingFlow() { + bool _augment=false; + + AugGraph res_graph(G, flow, capacity); + + typedef typename AugGraph::NodeMap ReachedMap; + BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); + bfs.pushAndSetReached(s); - typename Graph::NodeMap dist(G); //filled up with 0's + typename AugGraph::NodeMap dist(res_graph); //filled up with 0's while ( !bfs.finished() ) { - OutEdgeIt e=OutEdgeIt(bfs); + AugOutEdgeIt e=AugOutEdgeIt(bfs); if (e.valid() && bfs.isBNodeNewlyReached()) { - dist.set(G.head(e), dist.get(G.tail(e))+1); - //NodeIt v=res_graph.tail(e); - //NodeIt w=res_graph.head(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 (res_graph.head(e)==t) { _augment=true; break; } + dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); } ++bfs; - } //end of searching augmenting path + } //computing distances from s in the residual graph - double pre_time_copy=currTime(); - typedef Graph MutableGraph; MutableGraph F; - typename Graph::NodeMap G_to_F(G); - for(typename Graph::EachNodeIt n=G.template first(); n.valid(); ++n) { - G_to_F.set(n, F.addNode()); + typename AugGraph::NodeMap res_graph_to_F(res_graph); + for(typename AugGraph::EachNodeIt n=res_graph.template first(); n.valid(); ++n) { + res_graph_to_F.set(n, F.addNode()); } - for(typename Graph::EachEdgeIt e=G.template first(); e.valid(); ++e) { - if (dist.get(G.head(e))==dist.get(G.tail(e))+1) { - F.addEdge(G_to_F.get(G.tail(e)), G_to_F.get(G.head(e))); + + typename MutableGraph::NodeIt sF=res_graph_to_F.get(s); + typename MutableGraph::NodeIt tF=res_graph_to_F.get(t); + + typename MutableGraph::EdgeMap original_edge(F); + typename MutableGraph::EdgeMap free_on_edge(F); + + //Making F to the graph containing the edges of the residual graph + //which are in some shortest paths + for(typename AugGraph::EachEdgeIt e=res_graph.template first(); e.valid(); ++e) { + if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { + typename MutableGraph::EdgeIt f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); + original_edge.update(); + original_edge.set(f, e); + free_on_edge.update(); + free_on_edge.set(f, e.free()); + } + } + + bool __augment=true; + + while (__augment) { + __augment=false; + //computing blocking flow with dfs + typedef typename MutableGraph::NodeMap BlockingReachedMap; + DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F); + typename MutableGraph::NodeMap pred(F); //invalid iterators + typename MutableGraph::NodeMap free(F); + + dfs.pushAndSetReached(sF); + while (!dfs.finished()) { + ++dfs; + if (typename MutableGraph::OutEdgeIt(dfs).valid()) { + //std::cout << "OutEdgeIt: " << dfs; + //std::cout << " aNode: " << F.aNode(dfs); + //std::cout << " bNode: " << F.bNode(dfs) << " "; + + typename MutableGraph::NodeIt v=F.aNode(dfs); + typename MutableGraph::NodeIt w=F.bNode(dfs); + pred.set(w, dfs); + if (pred.get(v).valid()) { + free.set(w, std::min(free.get(v), free_on_edge.get(dfs))); + } else { + free.set(w, free_on_edge.get(dfs)/*original_edge.get(dfs).free()*/); + } + if (w==tF) { + //std::cout << "AUGMENTATION"<()) { + //std::cout << ++num_of_augmentations << " "; + //std::cout< void run() { + //int num_of_augmentations=0; + //while (augmentOnShortestPath()) { + while (augmentOnBlockingFlow()) { //std::cout << ++num_of_augmentations << " "; //std::cout< pred(res_graph); //filled up with invalid iterators - typename AugGraph::NodeMap free(res_graph); + typename AugGraph::NodeMap free(res_graph); //searching for augmenting path while ( !res_bfs.finished() ) {