marci@474: // -*- c++ -*- alpar@921: #ifndef LEMON_EDMONDS_KARP_H alpar@921: #define LEMON_EDMONDS_KARP_H marci@474: marci@474: #include marci@474: #include marci@474: #include marci@474: marci@474: #include marci@474: #include marci@474: #include marci@474: #include marci@474: #include marci@474: alpar@921: namespace lemon { marci@474: marci@474: template marci@474: class MaxFlow { marci@474: protected: marci@474: typedef typename Graph::Node Node; marci@474: typedef typename Graph::Edge Edge; marci@474: typedef typename Graph::EdgeIt EdgeIt; marci@474: typedef typename Graph::OutEdgeIt OutEdgeIt; marci@474: typedef typename Graph::InEdgeIt InEdgeIt; marci@474: const Graph* g; marci@474: Node s; marci@474: Node t; marci@474: const CapMap* capacity; marci@474: FlowMap* flow; marci@474: typedef ResGraphWrapper ResGW; marci@474: typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; marci@474: typedef typename ResGW::Edge ResGWEdge; marci@474: //typedef typename ResGW::template NodeMap ReachedMap; marci@474: typedef typename Graph::template NodeMap ReachedMap; marci@474: ReachedMap level; marci@474: //reached is called level because of compatibility with preflow marci@474: public: marci@474: marci@474: MaxFlow(const Graph& _g, Node _s, Node _t, const CapMap& _capacity, marci@474: FlowMap& _flow) : marci@474: g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow), level(_g) { } marci@474: marci@474: bool augmentOnShortestPath() { marci@474: ResGW res_graph(*g, *capacity, *flow); marci@474: bool _augment=false; marci@474: marci@474: //ReachedMap level(res_graph); marci@474: FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0); marci@474: BfsIterator bfs(res_graph, level); marci@474: bfs.pushAndSetReached(s); marci@474: marci@474: typename ResGW::template NodeMap pred(res_graph); marci@474: pred.set(s, INVALID); marci@474: marci@474: typename ResGW::template NodeMap free(res_graph); marci@474: marci@474: //searching for augmenting path marci@474: while ( !bfs.finished() ) { marci@474: ResGWOutEdgeIt e=bfs; marci@474: if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { alpar@986: Node v=res_graph.source(e); alpar@986: Node w=res_graph.target(e); marci@474: pred.set(w, e); marci@474: if (res_graph.valid(pred[v])) { marci@474: free.set(w, std::min(free[v], res_graph.resCap(e))); marci@474: } else { marci@474: free.set(w, res_graph.resCap(e)); marci@474: } alpar@986: if (res_graph.target(e)==t) { _augment=true; break; } marci@474: } marci@474: marci@474: ++bfs; marci@474: } //end of searching augmenting path marci@474: marci@474: if (_augment) { marci@474: Node n=t; marci@474: Num augment_value=free[t]; marci@474: while (res_graph.valid(pred[n])) { marci@474: ResGWEdge e=pred[n]; marci@474: res_graph.augment(e, augment_value); alpar@986: n=res_graph.source(e); marci@474: } marci@474: } marci@474: marci@474: return _augment; marci@474: } marci@474: marci@474: template marci@474: class DistanceMap { marci@474: protected: marci@474: const MapGraphWrapper* g; marci@474: typename MapGraphWrapper::template NodeMap dist; marci@474: public: marci@474: DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { } marci@474: void set(const typename MapGraphWrapper::Node& n, int a) { marci@474: dist.set(n, a); marci@474: } marci@474: int operator[](const typename MapGraphWrapper::Node& n) marci@474: { return dist[n]; } marci@474: // int get(const typename MapGraphWrapper::Node& n) const { marci@474: // return dist[n]; } marci@474: // bool get(const typename MapGraphWrapper::Edge& e) const { alpar@986: // return (dist.get(g->source(e))target(e))); } marci@474: bool operator[](const typename MapGraphWrapper::Edge& e) const { alpar@986: return (dist[g->source(e)]target(e)]); marci@474: } marci@474: }; marci@474: marci@474: template bool augmentOnBlockingFlow() { marci@474: typedef MutableGraph MG; marci@474: bool _augment=false; marci@474: marci@474: ResGW res_graph(*g, *capacity, *flow); marci@474: marci@474: //ReachedMap level(res_graph); marci@474: FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0); marci@474: BfsIterator bfs(res_graph, level); marci@474: marci@474: bfs.pushAndSetReached(s); marci@474: //typename ResGW::NodeMap dist(res_graph); //filled up with 0's marci@474: DistanceMap dist(res_graph); marci@474: while ( !bfs.finished() ) { marci@474: ResGWOutEdgeIt e=bfs; marci@474: if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { alpar@986: dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); marci@474: } marci@474: ++bfs; marci@474: } //computing distances from s in the residual graph marci@474: marci@474: MG F; marci@474: ConstMap true_map(true); marci@474: typedef SubGraphWrapper, marci@474: DistanceMap > FilterResGW; marci@474: FilterResGW filter_res_graph(res_graph, true_map, dist); marci@474: typename ResGW::template NodeMap marci@474: res_graph_to_F(res_graph); marci@474: { marci@474: typename ResGW::NodeIt n; marci@474: for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) { marci@474: res_graph_to_F.set(n, F.addNode()); marci@474: } marci@474: } marci@474: marci@474: typename MG::Node sF=res_graph_to_F[s]; marci@474: typename MG::Node tF=res_graph_to_F[t]; marci@474: typename MG::template EdgeMap original_edge(F); marci@474: typename MG::template EdgeMap residual_capacity(F); marci@474: marci@474: //Making F to the graph containing the edges of the residual graph marci@474: //which are in some shortest paths marci@474: { marci@474: typename FilterResGW::EdgeIt e; marci@474: for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) { alpar@986: //if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { alpar@986: typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]); marci@474: original_edge.update(); marci@474: original_edge.set(f, e); marci@474: residual_capacity.update(); marci@474: residual_capacity.set(f, res_graph.resCap(e)); marci@474: //} marci@474: } marci@474: } marci@474: marci@474: bool __augment=true; marci@474: marci@474: while (__augment) { marci@474: __augment=false; marci@474: //computing blocking flow with dfs marci@474: marci@474: DfsIterator< MG, typename MG::template NodeMap > dfs(F); marci@474: typename MG::template NodeMap pred(F); marci@474: pred.set(sF, INVALID); marci@474: //invalid iterators for sources marci@474: marci@474: typename MG::template NodeMap free(F); marci@474: marci@474: dfs.pushAndSetReached(sF); marci@474: while (!dfs.finished()) { marci@474: ++dfs; marci@474: if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { marci@474: if (dfs.isBNodeNewlyReached()) { marci@474: typename MG::Node v=F.aNode(dfs); marci@474: typename MG::Node w=F.bNode(dfs); marci@474: pred.set(w, dfs); marci@474: if (F.valid(pred[v])) { marci@474: free.set(w, std::min(free[v], residual_capacity[dfs])); marci@474: } else { marci@474: free.set(w, residual_capacity[dfs]); marci@474: } marci@474: if (w==tF) { marci@474: __augment=true; marci@474: _augment=true; marci@474: break; marci@474: } marci@474: marci@474: } else { marci@474: F.erase(/*typename MG::OutEdgeIt*/(dfs)); marci@474: } marci@474: } marci@474: } marci@474: marci@474: if (__augment) { marci@474: typename MG::Node n=tF; marci@474: Num augment_value=free[tF]; marci@474: while (F.valid(pred[n])) { marci@474: typename MG::Edge e=pred[n]; marci@474: res_graph.augment(original_edge[e], augment_value); alpar@986: n=F.source(e); marci@474: if (residual_capacity[e]==augment_value) marci@474: F.erase(e); marci@474: else marci@474: residual_capacity.set(e, residual_capacity[e]-augment_value); marci@474: } marci@474: } marci@474: marci@474: } marci@474: marci@474: return _augment; marci@474: } marci@474: marci@474: template bool augmentOnBlockingFlow1() { marci@474: typedef MutableGraph MG; marci@474: bool _augment=false; marci@474: marci@474: ResGW res_graph(*g, *capacity, *flow); marci@474: marci@474: //bfs for distances on the residual graph marci@474: //ReachedMap level(res_graph); marci@474: FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0); marci@474: BfsIterator bfs(res_graph, level); marci@474: bfs.pushAndSetReached(s); marci@474: typename ResGW::template NodeMap marci@474: dist(res_graph); //filled up with 0's marci@474: marci@474: //F will contain the physical copy of the residual graph marci@474: //with the set of edges which are on shortest paths marci@474: MG F; marci@474: typename ResGW::template NodeMap marci@474: res_graph_to_F(res_graph); marci@474: { marci@474: typename ResGW::NodeIt n; marci@474: for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) { marci@474: res_graph_to_F.set(n, F.addNode()); marci@474: } marci@474: } marci@474: marci@474: typename MG::Node sF=res_graph_to_F[s]; marci@474: typename MG::Node tF=res_graph_to_F[t]; marci@474: typename MG::template EdgeMap original_edge(F); marci@474: typename MG::template EdgeMap residual_capacity(F); marci@474: marci@474: while ( !bfs.finished() ) { marci@474: ResGWOutEdgeIt e=bfs; marci@474: if (res_graph.valid(e)) { marci@474: if (bfs.isBNodeNewlyReached()) { alpar@986: dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); alpar@986: typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]); marci@474: original_edge.update(); marci@474: original_edge.set(f, e); marci@474: residual_capacity.update(); marci@474: residual_capacity.set(f, res_graph.resCap(e)); marci@474: } else { alpar@986: if (dist[res_graph.target(e)]==(dist[res_graph.source(e)]+1)) { alpar@986: typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]); marci@474: original_edge.update(); marci@474: original_edge.set(f, e); marci@474: residual_capacity.update(); marci@474: residual_capacity.set(f, res_graph.resCap(e)); marci@474: } marci@474: } marci@474: } marci@474: ++bfs; marci@474: } //computing distances from s in the residual graph marci@474: marci@474: bool __augment=true; marci@474: marci@474: while (__augment) { marci@474: __augment=false; marci@474: //computing blocking flow with dfs marci@474: DfsIterator< MG, typename MG::template NodeMap > dfs(F); marci@474: typename MG::template NodeMap pred(F); marci@474: pred.set(sF, INVALID); marci@474: //invalid iterators for sources marci@474: marci@474: typename MG::template NodeMap free(F); marci@474: marci@474: dfs.pushAndSetReached(sF); marci@474: while (!dfs.finished()) { marci@474: ++dfs; marci@474: if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { marci@474: if (dfs.isBNodeNewlyReached()) { marci@474: typename MG::Node v=F.aNode(dfs); marci@474: typename MG::Node w=F.bNode(dfs); marci@474: pred.set(w, dfs); marci@474: if (F.valid(pred[v])) { marci@474: free.set(w, std::min(free[v], residual_capacity[dfs])); marci@474: } else { marci@474: free.set(w, residual_capacity[dfs]); marci@474: } marci@474: if (w==tF) { marci@474: __augment=true; marci@474: _augment=true; marci@474: break; marci@474: } marci@474: marci@474: } else { marci@474: F.erase(/*typename MG::OutEdgeIt*/(dfs)); marci@474: } marci@474: } marci@474: } marci@474: marci@474: if (__augment) { marci@474: typename MG::Node n=tF; marci@474: Num augment_value=free[tF]; marci@474: while (F.valid(pred[n])) { marci@474: typename MG::Edge e=pred[n]; marci@474: res_graph.augment(original_edge[e], augment_value); alpar@986: n=F.source(e); marci@474: if (residual_capacity[e]==augment_value) marci@474: F.erase(e); marci@474: else marci@474: residual_capacity.set(e, residual_capacity[e]-augment_value); marci@474: } marci@474: } marci@474: marci@474: } marci@474: marci@474: return _augment; marci@474: } marci@474: marci@474: bool augmentOnBlockingFlow2() { marci@474: bool _augment=false; marci@474: marci@474: ResGW res_graph(*g, *capacity, *flow); marci@474: marci@474: //ReachedMap level(res_graph); marci@474: FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0); marci@474: BfsIterator bfs(res_graph, level); marci@474: marci@474: bfs.pushAndSetReached(s); marci@474: DistanceMap dist(res_graph); marci@474: while ( !bfs.finished() ) { marci@474: ResGWOutEdgeIt e=bfs; marci@474: if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { alpar@986: dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); marci@474: } marci@474: ++bfs; marci@474: } //computing distances from s in the residual graph marci@474: marci@474: //Subgraph containing the edges on some shortest paths marci@474: ConstMap true_map(true); marci@474: typedef SubGraphWrapper, marci@474: DistanceMap > FilterResGW; marci@474: FilterResGW filter_res_graph(res_graph, true_map, dist); marci@474: marci@474: //Subgraph, which is able to delete edges which are already marci@474: //met by the dfs marci@474: typename FilterResGW::template NodeMap marci@474: first_out_edges(filter_res_graph); marci@474: typename FilterResGW::NodeIt v; marci@474: for(filter_res_graph.first(v); filter_res_graph.valid(v); marci@474: filter_res_graph.next(v)) marci@474: { marci@474: typename FilterResGW::OutEdgeIt e; marci@474: filter_res_graph.first(e, v); marci@474: first_out_edges.set(v, e); marci@474: } marci@474: typedef ErasingFirstGraphWrapper > ErasingResGW; marci@474: ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges); marci@474: marci@474: bool __augment=true; marci@474: marci@474: while (__augment) { marci@474: marci@474: __augment=false; marci@474: //computing blocking flow with dfs marci@474: DfsIterator< ErasingResGW, marci@474: typename ErasingResGW::template NodeMap > marci@474: dfs(erasing_res_graph); marci@474: typename ErasingResGW:: marci@474: template NodeMap marci@474: pred(erasing_res_graph); marci@474: pred.set(s, INVALID); marci@474: //invalid iterators for sources marci@474: marci@474: typename ErasingResGW::template NodeMap marci@474: free1(erasing_res_graph); marci@474: marci@474: dfs.pushAndSetReached( marci@474: typename ErasingResGW::Node( marci@474: typename FilterResGW::Node( marci@474: typename ResGW::Node(s) marci@474: ) marci@474: ) marci@474: ); marci@474: while (!dfs.finished()) { marci@474: ++dfs; marci@474: if (erasing_res_graph.valid( marci@474: typename ErasingResGW::OutEdgeIt(dfs))) marci@474: { marci@474: if (dfs.isBNodeNewlyReached()) { marci@474: marci@474: typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs); marci@474: typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs); marci@474: marci@474: pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs)); marci@474: if (erasing_res_graph.valid(pred[v])) { marci@474: free1.set(w, std::min(free1[v], res_graph.resCap( marci@474: typename ErasingResGW::OutEdgeIt(dfs)))); marci@474: } else { marci@474: free1.set(w, res_graph.resCap( marci@474: typename ErasingResGW::OutEdgeIt(dfs))); marci@474: } marci@474: marci@474: if (w==t) { marci@474: __augment=true; marci@474: _augment=true; marci@474: break; marci@474: } marci@474: } else { marci@474: erasing_res_graph.erase(dfs); marci@474: } marci@474: } marci@474: } marci@474: marci@474: if (__augment) { marci@474: typename ErasingResGW::Node n=typename FilterResGW::Node(typename ResGW::Node(t)); marci@474: // typename ResGW::NodeMap a(res_graph); marci@474: // typename ResGW::Node b; marci@474: // Num j=a[b]; marci@474: // typename FilterResGW::NodeMap a1(filter_res_graph); marci@474: // typename FilterResGW::Node b1; marci@474: // Num j1=a1[b1]; marci@474: // typename ErasingResGW::NodeMap a2(erasing_res_graph); marci@474: // typename ErasingResGW::Node b2; marci@474: // Num j2=a2[b2]; marci@474: Num augment_value=free1[n]; marci@474: while (erasing_res_graph.valid(pred[n])) { marci@474: typename ErasingResGW::OutEdgeIt e=pred[n]; marci@474: res_graph.augment(e, augment_value); alpar@986: n=erasing_res_graph.source(e); marci@474: if (res_graph.resCap(e)==0) marci@474: erasing_res_graph.erase(e); marci@474: } marci@474: } marci@474: marci@474: } //while (__augment) marci@474: marci@474: return _augment; marci@474: } marci@474: marci@474: void run() { marci@474: //int num_of_augmentations=0; marci@474: while (augmentOnShortestPath()) { marci@474: //while (augmentOnBlockingFlow()) { marci@474: //std::cout << ++num_of_augmentations << " "; marci@474: //std::cout< void run() { marci@474: //int num_of_augmentations=0; marci@474: //while (augmentOnShortestPath()) { marci@474: while (augmentOnBlockingFlow()) { marci@474: //std::cout << ++num_of_augmentations << " "; marci@474: //std::cout<first(e, s); g->valid(e); g->next(e)) { marci@474: a+=(*flow)[e]; marci@474: } marci@474: return a; marci@474: } marci@474: marci@474: }; marci@474: marci@474: marci@474: // template marci@474: // class MaxMatching { marci@474: // public: marci@474: // typedef typename Graph::Node Node; marci@474: // typedef typename Graph::NodeIt NodeIt; marci@474: // typedef typename Graph::Edge Edge; marci@474: // typedef typename Graph::EdgeIt EdgeIt; marci@474: // typedef typename Graph::OutEdgeIt OutEdgeIt; marci@474: // typedef typename Graph::InEdgeIt InEdgeIt; marci@474: marci@474: // typedef typename Graph::NodeMap SMap; marci@474: // typedef typename Graph::NodeMap TMap; marci@474: // private: marci@474: // const Graph* G; marci@474: // SMap* S; marci@474: // TMap* T; marci@474: // //Node s; marci@474: // //Node t; marci@474: // FlowMap* flow; marci@474: // const CapMap* capacity; marci@474: // typedef ResGraphWrapper AugGraph; marci@474: // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; marci@474: // typedef typename AugGraph::Edge AugEdge; marci@474: // typename Graph::NodeMap used; //0 marci@474: marci@474: // public: marci@474: // MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapMap& _capacity) : marci@474: // G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { } marci@474: // bool augmentOnShortestPath() { marci@474: // AugGraph res_graph(*G, *flow, *capacity); marci@474: // bool _augment=false; marci@474: marci@474: // typedef typename AugGraph::NodeMap ReachedMap; marci@474: // BfsIterator< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph); marci@474: // typename AugGraph::NodeMap pred(res_graph); marci@474: // for(NodeIt s=G->template first(); G->valid(s); G->next(s)) { marci@474: // if ((S->get(s)) && (used.get(s)<1) ) { marci@474: // //Num u=0; marci@474: // //for(OutEdgeIt e=G->template first(s); G->valid(e); G->next(e)) marci@474: // //u+=flow->get(e); marci@474: // //if (u<1) { marci@474: // bfs.pushAndSetReached(s); marci@474: // pred.set(s, AugEdge(INVALID)); marci@474: // //} marci@474: // } marci@474: // } marci@474: marci@474: // typename AugGraph::NodeMap free(res_graph); marci@474: marci@474: // Node n; marci@474: // //searching for augmenting path marci@474: // while ( !bfs.finished() ) { marci@474: // AugOutEdgeIt e=bfs; marci@474: // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { alpar@986: // Node v=res_graph.source(e); alpar@986: // Node w=res_graph.target(e); marci@474: // pred.set(w, e); marci@474: // if (res_graph.valid(pred.get(v))) { marci@474: // free.set(w, std::min(free.get(v), res_graph.free(e))); marci@474: // } else { marci@474: // free.set(w, res_graph.free(e)); marci@474: // } alpar@986: // n=res_graph.target(e); marci@474: // if (T->get(n) && (used.get(n)<1) ) { marci@474: // //Num u=0; marci@474: // //for(InEdgeIt f=G->template first(n); G->valid(f); G->next(f)) marci@474: // //u+=flow->get(f); marci@474: // //if (u<1) { marci@474: // _augment=true; marci@474: // break; marci@474: // //} marci@474: // } marci@474: // } marci@474: marci@474: // ++bfs; marci@474: // } //end of searching augmenting path marci@474: marci@474: // if (_augment) { marci@474: // //Node n=t; marci@474: // used.set(n, 1); //mind2 vegen jav marci@474: // Num augment_value=free.get(n); marci@474: // while (res_graph.valid(pred.get(n))) { marci@474: // AugEdge e=pred.get(n); marci@474: // res_graph.augment(e, augment_value); alpar@986: // n=res_graph.source(e); marci@474: // } marci@474: // used.set(n, 1); //mind2 vegen jav marci@474: // } marci@474: marci@474: // return _augment; marci@474: // } marci@474: marci@474: // // template bool augmentOnBlockingFlow() { marci@474: // // bool _augment=false; marci@474: marci@474: // // AugGraph res_graph(*G, *flow, *capacity); marci@474: marci@474: // // typedef typename AugGraph::NodeMap ReachedMap; marci@474: // // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); marci@474: marci@474: marci@474: marci@474: marci@474: marci@474: // // //typename AugGraph::NodeMap pred(res_graph); marci@474: // // for(NodeIt s=G->template first(); G->valid(s); G->next(s)) { marci@474: // // if (S->get(s)) { marci@474: // // Num u=0; marci@474: // // for(OutEdgeIt e=G->template first(s); G->valid(e); G->next(e)) marci@474: // // u+=flow->get(e); marci@474: // // if (u<1) { marci@474: // // bfs.pushAndSetReached(s); marci@474: // // //pred.set(s, AugEdge(INVALID)); marci@474: // // } marci@474: // // } marci@474: // // } marci@474: marci@474: marci@474: marci@474: marci@474: // // //bfs.pushAndSetReached(s); marci@474: // // typename AugGraph::NodeMap dist(res_graph); //filled up with 0's marci@474: // // while ( !bfs.finished() ) { marci@474: // // AugOutEdgeIt e=bfs; marci@474: // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { alpar@986: // // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); marci@474: // // } marci@474: marci@474: // // ++bfs; marci@474: // // } //computing distances from s in the residual graph marci@474: marci@474: // // MutableGraph F; marci@474: // // typename AugGraph::NodeMap marci@474: // // res_graph_to_F(res_graph); marci@474: // // for(typename AugGraph::NodeIt n=res_graph.template first(); res_graph.valid(n); res_graph.next(n)) { marci@474: // // res_graph_to_F.set(n, F.addNode()); marci@474: // // } marci@474: marci@474: // // typename MutableGraph::Node sF=res_graph_to_F.get(s); marci@474: // // typename MutableGraph::Node tF=res_graph_to_F.get(t); marci@474: marci@474: // // typename MutableGraph::EdgeMap original_edge(F); marci@474: // // typename MutableGraph::EdgeMap residual_capacity(F); marci@474: marci@474: // // //Making F to the graph containing the edges of the residual graph marci@474: // // //which are in some shortest paths marci@474: // // for(typename AugGraph::EdgeIt e=res_graph.template first(); res_graph.valid(e); res_graph.next(e)) { alpar@986: // // if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { alpar@986: // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); marci@474: // // original_edge.update(); marci@474: // // original_edge.set(f, e); marci@474: // // residual_capacity.update(); marci@474: // // residual_capacity.set(f, res_graph.free(e)); marci@474: // // } marci@474: // // } marci@474: marci@474: // // bool __augment=true; marci@474: marci@474: // // while (__augment) { marci@474: // // __augment=false; marci@474: // // //computing blocking flow with dfs marci@474: // // typedef typename MutableGraph::NodeMap BlockingReachedMap; marci@474: // // DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F); marci@474: // // typename MutableGraph::NodeMap pred(F); marci@474: // // pred.set(sF, typename MutableGraph::Edge(INVALID)); marci@474: // // //invalid iterators for sources marci@474: marci@474: // // typename MutableGraph::NodeMap free(F); marci@474: marci@474: // // dfs.pushAndSetReached(sF); marci@474: // // while (!dfs.finished()) { marci@474: // // ++dfs; marci@474: // // if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { marci@474: // // if (dfs.isBNodeNewlyReached()) { marci@474: // // typename MutableGraph::Node v=F.aNode(dfs); marci@474: // // typename MutableGraph::Node w=F.bNode(dfs); marci@474: // // pred.set(w, dfs); marci@474: // // if (F.valid(pred.get(v))) { marci@474: // // free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); marci@474: // // } else { marci@474: // // free.set(w, residual_capacity.get(dfs)); marci@474: // // } marci@474: // // if (w==tF) { marci@474: // // __augment=true; marci@474: // // _augment=true; marci@474: // // break; marci@474: // // } marci@474: marci@474: // // } else { marci@474: // // F.erase(typename MutableGraph::OutEdgeIt(dfs)); marci@474: // // } marci@474: // // } marci@474: // // } marci@474: marci@474: // // if (__augment) { marci@474: // // typename MutableGraph::Node n=tF; marci@474: // // Num augment_value=free.get(tF); marci@474: // // while (F.valid(pred.get(n))) { marci@474: // // typename MutableGraph::Edge e=pred.get(n); marci@474: // // res_graph.augment(original_edge.get(e), augment_value); alpar@986: // // n=F.source(e); marci@474: // // if (residual_capacity.get(e)==augment_value) marci@474: // // F.erase(e); marci@474: // // else marci@474: // // residual_capacity.set(e, residual_capacity.get(e)-augment_value); marci@474: // // } marci@474: // // } marci@474: marci@474: // // } marci@474: marci@474: // // return _augment; marci@474: // // } marci@474: // bool augmentOnBlockingFlow2() { marci@474: // bool _augment=false; marci@474: marci@474: // //typedef ErasingResGraphWrapper EAugGraph; marci@474: // typedef FilterGraphWrapper< ErasingResGraphWrapper > EAugGraph; marci@474: // typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; marci@474: // typedef typename EAugGraph::Edge EAugEdge; marci@474: marci@474: // EAugGraph res_graph(*G, *flow, *capacity); marci@474: marci@474: // //typedef typename EAugGraph::NodeMap ReachedMap; marci@474: // BfsIterator< marci@474: // ErasingResGraphWrapper, marci@474: // /*typename ErasingResGraphWrapper::OutEdgeIt,*/ marci@474: // ErasingResGraphWrapper::NodeMap > bfs(res_graph); marci@474: marci@474: marci@474: // //typename AugGraph::NodeMap pred(res_graph); marci@474: // for(NodeIt s=G->template first(); G->valid(s); G->next(s)) { marci@474: // if (S->get(s)) { marci@474: // Num u=0; marci@474: // for(OutEdgeIt e=G->template first(s); G->valid(e); G->next(e)) marci@474: // u+=flow->get(e); marci@474: // if (u<1) { marci@474: // bfs.pushAndSetReached(s); marci@474: // //pred.set(s, AugEdge(INVALID)); marci@474: // } marci@474: // } marci@474: // } marci@474: marci@474: marci@474: // //bfs.pushAndSetReached(s); marci@474: marci@474: // typename ErasingResGraphWrapper:: marci@474: // NodeMap& dist=res_graph.dist; marci@474: marci@474: // while ( !bfs.finished() ) { marci@474: // typename ErasingResGraphWrapper::OutEdgeIt e=bfs; marci@474: // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { alpar@986: // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); marci@474: // } marci@474: // ++bfs; marci@474: // } //computing distances from s in the residual graph marci@474: marci@474: // bool __augment=true; marci@474: marci@474: // while (__augment) { marci@474: marci@474: // __augment=false; marci@474: // //computing blocking flow with dfs marci@474: // typedef typename EAugGraph::NodeMap BlockingReachedMap; marci@474: // DfsIterator< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > marci@474: // dfs(res_graph); marci@474: // typename EAugGraph::NodeMap pred(res_graph, INVALID); marci@474: // //pred.set(s, EAugEdge(INVALID)); marci@474: // //invalid iterators for sources marci@474: marci@474: // typename EAugGraph::NodeMap free(res_graph); marci@474: marci@474: marci@474: // //typename AugGraph::NodeMap pred(res_graph); marci@474: // for(NodeIt s=G->template first(); G->valid(s); G->next(s)) { marci@474: // if (S->get(s)) { marci@474: // Num u=0; marci@474: // for(OutEdgeIt e=G->template first(s); G->valid(e); G->next(e)) marci@474: // u+=flow->get(e); marci@474: // if (u<1) { marci@474: // dfs.pushAndSetReached(s); marci@474: // //pred.set(s, AugEdge(INVALID)); marci@474: // } marci@474: // } marci@474: // } marci@474: marci@474: marci@474: marci@474: // //dfs.pushAndSetReached(s); marci@474: // typename EAugGraph::Node n; marci@474: // while (!dfs.finished()) { marci@474: // ++dfs; marci@474: // if (res_graph.valid(EAugOutEdgeIt(dfs))) { marci@474: // if (dfs.isBNodeNewlyReached()) { marci@474: marci@474: // typename EAugGraph::Node v=res_graph.aNode(dfs); marci@474: // typename EAugGraph::Node w=res_graph.bNode(dfs); marci@474: marci@474: // pred.set(w, EAugOutEdgeIt(dfs)); marci@474: // if (res_graph.valid(pred.get(v))) { marci@474: // free.set(w, std::min(free.get(v), res_graph.free(dfs))); marci@474: // } else { marci@474: // free.set(w, res_graph.free(dfs)); marci@474: // } marci@474: marci@474: // n=w; marci@474: // if (T->get(w)) { marci@474: // Num u=0; marci@474: // for(InEdgeIt f=G->template first(n); G->valid(f); G->next(f)) marci@474: // u+=flow->get(f); marci@474: // if (u<1) { marci@474: // __augment=true; marci@474: // _augment=true; marci@474: // break; marci@474: // } marci@474: // } marci@474: // } else { marci@474: // res_graph.erase(dfs); marci@474: // } marci@474: // } marci@474: marci@474: // } marci@474: marci@474: // if (__augment) { marci@474: // // typename EAugGraph::Node n=t; marci@474: // Num augment_value=free.get(n); marci@474: // while (res_graph.valid(pred.get(n))) { marci@474: // EAugEdge e=pred.get(n); marci@474: // res_graph.augment(e, augment_value); alpar@986: // n=res_graph.source(e); marci@474: // if (res_graph.free(e)==0) marci@474: // res_graph.erase(e); marci@474: // } marci@474: // } marci@474: marci@474: // } marci@474: marci@474: // return _augment; marci@474: // } marci@474: // void run() { marci@474: // //int num_of_augmentations=0; marci@474: // while (augmentOnShortestPath()) { marci@474: // //while (augmentOnBlockingFlow()) { marci@474: // //std::cout << ++num_of_augmentations << " "; marci@474: // //std::cout< void run() { marci@474: // // //int num_of_augmentations=0; marci@474: // // //while (augmentOnShortestPath()) { marci@474: // // while (augmentOnBlockingFlow()) { marci@474: // // //std::cout << ++num_of_augmentations << " "; marci@474: // // //std::cout</*getF*/first(e); G->valid(e); G->next(e)) { marci@474: // a+=flow->get(e); marci@474: // } marci@474: // return a; marci@474: // } marci@474: // }; marci@474: marci@474: marci@474: marci@474: marci@474: marci@474: marci@474: // // template marci@474: // // class MaxFlow2 { marci@474: // // public: marci@474: // // typedef typename Graph::Node Node; marci@474: // // typedef typename Graph::Edge Edge; marci@474: // // typedef typename Graph::EdgeIt EdgeIt; marci@474: // // typedef typename Graph::OutEdgeIt OutEdgeIt; marci@474: // // typedef typename Graph::InEdgeIt InEdgeIt; marci@474: // // private: marci@474: // // const Graph& G; marci@474: // // std::list& S; marci@474: // // std::list& T; marci@474: // // FlowMap& flow; marci@474: // // const CapMap& capacity; marci@474: // // typedef ResGraphWrapper AugGraph; marci@474: // // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; marci@474: // // typedef typename AugGraph::Edge AugEdge; marci@474: // // typename Graph::NodeMap SMap; marci@474: // // typename Graph::NodeMap TMap; marci@474: // // public: marci@474: // // MaxFlow2(const Graph& _G, std::list& _S, std::list& _T, FlowMap& _flow, const CapMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) { marci@474: // // for(typename std::list::const_iterator i=S.begin(); marci@474: // // i!=S.end(); ++i) { marci@474: // // SMap.set(*i, true); marci@474: // // } marci@474: // // for (typename std::list::const_iterator i=T.begin(); marci@474: // // i!=T.end(); ++i) { marci@474: // // TMap.set(*i, true); marci@474: // // } marci@474: // // } marci@474: // // bool augment() { marci@474: // // AugGraph res_graph(G, flow, capacity); marci@474: // // bool _augment=false; marci@474: // // Node reached_t_node; marci@474: marci@474: // // typedef typename AugGraph::NodeMap ReachedMap; marci@474: // // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); marci@474: // // for(typename std::list::const_iterator i=S.begin(); marci@474: // // i!=S.end(); ++i) { marci@474: // // bfs.pushAndSetReached(*i); marci@474: // // } marci@474: // // //bfs.pushAndSetReached(s); marci@474: marci@474: // // typename AugGraph::NodeMap pred(res_graph); marci@474: // // //filled up with invalid iterators marci@474: marci@474: // // typename AugGraph::NodeMap free(res_graph); marci@474: marci@474: // // //searching for augmenting path marci@474: // // while ( !bfs.finished() ) { marci@474: // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); marci@474: // // if (e.valid() && bfs.isBNodeNewlyReached()) { alpar@986: // // Node v=res_graph.source(e); alpar@986: // // Node w=res_graph.target(e); marci@474: // // pred.set(w, e); marci@474: // // if (pred.get(v).valid()) { marci@474: // // free.set(w, std::min(free.get(v), e.free())); marci@474: // // } else { marci@474: // // free.set(w, e.free()); marci@474: // // } alpar@986: // // if (TMap.get(res_graph.target(e))) { marci@474: // // _augment=true; alpar@986: // // reached_t_node=res_graph.target(e); marci@474: // // break; marci@474: // // } marci@474: // // } marci@474: marci@474: // // ++bfs; marci@474: // // } //end of searching augmenting path marci@474: marci@474: // // if (_augment) { marci@474: // // Node n=reached_t_node; marci@474: // // Num augment_value=free.get(reached_t_node); marci@474: // // while (pred.get(n).valid()) { marci@474: // // AugEdge e=pred.get(n); marci@474: // // e.augment(augment_value); alpar@986: // // n=res_graph.source(e); marci@474: // // } marci@474: // // } marci@474: marci@474: // // return _augment; marci@474: // // } marci@474: // // void run() { marci@474: // // while (augment()) { } marci@474: // // } marci@474: // // Num flowValue() { marci@474: // // Num a=0; marci@474: // // for(typename std::list::const_iterator i=S.begin(); marci@474: // // i!=S.end(); ++i) { marci@474: // // for(OutEdgeIt e=G.template first(*i); e.valid(); ++e) { marci@474: // // a+=flow.get(e); marci@474: // // } marci@474: // // for(InEdgeIt e=G.template first(*i); e.valid(); ++e) { marci@474: // // a-=flow.get(e); marci@474: // // } marci@474: // // } marci@474: // // return a; marci@474: // // } marci@474: // // }; marci@474: marci@474: alpar@921: } // namespace lemon marci@474: alpar@921: #endif //LEMON_EDMONDS_KARP_H