Index: src/work/edmonds_karp.h =================================================================== --- src/work/edmonds_karp.h (revision 265) +++ src/work/edmonds_karp.h (revision 266) @@ -248,28 +248,30 @@ - template + template class MaxFlow { public: - typedef typename Graph::Node Node; - typedef typename Graph::Edge Edge; - typedef typename Graph::EdgeIt EdgeIt; - typedef typename Graph::OutEdgeIt OutEdgeIt; - typedef typename Graph::InEdgeIt InEdgeIt; + typedef typename GraphWrapper::Node Node; + typedef typename GraphWrapper::Edge Edge; + typedef typename GraphWrapper::EdgeIt EdgeIt; + typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; + typedef typename GraphWrapper::InEdgeIt InEdgeIt; private: - const Graph* G; + //const Graph* G; + GraphWrapper gw; Node s; Node t; FlowMap* flow; const CapacityMap* capacity; - typedef ResGraphWrapper AugGraph; + typedef ResGraphWrapper + AugGraph; typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; typedef typename AugGraph::Edge AugEdge; public: - MaxFlow(const Graph& _G, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : - G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { } + MaxFlow(const GraphWrapper& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : + gw(_gw), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { } bool augmentOnShortestPath() { - AugGraph res_graph(*G, *flow, *capacity); + AugGraph res_graph(gw, *flow, *capacity); bool _augment=false; @@ -314,123 +316,16 @@ } -// template bool augmentOnBlockingFlow() { -// bool _augment=false; - -// AugGraph res_graph(*G, *flow, *capacity); - -// typedef typename AugGraph::NodeMap ReachedMap; -// BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph); - -// bfs.pushAndSetReached(s); -// typename AugGraph::NodeMap dist(res_graph); //filled up with 0's -// 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); -// } - -// ++bfs; -// } //computing distances from s in the residual graph - -// MutableGraph F; -// typename AugGraph::NodeMap -// res_graph_to_F(res_graph); -// for(typename AugGraph::NodeIt n=res_graph.template first(); res_graph.valid(n); res_graph.next(n)) { -// res_graph_to_F.set(n, F.addNode()); -// } - -// typename MutableGraph::Node sF=res_graph_to_F.get(s); -// typename MutableGraph::Node tF=res_graph_to_F.get(t); - -// typename MutableGraph::EdgeMap original_edge(F); -// typename MutableGraph::EdgeMap residual_capacity(F); - -// //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))); -// original_edge.update(); -// original_edge.set(f, e); -// residual_capacity.update(); -// residual_capacity.set(f, res_graph.free(e)); -// } -// } - -// bool __augment=true; - -// while (__augment) { -// __augment=false; -// //computing blocking flow with dfs -// typedef typename TrivGraphWrapper::NodeMap BlockingReachedMap; -// DfsIterator5< TrivGraphWrapper/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F); -// typename MutableGraph::NodeMap pred(F); -// pred.set(sF, typename MutableGraph::Edge(INVALID)); -// //invalid iterators for sources - -// typename MutableGraph::NodeMap free(F); - -// dfs.pushAndSetReached(sF); -// while (!dfs.finished()) { -// ++dfs; -// if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { -// if (dfs.isBNodeNewlyReached()) { -// typename MutableGraph::Node v=F.aNode(dfs); -// typename MutableGraph::Node w=F.bNode(dfs); -// pred.set(w, dfs); -// if (F.valid(pred.get(v))) { -// free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); -// } else { -// free.set(w, residual_capacity.get(dfs)); -// } -// if (w==tF) { -// __augment=true; -// _augment=true; -// break; -// } - -// } else { -// F.erase(typename MutableGraph::OutEdgeIt(dfs)); -// } -// } -// } - -// if (__augment) { -// typename MutableGraph::Node n=tF; -// Number augment_value=free.get(tF); -// 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); -// if (residual_capacity.get(e)==augment_value) -// F.erase(e); -// else -// residual_capacity.set(e, residual_capacity.get(e)-augment_value); -// } -// } - -// } - -// return _augment; -// } - - template + template class DistanceMap { protected: - GraphWrapper gw; - typename GraphWrapper::NodeMap dist; + MapGraphWrapper gw; + typename MapGraphWrapper::NodeMap dist; public: - DistanceMap(GraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { } - //NodeMap(const ListGraph& _G, T a) : - //G(_G), container(G.node_id, a) { } - void set(const typename GraphWrapper::Node& n, int a) { dist[n]=a; } - int get(const typename GraphWrapper::Node& n) const { return dist[n]; } - bool get(const typename GraphWrapper::Edge& e) const { + DistanceMap(MapGraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { } + 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(gw.tail(e))::reference operator[](Node n) { - //return container[/*G.id(n)*/n.node->id]; } - //typename std::vector::const_reference operator[](Node n) const { - //return container[/*G.id(n)*/n.node->id]; }; @@ -438,5 +333,5 @@ bool _augment=false; - AugGraph res_graph(*G, *flow, *capacity); + AugGraph res_graph(gw, *flow, *capacity); typedef typename AugGraph::NodeMap ReachedMap; @@ -454,32 +349,7 @@ } //computing distances from s in the residual graph -// MutableGraph F; -// typename AugGraph::NodeMap -// res_graph_to_F(res_graph); -// for(typename AugGraph::NodeIt n=res_graph.template first(); res_graph.valid(n); res_graph.next(n)) { -// res_graph_to_F.set(n, F.addNode()); -// } - -// typename MutableGraph::Node sF=res_graph_to_F.get(s); -// typename MutableGraph::Node tF=res_graph_to_F.get(t); - -// typename MutableGraph::EdgeMap original_edge(F); -// typename MutableGraph::EdgeMap residual_capacity(F); - -// //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))); -// original_edge.update(); -// original_edge.set(f, e); -// residual_capacity.update(); -// residual_capacity.set(f, res_graph.free(e)); -// } -// } - MutableGraph F; - //typedef SubGraphWrapper > FilterResGraph; - //FilterResGraph filter_res_graph(res_graph, dist); + typedef SubGraphWrapper > FilterResGraph; + FilterResGraph filter_res_graph(res_graph, dist); typename AugGraph::NodeMap res_graph_to_F(res_graph); @@ -496,8 +366,6 @@ //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) { + for(typename FilterResGraph::EdgeIt e=filter_res_graph.template first(); 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 MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); original_edge.update(); @@ -505,5 +373,5 @@ residual_capacity.update(); residual_capacity.set(f, res_graph.free(e)); - } + //} } @@ -565,353 +433,17 @@ } - template bool augmentOnBlockingFlow1() { - bool _augment=false; - - AugGraph res_graph(*G, *flow, *capacity); - - //bfs for distances on the residual graph - typedef typename AugGraph::NodeMap ReachedMap; - BfsIterator5< AugGraph, ReachedMap > bfs(res_graph); - bfs.pushAndSetReached(s); - typename AugGraph::NodeMap dist(res_graph); //filled up with 0's - - //F will contain the physical copy of the residual graph - //with the set of edges which areon shortest paths - MutableGraph F; - typename AugGraph::NodeMap - res_graph_to_F(res_graph); - for(typename AugGraph::NodeIt n=res_graph.template first(); res_graph.valid(n); res_graph.next(n)) { - res_graph_to_F.set(n, F.addNode()); - } - typename MutableGraph::Node sF=res_graph_to_F.get(s); - typename MutableGraph::Node tF=res_graph_to_F.get(t); - typename MutableGraph::EdgeMap original_edge(F); - typename MutableGraph::EdgeMap residual_capacity(F); - - while ( !bfs.finished() ) { - AugOutEdgeIt e=bfs; - if (res_graph.valid(e)) { - if (bfs.isBNodeNewlyReached()) { - dist.set(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))); - original_edge.update(); - original_edge.set(f, e); - residual_capacity.update(); - residual_capacity.set(f, res_graph.free(e)); - } else { - 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))); - original_edge.update(); - original_edge.set(f, e); - residual_capacity.update(); - residual_capacity.set(f, res_graph.free(e)); - } - } - } - ++bfs; - } //computing distances from s in the residual graph - - bool __augment=true; - - while (__augment) { - __augment=false; - //computing blocking flow with dfs - typedef typename TrivGraphWrapper::NodeMap BlockingReachedMap; - DfsIterator5< TrivGraphWrapper/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F); - typename MutableGraph::NodeMap pred(F); - pred.set(sF, typename MutableGraph::Edge(INVALID)); - //invalid iterators for sources - - typename MutableGraph::NodeMap free(F); - - dfs.pushAndSetReached(sF); - while (!dfs.finished()) { - ++dfs; - if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { - if (dfs.isBNodeNewlyReached()) { - typename MutableGraph::Node v=F.aNode(dfs); - typename MutableGraph::Node w=F.bNode(dfs); - pred.set(w, dfs); - if (F.valid(pred.get(v))) { - free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); - } else { - free.set(w, residual_capacity.get(dfs)); - } - if (w==tF) { - __augment=true; - _augment=true; - break; - } - - } else { - F.erase(typename MutableGraph::OutEdgeIt(dfs)); - } - } - } - - if (__augment) { - typename MutableGraph::Node n=tF; - Number augment_value=free.get(tF); - 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); - if (residual_capacity.get(e)==augment_value) - F.erase(e); - else - residual_capacity.set(e, residual_capacity.get(e)-augment_value); - } - } - - } - - return _augment; - } - bool augmentOnBlockingFlow2() { - bool _augment=false; - - //typedef ErasingResGraphWrapper EAugGraph; - typedef FilterGraphWrapper< ErasingResGraphWrapper > EAugGraph; - typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; - typedef typename EAugGraph::Edge EAugEdge; - - EAugGraph res_graph(*G, *flow, *capacity); - - //typedef typename EAugGraph::NodeMap ReachedMap; - BfsIterator5< - ErasingResGraphWrapper, - /*typename ErasingResGraphWrapper::OutEdgeIt,*/ - ErasingResGraphWrapper::NodeMap > bfs(res_graph); - - bfs.pushAndSetReached(s); - - typename ErasingResGraphWrapper:: - NodeMap& dist=res_graph.dist; - - 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); - } - ++bfs; - } //computing distances from s in the residual graph - - bool __augment=true; - - while (__augment) { - - __augment=false; - //computing blocking flow with dfs - typedef typename EAugGraph::NodeMap BlockingReachedMap; - DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > - dfs(res_graph); - typename EAugGraph::NodeMap pred(res_graph); - pred.set(s, EAugEdge(INVALID)); - //invalid iterators for sources - - typename EAugGraph::NodeMap free(res_graph); - - dfs.pushAndSetReached(s); - while (!dfs.finished()) { - ++dfs; - if (res_graph.valid(EAugOutEdgeIt(dfs))) { - if (dfs.isBNodeNewlyReached()) { - - typename EAugGraph::Node v=res_graph.aNode(dfs); - typename EAugGraph::Node w=res_graph.bNode(dfs); - - pred.set(w, EAugOutEdgeIt(dfs)); - if (res_graph.valid(pred.get(v))) { - free.set(w, std::min(free.get(v), res_graph.free(dfs))); - } else { - free.set(w, res_graph.free(dfs)); - } - - if (w==t) { - __augment=true; - _augment=true; - break; - } - } else { - res_graph.erase(dfs); - } - } - - } - - if (__augment) { - typename EAugGraph::Node n=t; - Number augment_value=free.get(t); - while (res_graph.valid(pred.get(n))) { - EAugEdge e=pred.get(n); - res_graph.augment(e, augment_value); - n=res_graph.tail(e); - if (res_graph.free(e)==0) - res_graph.erase(e); - } - } - - } - - return _augment; - } - void run() { - //int num_of_augmentations=0; - while (augmentOnShortestPath()) { - //while (augmentOnBlockingFlow()) { - //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</*getF*/first(e, s); G->valid(e); G->next(e)) { - a+=flow->get(e); - } - return a; - } - }; - - - template - class MaxMatching { - public: - typedef typename Graph::Node Node; - typedef typename Graph::NodeIt NodeIt; - typedef typename Graph::Edge Edge; - typedef typename Graph::EdgeIt EdgeIt; - typedef typename Graph::OutEdgeIt OutEdgeIt; - typedef typename Graph::InEdgeIt InEdgeIt; - - typedef typename Graph::NodeMap SMap; - typedef typename Graph::NodeMap TMap; - private: - const Graph* G; - SMap* S; - TMap* T; - //Node s; - //Node t; - FlowMap* flow; - const CapacityMap* capacity; - typedef ResGraphWrapper AugGraph; - typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; - typedef typename AugGraph::Edge AugEdge; - typename Graph::NodeMap used; //0 - - public: - MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) : - G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { } - bool augmentOnShortestPath() { - AugGraph res_graph(*G, *flow, *capacity); - bool _augment=false; - - typedef typename AugGraph::NodeMap ReachedMap; - BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph); - typename AugGraph::NodeMap pred(res_graph); - for(NodeIt s=G->template first(); G->valid(s); G->next(s)) { - if ((S->get(s)) && (used.get(s)<1) ) { - //Number u=0; - //for(OutEdgeIt e=G->template first(s); G->valid(e); G->next(e)) - //u+=flow->get(e); - //if (u<1) { - res_bfs.pushAndSetReached(s); - pred.set(s, AugEdge(INVALID)); - //} - } - } - - typename AugGraph::NodeMap free(res_graph); - - Node n; - //searching for augmenting path - while ( !res_bfs.finished() ) { - AugOutEdgeIt e=res_bfs; - if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) { - Node v=res_graph.tail(e); - Node w=res_graph.head(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); - if (T->get(n) && (used.get(n)<1) ) { - //Number u=0; - //for(InEdgeIt f=G->template first(n); G->valid(f); G->next(f)) - //u+=flow->get(f); - //if (u<1) { - _augment=true; - break; - //} - } - } - - ++res_bfs; - } //end of searching augmenting path - - if (_augment) { - //Node n=t; - used.set(n, 1); //mind2 vegen jav - Number augment_value=free.get(n); - while (res_graph.valid(pred.get(n))) { - AugEdge e=pred.get(n); - res_graph.augment(e, augment_value); - n=res_graph.tail(e); - } - used.set(n, 1); //mind2 vegen jav - } - - return _augment; - } - -// template bool augmentOnBlockingFlow() { +// template bool augmentOnBlockingFlow1() { // bool _augment=false; // AugGraph res_graph(*G, *flow, *capacity); +// //bfs for distances on the residual graph // typedef typename AugGraph::NodeMap ReachedMap; -// BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); - - - - - -// //typename AugGraph::NodeMap pred(res_graph); -// for(NodeIt s=G->template first(); G->valid(s); G->next(s)) { -// if (S->get(s)) { -// Number u=0; -// for(OutEdgeIt e=G->template first(s); G->valid(e); G->next(e)) -// u+=flow->get(e); -// if (u<1) { -// res_bfs.pushAndSetReached(s); -// //pred.set(s, AugEdge(INVALID)); -// } -// } -// } - - - - -// //bfs.pushAndSetReached(s); +// BfsIterator5< AugGraph, ReachedMap > bfs(res_graph); +// bfs.pushAndSetReached(s); // typename AugGraph::NodeMap dist(res_graph); //filled up with 0's -// 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); -// } - -// ++bfs; -// } //computing distances from s in the residual graph - + +// //F will contain the physical copy of the residual graph +// //with the set of edges which areon shortest paths // MutableGraph F; // typename AugGraph::NodeMap @@ -920,22 +452,31 @@ // res_graph_to_F.set(n, F.addNode()); // } - // typename MutableGraph::Node sF=res_graph_to_F.get(s); // typename MutableGraph::Node tF=res_graph_to_F.get(t); - // typename MutableGraph::EdgeMap original_edge(F); // typename MutableGraph::EdgeMap residual_capacity(F); -// //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))); -// original_edge.update(); -// original_edge.set(f, e); -// residual_capacity.update(); -// residual_capacity.set(f, res_graph.free(e)); -// } -// } +// while ( !bfs.finished() ) { +// AugOutEdgeIt e=bfs; +// if (res_graph.valid(e)) { +// if (bfs.isBNodeNewlyReached()) { +// dist.set(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))); +// original_edge.update(); +// original_edge.set(f, e); +// residual_capacity.update(); +// residual_capacity.set(f, res_graph.free(e)); +// } else { +// 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))); +// original_edge.update(); +// original_edge.set(f, e); +// residual_capacity.update(); +// residual_capacity.set(f, res_graph.free(e)); +// } +// } +// } +// ++bfs; +// } //computing distances from s in the residual graph // bool __augment=true; @@ -944,6 +485,6 @@ // __augment=false; // //computing blocking flow with dfs -// typedef typename MutableGraph::NodeMap BlockingReachedMap; -// DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F); +// typedef typename TrivGraphWrapper::NodeMap BlockingReachedMap; +// DfsIterator5< TrivGraphWrapper/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F); // typename MutableGraph::NodeMap pred(F); // pred.set(sF, typename MutableGraph::Edge(INVALID)); @@ -995,138 +536,100 @@ // return _augment; // } - bool augmentOnBlockingFlow2() { - bool _augment=false; - - //typedef ErasingResGraphWrapper EAugGraph; - typedef FilterGraphWrapper< ErasingResGraphWrapper > EAugGraph; - typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; - typedef typename EAugGraph::Edge EAugEdge; - - EAugGraph res_graph(*G, *flow, *capacity); - - //typedef typename EAugGraph::NodeMap ReachedMap; - BfsIterator5< - ErasingResGraphWrapper, - /*typename ErasingResGraphWrapper::OutEdgeIt,*/ - ErasingResGraphWrapper::NodeMap > bfs(res_graph); - - - //typename AugGraph::NodeMap pred(res_graph); - for(NodeIt s=G->template first(); G->valid(s); G->next(s)) { - if (S->get(s)) { - Number u=0; - for(OutEdgeIt e=G->template first(s); G->valid(e); G->next(e)) - u+=flow->get(e); - if (u<1) { - bfs.pushAndSetReached(s); - //pred.set(s, AugEdge(INVALID)); - } - } - } - +// bool augmentOnBlockingFlow2() { +// bool _augment=false; + +// //typedef ErasingResGraphWrapper EAugGraph; +// typedef FilterGraphWrapper< ErasingResGraphWrapper > EAugGraph; +// typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; +// typedef typename EAugGraph::Edge EAugEdge; + +// EAugGraph res_graph(*G, *flow, *capacity); + +// //typedef typename EAugGraph::NodeMap ReachedMap; +// BfsIterator5< +// ErasingResGraphWrapper, +// /*typename ErasingResGraphWrapper::OutEdgeIt,*/ +// ErasingResGraphWrapper::NodeMap > bfs(res_graph); - //bfs.pushAndSetReached(s); - - typename ErasingResGraphWrapper:: - NodeMap& dist=res_graph.dist; - - 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); - } - ++bfs; - } //computing distances from s in the residual graph - - bool __augment=true; - - while (__augment) { - - __augment=false; - //computing blocking flow with dfs - typedef typename EAugGraph::NodeMap BlockingReachedMap; - DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > - dfs(res_graph); - typename EAugGraph::NodeMap pred(res_graph, INVALID); - //pred.set(s, EAugEdge(INVALID)); - //invalid iterators for sources - - typename EAugGraph::NodeMap free(res_graph); - - - //typename AugGraph::NodeMap pred(res_graph); - for(NodeIt s=G->template first(); G->valid(s); G->next(s)) { - if (S->get(s)) { - Number u=0; - for(OutEdgeIt e=G->template first(s); G->valid(e); G->next(e)) - u+=flow->get(e); - if (u<1) { - dfs.pushAndSetReached(s); - //pred.set(s, AugEdge(INVALID)); - } - } - } - - - - //dfs.pushAndSetReached(s); - typename EAugGraph::Node n; - while (!dfs.finished()) { - ++dfs; - if (res_graph.valid(EAugOutEdgeIt(dfs))) { - if (dfs.isBNodeNewlyReached()) { +// bfs.pushAndSetReached(s); + +// typename ErasingResGraphWrapper:: +// NodeMap& dist=res_graph.dist; + +// 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); +// } +// ++bfs; +// } //computing distances from s in the residual graph + +// bool __augment=true; + +// while (__augment) { + +// __augment=false; +// //computing blocking flow with dfs +// typedef typename EAugGraph::NodeMap BlockingReachedMap; +// DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > +// dfs(res_graph); +// typename EAugGraph::NodeMap pred(res_graph); +// pred.set(s, EAugEdge(INVALID)); +// //invalid iterators for sources + +// typename EAugGraph::NodeMap free(res_graph); + +// dfs.pushAndSetReached(s); +// while (!dfs.finished()) { +// ++dfs; +// if (res_graph.valid(EAugOutEdgeIt(dfs))) { +// if (dfs.isBNodeNewlyReached()) { - typename EAugGraph::Node v=res_graph.aNode(dfs); - typename EAugGraph::Node w=res_graph.bNode(dfs); - - pred.set(w, EAugOutEdgeIt(dfs)); - if (res_graph.valid(pred.get(v))) { - free.set(w, std::min(free.get(v), res_graph.free(dfs))); - } else { - free.set(w, res_graph.free(dfs)); - } - - n=w; - if (T->get(w)) { - Number u=0; - for(InEdgeIt f=G->template first(n); G->valid(f); G->next(f)) - u+=flow->get(f); - if (u<1) { - __augment=true; - _augment=true; - break; - } - } - } else { - res_graph.erase(dfs); - } - } - - } - - if (__augment) { - // typename EAugGraph::Node n=t; - Number augment_value=free.get(n); - while (res_graph.valid(pred.get(n))) { - EAugEdge e=pred.get(n); - res_graph.augment(e, augment_value); - n=res_graph.tail(e); - if (res_graph.free(e)==0) - res_graph.erase(e); - } - } +// typename EAugGraph::Node v=res_graph.aNode(dfs); +// typename EAugGraph::Node w=res_graph.bNode(dfs); + +// pred.set(w, EAugOutEdgeIt(dfs)); +// if (res_graph.valid(pred.get(v))) { +// free.set(w, std::min(free.get(v), res_graph.free(dfs))); +// } else { +// free.set(w, res_graph.free(dfs)); +// } + +// if (w==t) { +// __augment=true; +// _augment=true; +// break; +// } +// } else { +// res_graph.erase(dfs); +// } +// } + +// } + +// if (__augment) { +// typename EAugGraph::Node n=t; +// Number augment_value=free.get(t); +// while (res_graph.valid(pred.get(n))) { +// EAugEdge e=pred.get(n); +// res_graph.augment(e, augment_value); +// n=res_graph.tail(e); +// if (res_graph.free(e)==0) +// res_graph.erase(e); +// } +// } - } +// } - return _augment; - } - void run() { - //int num_of_augmentations=0; - while (augmentOnShortestPath()) { - //while (augmentOnBlockingFlow()) { - //std::cout << ++num_of_augmentations << " "; - //std::cout<()) { +// //std::cout << ++num_of_augmentations << " "; +// //std::cout< void run() { // //int num_of_augmentations=0; @@ -1136,9 +639,9 @@ // //std::cout</*getF*/first(e); G->valid(e); G->next(e)) { + OutEdgeIt e; + for(gw.first(e, s); gw.valid(e); gw.next(e)) { a+=flow->get(e); } @@ -1148,72 +651,75 @@ - - - - // template -// class MaxFlow2 { +// class MaxMatching { // public: // typedef typename Graph::Node Node; +// typedef typename Graph::NodeIt NodeIt; // typedef typename Graph::Edge Edge; // typedef typename Graph::EdgeIt EdgeIt; // typedef typename Graph::OutEdgeIt OutEdgeIt; // typedef typename Graph::InEdgeIt InEdgeIt; + +// typedef typename Graph::NodeMap SMap; +// typedef typename Graph::NodeMap TMap; // private: -// const Graph& G; -// std::list& S; -// std::list& T; -// FlowMap& flow; -// const CapacityMap& capacity; +// const Graph* G; +// SMap* S; +// TMap* T; +// //Node s; +// //Node t; +// FlowMap* flow; +// const CapacityMap* capacity; // typedef ResGraphWrapper AugGraph; // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; // typedef typename AugGraph::Edge AugEdge; -// typename Graph::NodeMap SMap; -// typename Graph::NodeMap TMap; +// typename Graph::NodeMap used; //0 + // public: -// MaxFlow2(const Graph& _G, std::list& _S, std::list& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) { -// for(typename std::list::const_iterator i=S.begin(); -// i!=S.end(); ++i) { -// SMap.set(*i, true); -// } -// for (typename std::list::const_iterator i=T.begin(); -// i!=T.end(); ++i) { -// TMap.set(*i, true); -// } -// } -// bool augment() { -// AugGraph res_graph(G, flow, capacity); +// MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) : +// G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { } +// bool augmentOnShortestPath() { +// AugGraph res_graph(*G, *flow, *capacity); // bool _augment=false; -// Node reached_t_node; // typedef typename AugGraph::NodeMap ReachedMap; -// BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph); -// for(typename std::list::const_iterator i=S.begin(); -// i!=S.end(); ++i) { -// res_bfs.pushAndSetReached(*i); +// BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph); +// typename AugGraph::NodeMap pred(res_graph); +// for(NodeIt s=G->template first(); G->valid(s); G->next(s)) { +// if ((S->get(s)) && (used.get(s)<1) ) { +// //Number u=0; +// //for(OutEdgeIt e=G->template first(s); G->valid(e); G->next(e)) +// //u+=flow->get(e); +// //if (u<1) { +// res_bfs.pushAndSetReached(s); +// pred.set(s, AugEdge(INVALID)); +// //} +// } // } -// //res_bfs.pushAndSetReached(s); - -// typename AugGraph::NodeMap pred(res_graph); -// //filled up with invalid iterators // typename AugGraph::NodeMap free(res_graph); +// Node n; // //searching for augmenting path // while ( !res_bfs.finished() ) { -// AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs); -// if (e.valid() && res_bfs.isBNodeNewlyReached()) { +// AugOutEdgeIt e=res_bfs; +// if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) { // Node v=res_graph.tail(e); // Node w=res_graph.head(e); // pred.set(w, e); -// if (pred.get(v).valid()) { -// free.set(w, std::min(free.get(v), e.free())); +// if (res_graph.valid(pred.get(v))) { +// free.set(w, std::min(free.get(v), res_graph.free(e))); // } else { -// free.set(w, e.free()); +// free.set(w, res_graph.free(e)); // } -// if (TMap.get(res_graph.head(e))) { -// _augment=true; -// reached_t_node=res_graph.head(e); -// break; +// n=res_graph.head(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)) +// //u+=flow->get(f); +// //if (u<1) { +// _augment=true; +// break; +// //} // } // } @@ -1223,28 +729,285 @@ // if (_augment) { -// Node n=reached_t_node; -// Number augment_value=free.get(reached_t_node); -// while (pred.get(n).valid()) { +// //Node n=t; +// used.set(n, 1); //mind2 vegen jav +// Number augment_value=free.get(n); +// while (res_graph.valid(pred.get(n))) { // AugEdge e=pred.get(n); -// e.augment(augment_value); +// res_graph.augment(e, augment_value); // n=res_graph.tail(e); // } +// used.set(n, 1); //mind2 vegen jav // } +// return _augment; +// } + +// // template bool augmentOnBlockingFlow() { +// // bool _augment=false; + +// // AugGraph res_graph(*G, *flow, *capacity); + +// // typedef typename AugGraph::NodeMap ReachedMap; +// // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); + + + + + +// // //typename AugGraph::NodeMap pred(res_graph); +// // for(NodeIt s=G->template first(); G->valid(s); G->next(s)) { +// // if (S->get(s)) { +// // Number u=0; +// // for(OutEdgeIt e=G->template first(s); G->valid(e); G->next(e)) +// // u+=flow->get(e); +// // if (u<1) { +// // res_bfs.pushAndSetReached(s); +// // //pred.set(s, AugEdge(INVALID)); +// // } +// // } +// // } + + + + +// // //bfs.pushAndSetReached(s); +// // typename AugGraph::NodeMap dist(res_graph); //filled up with 0's +// // 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); +// // } + +// // ++bfs; +// // } //computing distances from s in the residual graph + +// // MutableGraph F; +// // typename AugGraph::NodeMap +// // res_graph_to_F(res_graph); +// // for(typename AugGraph::NodeIt n=res_graph.template first(); res_graph.valid(n); res_graph.next(n)) { +// // res_graph_to_F.set(n, F.addNode()); +// // } + +// // typename MutableGraph::Node sF=res_graph_to_F.get(s); +// // typename MutableGraph::Node tF=res_graph_to_F.get(t); + +// // typename MutableGraph::EdgeMap original_edge(F); +// // typename MutableGraph::EdgeMap residual_capacity(F); + +// // //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))); +// // original_edge.update(); +// // original_edge.set(f, e); +// // residual_capacity.update(); +// // residual_capacity.set(f, res_graph.free(e)); +// // } +// // } + +// // 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); +// // pred.set(sF, typename MutableGraph::Edge(INVALID)); +// // //invalid iterators for sources + +// // typename MutableGraph::NodeMap free(F); + +// // dfs.pushAndSetReached(sF); +// // while (!dfs.finished()) { +// // ++dfs; +// // if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { +// // if (dfs.isBNodeNewlyReached()) { +// // typename MutableGraph::Node v=F.aNode(dfs); +// // typename MutableGraph::Node w=F.bNode(dfs); +// // pred.set(w, dfs); +// // if (F.valid(pred.get(v))) { +// // free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); +// // } else { +// // free.set(w, residual_capacity.get(dfs)); +// // } +// // if (w==tF) { +// // __augment=true; +// // _augment=true; +// // break; +// // } + +// // } else { +// // F.erase(typename MutableGraph::OutEdgeIt(dfs)); +// // } +// // } +// // } + +// // if (__augment) { +// // typename MutableGraph::Node n=tF; +// // Number augment_value=free.get(tF); +// // 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); +// // if (residual_capacity.get(e)==augment_value) +// // F.erase(e); +// // else +// // residual_capacity.set(e, residual_capacity.get(e)-augment_value); +// // } +// // } + +// // } + +// // return _augment; +// // } +// bool augmentOnBlockingFlow2() { +// bool _augment=false; + +// //typedef ErasingResGraphWrapper EAugGraph; +// typedef FilterGraphWrapper< ErasingResGraphWrapper > EAugGraph; +// typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; +// typedef typename EAugGraph::Edge EAugEdge; + +// EAugGraph res_graph(*G, *flow, *capacity); + +// //typedef typename EAugGraph::NodeMap ReachedMap; +// BfsIterator5< +// ErasingResGraphWrapper, +// /*typename ErasingResGraphWrapper::OutEdgeIt,*/ +// ErasingResGraphWrapper::NodeMap > bfs(res_graph); + + +// //typename AugGraph::NodeMap pred(res_graph); +// for(NodeIt s=G->template first(); G->valid(s); G->next(s)) { +// if (S->get(s)) { +// Number u=0; +// for(OutEdgeIt e=G->template first(s); G->valid(e); G->next(e)) +// u+=flow->get(e); +// if (u<1) { +// bfs.pushAndSetReached(s); +// //pred.set(s, AugEdge(INVALID)); +// } +// } +// } + + +// //bfs.pushAndSetReached(s); + +// typename ErasingResGraphWrapper:: +// NodeMap& dist=res_graph.dist; + +// 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); +// } +// ++bfs; +// } //computing distances from s in the residual graph + +// bool __augment=true; + +// while (__augment) { + +// __augment=false; +// //computing blocking flow with dfs +// typedef typename EAugGraph::NodeMap BlockingReachedMap; +// DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > +// dfs(res_graph); +// typename EAugGraph::NodeMap pred(res_graph, INVALID); +// //pred.set(s, EAugEdge(INVALID)); +// //invalid iterators for sources + +// typename EAugGraph::NodeMap free(res_graph); + + +// //typename AugGraph::NodeMap pred(res_graph); +// for(NodeIt s=G->template first(); G->valid(s); G->next(s)) { +// if (S->get(s)) { +// Number u=0; +// for(OutEdgeIt e=G->template first(s); G->valid(e); G->next(e)) +// u+=flow->get(e); +// if (u<1) { +// dfs.pushAndSetReached(s); +// //pred.set(s, AugEdge(INVALID)); +// } +// } +// } + + + +// //dfs.pushAndSetReached(s); +// typename EAugGraph::Node n; +// while (!dfs.finished()) { +// ++dfs; +// if (res_graph.valid(EAugOutEdgeIt(dfs))) { +// if (dfs.isBNodeNewlyReached()) { + +// typename EAugGraph::Node v=res_graph.aNode(dfs); +// typename EAugGraph::Node w=res_graph.bNode(dfs); + +// pred.set(w, EAugOutEdgeIt(dfs)); +// if (res_graph.valid(pred.get(v))) { +// free.set(w, std::min(free.get(v), res_graph.free(dfs))); +// } else { +// free.set(w, res_graph.free(dfs)); +// } + +// n=w; +// if (T->get(w)) { +// Number u=0; +// for(InEdgeIt f=G->template first(n); G->valid(f); G->next(f)) +// u+=flow->get(f); +// if (u<1) { +// __augment=true; +// _augment=true; +// break; +// } +// } +// } else { +// res_graph.erase(dfs); +// } +// } + +// } + +// if (__augment) { +// // typename EAugGraph::Node n=t; +// Number augment_value=free.get(n); +// while (res_graph.valid(pred.get(n))) { +// EAugEdge e=pred.get(n); +// res_graph.augment(e, augment_value); +// n=res_graph.tail(e); +// if (res_graph.free(e)==0) +// res_graph.erase(e); +// } +// } + +// } + // return _augment; // } // void run() { -// while (augment()) { } +// //int num_of_augmentations=0; +// while (augmentOnShortestPath()) { +// //while (augmentOnBlockingFlow()) { +// //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<::const_iterator i=S.begin(); -// i!=S.end(); ++i) { -// for(OutEdgeIt e=G.template first(*i); e.valid(); ++e) { -// a+=flow.get(e); -// } -// for(InEdgeIt e=G.template first(*i); e.valid(); ++e) { -// a-=flow.get(e); -// } +// EdgeIt e; +// for(G->/*getF*/first(e); G->valid(e); G->next(e)) { +// a+=flow->get(e); // } // return a; @@ -1254,4 +1017,108 @@ + + + +// // template +// // class MaxFlow2 { +// // public: +// // typedef typename Graph::Node Node; +// // typedef typename Graph::Edge Edge; +// // typedef typename Graph::EdgeIt EdgeIt; +// // typedef typename Graph::OutEdgeIt OutEdgeIt; +// // typedef typename Graph::InEdgeIt InEdgeIt; +// // private: +// // const Graph& G; +// // std::list& S; +// // std::list& T; +// // FlowMap& flow; +// // const CapacityMap& capacity; +// // typedef ResGraphWrapper AugGraph; +// // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; +// // typedef typename AugGraph::Edge AugEdge; +// // typename Graph::NodeMap SMap; +// // typename Graph::NodeMap TMap; +// // public: +// // MaxFlow2(const Graph& _G, std::list& _S, std::list& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) { +// // for(typename std::list::const_iterator i=S.begin(); +// // i!=S.end(); ++i) { +// // SMap.set(*i, true); +// // } +// // for (typename std::list::const_iterator i=T.begin(); +// // i!=T.end(); ++i) { +// // TMap.set(*i, true); +// // } +// // } +// // bool augment() { +// // AugGraph res_graph(G, flow, capacity); +// // bool _augment=false; +// // Node reached_t_node; + +// // typedef typename AugGraph::NodeMap ReachedMap; +// // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph); +// // for(typename std::list::const_iterator i=S.begin(); +// // i!=S.end(); ++i) { +// // res_bfs.pushAndSetReached(*i); +// // } +// // //res_bfs.pushAndSetReached(s); + +// // typename AugGraph::NodeMap pred(res_graph); +// // //filled up with invalid iterators + +// // typename AugGraph::NodeMap free(res_graph); + +// // //searching for augmenting path +// // while ( !res_bfs.finished() ) { +// // AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs); +// // if (e.valid() && res_bfs.isBNodeNewlyReached()) { +// // Node v=res_graph.tail(e); +// // Node 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 (TMap.get(res_graph.head(e))) { +// // _augment=true; +// // reached_t_node=res_graph.head(e); +// // break; +// // } +// // } + +// // ++res_bfs; +// // } //end of searching augmenting path + +// // if (_augment) { +// // Node n=reached_t_node; +// // Number augment_value=free.get(reached_t_node); +// // while (pred.get(n).valid()) { +// // AugEdge e=pred.get(n); +// // e.augment(augment_value); +// // n=res_graph.tail(e); +// // } +// // } + +// // return _augment; +// // } +// // void run() { +// // while (augment()) { } +// // } +// // Number flowValue() { +// // Number a=0; +// // for(typename std::list::const_iterator i=S.begin(); +// // i!=S.end(); ++i) { +// // for(OutEdgeIt e=G.template first(*i); e.valid(); ++e) { +// // a+=flow.get(e); +// // } +// // for(InEdgeIt e=G.template first(*i); e.valid(); ++e) { +// // a-=flow.get(e); +// // } +// // } +// // return a; +// // } +// // }; + + } // namespace hugo Index: src/work/marci/edmonds_karp_demo.cc =================================================================== --- src/work/marci/edmonds_karp_demo.cc (revision 243) +++ src/work/marci/edmonds_karp_demo.cc (revision 266) @@ -9,4 +9,9 @@ #include #include + +class CM { +public: + template int get(T) const {return 1;} +}; using namespace hugo; @@ -87,12 +92,15 @@ { //std::cout << "SmartGraph..." << std::endl; + typedef TrivGraphWrapper GW; + GW gw(G); std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl; - Graph::EdgeMap flow(G); //0 flow + GW::EdgeMap flow(G); //0 flow Timer ts; ts.reset(); - MaxFlow, Graph::EdgeMap > max_flow_test(G, s, t, flow, cap); - //max_flow_test.augmentWithBlockingFlow(); + typedef GW::EdgeMapWrapper< Graph::EdgeMap, int > EMW; + EMW cw(cap); + MaxFlow, EMW > max_flow_test(G, s, t, flow, cw); int i=0; while (max_flow_test.augmentOnBlockingFlow()) { @@ -114,16 +122,74 @@ } +// { +// //std::cout << "SmartGraph..." << std::endl; +// std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl; +// Graph::EdgeMap flow(G); //0 flow + +// Timer ts; +// ts.reset(); + +// MaxFlow, Graph::EdgeMap > max_flow_test(G, s, t, flow, cap); +// int i=0; +// while (max_flow_test.augmentOnBlockingFlow1()) { +// // for(EdgeIt e=G.template first(); e.valid(); ++e) { +// // std::cout<<"("<"<(); e.valid(); ++e) { +// // std::cout<<"("<"< flow(G); //0 flow + +// Timer ts; +// ts.reset(); + +// MaxFlow, Graph::EdgeMap > max_flow_test(G, s, t, flow, cap); +// int i=0; +// while (max_flow_test.augmentOnBlockingFlow2()) { +// // for(EdgeIt e=G.template first(); e.valid(); ++e) { +// // std::cout<<"("<"<(); e.valid(); ++e) { +// // std::cout<<"("<"< flow(G); //0 flow + typedef TrivGraphWrapper GW; + GW gw(G); + std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl; + GW::EdgeMap flow(gw); //0 flow Timer ts; ts.reset(); - MaxFlow, Graph::EdgeMap > max_flow_test(G, s, t, flow, cap); - //max_flow_test.augmentWithBlockingFlow(); + //CM cm; + typedef GW::EdgeMapWrapper< Graph::EdgeMap, int > EMW; + EMW cw(cap); + MaxFlow, EMW> max_flow_test(gw, s, t, flow, cw); int i=0; - while (max_flow_test.augmentOnBlockingFlow1()) { + while (max_flow_test.augmentOnShortestPath()) { // for(EdgeIt e=G.template first(); e.valid(); ++e) { // std::cout<<"("<"< flow(G); //0 flow - - Timer ts; - ts.reset(); - - MaxFlow, Graph::EdgeMap > max_flow_test(G, s, t, flow, cap); - //max_flow_test.augmentWithBlockingFlow(); - int i=0; - while (max_flow_test.augmentOnBlockingFlow2()) { -// for(EdgeIt e=G.template first(); e.valid(); ++e) { -// std::cout<<"("<"<(); e.valid(); ++e) { -// std::cout<<"("<"< flow(G); //0 flow - - Timer ts; - ts.reset(); - - MaxFlow, Graph::EdgeMap > max_flow_test(G, s, t, flow, cap); - //max_flow_test.augmentWithBlockingFlow(); - int i=0; - while (max_flow_test.augmentOnShortestPath()) { -// for(EdgeIt e=G.template first(); e.valid(); ++e) { -// std::cout<<"("<"<(); e.valid(); ++e) { -// std::cout<<"("<"< class NodeMap : public Graph::NodeMap { public: - NodeMap(const TrivGraphWrapper& _G) : + NodeMap(const TrivGraphWrapper& _G) : Graph::NodeMap(*(_G.graph)) { } NodeMap(const TrivGraphWrapper& _G, T a) : @@ -132,8 +132,30 @@ template class EdgeMap : public Graph::EdgeMap { public: - EdgeMap(const TrivGraphWrapper& _G) : + EdgeMap(const TrivGraphWrapper& _G) : Graph::EdgeMap(*(_G.graph)) { } EdgeMap(const TrivGraphWrapper& _G, T a) : Graph::EdgeMap(*(_G.graph), a) { } + }; + + template class NodeMapWrapper { + protected: + Map* map; + public: + NodeMapWrapper(Map& _map) : map(&_map) { } + //template + void set(Node n, T a) { map->set(n, a); } + //template + T get(Node n) const { return map->get(n); } + }; + + template class EdgeMapWrapper { + protected: + Map* map; + public: + EdgeMapWrapper(Map& _map) : map(&_map) { } + //template + void set(Edge n, T a) { map->set(n, a); } + //template + T get(Edge n) const { return map->get(n); } }; }; @@ -248,5 +270,5 @@ template class NodeMap : public GraphWrapper::NodeMap { public: - NodeMap(const GraphWrapperSkeleton& _G) : + NodeMap(const GraphWrapperSkeleton& _G) : GraphWrapper::NodeMap(_G.gw) { } NodeMap(const GraphWrapperSkeleton& _G, T a) : @@ -256,5 +278,5 @@ template class EdgeMap : public GraphWrapper::EdgeMap { public: - EdgeMap(const GraphWrapperSkeleton& _G) : + EdgeMap(const GraphWrapperSkeleton& _G) : GraphWrapper::EdgeMap(_G.gw) { } EdgeMap(const GraphWrapperSkeleton& _G, T a) : @@ -760,5 +782,5 @@ template I& first(I& i) const { gw.first(i); return i; } template I& first(I& i, const P& p) const { - graph->first(i, p); return i; } + gw.first(i, p); return i; } OutEdgeIt& next(OutEdgeIt& e) const { @@ -912,24 +934,25 @@ - template - class ResGraphWrapper { + template + class ResGraphWrapper : public GraphWrapperSkeleton{ public: //typedef Graph BaseGraph; - typedef TrivGraphWrapper GraphWrapper; - typedef typename GraphWrapper::Node Node; - typedef typename GraphWrapper::NodeIt NodeIt; + //typedef TrivGraphWrapper GraphWrapper; + typedef typename GraphWrapperSkeleton::Node Node; + typedef typename GraphWrapperSkeleton::NodeIt NodeIt; private: - typedef typename GraphWrapper::OutEdgeIt OldOutEdgeIt; - typedef typename GraphWrapper::InEdgeIt OldInEdgeIt; + typedef typename GraphWrapperSkeleton::OutEdgeIt OldOutEdgeIt; + typedef typename GraphWrapperSkeleton::InEdgeIt OldInEdgeIt; protected: //const Graph* graph; - GraphWrapper gw; + //GraphWrapper gw; FlowMap* flow; const CapacityMap* capacity; public: - ResGraphWrapper(const Graph& _G, FlowMap& _flow, - const CapacityMap& _capacity) : - gw(_G), flow(&_flow), capacity(&_capacity) { } + ResGraphWrapper(const GraphWrapper& _gw, FlowMap& _flow, + const CapacityMap& _capacity) : + GraphWrapperSkeleton(_gw), + flow(&_flow), capacity(&_capacity) { } //void setGraph(const Graph& _graph) { graph = &_graph; } @@ -942,5 +965,5 @@ class Edge { - friend class ResGraphWrapper; + friend class ResGraphWrapper; protected: bool out_or_in; //true, iff out @@ -968,5 +991,5 @@ class OutEdgeIt : public Edge { - friend class ResGraphWrapper; + friend class ResGraphWrapper; public: OutEdgeIt() { } @@ -975,5 +998,5 @@ OutEdgeIt(const Invalid& i) : Edge(i) { } protected: - OutEdgeIt(const ResGraphWrapper& resG, Node v) : Edge() { + OutEdgeIt(const ResGraphWrapper& resG, Node v) : Edge() { resG.gw.first(out, v); while( resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); } @@ -1007,5 +1030,5 @@ class EdgeIt : public Edge { - friend class ResGraphWrapper; + friend class ResGraphWrapper; NodeIt v; public: @@ -1013,5 +1036,5 @@ //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { } EdgeIt(const Invalid& i) : Edge(i) { } - EdgeIt(const ResGraphWrapper& resG) : Edge() { + EdgeIt(const ResGraphWrapper& resG) : Edge() { resG.gw.first(v); if (resG.gw.valid(v)) resG.gw.first(out, v); else out=/*OldOutEdgeIt*/(INVALID); @@ -1067,5 +1090,5 @@ }; - NodeIt& first(NodeIt& v) const { return gw.first(v); } + NodeIt& first(NodeIt& v) const { gw.first(v); return v; } OutEdgeIt& first(OutEdgeIt& e, Node v) const { e=OutEdgeIt(*this, v); @@ -1186,11 +1209,11 @@ } - template class NodeMap : public GraphWrapper::NodeMap { - public: - NodeMap(const ResGraphWrapper& _G) - : GraphWrapper::NodeMap(_G.gw) { } - NodeMap(const ResGraphWrapper& _G, - T a) : GraphWrapper::NodeMap(_G.gw, a) { } - }; +// template class NodeMap : public GraphWrapper::NodeMap { +// public: +// NodeMap(const ResGraphWrapper& _G) +// : GraphWrapper::NodeMap(_G.gw) { } +// NodeMap(const ResGraphWrapper& _G, +// T a) : GraphWrapper::NodeMap(_G.gw, a) { } +// }; // template @@ -1208,6 +1231,6 @@ typename GraphWrapper::EdgeMap forward_map, backward_map; public: - EdgeMap(const ResGraphWrapper& _G) : forward_map(_G.gw), backward_map(_G.gw) { } - EdgeMap(const ResGraphWrapper& _G, T a) : forward_map(_G.gw, a), backward_map(_G.gw, a) { } + EdgeMap(const ResGraphWrapper& _G) : forward_map(_G.gw), backward_map(_G.gw) { } + EdgeMap(const ResGraphWrapper& _G, T a) : forward_map(_G.gw, a), backward_map(_G.gw, a) { } void set(Edge e, T a) { if (e.out_or_in) @@ -1225,241 +1248,241 @@ }; - template - class ErasingResGraphWrapper : public ResGraphWrapper { - protected: - ResGraphWrapper::NodeMap::OutEdgeIt> first_out_edges; - //ResGraphWrapper::NodeMap dist; - public: - ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow, - const CapacityMap& _capacity) : - ResGraphWrapper(_G, _flow, _capacity), - first_out_edges(*this) /*, dist(*this)*/ { - for(NodeIt n=this->template first(); this->valid(n); this->next(n)) { - OutEdgeIt e; - ResGraphWrapper::first(e, n); - first_out_edges.set(n, e); - } - } - - //void setGraph(Graph& _graph) { graph = &_graph; } - //Graph& getGraph() const { return (*graph); } - - //TrivGraphWrapper() : graph(0) { } - //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { } - - //typedef Graph BaseGraph; - - //typedef typename Graph::Node Node; - //typedef typename Graph::NodeIt NodeIt; - - //typedef typename Graph::Edge Edge; - //typedef typename Graph::OutEdgeIt OutEdgeIt; - //typedef typename Graph::InEdgeIt InEdgeIt; - //typedef typename Graph::SymEdgeIt SymEdgeIt; - //typedef typename Graph::EdgeIt EdgeIt; - - typedef typename ResGraphWrapper::Node Node; - typedef typename ResGraphWrapper::NodeIt NodeIt; - - typedef typename ResGraphWrapper::Edge Edge; - typedef typename ResGraphWrapper::OutEdgeIt OutEdgeIt; - //typedef typename ResGraphWrapper::InEdgeIt InEdgeIt; - //typedef typename Graph::SymEdgeIt SymEdgeIt; - //typedef typename ResGraphWrapper::EdgeIt EdgeIt; - - NodeIt& first(NodeIt& n) const { - return ResGraphWrapper::first(n); - } - - OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { - e=first_out_edges.get(n); - return e; - } - - //ROSSZ template I& first(I& i) const { return first(i); } - //ROSSZ template I& first(I& i, const P& p) const { - // return first(i, p); } - - //template I getNext(const I& i) const { - // return gw.getNext(i); } - //template I& next(I &i) const { return gw.next(i); } - - template< typename It > It first() const { - It e; first(e); return e; } - - template< typename It > It first(const Node& v) const { - It e; first(e, v); return e; } - - //Node head(const Edge& e) const { return gw.head(e); } - //Node tail(const Edge& e) const { return gw.tail(e); } - - //template bool valid(const I& i) const - // { return gw.valid(i); } - - //int nodeNum() const { return gw.nodeNum(); } - //int edgeNum() const { return gw.edgeNum(); } - - //template Node aNode(const I& e) const { - // return gw.aNode(e); } - //template Node bNode(const I& e) const { - // return gw.bNode(e); } - - //Node addNode() const { return gw.addNode(); } - //Edge addEdge(const Node& tail, const Node& head) const { - // return gw.addEdge(tail, head); } - - //void erase(const OutEdgeIt& e) { - // first_out_edge(this->tail(e))=e; - //} - void erase(const Edge& e) { - OutEdgeIt f(e); - next(f); - first_out_edges.set(this->tail(e), f); - } - //template void erase(const I& i) const { gw.erase(i); } - - //void clear() const { gw.clear(); } - - template class NodeMap : public ResGraphWrapper::NodeMap { - public: - NodeMap(const ErasingResGraphWrapper& _G) : - ResGraphWrapper::NodeMap(_G /*_G.getGraph()*/) { } - NodeMap(const ErasingResGraphWrapper& _G, T a) : - ResGraphWrapper::NodeMap(_G /*_G.getGraph()*/, a) { } - }; - - template class EdgeMap : public ResGraphWrapper::EdgeMap { - public: - EdgeMap(const ErasingResGraphWrapper& _G) : - ResGraphWrapper::EdgeMap(_G /*_G.getGraph()*/) { } - EdgeMap(const ErasingResGraphWrapper& _G, T a) : - ResGraphWrapper::EdgeMap(_G /*_G.getGraph()*/, a) { } - }; - }; - - template - class FilterGraphWrapper { - }; - - template - class FilterGraphWrapper > : public ErasingResGraphWrapper { - - //Graph* graph; - - public: - //typedef Graph BaseGraph; - - typedef typename ErasingResGraphWrapper::Node Node; - typedef typename ErasingResGraphWrapper::NodeIt NodeIt; - - typedef typename ErasingResGraphWrapper::Edge Edge; - typedef typename ErasingResGraphWrapper::OutEdgeIt OutEdgeIt; - //typedef typename ErasingResGraphWrapper::InEdgeIt InEdgeIt; - //typedef typename Graph::SymEdgeIt SymEdgeIt; - typedef typename ErasingResGraphWrapper::EdgeIt EdgeIt; - - //FilterGraphWrapper::NodeMap::OutEdgeIt> first_out_edges; - - public: - FilterGraphWrapper(const Graph& _G, FlowMap& _flow, - const CapacityMap& _capacity) : - ErasingResGraphWrapper(_G, _flow, _capacity), dist(*this, gw.nodeNum()) { - } - - OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { - ErasingResGraphWrapper::first(e, n); - while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e)))) - ErasingResGraphWrapper::next(e); - return e; - } - - NodeIt& next(NodeIt& e) const { - return ErasingResGraphWrapper::next(e); - } - - OutEdgeIt& next(OutEdgeIt& e) const { - ErasingResGraphWrapper::next(e); - while (valid(e) && (dist.get(tail(e))/*+1!*/>=dist.get(head(e)))) - ErasingResGraphWrapper::next(e); - return e; - } - - NodeIt& first(NodeIt& n) const { - return ErasingResGraphWrapper::first(n); - } - - void erase(const Edge& e) { - OutEdgeIt f(e); - ErasingResGraphWrapper::next(f); - while (valid(f) && (dist.get(tail(f))/*+1!=*/>=dist.get(head(f)))) - ErasingResGraphWrapper::next(f); - first_out_edges.set(this->tail(e), f); - } - - //TrivGraphWrapper() : graph(0) { } - //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { } - - //void setGraph(Graph& _graph) { graph = &_graph; } - //Graph& getGraph() const { return (*graph); } - - //template I& first(I& i) const { return gw.first(i); } - //template I& first(I& i, const P& p) const { - // return gw.first(i, p); } - - //template I getNext(const I& i) const { - // return gw.getNext(i); } - //template I& next(I &i) const { return gw.next(i); } - - template< typename It > It first() const { - It e; first(e); return e; } - - template< typename It > It first(const Node& v) const { - It e; first(e, v); return e; } - - //Node head(const Edge& e) const { return gw.head(e); } - //Node tail(const Edge& e) const { return gw.tail(e); } - - //template bool valid(const I& i) const - // { return gw.valid(i); } - - //template void setInvalid(const I &i); - //{ return gw.setInvalid(i); } - - //int nodeNum() const { return gw.nodeNum(); } - //int edgeNum() const { return gw.edgeNum(); } - - //template Node aNode(const I& e) const { - // return gw.aNode(e); } - //template Node bNode(const I& e) const { - // return gw.bNode(e); } - - //Node addNode() const { return gw.addNode(); } - //Edge addEdge(const Node& tail, const Node& head) const { - // return gw.addEdge(tail, head); } - - //template void erase(const I& i) const { gw.erase(i); } - - //void clear() const { gw.clear(); } - - template class NodeMap : public ErasingResGraphWrapper::NodeMap { - public: - NodeMap(const FilterGraphWrapper >& _G) : - ErasingResGraphWrapper::NodeMap(_G /*_G.getGraph()*/) { } - NodeMap(const FilterGraphWrapper >& _G, T a) : - ErasingResGraphWrapper::NodeMap(_G /*_G.getGraph()*/, a) { } - }; - - template class EdgeMap : public ErasingResGraphWrapper::EdgeMap { - public: - EdgeMap(const FilterGraphWrapper >& _G) : - ErasingResGraphWrapper::EdgeMap(_G /*_G.getGraph()*/) { } - EdgeMap(const FilterGraphWrapper >& _G, T a) : - ErasingResGraphWrapper::EdgeMap(_G /*_G.getGraph()*/, a) { } - }; - - public: - ErasingResGraphWrapper::NodeMap dist; - - }; +// template +// class ErasingResGraphWrapper : public ResGraphWrapper { +// protected: +// ResGraphWrapper::NodeMap::OutEdgeIt> first_out_edges; +// //ResGraphWrapper::NodeMap dist; +// public: +// ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow, +// const CapacityMap& _capacity) : +// ResGraphWrapper(_G, _flow, _capacity), +// first_out_edges(*this) /*, dist(*this)*/ { +// for(NodeIt n=this->template first(); this->valid(n); this->next(n)) { +// OutEdgeIt e; +// ResGraphWrapper::first(e, n); +// first_out_edges.set(n, e); +// } +// } + +// //void setGraph(Graph& _graph) { graph = &_graph; } +// //Graph& getGraph() const { return (*graph); } + +// //TrivGraphWrapper() : graph(0) { } +// //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { } + +// //typedef Graph BaseGraph; + +// //typedef typename Graph::Node Node; +// //typedef typename Graph::NodeIt NodeIt; + +// //typedef typename Graph::Edge Edge; +// //typedef typename Graph::OutEdgeIt OutEdgeIt; +// //typedef typename Graph::InEdgeIt InEdgeIt; +// //typedef typename Graph::SymEdgeIt SymEdgeIt; +// //typedef typename Graph::EdgeIt EdgeIt; + +// typedef typename ResGraphWrapper::Node Node; +// typedef typename ResGraphWrapper::NodeIt NodeIt; + +// typedef typename ResGraphWrapper::Edge Edge; +// typedef typename ResGraphWrapper::OutEdgeIt OutEdgeIt; +// //typedef typename ResGraphWrapper::InEdgeIt InEdgeIt; +// //typedef typename Graph::SymEdgeIt SymEdgeIt; +// //typedef typename ResGraphWrapper::EdgeIt EdgeIt; + +// NodeIt& first(NodeIt& n) const { +// return ResGraphWrapper::first(n); +// } + +// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { +// e=first_out_edges.get(n); +// return e; +// } + +// //ROSSZ template I& first(I& i) const { return first(i); } +// //ROSSZ template I& first(I& i, const P& p) const { +// // return first(i, p); } + +// //template I getNext(const I& i) const { +// // return gw.getNext(i); } +// //template I& next(I &i) const { return gw.next(i); } + +// template< typename It > It first() const { +// It e; first(e); return e; } + +// template< typename It > It first(const Node& v) const { +// It e; first(e, v); return e; } + +// //Node head(const Edge& e) const { return gw.head(e); } +// //Node tail(const Edge& e) const { return gw.tail(e); } + +// //template bool valid(const I& i) const +// // { return gw.valid(i); } + +// //int nodeNum() const { return gw.nodeNum(); } +// //int edgeNum() const { return gw.edgeNum(); } + +// //template Node aNode(const I& e) const { +// // return gw.aNode(e); } +// //template Node bNode(const I& e) const { +// // return gw.bNode(e); } + +// //Node addNode() const { return gw.addNode(); } +// //Edge addEdge(const Node& tail, const Node& head) const { +// // return gw.addEdge(tail, head); } + +// //void erase(const OutEdgeIt& e) { +// // first_out_edge(this->tail(e))=e; +// //} +// void erase(const Edge& e) { +// OutEdgeIt f(e); +// next(f); +// first_out_edges.set(this->tail(e), f); +// } +// //template void erase(const I& i) const { gw.erase(i); } + +// //void clear() const { gw.clear(); } + +// template class NodeMap : public ResGraphWrapper::NodeMap { +// public: +// NodeMap(const ErasingResGraphWrapper& _G) : +// ResGraphWrapper::NodeMap(_G /*_G.getGraph()*/) { } +// NodeMap(const ErasingResGraphWrapper& _G, T a) : +// ResGraphWrapper::NodeMap(_G /*_G.getGraph()*/, a) { } +// }; + +// template class EdgeMap : public ResGraphWrapper::EdgeMap { +// public: +// EdgeMap(const ErasingResGraphWrapper& _G) : +// ResGraphWrapper::EdgeMap(_G /*_G.getGraph()*/) { } +// EdgeMap(const ErasingResGraphWrapper& _G, T a) : +// ResGraphWrapper::EdgeMap(_G /*_G.getGraph()*/, a) { } +// }; +// }; + +// template +// class FilterGraphWrapper { +// }; + +// template +// class FilterGraphWrapper > : public ErasingResGraphWrapper { + +// //Graph* graph; + +// public: +// //typedef Graph BaseGraph; + +// typedef typename ErasingResGraphWrapper::Node Node; +// typedef typename ErasingResGraphWrapper::NodeIt NodeIt; + +// typedef typename ErasingResGraphWrapper::Edge Edge; +// typedef typename ErasingResGraphWrapper::OutEdgeIt OutEdgeIt; +// //typedef typename ErasingResGraphWrapper::InEdgeIt InEdgeIt; +// //typedef typename Graph::SymEdgeIt SymEdgeIt; +// typedef typename ErasingResGraphWrapper::EdgeIt EdgeIt; + +// //FilterGraphWrapper::NodeMap::OutEdgeIt> first_out_edges; + +// public: +// FilterGraphWrapper(const Graph& _G, FlowMap& _flow, +// const CapacityMap& _capacity) : +// ErasingResGraphWrapper(_G, _flow, _capacity), dist(*this, gw.nodeNum()) { +// } + +// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { +// ErasingResGraphWrapper::first(e, n); +// while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e)))) +// ErasingResGraphWrapper::next(e); +// return e; +// } + +// NodeIt& next(NodeIt& e) const { +// return ErasingResGraphWrapper::next(e); +// } + +// OutEdgeIt& next(OutEdgeIt& e) const { +// ErasingResGraphWrapper::next(e); +// while (valid(e) && (dist.get(tail(e))/*+1!*/>=dist.get(head(e)))) +// ErasingResGraphWrapper::next(e); +// return e; +// } + +// NodeIt& first(NodeIt& n) const { +// return ErasingResGraphWrapper::first(n); +// } + +// void erase(const Edge& e) { +// OutEdgeIt f(e); +// ErasingResGraphWrapper::next(f); +// while (valid(f) && (dist.get(tail(f))/*+1!=*/>=dist.get(head(f)))) +// ErasingResGraphWrapper::next(f); +// first_out_edges.set(this->tail(e), f); +// } + +// //TrivGraphWrapper() : graph(0) { } +// //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { } + +// //void setGraph(Graph& _graph) { graph = &_graph; } +// //Graph& getGraph() const { return (*graph); } + +// //template I& first(I& i) const { return gw.first(i); } +// //template I& first(I& i, const P& p) const { +// // return gw.first(i, p); } + +// //template I getNext(const I& i) const { +// // return gw.getNext(i); } +// //template I& next(I &i) const { return gw.next(i); } + +// template< typename It > It first() const { +// It e; first(e); return e; } + +// template< typename It > It first(const Node& v) const { +// It e; first(e, v); return e; } + +// //Node head(const Edge& e) const { return gw.head(e); } +// //Node tail(const Edge& e) const { return gw.tail(e); } + +// //template bool valid(const I& i) const +// // { return gw.valid(i); } + +// //template void setInvalid(const I &i); +// //{ return gw.setInvalid(i); } + +// //int nodeNum() const { return gw.nodeNum(); } +// //int edgeNum() const { return gw.edgeNum(); } + +// //template Node aNode(const I& e) const { +// // return gw.aNode(e); } +// //template Node bNode(const I& e) const { +// // return gw.bNode(e); } + +// //Node addNode() const { return gw.addNode(); } +// //Edge addEdge(const Node& tail, const Node& head) const { +// // return gw.addEdge(tail, head); } + +// //template void erase(const I& i) const { gw.erase(i); } + +// //void clear() const { gw.clear(); } + +// template class NodeMap : public ErasingResGraphWrapper::NodeMap { +// public: +// NodeMap(const FilterGraphWrapper >& _G) : +// ErasingResGraphWrapper::NodeMap(_G /*_G.getGraph()*/) { } +// NodeMap(const FilterGraphWrapper >& _G, T a) : +// ErasingResGraphWrapper::NodeMap(_G /*_G.getGraph()*/, a) { } +// }; + +// template class EdgeMap : public ErasingResGraphWrapper::EdgeMap { +// public: +// EdgeMap(const FilterGraphWrapper >& _G) : +// ErasingResGraphWrapper::EdgeMap(_G /*_G.getGraph()*/) { } +// EdgeMap(const FilterGraphWrapper >& _G, T a) : +// ErasingResGraphWrapper::EdgeMap(_G /*_G.getGraph()*/, a) { } +// }; + +// public: +// ErasingResGraphWrapper::NodeMap dist; + +// };