1.1 --- a/src/work/bfs_iterator.hh Thu Mar 11 12:55:50 2004 +0000
1.2 +++ b/src/work/bfs_iterator.hh Thu Mar 11 14:15:07 2004 +0000
1.3 @@ -562,10 +562,15 @@
1.4 own_reached_map(true) { }
1.5 ~BfsIterator4() { if (own_reached_map) delete &reached; }
1.6 void pushAndSetReached(NodeIt s) {
1.7 + //std::cout << "mimi" << &reached << std::endl;
1.8 reached.set(s, true);
1.9 + //std::cout << "mumus" << std::endl;
1.10 if (bfs_queue.empty()) {
1.11 + //std::cout << "bibi1" << std::endl;
1.12 bfs_queue.push(s);
1.13 + //std::cout << "zizi" << std::endl;
1.14 G.getFirst(actual_edge, s);
1.15 + //std::cout << "kiki" << std::endl;
1.16 if (G.valid(actual_edge)/*.valid()*/) {
1.17 NodeIt w=G.bNode(actual_edge);
1.18 if (!reached.get(w)) {
1.19 @@ -577,6 +582,7 @@
1.20 }
1.21 }
1.22 } else {
1.23 + //std::cout << "bibi2" << std::endl;
1.24 bfs_queue.push(s);
1.25 }
1.26 }
2.1 --- a/src/work/edmonds_karp.hh Thu Mar 11 12:55:50 2004 +0000
2.2 +++ b/src/work/edmonds_karp.hh Thu Mar 11 14:15:07 2004 +0000
2.3 @@ -279,7 +279,7 @@
2.4 bool _augment=false;
2.5
2.6 typedef typename AugGraph::NodeMap<bool> ReachedMap;
2.7 - BfsIterator5< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
2.8 + BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
2.9 res_bfs.pushAndSetReached(s);
2.10
2.11 typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
2.12 @@ -296,9 +296,9 @@
2.13 NodeIt w=res_graph.head(e);
2.14 pred.set(w, e);
2.15 if (res_graph.valid(pred.get(v))) {
2.16 - free.set(w, std::min(free.get(v), e.free()));
2.17 + free.set(w, std::min(free.get(v), res_graph.free(e)));
2.18 } else {
2.19 - free.set(w, e.free());
2.20 + free.set(w, res_graph.free(e));
2.21 }
2.22 if (res_graph.head(e)==t) { _augment=true; break; }
2.23 }
2.24 @@ -311,7 +311,8 @@
2.25 Number augment_value=free.get(t);
2.26 while (res_graph.valid(pred.get(n))) {
2.27 AugEdgeIt e=pred.get(n);
2.28 - e.augment(augment_value);
2.29 + res_graph.augment(e, augment_value);
2.30 + //e.augment(augment_value);
2.31 n=res_graph.tail(e);
2.32 }
2.33 }
2.34 @@ -358,7 +359,7 @@
2.35 original_edge.update();
2.36 original_edge.set(f, e);
2.37 residual_capacity.update();
2.38 - residual_capacity.set(f, e.free());
2.39 + residual_capacity.set(f, res_graph.free(e));
2.40 }
2.41 }
2.42
2.43 @@ -376,44 +377,30 @@
2.44 while (!dfs.finished()) {
2.45 ++dfs;
2.46 if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
2.47 - //std::cout << "OutEdgeIt: " << dfs;
2.48 - //std::cout << " aNode: " << F.aNode(dfs);
2.49 - //std::cout << " bNode: " << F.bNode(dfs) << " ";
2.50 + if (dfs.isBNodeNewlyReached()) {
2.51 +// std::cout << "OutEdgeIt: " << dfs;
2.52 +// std::cout << " aNode: " << F.aNode(dfs);
2.53 +// std::cout << " bNode: " << F.bNode(dfs) << " ";
2.54
2.55 - typename MutableGraph::NodeIt v=F.aNode(dfs);
2.56 - typename MutableGraph::NodeIt w=F.bNode(dfs);
2.57 - pred.set(w, dfs);
2.58 - if (F.valid(pred.get(v))) {
2.59 - free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
2.60 + typename MutableGraph::NodeIt v=F.aNode(dfs);
2.61 + typename MutableGraph::NodeIt w=F.bNode(dfs);
2.62 + pred.set(w, dfs);
2.63 + if (F.valid(pred.get(v))) {
2.64 + free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
2.65 + } else {
2.66 + free.set(w, residual_capacity.get(dfs));
2.67 + }
2.68 + if (w==tF) {
2.69 + //std::cout << "AUGMENTATION"<<std::endl;
2.70 + __augment=true;
2.71 + _augment=true;
2.72 + break;
2.73 + }
2.74 +
2.75 } else {
2.76 - free.set(w, residual_capacity.get(dfs)/*original_edge.get(dfs).free()*/);
2.77 - }
2.78 - if (w==tF) {
2.79 - //std::cout << "AUGMENTATION"<<std::endl;
2.80 - __augment=true;
2.81 - _augment=true;
2.82 - break;
2.83 - }
2.84 - } else {
2.85 - //std::cout << "OutEdgeIt: " << "invalid";
2.86 - //std::cout << " aNode: " << dfs.aNode();
2.87 - //std::cout << " bNode: " << "invalid" << " ";
2.88 - }
2.89 - if (dfs.isBNodeNewlyReached()) {
2.90 - //std::cout << "bNodeIsNewlyReached ";
2.91 - } else {
2.92 - //std::cout << "bNodeIsNotNewlyReached ";
2.93 - if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
2.94 - //std::cout << "DELETE ";
2.95 F.erase(typename MutableGraph::OutEdgeIt(dfs));
2.96 }
2.97 }
2.98 - //if (dfs.isANodeExamined()) {
2.99 - //std::cout << "aNodeIsExamined ";
2.100 - //} else {
2.101 - //std::cout << "aNodeIsNotExamined ";
2.102 - //}
2.103 - //std::cout<<std::endl;
2.104 }
2.105
2.106 if (__augment) {
2.107 @@ -421,7 +408,8 @@
2.108 Number augment_value=free.get(tF);
2.109 while (F.valid(pred.get(n))) {
2.110 typename MutableGraph::EdgeIt e=pred.get(n);
2.111 - original_edge.get(e).augment(augment_value);
2.112 + res_graph.augment(original_edge.get(e), augment_value);
2.113 + //original_edge.get(e).augment(augment_value);
2.114 n=F.tail(e);
2.115 if (residual_capacity.get(e)==augment_value)
2.116 F.erase(e);
2.117 @@ -429,6 +417,127 @@
2.118 residual_capacity.set(e, residual_capacity.get(e)-augment_value);
2.119 }
2.120 }
2.121 +
2.122 + }
2.123 +
2.124 + return _augment;
2.125 + }
2.126 + bool augmentOnBlockingFlow2() {
2.127 + bool _augment=false;
2.128 +
2.129 + //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
2.130 + typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
2.131 + typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
2.132 + typedef typename EAugGraph::EdgeIt EAugEdgeIt;
2.133 +
2.134 + EAugGraph res_graph(*G, *flow, *capacity);
2.135 +
2.136 + //std::cout << "meg jo1" << std::endl;
2.137 +
2.138 + //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
2.139 + BfsIterator4<
2.140 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
2.141 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
2.142 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
2.143 +
2.144 + //std::cout << "meg jo2" << std::endl;
2.145 +
2.146 + bfs.pushAndSetReached(s);
2.147 + //std::cout << "meg jo2.5" << std::endl;
2.148 +
2.149 + //typename EAugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
2.150 + typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
2.151 + NodeMap<int>& dist=res_graph.dist;
2.152 + //std::cout << "meg jo2.6" << std::endl;
2.153 +
2.154 + while ( !bfs.finished() ) {
2.155 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
2.156 +// EAugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
2.157 + //if (res_graph.valid(e)) {
2.158 + // std::cout<<"a:"<<res_graph.tail(e)<<"b:"<<res_graph.head(e)<<std::endl;
2.159 + //}
2.160 + if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
2.161 + dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
2.162 + }
2.163 +
2.164 + ++bfs;
2.165 + } //computing distances from s in the residual graph
2.166 +
2.167 +
2.168 + //std::cout << "meg jo3" << std::endl;
2.169 +
2.170 +// typedef typename EAugGraph::EachNodeIt EAugEachNodeIt;
2.171 +// for(EAugEachNodeIt n=res_graph.template first<EAugEachNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
2.172 +// std::cout << "dist: " << dist.get(n) << std::endl;
2.173 +// }
2.174 +
2.175 + bool __augment=true;
2.176 +
2.177 + while (__augment) {
2.178 +// std::cout << "new iteration"<< std::endl;
2.179 +
2.180 + __augment=false;
2.181 + //computing blocking flow with dfs
2.182 + typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
2.183 + DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
2.184 + dfs(res_graph);
2.185 + typename EAugGraph::NodeMap<EAugEdgeIt> pred(res_graph); //invalid iterators
2.186 + typename EAugGraph::NodeMap<Number> free(res_graph);
2.187 +
2.188 + dfs.pushAndSetReached(s);
2.189 + while (!dfs.finished()) {
2.190 + ++dfs;
2.191 + if (res_graph.valid(EAugOutEdgeIt(dfs))) {
2.192 + if (dfs.isBNodeNewlyReached()) {
2.193 +// std::cout << "OutEdgeIt: " << dfs;
2.194 +// std::cout << " aNode: " << res_graph.aNode(dfs);
2.195 +// std::cout << " res cap: " << EAugOutEdgeIt(dfs).free();
2.196 +// std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
2.197 +
2.198 + typename EAugGraph::NodeIt v=res_graph.aNode(dfs);
2.199 + typename EAugGraph::NodeIt w=res_graph.bNode(dfs);
2.200 +
2.201 + pred.set(w, EAugOutEdgeIt(dfs));
2.202 +
2.203 + //std::cout << EAugOutEdgeIt(dfs).free() << std::endl;
2.204 + if (res_graph.valid(pred.get(v))) {
2.205 + free.set(w, std::min(free.get(v), res_graph.free(/*EAugOutEdgeIt*/(dfs))));
2.206 + } else {
2.207 + free.set(w, res_graph.free(/*EAugOutEdgeIt*/(dfs)));
2.208 + }
2.209 +
2.210 + if (w==t) {
2.211 +// std::cout << "t is reached, AUGMENTATION"<<std::endl;
2.212 + __augment=true;
2.213 + _augment=true;
2.214 + break;
2.215 + }
2.216 + } else {
2.217 +// std::cout << "<<DELETE ";
2.218 +// std::cout << " aNode: " << res_graph.aNode(dfs);
2.219 +// std::cout << " res cap: " << EAugOutEdgeIt(dfs).free();
2.220 +// std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
2.221 +// std::cout << "DELETE>> ";
2.222 +
2.223 + res_graph.erase(dfs);
2.224 + }
2.225 + }
2.226 +
2.227 + }
2.228 +
2.229 + if (__augment) {
2.230 + typename EAugGraph::NodeIt n=t;
2.231 + Number augment_value=free.get(t);
2.232 +// std::cout << "av:" << augment_value << std::endl;
2.233 + while (res_graph.valid(pred.get(n))) {
2.234 + EAugEdgeIt e=pred.get(n);
2.235 + res_graph.augment(e, augment_value);
2.236 + //e.augment(augment_value);
2.237 + n=res_graph.tail(e);
2.238 + if (res_graph.free(e)==0)
2.239 + res_graph.erase(e);
2.240 + }
2.241 + }
2.242
2.243 }
2.244
3.1 --- a/src/work/marci/edmonds_karp_demo.cc Thu Mar 11 12:55:50 2004 +0000
3.2 +++ b/src/work/marci/edmonds_karp_demo.cc Thu Mar 11 14:15:07 2004 +0000
3.3 @@ -87,7 +87,42 @@
3.4 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
3.5 //max_flow_test.augmentWithBlockingFlow<ListGraph>();
3.6 int i=0;
3.7 - while (max_flow_test.augmentOnBlockingFlow<ListGraph>()) { ++i; }
3.8 + while (max_flow_test.augmentOnBlockingFlow<ListGraph>()) {
3.9 +// for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
3.10 +// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
3.11 +// }
3.12 +// std::cout<<std::endl;
3.13 + ++i;
3.14 + }
3.15 + //double post_time=currTime();
3.16 +
3.17 + //std::cout << "maximum flow: "<< std::endl;
3.18 + //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
3.19 + // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
3.20 + //}
3.21 + //std::cout<<std::endl;
3.22 + std::cout << "elapsed time: " << ts << std::endl;
3.23 + std::cout << "number of augmentation phases: " << i << std::endl;
3.24 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
3.25 + }
3.26 +
3.27 + {
3.28 + std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl;
3.29 + ListGraph::EdgeMap<int> flow(G); //0 flow
3.30 +
3.31 + Timer ts;
3.32 + ts.reset();
3.33 + //double pre_time=currTime();
3.34 + MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
3.35 + //max_flow_test.augmentWithBlockingFlow<ListGraph>();
3.36 + int i=0;
3.37 + while (max_flow_test.augmentOnBlockingFlow2()) {
3.38 +// for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
3.39 +// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
3.40 +// }
3.41 +// std::cout<<std::endl;
3.42 + ++i;
3.43 + }
3.44 //double post_time=currTime();
3.45
3.46 //std::cout << "maximum flow: "<< std::endl;
3.47 @@ -110,7 +145,13 @@
3.48 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
3.49 //max_flow_test.augmentWithBlockingFlow<ListGraph>();
3.50 int i=0;
3.51 - while (max_flow_test.augmentOnShortestPath()) { ++i; }
3.52 + while (max_flow_test.augmentOnShortestPath()) {
3.53 +// for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
3.54 +// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
3.55 +// }
3.56 +// std::cout<<std::endl;
3.57 + ++i;
3.58 + }
3.59 //double post_time=currTime();
3.60
3.61 //std::cout << "maximum flow: "<< std::endl;
4.1 --- a/src/work/marci/graph_wrapper.h Thu Mar 11 12:55:50 2004 +0000
4.2 +++ b/src/work/marci/graph_wrapper.h Thu Mar 11 14:15:07 2004 +0000
4.3 @@ -19,6 +19,12 @@
4.4 typedef typename Graph::InEdgeIt InEdgeIt;
4.5 //typedef typename Graph::SymEdgeIt SymEdgeIt;
4.6 typedef typename Graph::EachEdgeIt EachEdgeIt;
4.7 +
4.8 + //TrivGraphWrapper() : graph(0) { }
4.9 + TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
4.10 +
4.11 + void setGraph(Graph& _graph) { graph = &_graph; }
4.12 + Graph& getGraph() const { return (*graph); }
4.13
4.14 template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
4.15 template<typename I, typename P> I& getFirst(I& i, const P& p) const {
4.16 @@ -66,6 +72,7 @@
4.17 NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :
4.18 Graph::NodeMap<T>(_G.getGraph(), a) { }
4.19 };
4.20 +
4.21 template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
4.22 public:
4.23 EdgeMap(const TrivGraphWrapper<Graph>& _G) :
4.24 @@ -73,12 +80,6 @@
4.25 EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
4.26 Graph::EdgeMap<T>(_G.getGraph(), a) { }
4.27 };
4.28 -
4.29 - void setGraph(Graph& _graph) { graph = &_graph; }
4.30 - Graph& getGraph() const { return (*graph); }
4.31 -
4.32 - //TrivGraphWrapper() : graph(0) { }
4.33 - TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
4.34 };
4.35
4.36 template<typename Graph>
4.37 @@ -97,6 +98,12 @@
4.38 typedef typename Graph::InEdgeIt OutEdgeIt;
4.39 //typedef typename Graph::SymEdgeIt SymEdgeIt;
4.40 typedef typename Graph::EachEdgeIt EachEdgeIt;
4.41 +
4.42 + //RevGraphWrapper() : graph(0) { }
4.43 + RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
4.44 +
4.45 + void setGraph(Graph& _graph) { graph = &_graph; }
4.46 + Graph& getGraph() const { return (*graph); }
4.47
4.48 template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
4.49 template<typename I, typename P> I& getFirst(I& i, const P& p) const {
4.50 @@ -144,6 +151,7 @@
4.51 NodeMap(const RevGraphWrapper<Graph>& _G, T a) :
4.52 Graph::NodeMap<T>(_G.getGraph(), a) { }
4.53 };
4.54 +
4.55 template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
4.56 public:
4.57 EdgeMap(const RevGraphWrapper<Graph>& _G) :
4.58 @@ -151,12 +159,6 @@
4.59 EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :
4.60 Graph::EdgeMap<T>(_G.getGraph(), a) { }
4.61 };
4.62 -
4.63 - void setGraph(Graph& _graph) { graph = &_graph; }
4.64 - Graph& getGraph() const { return (*graph); }
4.65 -
4.66 - //RevGraphWrapper() : graph(0) { }
4.67 - RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
4.68 };
4.69
4.70
4.71 @@ -182,6 +184,12 @@
4.72 typedef typename Graph::InEdgeIt GraphInEdgeIt;
4.73 //public:
4.74
4.75 + //UndirGraphWrapper() : graph(0) { }
4.76 + UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }
4.77 +
4.78 + void setGraph(Graph& _graph) { graph = &_graph; }
4.79 + Graph& getGraph() const { return (*graph); }
4.80 +
4.81 class EdgeIt {
4.82 friend class UndirGraphWrapper<Graph>;
4.83 bool out_or_in; //true iff out
4.84 @@ -196,9 +204,6 @@
4.85
4.86 class OutEdgeIt : public EdgeIt {
4.87 friend class UndirGraphWrapper<Graph>;
4.88 - //bool out_or_in; //true iff out
4.89 - //GraphOutEdgeIt out;
4.90 - //GraphInEdgeIt in;
4.91 public:
4.92 OutEdgeIt() : EdgeIt() { }
4.93 OutEdgeIt(const UndirGraphWrapper& _G, const NodeIt& n) : EdgeIt() {
4.94 @@ -287,6 +292,7 @@
4.95 NodeMap(const UndirGraphWrapper<Graph>& _G, T a) :
4.96 Graph::NodeMap<T>(_G.getGraph(), a) { }
4.97 };
4.98 +
4.99 template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
4.100 public:
4.101 EdgeMap(const UndirGraphWrapper<Graph>& _G) :
4.102 @@ -294,12 +300,6 @@
4.103 EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) :
4.104 Graph::EdgeMap<T>(_G.getGraph(), a) { }
4.105 };
4.106 -
4.107 - void setGraph(Graph& _graph) { graph = &_graph; }
4.108 - Graph& getGraph() const { return (*graph); }
4.109 -
4.110 - //TrivGraphWrapper() : graph(0) { }
4.111 - UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }
4.112 };
4.113
4.114
4.115 @@ -386,13 +386,16 @@
4.116 FlowMap* flow;
4.117 const CapacityMap* capacity;
4.118 public:
4.119 +
4.120 ResGraphWrapper(const Graph& _G, FlowMap& _flow,
4.121 const CapacityMap& _capacity) :
4.122 G(&_G), flow(&_flow), capacity(&_capacity) { }
4.123 // ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) :
4.124 // G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }
4.125 - void setGraph(Graph& _graph) { graph = &_graph; }
4.126 - Graph& getGraph() const { return (*graph); }
4.127 +
4.128 + void setGraph(const Graph& _graph) { graph = &_graph; }
4.129 + const Graph& getGraph() const { return (*G); }
4.130 +
4.131 class EdgeIt;
4.132 class OutEdgeIt;
4.133 friend class EdgeIt;
4.134 @@ -401,94 +404,49 @@
4.135 class EdgeIt {
4.136 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
4.137 protected:
4.138 - //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
4.139 - const Graph* G;
4.140 - FlowMap* flow;
4.141 - const CapacityMap* capacity;
4.142 - //OldSymEdgeIt sym;
4.143 + bool out_or_in; //true, iff out
4.144 OldOutEdgeIt out;
4.145 OldInEdgeIt in;
4.146 - bool out_or_in; //true, iff out
4.147 public:
4.148 EdgeIt() : out_or_in(true) { }
4.149 - EdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) :
4.150 - G(&_G), flow(&_flow), capacity(&_capacity), out_or_in(true) { }
4.151 - //EdgeIt(const EdgeIt& e) : G(e.G), flow(e.flow), capacity(e.capacity), out(e.out), in(e.in), out_or_in(e.out_or_in) { }
4.152 - Number free() const {
4.153 - if (out_or_in) {
4.154 - return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
4.155 - } else {
4.156 - return (/*resG->*/flow->get(in));
4.157 - }
4.158 - }
4.159 - bool valid() const {
4.160 - return out_or_in && out.valid() || in.valid(); }
4.161 - void augment(Number a) const {
4.162 - if (out_or_in) {
4.163 - /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);
4.164 - } else {
4.165 - /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
4.166 - }
4.167 - }
4.168 - void print() {
4.169 - if (out_or_in) {
4.170 - std::cout << "out ";
4.171 - if (out.valid())
4.172 - std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out));
4.173 - else
4.174 - std::cout << "invalid";
4.175 - }
4.176 - else {
4.177 - std::cout << "in ";
4.178 - if (in.valid())
4.179 - std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in));
4.180 - else
4.181 - std::cout << "invalid";
4.182 - }
4.183 - std::cout << std::endl;
4.184 - }
4.185 +// bool valid() const {
4.186 +// return out_or_in && out.valid() || in.valid(); }
4.187 };
4.188
4.189 - Number free(OldOutEdgeIt out) const {
4.190 - return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
4.191 - }
4.192 - Number free(OldInEdgeIt in) const {
4.193 - return (/*resG->*/flow->get(in));
4.194 - }
4.195
4.196 class OutEdgeIt : public EdgeIt {
4.197 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
4.198 public:
4.199 OutEdgeIt() { }
4.200 + //FIXME
4.201 + OutEdgeIt(const EdgeIt& e) : EdgeIt(e) { }
4.202 private:
4.203 - OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
4.204 - //out=/*resG->*/G->template first<OldOutEdgeIt>(v);
4.205 - G->getFirst(out, v);
4.206 - while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
4.207 + OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, NodeIt v) : EdgeIt() {
4.208 + resG.G->getFirst(out, v);
4.209 + while( out.valid() && !(resG.free(out)>0) ) { ++out; }
4.210 if (!out.valid()) {
4.211 out_or_in=0;
4.212 - //in=/*resG->*/G->template first<OldInEdgeIt>(v);
4.213 - G->getFirst(in, v);
4.214 - while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
4.215 + resG.G->getFirst(in, v);
4.216 + while( in.valid() && !(resG.free(in)>0) ) { ++in; }
4.217 }
4.218 }
4.219 - public:
4.220 - OutEdgeIt& operator++() {
4.221 - if (out_or_in) {
4.222 - NodeIt v=/*resG->*/G->aNode(out);
4.223 - ++out;
4.224 - while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
4.225 - if (!out.valid()) {
4.226 - out_or_in=0;
4.227 - G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
4.228 - while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
4.229 - }
4.230 - } else {
4.231 - ++in;
4.232 - while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
4.233 - }
4.234 - return *this;
4.235 - }
4.236 +// public:
4.237 +// OutEdgeIt& operator++() {
4.238 +// if (out_or_in) {
4.239 +// NodeIt v=/*resG->*/G->aNode(out);
4.240 +// ++out;
4.241 +// while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
4.242 +// if (!out.valid()) {
4.243 +// out_or_in=0;
4.244 +// G->getFirst(in, v);
4.245 +// while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
4.246 +// }
4.247 +// } else {
4.248 +// ++in;
4.249 +// while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
4.250 +// }
4.251 +// return *this;
4.252 +// }
4.253 };
4.254
4.255 class EachEdgeIt : public EdgeIt {
4.256 @@ -497,67 +455,66 @@
4.257 public:
4.258 EachEdgeIt() { }
4.259 //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
4.260 - EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
4.261 - out_or_in=true;
4.262 - G->getFirst(v);
4.263 - if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
4.264 - while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
4.265 + EachEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : EdgeIt() {
4.266 + resG.G->getFirst(v);
4.267 + if (v.valid()) resG.G->getFirst(out, v); else out=OldOutEdgeIt();
4.268 + while (out.valid() && !(resG.free(out)>0) ) { ++out; }
4.269 while (v.valid() && !out.valid()) {
4.270 ++v;
4.271 - if (v.valid()) G->getFirst(out, v);
4.272 - while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
4.273 + if (v.valid()) resG.G->getFirst(out, v);
4.274 + while (out.valid() && !(resG.free(out)>0) ) { ++out; }
4.275 }
4.276 if (!out.valid()) {
4.277 out_or_in=0;
4.278 - G->getFirst(v);
4.279 - if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
4.280 - while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
4.281 + resG.G->getFirst(v);
4.282 + if (v.valid()) resG.G->getFirst(in, v); else in=OldInEdgeIt();
4.283 + while (in.valid() && !(resG.free(in)>0) ) { ++in; }
4.284 while (v.valid() && !in.valid()) {
4.285 ++v;
4.286 - if (v.valid()) G->getFirst(in, v);
4.287 - while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
4.288 + if (v.valid()) resG.G->getFirst(in, v);
4.289 + while (in.valid() && !(resG.free(in)>0) ) { ++in; }
4.290 }
4.291 }
4.292 }
4.293 - EachEdgeIt& operator++() {
4.294 - if (out_or_in) {
4.295 - ++out;
4.296 - while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
4.297 - while (v.valid() && !out.valid()) {
4.298 - ++v;
4.299 - if (v.valid()) G->getFirst(out, v);
4.300 - while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
4.301 - }
4.302 - if (!out.valid()) {
4.303 - out_or_in=0;
4.304 - G->getFirst(v);
4.305 - if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
4.306 - while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
4.307 - while (v.valid() && !in.valid()) {
4.308 - ++v;
4.309 - if (v.valid()) G->getFirst(in, v);
4.310 - while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
4.311 - }
4.312 - }
4.313 - } else {
4.314 - ++in;
4.315 - while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
4.316 - while (v.valid() && !in.valid()) {
4.317 - ++v;
4.318 - if (v.valid()) G->getFirst(in, v);
4.319 - while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
4.320 - }
4.321 - }
4.322 - return *this;
4.323 - }
4.324 +// EachEdgeIt& operator++() {
4.325 +// if (out_or_in) {
4.326 +// ++out;
4.327 +// while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
4.328 +// while (v.valid() && !out.valid()) {
4.329 +// ++v;
4.330 +// if (v.valid()) G->getFirst(out, v);
4.331 +// while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
4.332 +// }
4.333 +// if (!out.valid()) {
4.334 +// out_or_in=0;
4.335 +// G->getFirst(v);
4.336 +// if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
4.337 +// while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
4.338 +// while (v.valid() && !in.valid()) {
4.339 +// ++v;
4.340 +// if (v.valid()) G->getFirst(in, v);
4.341 +// while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
4.342 +// }
4.343 +// }
4.344 +// } else {
4.345 +// ++in;
4.346 +// while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
4.347 +// while (v.valid() && !in.valid()) {
4.348 +// ++v;
4.349 +// if (v.valid()) G->getFirst(in, v);
4.350 +// while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
4.351 +// }
4.352 +// }
4.353 +// return *this;
4.354 +// }
4.355 };
4.356
4.357 - void getFirst(EachNodeIt& v) const { G->getFirst(v); }
4.358 - void getFirst(OutEdgeIt& e, NodeIt v) const {
4.359 - e=OutEdgeIt(*G, v, *flow, *capacity);
4.360 + EachNodeIt& getFirst(EachNodeIt& v) const { G->getFirst(v); }
4.361 + OutEdgeIt& getFirst(OutEdgeIt& e, NodeIt v) const {
4.362 + e=OutEdgeIt(*this, v);
4.363 }
4.364 - void getFirst(EachEdgeIt& e) const {
4.365 - e=EachEdgeIt(*G, *flow, *capacity);
4.366 + EachEdgeIt& getFirst(EachEdgeIt& e) const {
4.367 + e=EachEdgeIt(*this);
4.368 }
4.369
4.370 EachNodeIt& next(EachNodeIt& n) const { return G->next(n); }
4.371 @@ -566,15 +523,15 @@
4.372 if (e.out_or_in) {
4.373 NodeIt v=G->aNode(e.out);
4.374 ++(e.out);
4.375 - while( G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
4.376 + while( G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
4.377 if (!G->valid(e.out)) {
4.378 e.out_or_in=0;
4.379 - G->getFirst(e.in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
4.380 - while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
4.381 + G->getFirst(e.in, v);
4.382 + while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
4.383 }
4.384 } else {
4.385 ++(e.in);
4.386 - while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
4.387 + while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
4.388 }
4.389 return e;
4.390 }
4.391 @@ -582,30 +539,30 @@
4.392 EachEdgeIt& next(EachEdgeIt& e) const {
4.393 if (e.out_or_in) {
4.394 ++(e.out);
4.395 - while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
4.396 + while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
4.397 while (G->valid(e.v) && !G->valid(e.out)) {
4.398 ++(e.v);
4.399 if (G->valid(e.v)) G->getFirst(e.out, e.v);
4.400 - while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
4.401 + while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
4.402 }
4.403 if (!G->valid(e.out)) {
4.404 e.out_or_in=0;
4.405 G->getFirst(e.v);
4.406 if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt();
4.407 - while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
4.408 + while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
4.409 while (G->valid(e.v) && !G->valid(e.in)) {
4.410 ++(e.v);
4.411 if (G->valid(e.v)) G->getFirst(e.in, e.v);
4.412 - while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
4.413 + while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
4.414 }
4.415 }
4.416 } else {
4.417 ++(e.in);
4.418 - while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
4.419 + while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
4.420 while (G->valid(e.v) && !G->valid(e.in)) {
4.421 ++(e.v);
4.422 if (G->valid(e.v)) G->getFirst(e.in, e.v);
4.423 - while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
4.424 + while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
4.425 }
4.426 }
4.427 return e;
4.428 @@ -642,6 +599,28 @@
4.429 bool valid(EdgeIt e) const {
4.430 return e.out_or_in ? G->valid(e.out) : G->valid(e.in); }
4.431
4.432 + void augment(const EdgeIt& e, Number a) const {
4.433 + if (e.out_or_in)
4.434 + flow->set(e.out, flow->get(e.out)+a);
4.435 + else
4.436 + flow->set(e.in, flow->get(e.in)-a);
4.437 + }
4.438 +
4.439 + Number free(const EdgeIt& e) const {
4.440 + if (e.out_or_in)
4.441 + return (capacity->get(e.out)-flow->get(e.out));
4.442 + else
4.443 + return (flow->get(e.in));
4.444 + }
4.445 +
4.446 + Number free(OldOutEdgeIt out) const {
4.447 + return (capacity->get(out)-flow->get(out));
4.448 + }
4.449 +
4.450 + Number free(OldInEdgeIt in) const {
4.451 + return (flow->get(in));
4.452 + }
4.453 +
4.454 template<typename T> class NodeMap : public Graph::NodeMap<T> {
4.455 public:
4.456 NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
4.457 @@ -679,6 +658,243 @@
4.458 return backward_map.get(e.in);
4.459 }
4.460 };
4.461 + };
4.462 +
4.463 + template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
4.464 + class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
4.465 + protected:
4.466 + ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
4.467 + //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
4.468 + public:
4.469 + ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,
4.470 + const CapacityMap& _capacity) :
4.471 + ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),
4.472 + first_out_edges(*this) /*, dist(*this)*/ {
4.473 + for(EachNodeIt n=this->template first<EachNodeIt>(); this->valid(n); this->next(n)) {
4.474 + OutEdgeIt e;
4.475 + ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(e, n);
4.476 + first_out_edges.set(n, e);
4.477 + }
4.478 + }
4.479 +
4.480 + //void setGraph(Graph& _graph) { graph = &_graph; }
4.481 + //Graph& getGraph() const { return (*graph); }
4.482 +
4.483 + //TrivGraphWrapper() : graph(0) { }
4.484 + //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }
4.485 +
4.486 + //typedef Graph BaseGraph;
4.487 +
4.488 + //typedef typename Graph::NodeIt NodeIt;
4.489 + //typedef typename Graph::EachNodeIt EachNodeIt;
4.490 +
4.491 + //typedef typename Graph::EdgeIt EdgeIt;
4.492 + //typedef typename Graph::OutEdgeIt OutEdgeIt;
4.493 + //typedef typename Graph::InEdgeIt InEdgeIt;
4.494 + //typedef typename Graph::SymEdgeIt SymEdgeIt;
4.495 + //typedef typename Graph::EachEdgeIt EachEdgeIt;
4.496 +
4.497 + typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
4.498 + typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt;
4.499 +
4.500 + typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
4.501 + typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
4.502 + //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
4.503 + //typedef typename Graph::SymEdgeIt SymEdgeIt;
4.504 + //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachEdgeIt EachEdgeIt;
4.505 +
4.506 + EachNodeIt& getFirst(EachNodeIt& n) const {
4.507 + return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(n);
4.508 + }
4.509 +
4.510 + OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {
4.511 + e=first_out_edges.get(n);
4.512 + return e;
4.513 + }
4.514 +
4.515 + //ROSSZ template<typename I> I& getFirst(I& i) const { return getFirst(i); }
4.516 + //ROSSZ template<typename I, typename P> I& getFirst(I& i, const P& p) const {
4.517 + // return getFirst(i, p); }
4.518 +
4.519 + //template<typename I> I getNext(const I& i) const {
4.520 + // return graph->getNext(i); }
4.521 + //template<typename I> I& next(I &i) const { return graph->next(i); }
4.522 +
4.523 + template< typename It > It first() const {
4.524 + It e; getFirst(e); return e; }
4.525 +
4.526 + template< typename It > It first(const NodeIt& v) const {
4.527 + It e; getFirst(e, v); return e; }
4.528 +
4.529 + //NodeIt head(const EdgeIt& e) const { return graph->head(e); }
4.530 + //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
4.531 +
4.532 + //template<typename I> bool valid(const I& i) const
4.533 + // { return graph->valid(i); }
4.534 +
4.535 + //int nodeNum() const { return graph->nodeNum(); }
4.536 + //int edgeNum() const { return graph->edgeNum(); }
4.537 +
4.538 + //template<typename I> NodeIt aNode(const I& e) const {
4.539 + // return graph->aNode(e); }
4.540 + //template<typename I> NodeIt bNode(const I& e) const {
4.541 + // return graph->bNode(e); }
4.542 +
4.543 + //NodeIt addNode() const { return graph->addNode(); }
4.544 + //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
4.545 + // return graph->addEdge(tail, head); }
4.546 +
4.547 + //void erase(const OutEdgeIt& e) {
4.548 + // first_out_edge(this->tail(e))=e;
4.549 + //}
4.550 + void erase(const EdgeIt& e) {
4.551 + OutEdgeIt f(e);
4.552 + next(f);
4.553 + first_out_edges.set(this->tail(e), f);
4.554 + }
4.555 + //template<typename I> void erase(const I& i) const { graph->erase(i); }
4.556 +
4.557 + //void clear() const { graph->clear(); }
4.558 +
4.559 + template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
4.560 + public:
4.561 + NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
4.562 + ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
4.563 + NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
4.564 + ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
4.565 + };
4.566 +
4.567 + template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
4.568 + public:
4.569 + EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
4.570 + ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
4.571 + EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
4.572 + ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
4.573 + };
4.574 + };
4.575 +
4.576 + template<typename GraphWrapper>
4.577 + class FilterGraphWrapper {
4.578 + };
4.579 +
4.580 + template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
4.581 + class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
4.582 +
4.583 + //Graph* graph;
4.584 +
4.585 + public:
4.586 + //typedef Graph BaseGraph;
4.587 +
4.588 + typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
4.589 + typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt;
4.590 +
4.591 + typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
4.592 + typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
4.593 + //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
4.594 + //typedef typename Graph::SymEdgeIt SymEdgeIt;
4.595 + typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachEdgeIt EachEdgeIt;
4.596 +
4.597 + //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
4.598 +
4.599 + public:
4.600 + FilterGraphWrapper(const Graph& _G, FlowMap& _flow,
4.601 + const CapacityMap& _capacity) :
4.602 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this) {
4.603 + }
4.604 +
4.605 + OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {
4.606 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(e, n);
4.607 + while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e))))
4.608 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
4.609 + return e;
4.610 + }
4.611 +
4.612 + EachNodeIt& next(EachNodeIt& e) const {
4.613 + return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
4.614 + }
4.615 +
4.616 + OutEdgeIt& next(OutEdgeIt& e) const {
4.617 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
4.618 + while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e))))
4.619 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
4.620 + return e;
4.621 + }
4.622 +
4.623 + EachNodeIt& getFirst(EachNodeIt& n) const {
4.624 + return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(n);
4.625 + }
4.626 +
4.627 + void erase(const EdgeIt& e) {
4.628 + OutEdgeIt f(e);
4.629 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
4.630 + while (valid(f) && (dist.get(tail(f))+1!=dist.get(head(f))))
4.631 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
4.632 + first_out_edges.set(this->tail(e), f);
4.633 + }
4.634 +
4.635 + //TrivGraphWrapper() : graph(0) { }
4.636 + //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
4.637 +
4.638 + //void setGraph(Graph& _graph) { graph = &_graph; }
4.639 + //Graph& getGraph() const { return (*graph); }
4.640 +
4.641 + //template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
4.642 + //template<typename I, typename P> I& getFirst(I& i, const P& p) const {
4.643 + // return graph->getFirst(i, p); }
4.644 +
4.645 + //template<typename I> I getNext(const I& i) const {
4.646 + // return graph->getNext(i); }
4.647 + //template<typename I> I& next(I &i) const { return graph->next(i); }
4.648 +
4.649 + template< typename It > It first() const {
4.650 + It e; getFirst(e); return e; }
4.651 +
4.652 + template< typename It > It first(const NodeIt& v) const {
4.653 + It e; getFirst(e, v); return e; }
4.654 +
4.655 + //NodeIt head(const EdgeIt& e) const { return graph->head(e); }
4.656 + //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
4.657 +
4.658 + //template<typename I> bool valid(const I& i) const
4.659 + // { return graph->valid(i); }
4.660 +
4.661 + //template<typename I> void setInvalid(const I &i);
4.662 + //{ return graph->setInvalid(i); }
4.663 +
4.664 + //int nodeNum() const { return graph->nodeNum(); }
4.665 + //int edgeNum() const { return graph->edgeNum(); }
4.666 +
4.667 + //template<typename I> NodeIt aNode(const I& e) const {
4.668 + // return graph->aNode(e); }
4.669 + //template<typename I> NodeIt bNode(const I& e) const {
4.670 + // return graph->bNode(e); }
4.671 +
4.672 + //NodeIt addNode() const { return graph->addNode(); }
4.673 + //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
4.674 + // return graph->addEdge(tail, head); }
4.675 +
4.676 + //template<typename I> void erase(const I& i) const { graph->erase(i); }
4.677 +
4.678 + //void clear() const { graph->clear(); }
4.679 +
4.680 + template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
4.681 + public:
4.682 + NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
4.683 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
4.684 + NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
4.685 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
4.686 + };
4.687 +
4.688 + template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
4.689 + public:
4.690 + EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
4.691 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
4.692 + EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
4.693 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
4.694 + };
4.695 +
4.696 + public:
4.697 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
4.698
4.699 };
4.700
5.1 --- a/src/work/marci/makefile Thu Mar 11 12:55:50 2004 +0000
5.2 +++ b/src/work/marci/makefile Thu Mar 11 14:15:07 2004 +0000
5.3 @@ -16,8 +16,8 @@
5.4 sinclude .depend
5.5
5.6 edmonds_karp_demo:
5.7 - $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -o edmonds_karp_demo edmonds_karp_demo.cc
5.8 - $(CXX3) $(CXXFLAGS) -g -pg -O3 -I. -I.. -o edmonds_karp_demo_prof edmonds_karp_demo.cc
5.9 + $(CXX3) $(CXXFLAGS) -g -O3 -I. -I.. -o edmonds_karp_demo edmonds_karp_demo.cc
5.10 + $(CXX3) $(CXXFLAGS) -g -pg -O3 -I. -I.. -o edmonds_karp_demo_prof edmonds_karp_demo_prof.cc
5.11
5.12 edmonds_karp_demo_alpar:
5.13 $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../alpar -o edmonds_karp_demo_alpar edmonds_karp_demo_alpar.cc
6.1 --- a/src/work/marci_graph_demo.cc Thu Mar 11 12:55:50 2004 +0000
6.2 +++ b/src/work/marci_graph_demo.cc Thu Mar 11 14:15:07 2004 +0000
6.3 @@ -236,13 +236,15 @@
6.4 std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
6.5 }
6.6 std::cout<<std::endl;*/
6.7 - max_flow_test.run();
6.8 + //max_flow_test.run();
6.9
6.10 - std::cout << "maximum flow: "<< std::endl;
6.11 - for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
6.12 - std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
6.13 + //std::cout << "maximum flow: "<< std::endl;
6.14 + while (max_flow_test.augmentOnShortestPath()) {
6.15 + for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
6.16 + std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
6.17 + }
6.18 + std::cout<<std::endl;
6.19 }
6.20 - std::cout<<std::endl;
6.21 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
6.22 }
6.23 /*