1.1 --- a/src/work/bfs_iterator.hh Thu Feb 26 16:07:40 2004 +0000
1.2 +++ b/src/work/bfs_iterator.hh Fri Feb 27 12:39:15 2004 +0000
1.3 @@ -644,6 +644,7 @@
1.4 //}
1.5 }
1.6 void pushAndSetReached(NodeIt s) {
1.7 + actual_node=s;
1.8 reached.set(s, true);
1.9 dfs_stack.push(G.template first<OutEdgeIt>(s));
1.10 }
1.11 @@ -659,6 +660,7 @@
1.12 reached.set(w, true);
1.13 b_node_newly_reached=true;
1.14 } else {
1.15 + actual_node=G.aNode(actual_edge);
1.16 ++(dfs_stack.top());
1.17 b_node_newly_reached=false;
1.18 }
1.19 @@ -672,7 +674,7 @@
1.20 operator OutEdgeIt () const { return actual_edge; }
1.21 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.22 bool isANodeExamined() const { return !(actual_edge.valid()); }
1.23 - NodeIt aNode() const { return actual_node; }
1.24 + NodeIt aNode() const { return actual_node; /*FIXME*/}
1.25 NodeIt bNode() const { return G.bNode(actual_edge); }
1.26 const ReachedMap& getReachedMap() const { return reached; }
1.27 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
2.1 --- a/src/work/edmonds_karp.hh Thu Feb 26 16:07:40 2004 +0000
2.2 +++ b/src/work/edmonds_karp.hh Fri Feb 27 12:39:15 2004 +0000
2.3 @@ -6,7 +6,7 @@
2.4 #include <iterator>
2.5
2.6 #include <bfs_iterator.hh>
2.7 -#include <time_measure.h>
2.8 +//#include <time_measure.h>
2.9
2.10 namespace hugo {
2.11
2.12 @@ -281,6 +281,7 @@
2.13 bool out_or_in; //1, iff out
2.14 public:
2.15 EdgeIt() : out_or_in(1) { }
2.16 + //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) { }
2.17 Number free() const {
2.18 if (out_or_in) {
2.19 return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
2.20 @@ -297,6 +298,23 @@
2.21 /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
2.22 }
2.23 }
2.24 + void print() {
2.25 + if (out_or_in) {
2.26 + std::cout << "out ";
2.27 + if (out.valid())
2.28 + std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out));
2.29 + else
2.30 + std::cout << "invalid";
2.31 + }
2.32 + else {
2.33 + std::cout << "in ";
2.34 + if (in.valid())
2.35 + std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in));
2.36 + else
2.37 + std::cout << "invalid";
2.38 + }
2.39 + std::cout << std::endl;
2.40 + }
2.41 };
2.42
2.43 class OutEdgeIt : public EdgeIt {
2.44 @@ -308,11 +326,13 @@
2.45 G=&_G;
2.46 flow=&_flow;
2.47 capacity=&_capacity;
2.48 - out=/*resG->*/G->template first<OldOutEdgeIt>(v);
2.49 + //out=/*resG->*/G->template first<OldOutEdgeIt>(v);
2.50 + G->getFirst(out, v);
2.51 while( out.valid() && !(free()>0) ) { ++out; }
2.52 if (!out.valid()) {
2.53 out_or_in=0;
2.54 - in=/*resG->*/G->template first<OldInEdgeIt>(v);
2.55 + //in=/*resG->*/G->template first<OldInEdgeIt>(v);
2.56 + G->getFirst(in, v);
2.57 while( in.valid() && !(free()>0) ) { ++in; }
2.58 }
2.59 }
2.60 @@ -324,7 +344,7 @@
2.61 while( out.valid() && !(free()>0) ) { ++out; }
2.62 if (!out.valid()) {
2.63 out_or_in=0;
2.64 - in=/*resG->*/G->template first<OldInEdgeIt>(v);
2.65 + G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
2.66 while( in.valid() && !(free()>0) ) { ++in; }
2.67 }
2.68 } else {
2.69 @@ -335,9 +355,75 @@
2.70 }
2.71 };
2.72
2.73 + class EachEdgeIt : public EdgeIt {
2.74 + typename Graph::EachNodeIt v;
2.75 + public:
2.76 + EachEdgeIt() { }
2.77 + //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
2.78 + EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) {
2.79 + G=&_G;
2.80 + flow=&_flow;
2.81 + capacity=&_capacity;
2.82 + out_or_in=1;
2.83 + G->getFirst(v);
2.84 + if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
2.85 + while (out.valid() && !(free()>0) ) { ++out; }
2.86 + while (v.valid() && !out.valid()) {
2.87 + ++v;
2.88 + if (v.valid()) G->getFirst(out, v);
2.89 + while (out.valid() && !(free()>0) ) { ++out; }
2.90 + }
2.91 + if (!out.valid()) {
2.92 + out_or_in=0;
2.93 + G->getFirst(v);
2.94 + if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
2.95 + while (in.valid() && !(free()>0) ) { ++in; }
2.96 + while (v.valid() && !in.valid()) {
2.97 + ++v;
2.98 + if (v.valid()) G->getFirst(in, v);
2.99 + while (in.valid() && !(free()>0) ) { ++in; }
2.100 + }
2.101 + }
2.102 + }
2.103 + EachEdgeIt& operator++() {
2.104 + if (out_or_in) {
2.105 + ++out;
2.106 + while (out.valid() && !(free()>0) ) { ++out; }
2.107 + while (v.valid() && !out.valid()) {
2.108 + ++v;
2.109 + if (v.valid()) G->getFirst(out, v);
2.110 + while (out.valid() && !(free()>0) ) { ++out; }
2.111 + }
2.112 + if (!out.valid()) {
2.113 + out_or_in=0;
2.114 + G->getFirst(v);
2.115 + if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
2.116 + while (in.valid() && !(free()>0) ) { ++in; }
2.117 + while (v.valid() && !in.valid()) {
2.118 + ++v;
2.119 + if (v.valid()) G->getFirst(in, v);
2.120 + while (in.valid() && !(free()>0) ) { ++in; }
2.121 + }
2.122 + }
2.123 + } else {
2.124 + ++in;
2.125 + while (in.valid() && !(free()>0) ) { ++in; }
2.126 + while (v.valid() && !in.valid()) {
2.127 + ++v;
2.128 + if (v.valid()) G->getFirst(in, v);
2.129 + while (in.valid() && !(free()>0) ) { ++in; }
2.130 + }
2.131 + }
2.132 + return *this;
2.133 + }
2.134 + };
2.135 +
2.136 void getFirst(OutEdgeIt& e, NodeIt v) const {
2.137 e=OutEdgeIt(G, v, flow, capacity);
2.138 }
2.139 + void getFirst(EachEdgeIt& e) const {
2.140 + e=EachEdgeIt(G, flow, capacity);
2.141 + }
2.142 void getFirst(EachNodeIt& v) const { G.getFirst(v); }
2.143
2.144 template< typename It >
2.145 @@ -401,13 +487,13 @@
2.146 //AugGraph res_graph;
2.147 //typedef typename AugGraph::NodeMap<bool> ReachedMap;
2.148 //typename AugGraph::NodeMap<AugEdgeIt> pred;
2.149 - //typename AugGraph::NodeMap<int> free;
2.150 + //typename AugGraph::NodeMap<Number> free;
2.151 public:
2.152 MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) :
2.153 G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) //,
2.154 //res_graph(G, flow, capacity), pred(res_graph), free(res_graph)
2.155 { }
2.156 - bool augment() {
2.157 + bool augmentOnShortestPath() {
2.158 AugGraph res_graph(G, flow, capacity);
2.159 bool _augment=false;
2.160
2.161 @@ -419,7 +505,7 @@
2.162 //filled up with invalid iterators
2.163 //pred.set(s, AugEdgeIt());
2.164
2.165 - typename AugGraph::NodeMap<int> free(res_graph);
2.166 + typename AugGraph::NodeMap<Number> free(res_graph);
2.167
2.168 //searching for augmenting path
2.169 while ( !res_bfs.finished() ) {
2.170 @@ -451,48 +537,130 @@
2.171
2.172 return _augment;
2.173 }
2.174 - bool augmentWithBlockingFlow() {
2.175 - BfsIterator4< Graph, OutEdgeIt, typename Graph::NodeMap<bool> > bfs(G);
2.176 + template<typename MutableGraph> bool augmentOnBlockingFlow() {
2.177 + bool _augment=false;
2.178 +
2.179 + AugGraph res_graph(G, flow, capacity);
2.180 +
2.181 + typedef typename AugGraph::NodeMap<bool> ReachedMap;
2.182 + BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
2.183 +
2.184 bfs.pushAndSetReached(s);
2.185 - typename Graph::NodeMap<int> dist(G); //filled up with 0's
2.186 + typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
2.187 while ( !bfs.finished() ) {
2.188 - OutEdgeIt e=OutEdgeIt(bfs);
2.189 + AugOutEdgeIt e=AugOutEdgeIt(bfs);
2.190 if (e.valid() && bfs.isBNodeNewlyReached()) {
2.191 - dist.set(G.head(e), dist.get(G.tail(e))+1);
2.192 - //NodeIt v=res_graph.tail(e);
2.193 - //NodeIt w=res_graph.head(e);
2.194 - //pred.set(w, e);
2.195 - //if (pred.get(v).valid()) {
2.196 - // free.set(w, std::min(free.get(v), e.free()));
2.197 - //} else {
2.198 - // free.set(w, e.free());
2.199 - //}
2.200 - //if (res_graph.head(e)==t) { _augment=true; break; }
2.201 + dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
2.202 }
2.203
2.204 ++bfs;
2.205 - } //end of searching augmenting path
2.206 + } //computing distances from s in the residual graph
2.207
2.208 - double pre_time_copy=currTime();
2.209 - typedef Graph MutableGraph;
2.210 MutableGraph F;
2.211 - typename Graph::NodeMap<NodeIt> G_to_F(G);
2.212 - for(typename Graph::EachNodeIt n=G.template first<typename Graph::EachNodeIt>(); n.valid(); ++n) {
2.213 - G_to_F.set(n, F.addNode());
2.214 + typename AugGraph::NodeMap<NodeIt> res_graph_to_F(res_graph);
2.215 + for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); n.valid(); ++n) {
2.216 + res_graph_to_F.set(n, F.addNode());
2.217 }
2.218 - for(typename Graph::EachEdgeIt e=G.template first<typename Graph::EachEdgeIt>(); e.valid(); ++e) {
2.219 - if (dist.get(G.head(e))==dist.get(G.tail(e))+1) {
2.220 - F.addEdge(G_to_F.get(G.tail(e)), G_to_F.get(G.head(e)));
2.221 +
2.222 + typename MutableGraph::NodeIt sF=res_graph_to_F.get(s);
2.223 + typename MutableGraph::NodeIt tF=res_graph_to_F.get(t);
2.224 +
2.225 + typename MutableGraph::EdgeMap<AugEdgeIt> original_edge(F);
2.226 + typename MutableGraph::EdgeMap<Number> free_on_edge(F);
2.227 +
2.228 + //Making F to the graph containing the edges of the residual graph
2.229 + //which are in some shortest paths
2.230 + for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); e.valid(); ++e) {
2.231 + if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
2.232 + typename MutableGraph::EdgeIt f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
2.233 + original_edge.update();
2.234 + original_edge.set(f, e);
2.235 + free_on_edge.update();
2.236 + free_on_edge.set(f, e.free());
2.237 + }
2.238 + }
2.239 +
2.240 + bool __augment=true;
2.241 +
2.242 + while (__augment) {
2.243 + __augment=false;
2.244 + //computing blocking flow with dfs
2.245 + typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
2.246 + DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
2.247 + typename MutableGraph::NodeMap<EdgeIt> pred(F); //invalid iterators
2.248 + typename MutableGraph::NodeMap<Number> free(F);
2.249 +
2.250 + dfs.pushAndSetReached(sF);
2.251 + while (!dfs.finished()) {
2.252 + ++dfs;
2.253 + if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
2.254 + //std::cout << "OutEdgeIt: " << dfs;
2.255 + //std::cout << " aNode: " << F.aNode(dfs);
2.256 + //std::cout << " bNode: " << F.bNode(dfs) << " ";
2.257 +
2.258 + typename MutableGraph::NodeIt v=F.aNode(dfs);
2.259 + typename MutableGraph::NodeIt w=F.bNode(dfs);
2.260 + pred.set(w, dfs);
2.261 + if (pred.get(v).valid()) {
2.262 + free.set(w, std::min(free.get(v), free_on_edge.get(dfs)));
2.263 + } else {
2.264 + free.set(w, free_on_edge.get(dfs)/*original_edge.get(dfs).free()*/);
2.265 + }
2.266 + if (w==tF) {
2.267 + //std::cout << "AUGMENTATION"<<std::endl;
2.268 + __augment=true;
2.269 + _augment=true;
2.270 + break;
2.271 + }
2.272 + } else {
2.273 + //std::cout << "OutEdgeIt: " << "invalid";
2.274 + //std::cout << " aNode: " << dfs.aNode();
2.275 + //std::cout << " bNode: " << "invalid" << " ";
2.276 + }
2.277 + if (dfs.isBNodeNewlyReached()) {
2.278 + //std::cout << "bNodeIsNewlyReached ";
2.279 + } else {
2.280 + //std::cout << "bNodeIsNotNewlyReached ";
2.281 + if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
2.282 + //std::cout << "DELETE ";
2.283 + F.erase(typename MutableGraph::OutEdgeIt(dfs));
2.284 + }
2.285 + }
2.286 + //if (dfs.isANodeExamined()) {
2.287 + //std::cout << "aNodeIsExamined ";
2.288 + //} else {
2.289 + //std::cout << "aNodeIsNotExamined ";
2.290 + //}
2.291 + //std::cout<<std::endl;
2.292 }
2.293 +
2.294 + if (__augment) {
2.295 + typename MutableGraph::NodeIt n=tF;
2.296 + Number augment_value=free.get(tF);
2.297 + while (pred.get(n).valid()) {
2.298 + typename MutableGraph::EdgeIt e=pred.get(n);
2.299 + original_edge.get(e).augment(augment_value);
2.300 + n=F.tail(e);
2.301 + F.erase(e);
2.302 + }
2.303 + }
2.304 +
2.305 }
2.306 - double post_time_copy=currTime();
2.307 - std::cout << "copy time: " << post_time_copy-pre_time_copy << " sec"<< std::endl;
2.308 -
2.309 - return 0;
2.310 +
2.311 + return _augment;
2.312 }
2.313 void run() {
2.314 //int num_of_augmentations=0;
2.315 - while (augment()) {
2.316 + while (augmentOnShortestPath()) {
2.317 + //while (augmentOnBlockingFlow<MutableGraph>()) {
2.318 + //std::cout << ++num_of_augmentations << " ";
2.319 + //std::cout<<std::endl;
2.320 + }
2.321 + }
2.322 + template<typename MutableGraph> void run() {
2.323 + //int num_of_augmentations=0;
2.324 + //while (augmentOnShortestPath()) {
2.325 + while (augmentOnBlockingFlow<MutableGraph>()) {
2.326 //std::cout << ++num_of_augmentations << " ";
2.327 //std::cout<<std::endl;
2.328 }
2.329 @@ -599,7 +767,7 @@
2.330 typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
2.331 //filled up with invalid iterators
2.332
2.333 - typename AugGraph::NodeMap<int> free(res_graph);
2.334 + typename AugGraph::NodeMap<Number> free(res_graph);
2.335
2.336 //searching for augmenting path
2.337 while ( !res_bfs.finished() ) {
3.1 --- a/src/work/marci/edmonds_karp_demo.cc Thu Feb 26 16:07:40 2004 +0000
3.2 +++ b/src/work/marci/edmonds_karp_demo.cc Fri Feb 27 12:39:15 2004 +0000
3.3 @@ -19,29 +19,16 @@
3.4 ListGraph::EdgeMap<int> cap(G);
3.5 readDimacsMaxFlow(std::cin, G, s, t, cap);
3.6
3.7 -/*
3.8 - double pre_time_copy=currTime();
3.9 - ListGraph F;
3.10 - ListGraph::NodeMap<NodeIt> G_to_F(G);
3.11 - typedef ListGraph::EachNodeIt EachNodeIt;
3.12 - for(EachNodeIt n=G.first<EachNodeIt>(); n.valid(); ++n) {
3.13 - G_to_F.set(n, F.addNode());
3.14 - }
3.15 - for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
3.16 - F.addEdge(G_to_F.get(G.tail(e)), G_to_F.get(G.head(e)));
3.17 - }
3.18 - double post_time_copy=currTime();
3.19 - std::cout << "copy time: " << post_time_copy-pre_time_copy << " sec"<< std::endl;
3.20 -*/
3.21 -
3.22 - std::cout << "edmonds karp demo..." << std::endl;
3.23 + {
3.24 + std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl;
3.25 ListGraph::EdgeMap<int> flow(G); //0 flow
3.26
3.27 double pre_time=currTime();
3.28 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
3.29 - max_flow_test.augmentWithBlockingFlow();
3.30 - max_flow_test.run();
3.31 + //max_flow_test.augmentWithBlockingFlow<ListGraph>();
3.32 + max_flow_test.run<ListGraph>();
3.33 double post_time=currTime();
3.34 +
3.35 //std::cout << "maximum flow: "<< std::endl;
3.36 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
3.37 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
3.38 @@ -49,6 +36,26 @@
3.39 //std::cout<<std::endl;
3.40 std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl;
3.41 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
3.42 + }
3.43 +
3.44 + {
3.45 + std::cout << "edmonds karp demo (shortest path augmentation)..." << std::endl;
3.46 + ListGraph::EdgeMap<int> flow(G); //0 flow
3.47 +
3.48 + double pre_time=currTime();
3.49 + MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
3.50 + //max_flow_test.augmentWithBlockingFlow<ListGraph>();
3.51 + max_flow_test.run();
3.52 + double post_time=currTime();
3.53 +
3.54 + //std::cout << "maximum flow: "<< std::endl;
3.55 + //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
3.56 + // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
3.57 + //}
3.58 + //std::cout<<std::endl;
3.59 + std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl;
3.60 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
3.61 + }
3.62
3.63 return 0;
3.64 }
4.1 --- a/src/work/marci_graph_demo.cc Thu Feb 26 16:07:40 2004 +0000
4.2 +++ b/src/work/marci_graph_demo.cc Fri Feb 27 12:39:15 2004 +0000
4.3 @@ -225,6 +225,17 @@
4.4 {
4.5 ListGraph::EdgeMap<int> flow(flowG, 0);
4.6 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap);
4.7 + /*
4.8 + max_flow_test.augmentOnBlockingFlow<ListGraph>();
4.9 + for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
4.10 + std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
4.11 + }
4.12 + std::cout<<std::endl;
4.13 + max_flow_test.augmentOnBlockingFlow<ListGraph>();
4.14 + for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
4.15 + std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
4.16 + }
4.17 + std::cout<<std::endl;*/
4.18 max_flow_test.run();
4.19
4.20 std::cout << "maximum flow: "<< std::endl;