# HG changeset patch # User marci # Date 1081183966 0 # Node ID 1b377a730d027d439d1c7c5b14ff50a2f50d5fcd # Parent 2c52fc9781d49c6195ca29bdea0008f22fbcb3cb konvergalunk, konvergalunk... diff -r 2c52fc9781d4 -r 1b377a730d02 src/work/marci/bfs_iterator.h --- a/src/work/marci/bfs_iterator.h Mon Apr 05 15:31:21 2004 +0000 +++ b/src/work/marci/bfs_iterator.h Mon Apr 05 16:52:46 2004 +0000 @@ -5,7 +5,6 @@ #include #include #include -#include namespace hugo { @@ -630,40 +629,34 @@ // }; - template */ > + template */ > class BfsIterator5 { - typedef typename GraphWrapper::Node Node; - typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; - GraphWrapper G; + protected: + typedef typename Graph::Node Node; + typedef typename Graph::OutEdgeIt OutEdgeIt; + const Graph* graph; std::queue bfs_queue; ReachedMap& reached; bool b_node_newly_reached; OutEdgeIt actual_edge; bool own_reached_map; public: - BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) : - G(_G), reached(_reached), + BfsIterator5(const Graph& _graph, ReachedMap& _reached) : + graph(&_graph), reached(_reached), own_reached_map(false) { } - BfsIterator5(const GraphWrapper& _G) : - G(_G), reached(*(new ReachedMap(G /*, false*/))), + BfsIterator5(const Graph& _graph) : + graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), own_reached_map(true) { } -// BfsIterator5(const typename GraphWrapper::BaseGraph& _G, -// ReachedMap& _reached) : -// G(_G), reached(_reached), -// own_reached_map(false) { } -// BfsIterator5(const typename GraphWrapper::BaseGraph& _G) : -// G(_G), reached(*(new ReachedMap(G /*, false*/))), -// own_reached_map(true) { } ~BfsIterator5() { if (own_reached_map) delete &reached; } void pushAndSetReached(Node s) { reached.set(s, true); if (bfs_queue.empty()) { bfs_queue.push(s); - G./*getF*/first(actual_edge, s); - if (G.valid(actual_edge)/*.valid()*/) { - Node w=G.bNode(actual_edge); - if (!reached.get(w)) { + graph->first(actual_edge, s); + if (graph->valid(actual_edge)) { + Node w=graph->bNode(actual_edge); + if (!reached[w]) { bfs_queue.push(w); reached.set(w, true); b_node_newly_reached=true; @@ -675,13 +668,13 @@ bfs_queue.push(s); } } - BfsIterator5& + BfsIterator5& operator++() { - if (G.valid(actual_edge)/*.valid()*/) { - /*++*/G.next(actual_edge); - if (G.valid(actual_edge)/*.valid()*/) { - Node w=G.bNode(actual_edge); - if (!reached.get(w)) { + if (graph->valid(actual_edge)) { + graph->next(actual_edge); + if (graph->valid(actual_edge)) { + Node w=graph->bNode(actual_edge); + if (!reached[w]) { bfs_queue.push(w); reached.set(w, true); b_node_newly_reached=true; @@ -692,10 +685,10 @@ } else { bfs_queue.pop(); if (!bfs_queue.empty()) { - G./*getF*/first(actual_edge, bfs_queue.front()); - if (G.valid(actual_edge)/*.valid()*/) { - Node w=G.bNode(actual_edge); - if (!reached.get(w)) { + graph->first(actual_edge, bfs_queue.front()); + if (graph->valid(actual_edge)) { + Node w=graph->bNode(actual_edge); + if (!reached[w]) { bfs_queue.push(w); reached.set(w, true); b_node_newly_reached=true; @@ -710,9 +703,9 @@ bool finished() const { return bfs_queue.empty(); } operator OutEdgeIt () const { return actual_edge; } bool isBNodeNewlyReached() const { return b_node_newly_reached; } - bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } + bool isANodeExamined() const { return !(graph->valid(actual_edge)); } Node aNode() const { return bfs_queue.front(); } - Node bNode() const { return G.bNode(actual_edge); } + Node bNode() const { return graph->bNode(actual_edge); } const ReachedMap& getReachedMap() const { return reached; } const std::queue& getBfsQueue() const { return bfs_queue; } }; @@ -773,12 +766,13 @@ // const std::stack& getDfsStack() const { return dfs_stack; } // }; - template */ > + template */ > class DfsIterator5 { - typedef typename GraphWrapper::Node Node; - typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; - GraphWrapper G; + protected: + typedef typename Graph::Node Node; + typedef typename Graph::OutEdgeIt OutEdgeIt; + const Graph* graph; std::stack dfs_stack; bool b_node_newly_reached; OutEdgeIt actual_edge; @@ -786,36 +780,36 @@ ReachedMap& reached; bool own_reached_map; public: - DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) : - G(_G), reached(_reached), + DfsIterator5(const Graph& _graph, ReachedMap& _reached) : + graph(&_graph), reached(_reached), own_reached_map(false) { } - DfsIterator5(const GraphWrapper& _G) : - G(_G), reached(*(new ReachedMap(G /*, false*/))), + DfsIterator5(const Graph& _graph) : + graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), own_reached_map(true) { } ~DfsIterator5() { if (own_reached_map) delete &reached; } void pushAndSetReached(Node s) { actual_node=s; reached.set(s, true); OutEdgeIt e; - G.first(e, s); + graph->first(e, s); dfs_stack.push(e); } - DfsIterator5& + DfsIterator5& operator++() { actual_edge=dfs_stack.top(); //actual_node=G.aNode(actual_edge); - if (G.valid(actual_edge)/*.valid()*/) { - Node w=G.bNode(actual_edge); + if (graph->valid(actual_edge)/*.valid()*/) { + Node w=graph->bNode(actual_edge); actual_node=w; - if (!reached.get(w)) { + if (!reached[w]) { OutEdgeIt e; - G.first(e, w); + graph->first(e, w); dfs_stack.push(e); reached.set(w, true); b_node_newly_reached=true; } else { - actual_node=G.aNode(actual_edge); - /*++*/G.next(dfs_stack.top()); + actual_node=graph->aNode(actual_edge); + graph->next(dfs_stack.top()); b_node_newly_reached=false; } } else { @@ -827,7 +821,7 @@ bool finished() const { return dfs_stack.empty(); } operator OutEdgeIt () const { return actual_edge; } bool isBNodeNewlyReached() const { return b_node_newly_reached; } - bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } + bool isANodeExamined() const { return !(graph->valid(actual_edge)); } Node aNode() const { return actual_node; /*FIXME*/} Node bNode() const { return G.bNode(actual_edge); } const ReachedMap& getReachedMap() const { return reached; } diff -r 2c52fc9781d4 -r 1b377a730d02 src/work/marci/edmonds_karp.h --- a/src/work/marci/edmonds_karp.h Mon Apr 05 15:31:21 2004 +0000 +++ b/src/work/marci/edmonds_karp.h Mon Apr 05 16:52:46 2004 +0000 @@ -8,6 +8,7 @@ #include #include +#include namespace hugo { @@ -247,31 +248,29 @@ }; - template + template class MaxFlow { protected: - typedef GraphWrapper GW; - typedef typename GW::Node Node; - typedef typename GW::Edge Edge; - typedef typename GW::EdgeIt EdgeIt; - typedef typename GW::OutEdgeIt OutEdgeIt; - typedef typename GW::InEdgeIt InEdgeIt; - //const Graph* G; - GW gw; + 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; + const Graph* g; Node s; Node t; FlowMap* flow; const CapacityMap* capacity; - typedef ResGraphWrapper ResGW; + typedef ResGraphWrapper ResGW; typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; typedef typename ResGW::Edge ResGWEdge; public: - MaxFlow(const GW& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : - gw(_gw), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { } + MaxFlow(const Graph& _g, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : + g(&_g), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { } bool augmentOnShortestPath() { - ResGW res_graph(gw, *flow, *capacity); + ResGW res_graph(*g, *flow, *capacity); bool _augment=false; typedef typename ResGW::NodeMap ReachedMap; @@ -290,8 +289,8 @@ 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.resCap(e))); + if (res_graph.valid(pred[v])) { + free.set(w, std::min(free[v], res_graph.resCap(e))); } else { free.set(w, res_graph.resCap(e)); } @@ -303,9 +302,9 @@ if (_augment) { Node n=t; - Number augment_value=free.get(t); - while (res_graph.valid(pred.get(n))) { - ResGWEdge e=pred.get(n); + Number augment_value=free[t]; + while (res_graph.valid(pred[n])) { + ResGWEdge e=pred[n]; res_graph.augment(e, augment_value); n=res_graph.tail(e); } @@ -317,14 +316,19 @@ template class DistanceMap { protected: - MapGraphWrapper gw; + const MapGraphWrapper* g; typename MapGraphWrapper::NodeMap dist; public: - DistanceMap(MapGraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { } + DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->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))tail(e))head(e))); } + bool operator[](const typename MapGraphWrapper::Edge& e) const { + return (dist[g->tail(e)]head(e)]); } }; @@ -332,7 +336,7 @@ typedef MutableGraph MG; bool _augment=false; - ResGW res_graph(gw, *flow, *capacity); + ResGW res_graph(*g, *flow, *capacity); typedef typename ResGW::NodeMap ReachedMap; BfsIterator5< ResGW, ReachedMap > bfs(res_graph); @@ -343,7 +347,7 @@ while ( !bfs.finished() ) { ResGWOutEdgeIt e=bfs; if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { - dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); + dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); } ++bfs; } //computing distances from s in the residual graph @@ -359,8 +363,8 @@ } } - typename MG::Node sF=res_graph_to_F.get(s); - typename MG::Node tF=res_graph_to_F.get(t); + typename MG::Node sF=res_graph_to_F[s]; + typename MG::Node tF=res_graph_to_F[t]; typename MG::EdgeMap original_edge(F); typename MG::EdgeMap residual_capacity(F); @@ -370,7 +374,7 @@ typename FilterResGW::EdgeIt e; for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) { //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { - typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); + typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]); original_edge.update(); original_edge.set(f, e); residual_capacity.update(); @@ -400,10 +404,10 @@ typename MG::Node v=F.aNode(dfs); typename MG::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))); + if (F.valid(pred[v])) { + free.set(w, std::min(free[v], residual_capacity[dfs])); } else { - free.set(w, residual_capacity.get(dfs)); + free.set(w, residual_capacity[dfs]); } if (w==tF) { __augment=true; @@ -419,15 +423,15 @@ if (__augment) { typename MG::Node n=tF; - Number augment_value=free.get(tF); - while (F.valid(pred.get(n))) { - typename MG::Edge e=pred.get(n); - res_graph.augment(original_edge.get(e), augment_value); + Number augment_value=free[tF]; + while (F.valid(pred[n])) { + typename MG::Edge e=pred[n]; + res_graph.augment(original_edge[e], augment_value); n=F.tail(e); - if (residual_capacity.get(e)==augment_value) + if (residual_capacity[e]==augment_value) F.erase(e); else - residual_capacity.set(e, residual_capacity.get(e)-augment_value); + residual_capacity.set(e, residual_capacity[e]-augment_value); } } @@ -440,7 +444,7 @@ typedef MutableGraph MG; bool _augment=false; - ResGW res_graph(gw, *flow, *capacity); + ResGW res_graph(*g, *flow, *capacity); //bfs for distances on the residual graph typedef typename ResGW::NodeMap ReachedMap; @@ -459,8 +463,8 @@ } } - typename MG::Node sF=res_graph_to_F.get(s); - typename MG::Node tF=res_graph_to_F.get(t); + typename MG::Node sF=res_graph_to_F[s]; + typename MG::Node tF=res_graph_to_F[t]; typename MG::EdgeMap original_edge(F); typename MG::EdgeMap residual_capacity(F); @@ -468,15 +472,15 @@ ResGWOutEdgeIt e=bfs; if (res_graph.valid(e)) { if (bfs.isBNodeNewlyReached()) { - dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); - typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); + dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); + typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]); original_edge.update(); original_edge.set(f, e); residual_capacity.update(); residual_capacity.set(f, res_graph.resCap(e)); } else { - if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) { - typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); + if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) { + typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]); original_edge.update(); original_edge.set(f, e); residual_capacity.update(); @@ -508,10 +512,10 @@ typename MG::Node v=F.aNode(dfs); typename MG::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))); + if (F.valid(pred[v])) { + free.set(w, std::min(free[v], residual_capacity[dfs])); } else { - free.set(w, residual_capacity.get(dfs)); + free.set(w, residual_capacity[dfs]); } if (w==tF) { __augment=true; @@ -527,15 +531,15 @@ if (__augment) { typename MG::Node n=tF; - Number augment_value=free.get(tF); - while (F.valid(pred.get(n))) { - typename MG::Edge e=pred.get(n); - res_graph.augment(original_edge.get(e), augment_value); + Number augment_value=free[tF]; + while (F.valid(pred[n])) { + typename MG::Edge e=pred[n]; + res_graph.augment(original_edge[e], augment_value); n=F.tail(e); - if (residual_capacity.get(e)==augment_value) + if (residual_capacity[e]==augment_value) F.erase(e); else - residual_capacity.set(e, residual_capacity.get(e)-augment_value); + residual_capacity.set(e, residual_capacity[e]-augment_value); } } @@ -547,7 +551,7 @@ bool augmentOnBlockingFlow2() { bool _augment=false; - ResGW res_graph(gw, *flow, *capacity); + ResGW res_graph(*g, *flow, *capacity); typedef typename ResGW::NodeMap ReachedMap; BfsIterator5< ResGW, ReachedMap > bfs(res_graph); @@ -557,7 +561,7 @@ while ( !bfs.finished() ) { ResGWOutEdgeIt e=bfs; if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { - dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); + dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); } ++bfs; } //computing distances from s in the residual graph @@ -610,8 +614,8 @@ typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs); pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs)); - if (erasing_res_graph.valid(pred.get(v))) { - free.set(w, std::min(free.get(v), res_graph.resCap(dfs))); + if (erasing_res_graph.valid(pred[v])) { + free.set(w, std::min(free[v], res_graph.resCap(dfs))); } else { free.set(w, res_graph.resCap(dfs)); } @@ -629,9 +633,9 @@ if (__augment) { typename ErasingResGW::Node n=t; - Number augment_value=free.get(n); - while (erasing_res_graph.valid(pred.get(n))) { - typename ErasingResGW::OutEdgeIt e=pred.get(n); + Number augment_value=free[n]; + while (erasing_res_graph.valid(pred[n])) { + typename ErasingResGW::OutEdgeIt e=pred[n]; res_graph.augment(e, augment_value); n=erasing_res_graph.tail(e); if (res_graph.resCap(e)==0) @@ -644,95 +648,6 @@ 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()) { @@ -754,8 +669,8 @@ Number flowValue() { Number a=0; OutEdgeIt e; - for(gw.first(e, s); gw.valid(e); gw.next(e)) { - a+=flow->get(e); + for(g->first(e, s); g->valid(e); g->next(e)) { + a+=(*flow)[e]; } return a; } diff -r 2c52fc9781d4 -r 1b377a730d02 src/work/marci/edmonds_karp_demo.cc --- a/src/work/marci/edmonds_karp_demo.cc Mon Apr 05 15:31:21 2004 +0000 +++ b/src/work/marci/edmonds_karp_demo.cc Mon Apr 05 16:52:46 2004 +0000 @@ -3,11 +3,11 @@ #include #include -#include +//#include #include #include #include -#include +//#include class CM { public: @@ -90,17 +90,14 @@ { - typedef TrivGraphWrapper GW; - GW gw(G); std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl; - GW::EdgeMap flow(gw); //0 flow + Graph::EdgeMap flow(G); //0 flow Timer ts; ts.reset(); - typedef GW::EdgeMapWrapper< Graph::EdgeMap, int > EMW; - EMW cw(cap); - MaxFlow, EMW > max_flow_test(gw, s, t, flow, cw); + MaxFlow, Graph::EdgeMap > + max_flow_test(G, s, t, flow, cap); int i=0; while (max_flow_test.augmentOnBlockingFlow()) { // for(EdgeIt e=G.template first(); e.valid(); ++e) { @@ -121,17 +118,14 @@ } { - typedef TrivGraphWrapper GW; - GW gw(G); std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl; - GW::EdgeMap flow(gw); //0 flow + Graph::EdgeMap flow(G); //0 flow Timer ts; ts.reset(); - typedef GW::EdgeMapWrapper< Graph::EdgeMap, int > EMW; - EMW cw(cap); - MaxFlow, EMW > max_flow_test(gw, s, t, flow, cw); + 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) { @@ -152,17 +146,14 @@ } { - typedef TrivGraphWrapper GW; - GW gw(G); std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl; - GW::EdgeMap flow(gw); //0 flow + Graph::EdgeMap flow(G); //0 flow Timer ts; ts.reset(); - typedef GW::EdgeMapWrapper< Graph::EdgeMap, int > EMW; - EMW cw(cap); - MaxFlow, EMW > max_flow_test(gw, s, t, flow, cw); + 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) { @@ -183,17 +174,14 @@ } { - 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 + Graph::EdgeMap flow(G); //0 flow Timer ts; ts.reset(); - typedef GW::EdgeMapWrapper< Graph::EdgeMap, int > EMW; - EMW cw(cap); - MaxFlow, EMW> max_flow_test(gw, s, t, flow, cw); + MaxFlow, Graph::EdgeMap > + max_flow_test(G, s, t, flow, cap); int i=0; while (max_flow_test.augmentOnShortestPath()) { // for(EdgeIt e=G.template first(); e.valid(); ++e) { diff -r 2c52fc9781d4 -r 1b377a730d02 src/work/marci/experiment/iterator_bfs_demo.cc --- a/src/work/marci/experiment/iterator_bfs_demo.cc Mon Apr 05 15:31:21 2004 +0000 +++ b/src/work/marci/experiment/iterator_bfs_demo.cc Mon Apr 05 16:52:46 2004 +0000 @@ -5,8 +5,8 @@ #include //#include -#include -#include +#include +#include using namespace hugo; using std::cout; diff -r 2c52fc9781d4 -r 1b377a730d02 src/work/marci/experiment/iterator_bfs_demo_1.cc --- a/src/work/marci/experiment/iterator_bfs_demo_1.cc Mon Apr 05 15:31:21 2004 +0000 +++ b/src/work/marci/experiment/iterator_bfs_demo_1.cc Mon Apr 05 16:52:46 2004 +0000 @@ -5,8 +5,8 @@ #include #include -#include -#include +#include +#include using namespace hugo; using std::cout; diff -r 2c52fc9781d4 -r 1b377a730d02 src/work/marci/graph_wrapper.h --- a/src/work/marci/graph_wrapper.h Mon Apr 05 15:31:21 2004 +0000 +++ b/src/work/marci/graph_wrapper.h Mon Apr 05 16:52:46 2004 +0000 @@ -12,7 +12,12 @@ Graph* graph; public: - typedef Graph BaseGraph; + typedef Graph ParentGraph; + +// TrivGraphWrapper() : graph(0) { } + TrivGraphWrapper(Graph& _graph) : graph(&_graph) { } +// void setGraph(Graph& _graph) { graph = &_graph; } +// Graph& getGraph() const { return *graph; } typedef typename Graph::Node Node; class NodeIt : public Graph::NodeIt { @@ -24,7 +29,6 @@ Graph::NodeIt(*(_G.graph)) { } }; typedef typename Graph::Edge Edge; - //typedef typename Graph::OutEdgeIt OutEdgeIt; class OutEdgeIt : public Graph::OutEdgeIt { public: OutEdgeIt() { } @@ -33,7 +37,6 @@ OutEdgeIt(const TrivGraphWrapper& _G, const Node& n) : Graph::OutEdgeIt(*(_G.graph), n) { } }; - //typedef typename Graph::InEdgeIt InEdgeIt; class InEdgeIt : public Graph::InEdgeIt { public: InEdgeIt() { } @@ -43,7 +46,6 @@ Graph::InEdgeIt(*(_G.graph), n) { } }; //typedef typename Graph::SymEdgeIt SymEdgeIt; - //typedef typename Graph::EdgeIt EdgeIt; class EdgeIt : public Graph::EdgeIt { public: EdgeIt() { } @@ -53,12 +55,6 @@ Graph::EdgeIt(*(_G.graph)) { } }; - //TrivGraphWrapper() : graph(0) { } - TrivGraphWrapper(Graph& _graph) : graph(&_graph) { } - -// void setGraph(Graph& _graph) { graph = &_graph; } -// Graph& getGraph() const { return (*graph); } - NodeIt& first(NodeIt& i) const { i=NodeIt(*this); return i; @@ -68,7 +64,6 @@ return i; } // template I& first(I& i) const { -// //return graph->first(i); // i=I(*this); // return i; // } @@ -81,7 +76,6 @@ return i; } // template I& first(I& i, const P& p) const { -// //return graph->first(i, p); // i=I(*this, p); // return i; // } @@ -91,16 +85,16 @@ template I& next(I &i) const { graph->next(i); return i; } template< typename It > It first() const { - It e; first(e); return e; } + It e; this->first(e); return e; } template< typename It > It first(const Node& v) const { - It e; first(e, v); return e; } + It e; this->first(e, v); return e; } Node head(const Edge& e) const { return graph->head(e); } Node tail(const Edge& e) const { return graph->tail(e); } - template bool valid(const I& i) const - { return graph->valid(i); } + template bool valid(const I& i) const { + return graph->valid(i); } //template void setInvalid(const I &i); //{ return graph->setInvalid(i); } @@ -137,107 +131,103 @@ 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 NodeMapWrapper { +// protected: +// Map* map; +// public: +// NodeMapWrapper(Map& _map) : map(&_map) { } +// void set(Node n, T a) { map->set(n, a); } +// 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); } - }; +// template class EdgeMapWrapper { +// protected: +// Map* map; +// public: +// EdgeMapWrapper(Map& _map) : map(&_map) { } +// void set(Edge n, T a) { map->set(n, a); } +// T get(Edge n) const { return map->get(n); } +// }; }; - template - class GraphWrapperSkeleton { + + template + class GraphWrapper { protected: - GraphWrapper gw; + Graph* graph; public: - //typedef typename GraphWrapper::BaseGraph BaseGraph; + typedef Graph ParentGraph; -// typedef typename GraphWrapper::Node Node; -// typedef typename GraphWrapper::NodeIt NodeIt; - -// typedef typename GraphWrapper::Edge Edge; -// typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; -// typedef typename GraphWrapper::InEdgeIt InEdgeIt; -// //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt; -// typedef typename GraphWrapper::EdgeIt EdgeIt; - - typedef typename GraphWrapper::Node Node; - class NodeIt : public GraphWrapper::NodeIt { +// GraphWrapper() : graph(0) { } + GraphWrapper(Graph& _graph) : graph(&_graph) { } +// void setGraph(Graph& _graph) { graph=&_graph; } +// Graph& getGraph() const { return *graph; } + + typedef typename Graph::Node Node; + class NodeIt : public Graph::NodeIt { public: NodeIt() { } - NodeIt(const typename GraphWrapper::NodeIt& n) : - GraphWrapper::NodeIt(n) { } - NodeIt(const Invalid& i) : GraphWrapper::NodeIt(i) { } - NodeIt(const GraphWrapperSkeleton& _G) : - GraphWrapper::NodeIt(_G.gw) { } + NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } + NodeIt(const Invalid& i) : Graph::NodeIt(i) { } + NodeIt(const GraphWrapper& _G) : + Graph::NodeIt(*(_G.graph)) { } }; - typedef typename GraphWrapper::Edge Edge; - //typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; - class OutEdgeIt : public GraphWrapper::OutEdgeIt { + typedef typename Graph::Edge Edge; + class OutEdgeIt : public Graph::OutEdgeIt { public: OutEdgeIt() { } - OutEdgeIt(const typename GraphWrapper::OutEdgeIt& e) : - GraphWrapper::OutEdgeIt(e) { } - OutEdgeIt(const Invalid& i) : GraphWrapper::OutEdgeIt(i) { } - OutEdgeIt(const GraphWrapperSkeleton& _G, const Node& n) : - GraphWrapper::OutEdgeIt(_G.gw, n) { } + OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } + OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } + OutEdgeIt(const GraphWrapper& _G, const Node& n) : + Graph::OutEdgeIt(*(_G.graph), n) { } }; - //typedef typename GraphWrapper::InEdgeIt InEdgeIt; - class InEdgeIt : public GraphWrapper::InEdgeIt { + class InEdgeIt : public Graph::InEdgeIt { public: InEdgeIt() { } - InEdgeIt(const typename GraphWrapper::InEdgeIt& e) : - GraphWrapper::InEdgeIt(e) { } - InEdgeIt(const Invalid& i) : GraphWrapper::InEdgeIt(i) { } - InEdgeIt(const GraphWrapperSkeleton& _G, const Node& n) : - GraphWrapper::InEdgeIt(_G.gw, n) { } + InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } + InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } + InEdgeIt(const GraphWrapper& _G, const Node& n) : + Graph::InEdgeIt(*(_G.graph), n) { } }; - //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt; - //typedef typename GraphWrapper::EdgeIt EdgeIt; - class EdgeIt : public GraphWrapper::EdgeIt { + //typedef typename Graph::SymEdgeIt SymEdgeIt; + class EdgeIt : public Graph::EdgeIt { public: EdgeIt() { } - EdgeIt(const typename GraphWrapper::EdgeIt& e) : - GraphWrapper::EdgeIt(e) { } - EdgeIt(const Invalid& i) : GraphWrapper::EdgeIt(i) { } - EdgeIt(const GraphWrapperSkeleton& _G) : - GraphWrapper::EdgeIt(_G.gw) { } + EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } + EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } + EdgeIt(const GraphWrapper& _G) : + Graph::EdgeIt(*(_G.graph)) { } }; - - - //GraphWrapperSkeleton() : gw() { } - GraphWrapperSkeleton(GraphWrapper _gw) : gw(_gw) { } - - //void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); } - //BaseGraph& getGraph() const { return gw.getGraph(); } - - template I& first(I& i) const { - i=I(*this); + + NodeIt& first(NodeIt& i) const { + i=NodeIt(*this); return i; } - template I& first(I& i, const P& p) const { - i=I(*this, p); - return i; + EdgeIt& first(EdgeIt& i) const { + i=EdgeIt(*this); + return i; } +// template I& first(I& i) const { +// i=I(*this); +// return i; +// } + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { + i=OutEdgeIt(*this, p); + return i; + } + InEdgeIt& first(InEdgeIt& i, const Node& p) const { + i=InEdgeIt(*this, p); + return i; + } +// template I& first(I& i, const P& p) const { +// i=I(*this, p); +// return i; +// } -// template I getNext(const I& i) const { return gw.getNext(i); } - template I& next(I &i) const { gw.next(i); return i; } +// template I getNext(const I& i) const { +// return gw.getNext(i); } + template I& next(I &i) const { graph->next(i); return i; } template< typename It > It first() const { It e; this->first(e); return e; } @@ -245,45 +235,49 @@ template< typename It > It first(const Node& v) const { It e; this->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); } + Node head(const Edge& e) const { return graph->head(e); } + Node tail(const Edge& e) const { return graph->tail(e); } - template bool valid(const I& i) const { return gw.valid(i); } + template bool valid(const I& i) const { + return graph->valid(i); } //template void setInvalid(const I &i); //{ return graph->setInvalid(i); } - int nodeNum() const { return gw.nodeNum(); } - int edgeNum() const { return gw.edgeNum(); } + int nodeNum() const { return graph->nodeNum(); } + int edgeNum() const { return graph->edgeNum(); } - template Node aNode(const I& e) const { return gw.aNode(e); } - template Node bNode(const I& e) const { return gw.bNode(e); } + template Node aNode(const I& e) const { + return graph->aNode(e); } + template Node bNode(const I& e) const { + return graph->bNode(e); } - Node addNode() const { return gw.addNode(); } + Node addNode() const { return graph->addNode(); } Edge addEdge(const Node& tail, const Node& head) const { - return gw.addEdge(tail, head); } + return graph->addEdge(tail, head); } - template void erase(const I& i) const { gw.erase(i); } + template void erase(const I& i) const { graph->erase(i); } - void clear() const { gw.clear(); } + void clear() const { graph->clear(); } - template class NodeMap : public GraphWrapper::NodeMap { + template class NodeMap : public Graph::NodeMap { public: - NodeMap(const GraphWrapperSkeleton& _G) : - GraphWrapper::NodeMap(_G.gw) { } - NodeMap(const GraphWrapperSkeleton& _G, T a) : - GraphWrapper::NodeMap(_G.gw, a) { } + NodeMap(const GraphWrapper& _G) : + Graph::NodeMap(*(_G.graph)) { } + NodeMap(const GraphWrapper& _G, T a) : + Graph::NodeMap(*(_G.graph), a) { } }; - template class EdgeMap : public GraphWrapper::EdgeMap { + template class EdgeMap : public Graph::EdgeMap { public: - EdgeMap(const GraphWrapperSkeleton& _G) : - GraphWrapper::EdgeMap(_G.gw) { } - EdgeMap(const GraphWrapperSkeleton& _G, T a) : - GraphWrapper::EdgeMap(_G.gw, a) { } + EdgeMap(const GraphWrapper& _G) : + Graph::EdgeMap(*(_G.graph)) { } + EdgeMap(const GraphWrapper& _G, T a) : + Graph::EdgeMap(*(_G.graph), a) { } }; }; + // template // class RevGraphWrapper // { @@ -291,7 +285,7 @@ // Graph* graph; // public: -// typedef Graph BaseGraph; +// typedef Graph ParentGraph; // typedef typename Graph::Node Node; // typedef typename Graph::NodeIt NodeIt; @@ -364,139 +358,59 @@ // }; // }; -// template*/ > -// class RevGraphWrapper : -// public GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper >*/ { -// protected: -// //Graph* graph; - -// public: -// //typedef Graph BaseGraph; -// //typedef typename Graph::Node Node; -// //typedef typename Graph::NodeIt NodeIt; - -// //typedef typename Graph::Edge Edge; -// typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper >*/::OutEdgeIt InEdgeIt; -// typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper >*/::InEdgeIt OutEdgeIt; -// //typedef typename Graph::SymEdgeIt SymEdgeIt; -// //typedef typename Graph::EdgeIt EdgeIt; - -// //RevGraphWrapper() : graph(0) { } -// RevGraphWrapper(GraphWrapper _gw/*BaseGraph& _graph*/) : GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper >*/(_gw/*TrivGraphWrapper(_graph)*/) { } - -// //void setGraph(Graph& _graph) { graph = &_graph; } -// //Graph& getGraph() const { return (*graph); } - -// //template I& first(I& i) const { return graph->first(i); } -// //template I& first(I& i, const P& p) const { -// // return graph->first(i, p); } - -// //template I getNext(const I& i) const { -// // return graph->getNext(i); } -// //template I& next(I &i) const { return graph->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 graph->tail(e); } -// //Node tail(const Edge& e) const { return graph->head(e); } - -// //template bool valid(const I& i) const -// // { return graph->valid(i); } - -// //template void setInvalid(const I &i); -// //{ return graph->setInvalid(i); } - -// //template Node aNode(const I& e) const { -// // return graph->aNode(e); } -// //template Node bNode(const I& e) const { -// // return graph->bNode(e); } - -// //Node addNode() const { return graph->addNode(); } -// //Edge addEdge(const Node& tail, const Node& head) const { -// // return graph->addEdge(tail, head); } - -// //int nodeNum() const { return graph->nodeNum(); } -// //int edgeNum() const { return graph->edgeNum(); } - -// //template void erase(const I& i) const { graph->erase(i); } - -// //void clear() const { graph->clear(); } - -// template class NodeMap : -// public GraphWrapper/*Skeleton< TrivGraphWrapper >*/::NodeMap -// { -// public: -// NodeMap(const RevGraphWrapper& _gw) : -// GraphWrapper/*Skeleton< TrivGraphWrapper >*/::NodeMap(_gw) { } -// NodeMap(const RevGraphWrapper& _gw, T a) : -// GraphWrapper/*Skeleton< TrivGraphWrapper >*/::NodeMap(_gw, a) { } -// }; - -// template class EdgeMap : -// public GraphWrapper/*Skeleton< TrivGraphWrapper >*/::EdgeMap { -// public: -// EdgeMap(const RevGraphWrapper& _gw) : -// GraphWrapper/*Skeleton< TrivGraphWrapper >*/::EdgeMap(_gw) { } -// EdgeMap(const RevGraphWrapper& _gw, T a) : -// GraphWrapper/*Skeleton< TrivGraphWrapper >*/::EdgeMap(_gw, a) { } -// }; -// }; - - template - class RevGraphWrapper : public GraphWrapperSkeleton { + template + class RevGraphWrapper : public GraphWrapper { public: - typedef typename GraphWrapperSkeleton::Node Node; - typedef typename GraphWrapperSkeleton::Edge Edge; + typedef typename GraphWrapper::Node Node; + typedef typename GraphWrapper::Edge Edge; //FIXME - //If GraphWrapper::OutEdgeIt is not defined + //If Graph::OutEdgeIt is not defined //and we do not want to use RevGraphWrapper::InEdgeIt, //this won't work, because of typedef //OR //graphs have to define their non-existing iterators to void //Unfortunately all the typedefs are instantiated in templates, //unlike other stuff - typedef typename GraphWrapperSkeleton::OutEdgeIt InEdgeIt; - typedef typename GraphWrapperSkeleton::InEdgeIt OutEdgeIt; + typedef typename GraphWrapper::OutEdgeIt InEdgeIt; + typedef typename GraphWrapper::InEdgeIt OutEdgeIt; - RevGraphWrapper(GraphWrapper _gw) : - GraphWrapperSkeleton(_gw) { } +// RevGraphWrapper() : GraphWrapper() { } + RevGraphWrapper(Graph& _graph) : GraphWrapper(_graph) { } Node head(const Edge& e) const - { return GraphWrapperSkeleton::tail(e); } + { return GraphWrapper::tail(e); } Node tail(const Edge& e) const - { return GraphWrapperSkeleton::head(e); } + { return GraphWrapper::head(e); } }; //Subgraph on the same node-set and partial edge-set - template - class SubGraphWrapper : public GraphWrapperSkeleton { + template + class SubGraphWrapper : public GraphWrapper { protected: EdgeFilterMap* filter_map; public: - typedef typename GraphWrapperSkeleton::Node Node; - typedef typename GraphWrapperSkeleton::NodeIt NodeIt; - typedef typename GraphWrapperSkeleton::Edge Edge; - typedef typename GraphWrapperSkeleton::EdgeIt EdgeIt; - typedef typename GraphWrapperSkeleton::InEdgeIt InEdgeIt; - typedef typename GraphWrapperSkeleton::OutEdgeIt OutEdgeIt; + typedef typename GraphWrapper::Node Node; + typedef typename GraphWrapper::NodeIt NodeIt; + typedef typename GraphWrapper::Edge Edge; + typedef typename GraphWrapper::EdgeIt EdgeIt; + typedef typename GraphWrapper::InEdgeIt InEdgeIt; + typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; - SubGraphWrapper(GraphWrapper _gw, EdgeFilterMap& _filter_map) : - GraphWrapperSkeleton(_gw), filter_map(&_filter_map) { } +// SubGraphWrapper() : GraphWrapper(), filter_map(0) { } + SubGraphWrapper(Graph& _graph, EdgeFilterMap& _filter_map) : + GraphWrapper(_graph), filter_map(&_filter_map) { } template I& first(I& i) const { - gw.first(i); - while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); } + graph->first(i); + //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } + while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); } return i; } template I& first(I& i, const P& p) const { - gw.first(i, p); - while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); } + graph->first(i, p); +// while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } + while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); } return i; } @@ -504,8 +418,9 @@ // return gw.getNext(i); //} template I& next(I &i) const { - gw.next(i); - while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); } + graph->next(i); +// while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); } + while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); } return i; } @@ -523,7 +438,7 @@ // GraphWrapper gw; // public: -// typedef GraphWrapper BaseGraph; +// typedef GraphWrapper ParentGraph; // typedef typename GraphWrapper::Node Node; // typedef typename GraphWrapper::NodeIt NodeIt; @@ -676,39 +591,21 @@ // }; - template - class UndirGraphWrapper : public GraphWrapperSkeleton { + template + class UndirGraphWrapper : public GraphWrapper { protected: -// GraphWrapper gw; + typedef typename Graph::Edge GraphEdge; + typedef typename Graph::OutEdgeIt GraphOutEdgeIt; + typedef typename Graph::InEdgeIt GraphInEdgeIt; + public: + typedef typename GraphWrapper::Node Node; + typedef typename GraphWrapper::NodeIt NodeIt; - public: - //typedef GraphWrapper BaseGraph; +// UndirGraphWrapper() : GraphWrapper() { } + UndirGraphWrapper(Graph& _graph) : GraphWrapper(_graph) { } - typedef typename GraphWrapperSkeleton::Node Node; - typedef typename GraphWrapperSkeleton::NodeIt NodeIt; - - //private: - //FIXME ezeknek valojaban a GraphWrapper megfelelo dolgai kellene hogy - //legyenek, at kell irni - typedef typename /*GraphWrapperSkeleton*/ - GraphWrapper::Edge GraphEdge; - typedef typename /*GraphWrapperSkeleton*/ - GraphWrapper::OutEdgeIt GraphOutEdgeIt; - typedef typename /*GraphWrapperSkeleton*/ - GraphWrapper::InEdgeIt GraphInEdgeIt; - //public: - - //UndirGraphWrapper() : graph(0) { } - UndirGraphWrapper(GraphWrapper _gw) : - GraphWrapperSkeleton(_gw) { } - - //UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { } - - //void setGraph(Graph& _graph) { graph = &_graph; } - //Graph& getGraph() const { return (*graph); } - class Edge { - friend class UndirGraphWrapper; + friend class UndirGraphWrapper; protected: bool out_or_in; //true iff out GraphOutEdgeIt out; @@ -741,42 +638,42 @@ }; class OutEdgeIt : public Edge { - friend class UndirGraphWrapper; + friend class UndirGraphWrapper; public: OutEdgeIt() : Edge() { } OutEdgeIt(const Invalid& i) : Edge(i) { } - OutEdgeIt(const UndirGraphWrapper& _G, const Node& n) + OutEdgeIt(const UndirGraphWrapper& _G, const Node& n) : Edge() { - out_or_in=true; _G.gw.first(out, n); - if (!(_G.gw.valid(out))) { out_or_in=false; _G.gw.first(in, n); } + out_or_in=true; _G.graph->first(out, n); + if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); } } }; typedef OutEdgeIt InEdgeIt; class EdgeIt : public Edge { - friend class UndirGraphWrapper; + friend class UndirGraphWrapper; protected: NodeIt v; public: EdgeIt() : Edge() { } EdgeIt(const Invalid& i) : Edge(i) { } - EdgeIt(const UndirGraphWrapper& _G) + EdgeIt(const UndirGraphWrapper& _G) : Edge() { out_or_in=true; //Node v; _G.first(v); - if (_G.valid(v)) _G.gw.first(out); else out=INVALID; - while (_G.valid(v) && !_G.gw.valid(out)) { - _G.gw.next(v); - if (_G.valid(v)) _G.gw.first(out); + if (_G.valid(v)) _G.graph->first(out); else out=INVALID; + while (_G.valid(v) && !_G.graph->valid(out)) { + _G.graph->next(v); + if (_G.valid(v)) _G.graph->first(out); } } }; OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { - e.out_or_in=true; gw.first(e.out, n); - if (!(gw.valid(e.out))) { e.out_or_in=false; gw.first(e.in, n); } + e.out_or_in=true; graph->first(e.out, n); + if (!(graph->valid(e.out))) { e.out_or_in=false; graph->first(e.in, n); } return e; } @@ -784,47 +681,47 @@ e.out_or_in=true; //NodeIt v; first(e.v); - if (valid(e.v)) gw.first(e.out, e.v); else e.out=INVALID; - while (valid(e.v) && !gw.valid(e.out)) { - gw.next(e.v); - if (valid(e.v)) gw.first(e.out, e.v); + if (valid(e.v)) graph->first(e.out, e.v); else e.out=INVALID; + while (valid(e.v) && !graph->valid(e.out)) { + graph->next(e.v); + if (valid(e.v)) graph->first(e.out, e.v); } return e; } - template I& first(I& i) const { gw.first(i); return i; } + template I& first(I& i) const { graph->first(i); return i; } template I& first(I& i, const P& p) const { - gw.first(i, p); return i; } + graph->first(i, p); return i; } OutEdgeIt& next(OutEdgeIt& e) const { if (e.out_or_in) { - Node n=gw.tail(e.out); - gw.next(e.out); - if (!gw.valid(e.out)) { e.out_or_in=false; gw.first(e.in, n); } + Node n=graph->tail(e.out); + graph->next(e.out); + if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); } } else { - gw.next(e.in); + graph->next(e.in); } return e; } EdgeIt& next(EdgeIt& e) const { //NodeIt v=tail(e); - gw.next(e.out); - while (valid(e.v) && !gw.valid(e.out)) { + graph->next(e.out); + while (valid(e.v) && !graph->valid(e.out)) { next(e.v); - if (valid(e.v)) gw.first(e.out, e.v); + if (valid(e.v)) graph->first(e.out, e.v); } return e; } - template I& next(I &i) const { return gw.next(i); } + template I& next(I &i) const { return graph->next(i); } // template I getNext(const I& i) const { return gw.getNext(i); } template< typename It > It first() const { - It e; first(e); return e; } + It e; this->first(e); return e; } template< typename It > It first(const Node& v) const { - It e; first(e, v); return e; } + It e; this->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); } @@ -841,9 +738,9 @@ // return graph->bNode(e); } Node aNode(const OutEdgeIt& e) const { - if (e.out_or_in) return gw.tail(e); else return gw.head(e); } + if (e.out_or_in) return graph->tail(e); else return graph->head(e); } Node bNode(const OutEdgeIt& e) const { - if (e.out_or_in) return gw.head(e); else return gw.tail(e); } + if (e.out_or_in) return graph->head(e); else return graph->tail(e); } // Node addNode() const { return gw.addNode(); } @@ -855,21 +752,21 @@ // void clear() const { gw.clear(); } -// template class NodeMap : public GraphWrapper::NodeMap { +// template class NodeMap : public Graph::NodeMap { // public: -// NodeMap(const UndirGraphWrapper& _G) : -// GraphWrapper::NodeMap(_G.gw) { } -// NodeMap(const UndirGraphWrapper& _G, T a) : -// GraphWrapper::NodeMap(_G.gw, a) { } +// NodeMap(const UndirGraphWrapper& _G) : +// Graph::NodeMap(_G.gw) { } +// NodeMap(const UndirGraphWrapper& _G, T a) : +// Graph::NodeMap(_G.gw, a) { } // }; // template class EdgeMap : -// public GraphWrapperSkeleton::EdgeMap { +// public GraphWrapperSkeleton::EdgeMap { // public: -// EdgeMap(const UndirGraphWrapper& _G) : -// GraphWrapperSkeleton::EdgeMap(_G.gw) { } -// EdgeMap(const UndirGraphWrapper& _G, T a) : -// GraphWrapper::EdgeMap(_G.gw, a) { } +// EdgeMap(const UndirGraphWrapper& _G) : +// GraphWrapperSkeleton::EdgeMap(_G.gw) { } +// EdgeMap(const UndirGraphWrapper& _G, T a) : +// Graph::EdgeMap(_G.gw, a) { } // }; }; @@ -883,7 +780,7 @@ // Graph* graph; // public: -// typedef Graph BaseGraph; +// typedef Graph ParentGraph; // typedef typename Graph::Node Node; // typedef typename Graph::Edge Edge; @@ -946,32 +843,22 @@ // }; - template - class ResGraphWrapper : public GraphWrapperSkeleton{ + template + class ResGraphWrapper : public GraphWrapper{ public: - //typedef Graph BaseGraph; - //typedef TrivGraphWrapper GraphWrapper; - typedef typename GraphWrapperSkeleton::Node Node; - typedef typename GraphWrapperSkeleton::NodeIt NodeIt; - private: - typedef typename /*GraphWrapperSkeleton*/ - GraphWrapper::OutEdgeIt OldOutEdgeIt; - typedef typename /*GraphWrapperSkeleton*/ - GraphWrapper::InEdgeIt OldInEdgeIt; + typedef typename GraphWrapper::Node Node; + typedef typename GraphWrapper::NodeIt NodeIt; protected: - //const Graph* graph; - //GraphWrapper gw; + typedef typename Graph::OutEdgeIt GraphOutEdgeIt; + typedef typename Graph::InEdgeIt GraphInEdgeIt; + typedef typename Graph::Edge GraphEdge; FlowMap* flow; const CapacityMap* capacity; public: - ResGraphWrapper(const GraphWrapper& _gw, FlowMap& _flow, + ResGraphWrapper(Graph& _graph, FlowMap& _flow, const CapacityMap& _capacity) : - GraphWrapperSkeleton(_gw), - flow(&_flow), capacity(&_capacity) { } - - //void setGraph(const Graph& _graph) { graph = &_graph; } - //const Graph& getGraph() const { return (*graph); } + GraphWrapper(_graph), flow(&_flow), capacity(&_capacity) { } class Edge; class OutEdgeIt; @@ -979,11 +866,11 @@ friend class OutEdgeIt; class Edge { - friend class ResGraphWrapper; + friend class ResGraphWrapper; protected: bool out_or_in; //true, iff out - OldOutEdgeIt out; - OldInEdgeIt in; + GraphOutEdgeIt out; + GraphInEdgeIt in; public: Edge() : out_or_in(true) { } Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } @@ -1001,24 +888,27 @@ else return (u.out_or_in || u.in!=v.in); } + operator GraphEdge() const { + if (out_or_in) return(out); else return(in); + } }; class OutEdgeIt : public Edge { - friend class ResGraphWrapper; + friend class ResGraphWrapper; public: OutEdgeIt() { } //FIXME OutEdgeIt(const Edge& e) : Edge(e) { } OutEdgeIt(const Invalid& i) : Edge(i) { } protected: - OutEdgeIt(const ResGraphWrapper& resG, Node v) : Edge() { - resG.gw.first(out, v); - while( resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); } - if (!resG.gw.valid(out)) { + OutEdgeIt(const ResGraphWrapper& resG, Node v) : Edge() { + resG.graph->first(out, v); + while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } + if (!resG.graph->valid(out)) { out_or_in=0; - resG.gw.first(in, v); - while( resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); } + resG.graph->first(in, v); + while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } } } // public: @@ -1044,30 +934,30 @@ typedef void InEdgeIt; class EdgeIt : public Edge { - friend class ResGraphWrapper; + friend class ResGraphWrapper; NodeIt v; public: EdgeIt() { } //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { } EdgeIt(const Invalid& i) : Edge(i) { } - EdgeIt(const ResGraphWrapper& resG) : Edge() { - resG.gw.first(v); - if (resG.gw.valid(v)) resG.gw.first(out, v); else out=INVALID; - while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); } - while (resG.gw.valid(v) && !resG.gw.valid(out)) { - resG.gw.next(v); - if (resG.gw.valid(v)) resG.gw.first(out, v); - while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); } + EdgeIt(const ResGraphWrapper& resG) : Edge() { + resG.graph->first(v); + if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID; + while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } + while (resG.graph->valid(v) && !resG.graph->valid(out)) { + resG.graph->next(v); + if (resG.graph->valid(v)) resG.graph->first(out, v); + while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } } - if (!resG.gw.valid(out)) { + if (!resG.graph->valid(out)) { out_or_in=0; - resG.gw.first(v); - if (resG.gw.valid(v)) resG.gw.first(in, v); else in=INVALID; - while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); } - while (resG.gw.valid(v) && !resG.gw.valid(in)) { - resG.gw.next(v); - if (resG.gw.valid(v)) resG.gw.first(in, v); - while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); } + resG.graph->first(v); + if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID; + while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } + while (resG.graph->valid(v) && !resG.graph->valid(in)) { + resG.graph->next(v); + if (resG.graph->valid(v)) resG.graph->first(in, v); + while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } } } } @@ -1083,7 +973,7 @@ // if (!out.valid()) { // out_or_in=0; // G->first(v); -// if (v.valid()) G->first(in, v); else in=OldInEdgeIt(); +// if (v.valid()) G->first(in, v); else in=GraphInEdgeIt(); // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } // while (v.valid() && !in.valid()) { // ++v; @@ -1104,7 +994,7 @@ // } }; - NodeIt& first(NodeIt& v) const { gw.first(v); return v; } + NodeIt& first(NodeIt& v) const { graph->first(v); return v; } OutEdgeIt& first(OutEdgeIt& e, Node v) const { e=OutEdgeIt(*this, v); return e; @@ -1114,52 +1004,52 @@ return e; } - NodeIt& next(NodeIt& n) const { return gw.next(n); } + NodeIt& next(NodeIt& n) const { return graph->next(n); } OutEdgeIt& next(OutEdgeIt& e) const { if (e.out_or_in) { - Node v=gw.aNode(e.out); - gw.next(e.out); - while( gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); } - if (!gw.valid(e.out)) { + Node v=graph->aNode(e.out); + graph->next(e.out); + while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } + if (!graph->valid(e.out)) { e.out_or_in=0; - gw.first(e.in, v); - while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); } + graph->first(e.in, v); + while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } } } else { - gw.next(e.in); - while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); } + graph->next(e.in); + while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } } return e; } EdgeIt& next(EdgeIt& e) const { if (e.out_or_in) { - gw.next(e.out); - while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); } - while (gw.valid(e.v) && !gw.valid(e.out)) { - gw.next(e.v); - if (gw.valid(e.v)) gw.first(e.out, e.v); - while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); } + graph->next(e.out); + while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } + while (graph->valid(e.v) && !graph->valid(e.out)) { + graph->next(e.v); + if (graph->valid(e.v)) graph->first(e.out, e.v); + while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } } - if (!gw.valid(e.out)) { + if (!graph->valid(e.out)) { e.out_or_in=0; - gw.first(e.v); - if (gw.valid(e.v)) gw.first(e.in, e.v); else e.in=INVALID; - while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); } - while (gw.valid(e.v) && !gw.valid(e.in)) { - gw.next(e.v); - if (gw.valid(e.v)) gw.first(e.in, e.v); - while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); } + graph->first(e.v); + if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID; + while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } + while (graph->valid(e.v) && !graph->valid(e.in)) { + graph->next(e.v); + if (graph->valid(e.v)) graph->first(e.in, e.v); + while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } } } } else { - gw.next(e.in); - while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); } - while (gw.valid(e.v) && !gw.valid(e.in)) { - gw.next(e.v); - if (gw.valid(e.v)) gw.first(e.in, e.v); - while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); } + graph->next(e.in); + while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } + while (graph->valid(e.v) && !graph->valid(e.in)) { + graph->next(e.v); + if (graph->valid(e.v)) graph->first(e.in, e.v); + while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } } } return e; @@ -1181,54 +1071,60 @@ } Node tail(Edge e) const { - return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); } + return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } Node head(Edge e) const { - return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); } + return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } Node aNode(OutEdgeIt e) const { - return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); } + return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } Node bNode(OutEdgeIt e) const { - return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); } + return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } - int nodeNum() const { return gw.nodeNum(); } + int nodeNum() const { return graph->nodeNum(); } //FIXME - //int edgeNum() const { return gw.edgeNum(); } + //int edgeNum() const { return graph->edgeNum(); } - int id(Node v) const { return gw.id(v); } + int id(Node v) const { return graph->id(v); } - bool valid(Node n) const { return gw.valid(n); } + bool valid(Node n) const { return graph->valid(n); } bool valid(Edge e) const { - return e.out_or_in ? gw.valid(e.out) : gw.valid(e.in); } + return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); } void augment(const Edge& e, Number a) const { if (e.out_or_in) - flow->set(e.out, flow->get(e.out)+a); +// flow->set(e.out, flow->get(e.out)+a); + flow->set(e.out, (*flow)[e.out]+a); else - flow->set(e.in, flow->get(e.in)-a); +// flow->set(e.in, flow->get(e.in)-a); + flow->set(e.in, (*flow)[e.in]-a); } Number resCap(const Edge& e) const { if (e.out_or_in) - return (capacity->get(e.out)-flow->get(e.out)); +// return (capacity->get(e.out)-flow->get(e.out)); + return ((*capacity)[e.out]-(*flow)[e.out]); else - return (flow->get(e.in)); +// return (flow->get(e.in)); + return ((*flow)[e.in]); } - Number resCap(OldOutEdgeIt out) const { - return (capacity->get(out)-flow->get(out)); + Number resCap(GraphOutEdgeIt out) const { +// return (capacity->get(out)-flow->get(out)); + return ((*capacity)[out]-(*flow)[out]); } - Number resCap(OldInEdgeIt in) const { - return (flow->get(in)); + Number resCap(GraphInEdgeIt in) const { +// return (flow->get(in)); + return ((*flow)[in]); } -// template class NodeMap : public GraphWrapper::NodeMap { +// template class NodeMap : public Graph::NodeMap { // public: -// NodeMap(const ResGraphWrapper& _G) -// : GraphWrapper::NodeMap(_G.gw) { } -// NodeMap(const ResGraphWrapper& _G, -// T a) : GraphWrapper::NodeMap(_G.gw, a) { } +// NodeMap(const ResGraphWrapper& _G) +// : Graph::NodeMap(_G.gw) { } +// NodeMap(const ResGraphWrapper& _G, +// T a) : Graph::NodeMap(_G.gw, a) { } // }; // template @@ -1243,53 +1139,59 @@ template class EdgeMap { - typename GraphWrapper::EdgeMap forward_map, backward_map; + typename Graph::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.graph)), backward_map(*(_G.graph)) { } + EdgeMap(const ResGraphWrapper& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } void set(Edge e, T a) { if (e.out_or_in) forward_map.set(e.out, a); else backward_map.set(e.in, a); } - T get(Edge e) { + T operator[](Edge e) const { if (e.out_or_in) - return forward_map.get(e.out); + return forward_map[e.out]; else - return backward_map.get(e.in); + return backward_map[e.in]; } +// T get(Edge e) const { +// if (e.out_or_in) +// return forward_map.get(e.out); +// else +// return backward_map.get(e.in); +// } }; }; - //Subgraph on the same node-set and partial edge-set - template - class ErasingFirstGraphWrapper : public GraphWrapperSkeleton { + //ErasingFirstGraphWrapper for blocking flows + template + class ErasingFirstGraphWrapper : public GraphWrapper { protected: FirstOutEdgesMap* first_out_edges; public: - typedef typename GraphWrapperSkeleton::Node Node; - typedef typename GraphWrapperSkeleton::NodeIt NodeIt; - typedef typename GraphWrapperSkeleton::Edge Edge; - typedef typename GraphWrapperSkeleton::EdgeIt EdgeIt; - typedef typename GraphWrapperSkeleton::InEdgeIt InEdgeIt; - typedef typename GraphWrapperSkeleton::OutEdgeIt OutEdgeIt; + typedef typename GraphWrapper::Node Node; + typedef typename GraphWrapper::NodeIt NodeIt; + typedef typename GraphWrapper::Edge Edge; + typedef typename GraphWrapper::EdgeIt EdgeIt; + typedef typename GraphWrapper::InEdgeIt InEdgeIt; + typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; - ErasingFirstGraphWrapper(GraphWrapper _gw, FirstOutEdgesMap& _first_out_edges) : - GraphWrapperSkeleton(_gw), first_out_edges(&_first_out_edges) { } + ErasingFirstGraphWrapper(Graph& _graph, + FirstOutEdgesMap& _first_out_edges) : + GraphWrapper(_graph), first_out_edges(&_first_out_edges) { } template I& first(I& i) const { - gw.first(i); - //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); } + graph->first(i); return i; } OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { - e=first_out_edges->get(n); +// e=first_out_edges->get(n); + e=(*first_out_edges)[n]; return e; } template I& first(I& i, const P& p) const { - gw.first(i, p); - //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); } + graph->first(i, p); return i; } @@ -1297,8 +1199,7 @@ // return gw.getNext(i); //} template I& next(I &i) const { - gw.next(i); - //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); } + graph->next(i); return i; } @@ -1315,246 +1216,6 @@ } }; -// 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