# HG changeset patch
# User marci
# Date 1079014507 0
# Node ID 27fbd1559fb7edbd60e1fc006afa8a6eb7fa5c63
# Parent 7949a29a334e0fd8267d68da67090f5ea37b26fa
graph wrapper improvements, blocking flow on fly
diff -r 7949a29a334e -r 27fbd1559fb7 src/work/bfs_iterator.hh
--- a/src/work/bfs_iterator.hh Thu Mar 11 12:55:50 2004 +0000
+++ b/src/work/bfs_iterator.hh Thu Mar 11 14:15:07 2004 +0000
@@ -562,10 +562,15 @@
own_reached_map(true) { }
~BfsIterator4() { if (own_reached_map) delete &reached; }
void pushAndSetReached(NodeIt s) {
+ //std::cout << "mimi" << &reached << std::endl;
reached.set(s, true);
+ //std::cout << "mumus" << std::endl;
if (bfs_queue.empty()) {
+ //std::cout << "bibi1" << std::endl;
bfs_queue.push(s);
+ //std::cout << "zizi" << std::endl;
G.getFirst(actual_edge, s);
+ //std::cout << "kiki" << std::endl;
if (G.valid(actual_edge)/*.valid()*/) {
NodeIt w=G.bNode(actual_edge);
if (!reached.get(w)) {
@@ -577,6 +582,7 @@
}
}
} else {
+ //std::cout << "bibi2" << std::endl;
bfs_queue.push(s);
}
}
diff -r 7949a29a334e -r 27fbd1559fb7 src/work/edmonds_karp.hh
--- a/src/work/edmonds_karp.hh Thu Mar 11 12:55:50 2004 +0000
+++ b/src/work/edmonds_karp.hh Thu Mar 11 14:15:07 2004 +0000
@@ -279,7 +279,7 @@
bool _augment=false;
typedef typename AugGraph::NodeMap<bool> ReachedMap;
- BfsIterator5< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
+ BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
res_bfs.pushAndSetReached(s);
typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
@@ -296,9 +296,9 @@
NodeIt w=res_graph.head(e);
pred.set(w, e);
if (res_graph.valid(pred.get(v))) {
- free.set(w, std::min(free.get(v), e.free()));
+ free.set(w, std::min(free.get(v), res_graph.free(e)));
} else {
- free.set(w, e.free());
+ free.set(w, res_graph.free(e));
}
if (res_graph.head(e)==t) { _augment=true; break; }
}
@@ -311,7 +311,8 @@
Number augment_value=free.get(t);
while (res_graph.valid(pred.get(n))) {
AugEdgeIt e=pred.get(n);
- e.augment(augment_value);
+ res_graph.augment(e, augment_value);
+ //e.augment(augment_value);
n=res_graph.tail(e);
}
}
@@ -358,7 +359,7 @@
original_edge.update();
original_edge.set(f, e);
residual_capacity.update();
- residual_capacity.set(f, e.free());
+ residual_capacity.set(f, res_graph.free(e));
}
}
@@ -376,44 +377,30 @@
while (!dfs.finished()) {
++dfs;
if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
- //std::cout << "OutEdgeIt: " << dfs;
- //std::cout << " aNode: " << F.aNode(dfs);
- //std::cout << " bNode: " << F.bNode(dfs) << " ";
+ if (dfs.isBNodeNewlyReached()) {
+// std::cout << "OutEdgeIt: " << dfs;
+// std::cout << " aNode: " << F.aNode(dfs);
+// std::cout << " bNode: " << F.bNode(dfs) << " ";
- typename MutableGraph::NodeIt v=F.aNode(dfs);
- typename MutableGraph::NodeIt 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)));
+ typename MutableGraph::NodeIt v=F.aNode(dfs);
+ typename MutableGraph::NodeIt w=F.bNode(dfs);
+ pred.set(w, dfs);
+ if (F.valid(pred.get(v))) {
+ free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
+ } else {
+ free.set(w, residual_capacity.get(dfs));
+ }
+ if (w==tF) {
+ //std::cout << "AUGMENTATION"<<std::endl;
+ __augment=true;
+ _augment=true;
+ break;
+ }
+
} else {
- free.set(w, residual_capacity.get(dfs)/*original_edge.get(dfs).free()*/);
- }
- if (w==tF) {
- //std::cout << "AUGMENTATION"<<std::endl;
- __augment=true;
- _augment=true;
- break;
- }
- } else {
- //std::cout << "OutEdgeIt: " << "invalid";
- //std::cout << " aNode: " << dfs.aNode();
- //std::cout << " bNode: " << "invalid" << " ";
- }
- if (dfs.isBNodeNewlyReached()) {
- //std::cout << "bNodeIsNewlyReached ";
- } else {
- //std::cout << "bNodeIsNotNewlyReached ";
- if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
- //std::cout << "DELETE ";
F.erase(typename MutableGraph::OutEdgeIt(dfs));
}
}
- //if (dfs.isANodeExamined()) {
- //std::cout << "aNodeIsExamined ";
- //} else {
- //std::cout << "aNodeIsNotExamined ";
- //}
- //std::cout<<std::endl;
}
if (__augment) {
@@ -421,7 +408,8 @@
Number augment_value=free.get(tF);
while (F.valid(pred.get(n))) {
typename MutableGraph::EdgeIt e=pred.get(n);
- original_edge.get(e).augment(augment_value);
+ res_graph.augment(original_edge.get(e), augment_value);
+ //original_edge.get(e).augment(augment_value);
n=F.tail(e);
if (residual_capacity.get(e)==augment_value)
F.erase(e);
@@ -429,6 +417,127 @@
residual_capacity.set(e, residual_capacity.get(e)-augment_value);
}
}
+
+ }
+
+ return _augment;
+ }
+ bool augmentOnBlockingFlow2() {
+ bool _augment=false;
+
+ //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
+ typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
+ typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
+ typedef typename EAugGraph::EdgeIt EAugEdgeIt;
+
+ EAugGraph res_graph(*G, *flow, *capacity);
+
+ //std::cout << "meg jo1" << std::endl;
+
+ //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
+ BfsIterator4<
+ ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
+ ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
+ ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
+
+ //std::cout << "meg jo2" << std::endl;
+
+ bfs.pushAndSetReached(s);
+ //std::cout << "meg jo2.5" << std::endl;
+
+ //typename EAugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
+ typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
+ NodeMap<int>& dist=res_graph.dist;
+ //std::cout << "meg jo2.6" << std::endl;
+
+ while ( !bfs.finished() ) {
+ ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
+// EAugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
+ //if (res_graph.valid(e)) {
+ // std::cout<<"a:"<<res_graph.tail(e)<<"b:"<<res_graph.head(e)<<std::endl;
+ //}
+ 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
+
+
+ //std::cout << "meg jo3" << std::endl;
+
+// typedef typename EAugGraph::EachNodeIt EAugEachNodeIt;
+// for(EAugEachNodeIt n=res_graph.template first<EAugEachNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
+// std::cout << "dist: " << dist.get(n) << std::endl;
+// }
+
+ bool __augment=true;
+
+ while (__augment) {
+// std::cout << "new iteration"<< std::endl;
+
+ __augment=false;
+ //computing blocking flow with dfs
+ typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
+ DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
+ dfs(res_graph);
+ typename EAugGraph::NodeMap<EAugEdgeIt> pred(res_graph); //invalid iterators
+ typename EAugGraph::NodeMap<Number> free(res_graph);
+
+ dfs.pushAndSetReached(s);
+ while (!dfs.finished()) {
+ ++dfs;
+ if (res_graph.valid(EAugOutEdgeIt(dfs))) {
+ if (dfs.isBNodeNewlyReached()) {
+// std::cout << "OutEdgeIt: " << dfs;
+// std::cout << " aNode: " << res_graph.aNode(dfs);
+// std::cout << " res cap: " << EAugOutEdgeIt(dfs).free();
+// std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
+
+ typename EAugGraph::NodeIt v=res_graph.aNode(dfs);
+ typename EAugGraph::NodeIt w=res_graph.bNode(dfs);
+
+ pred.set(w, EAugOutEdgeIt(dfs));
+
+ //std::cout << EAugOutEdgeIt(dfs).free() << std::endl;
+ if (res_graph.valid(pred.get(v))) {
+ free.set(w, std::min(free.get(v), res_graph.free(/*EAugOutEdgeIt*/(dfs))));
+ } else {
+ free.set(w, res_graph.free(/*EAugOutEdgeIt*/(dfs)));
+ }
+
+ if (w==t) {
+// std::cout << "t is reached, AUGMENTATION"<<std::endl;
+ __augment=true;
+ _augment=true;
+ break;
+ }
+ } else {
+// std::cout << "<<DELETE ";
+// std::cout << " aNode: " << res_graph.aNode(dfs);
+// std::cout << " res cap: " << EAugOutEdgeIt(dfs).free();
+// std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
+// std::cout << "DELETE>> ";
+
+ res_graph.erase(dfs);
+ }
+ }
+
+ }
+
+ if (__augment) {
+ typename EAugGraph::NodeIt n=t;
+ Number augment_value=free.get(t);
+// std::cout << "av:" << augment_value << std::endl;
+ while (res_graph.valid(pred.get(n))) {
+ EAugEdgeIt e=pred.get(n);
+ res_graph.augment(e, augment_value);
+ //e.augment(augment_value);
+ n=res_graph.tail(e);
+ if (res_graph.free(e)==0)
+ res_graph.erase(e);
+ }
+ }
}
diff -r 7949a29a334e -r 27fbd1559fb7 src/work/marci/edmonds_karp_demo.cc
--- a/src/work/marci/edmonds_karp_demo.cc Thu Mar 11 12:55:50 2004 +0000
+++ b/src/work/marci/edmonds_karp_demo.cc Thu Mar 11 14:15:07 2004 +0000
@@ -87,7 +87,42 @@
MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
//max_flow_test.augmentWithBlockingFlow<ListGraph>();
int i=0;
- while (max_flow_test.augmentOnBlockingFlow<ListGraph>()) { ++i; }
+ while (max_flow_test.augmentOnBlockingFlow<ListGraph>()) {
+// for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
+// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
+// }
+// std::cout<<std::endl;
+ ++i;
+ }
+ //double post_time=currTime();
+
+ //std::cout << "maximum flow: "<< std::endl;
+ //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
+ // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
+ //}
+ //std::cout<<std::endl;
+ std::cout << "elapsed time: " << ts << std::endl;
+ std::cout << "number of augmentation phases: " << i << std::endl;
+ std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+ }
+
+ {
+ std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl;
+ ListGraph::EdgeMap<int> flow(G); //0 flow
+
+ Timer ts;
+ ts.reset();
+ //double pre_time=currTime();
+ MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
+ //max_flow_test.augmentWithBlockingFlow<ListGraph>();
+ int i=0;
+ while (max_flow_test.augmentOnBlockingFlow2()) {
+// for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
+// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
+// }
+// std::cout<<std::endl;
+ ++i;
+ }
//double post_time=currTime();
//std::cout << "maximum flow: "<< std::endl;
@@ -110,7 +145,13 @@
MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
//max_flow_test.augmentWithBlockingFlow<ListGraph>();
int i=0;
- while (max_flow_test.augmentOnShortestPath()) { ++i; }
+ while (max_flow_test.augmentOnShortestPath()) {
+// for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
+// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
+// }
+// std::cout<<std::endl;
+ ++i;
+ }
//double post_time=currTime();
//std::cout << "maximum flow: "<< std::endl;
diff -r 7949a29a334e -r 27fbd1559fb7 src/work/marci/graph_wrapper.h
--- a/src/work/marci/graph_wrapper.h Thu Mar 11 12:55:50 2004 +0000
+++ b/src/work/marci/graph_wrapper.h Thu Mar 11 14:15:07 2004 +0000
@@ -19,6 +19,12 @@
typedef typename Graph::InEdgeIt InEdgeIt;
//typedef typename Graph::SymEdgeIt SymEdgeIt;
typedef typename Graph::EachEdgeIt EachEdgeIt;
+
+ //TrivGraphWrapper() : graph(0) { }
+ TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
+
+ void setGraph(Graph& _graph) { graph = &_graph; }
+ Graph& getGraph() const { return (*graph); }
template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
template<typename I, typename P> I& getFirst(I& i, const P& p) const {
@@ -66,6 +72,7 @@
NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :
Graph::NodeMap<T>(_G.getGraph(), a) { }
};
+
template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
public:
EdgeMap(const TrivGraphWrapper<Graph>& _G) :
@@ -73,12 +80,6 @@
EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
Graph::EdgeMap<T>(_G.getGraph(), a) { }
};
-
- void setGraph(Graph& _graph) { graph = &_graph; }
- Graph& getGraph() const { return (*graph); }
-
- //TrivGraphWrapper() : graph(0) { }
- TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
};
template<typename Graph>
@@ -97,6 +98,12 @@
typedef typename Graph::InEdgeIt OutEdgeIt;
//typedef typename Graph::SymEdgeIt SymEdgeIt;
typedef typename Graph::EachEdgeIt EachEdgeIt;
+
+ //RevGraphWrapper() : graph(0) { }
+ RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
+
+ void setGraph(Graph& _graph) { graph = &_graph; }
+ Graph& getGraph() const { return (*graph); }
template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
template<typename I, typename P> I& getFirst(I& i, const P& p) const {
@@ -144,6 +151,7 @@
NodeMap(const RevGraphWrapper<Graph>& _G, T a) :
Graph::NodeMap<T>(_G.getGraph(), a) { }
};
+
template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
public:
EdgeMap(const RevGraphWrapper<Graph>& _G) :
@@ -151,12 +159,6 @@
EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :
Graph::EdgeMap<T>(_G.getGraph(), a) { }
};
-
- void setGraph(Graph& _graph) { graph = &_graph; }
- Graph& getGraph() const { return (*graph); }
-
- //RevGraphWrapper() : graph(0) { }
- RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
};
@@ -182,6 +184,12 @@
typedef typename Graph::InEdgeIt GraphInEdgeIt;
//public:
+ //UndirGraphWrapper() : graph(0) { }
+ UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }
+
+ void setGraph(Graph& _graph) { graph = &_graph; }
+ Graph& getGraph() const { return (*graph); }
+
class EdgeIt {
friend class UndirGraphWrapper<Graph>;
bool out_or_in; //true iff out
@@ -196,9 +204,6 @@
class OutEdgeIt : public EdgeIt {
friend class UndirGraphWrapper<Graph>;
- //bool out_or_in; //true iff out
- //GraphOutEdgeIt out;
- //GraphInEdgeIt in;
public:
OutEdgeIt() : EdgeIt() { }
OutEdgeIt(const UndirGraphWrapper& _G, const NodeIt& n) : EdgeIt() {
@@ -287,6 +292,7 @@
NodeMap(const UndirGraphWrapper<Graph>& _G, T a) :
Graph::NodeMap<T>(_G.getGraph(), a) { }
};
+
template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
public:
EdgeMap(const UndirGraphWrapper<Graph>& _G) :
@@ -294,12 +300,6 @@
EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) :
Graph::EdgeMap<T>(_G.getGraph(), a) { }
};
-
- void setGraph(Graph& _graph) { graph = &_graph; }
- Graph& getGraph() const { return (*graph); }
-
- //TrivGraphWrapper() : graph(0) { }
- UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }
};
@@ -386,13 +386,16 @@
FlowMap* flow;
const CapacityMap* capacity;
public:
+
ResGraphWrapper(const Graph& _G, FlowMap& _flow,
const CapacityMap& _capacity) :
G(&_G), flow(&_flow), capacity(&_capacity) { }
// ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) :
// G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }
- void setGraph(Graph& _graph) { graph = &_graph; }
- Graph& getGraph() const { return (*graph); }
+
+ void setGraph(const Graph& _graph) { graph = &_graph; }
+ const Graph& getGraph() const { return (*G); }
+
class EdgeIt;
class OutEdgeIt;
friend class EdgeIt;
@@ -401,94 +404,49 @@
class EdgeIt {
friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
protected:
- //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
- const Graph* G;
- FlowMap* flow;
- const CapacityMap* capacity;
- //OldSymEdgeIt sym;
+ bool out_or_in; //true, iff out
OldOutEdgeIt out;
OldInEdgeIt in;
- bool out_or_in; //true, iff out
public:
EdgeIt() : out_or_in(true) { }
- EdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) :
- G(&_G), flow(&_flow), capacity(&_capacity), out_or_in(true) { }
- //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) { }
- Number free() const {
- if (out_or_in) {
- return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
- } else {
- return (/*resG->*/flow->get(in));
- }
- }
- bool valid() const {
- return out_or_in && out.valid() || in.valid(); }
- void augment(Number a) const {
- if (out_or_in) {
- /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);
- } else {
- /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
- }
- }
- void print() {
- if (out_or_in) {
- std::cout << "out ";
- if (out.valid())
- std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out));
- else
- std::cout << "invalid";
- }
- else {
- std::cout << "in ";
- if (in.valid())
- std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in));
- else
- std::cout << "invalid";
- }
- std::cout << std::endl;
- }
+// bool valid() const {
+// return out_or_in && out.valid() || in.valid(); }
};
- Number free(OldOutEdgeIt out) const {
- return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
- }
- Number free(OldInEdgeIt in) const {
- return (/*resG->*/flow->get(in));
- }
class OutEdgeIt : public EdgeIt {
friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
public:
OutEdgeIt() { }
+ //FIXME
+ OutEdgeIt(const EdgeIt& e) : EdgeIt(e) { }
private:
- OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
- //out=/*resG->*/G->template first<OldOutEdgeIt>(v);
- G->getFirst(out, v);
- while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
+ OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, NodeIt v) : EdgeIt() {
+ resG.G->getFirst(out, v);
+ while( out.valid() && !(resG.free(out)>0) ) { ++out; }
if (!out.valid()) {
out_or_in=0;
- //in=/*resG->*/G->template first<OldInEdgeIt>(v);
- G->getFirst(in, v);
- while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
+ resG.G->getFirst(in, v);
+ while( in.valid() && !(resG.free(in)>0) ) { ++in; }
}
}
- public:
- OutEdgeIt& operator++() {
- if (out_or_in) {
- NodeIt v=/*resG->*/G->aNode(out);
- ++out;
- while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
- if (!out.valid()) {
- out_or_in=0;
- G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
- while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
- }
- } else {
- ++in;
- while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
- }
- return *this;
- }
+// public:
+// OutEdgeIt& operator++() {
+// if (out_or_in) {
+// NodeIt v=/*resG->*/G->aNode(out);
+// ++out;
+// while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
+// if (!out.valid()) {
+// out_or_in=0;
+// G->getFirst(in, v);
+// while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
+// }
+// } else {
+// ++in;
+// while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
+// }
+// return *this;
+// }
};
class EachEdgeIt : public EdgeIt {
@@ -497,67 +455,66 @@
public:
EachEdgeIt() { }
//EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
- EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
- out_or_in=true;
- G->getFirst(v);
- if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
- while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
+ EachEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : EdgeIt() {
+ resG.G->getFirst(v);
+ if (v.valid()) resG.G->getFirst(out, v); else out=OldOutEdgeIt();
+ while (out.valid() && !(resG.free(out)>0) ) { ++out; }
while (v.valid() && !out.valid()) {
++v;
- if (v.valid()) G->getFirst(out, v);
- while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
+ if (v.valid()) resG.G->getFirst(out, v);
+ while (out.valid() && !(resG.free(out)>0) ) { ++out; }
}
if (!out.valid()) {
out_or_in=0;
- G->getFirst(v);
- if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
- while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
+ resG.G->getFirst(v);
+ if (v.valid()) resG.G->getFirst(in, v); else in=OldInEdgeIt();
+ while (in.valid() && !(resG.free(in)>0) ) { ++in; }
while (v.valid() && !in.valid()) {
++v;
- if (v.valid()) G->getFirst(in, v);
- while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
+ if (v.valid()) resG.G->getFirst(in, v);
+ while (in.valid() && !(resG.free(in)>0) ) { ++in; }
}
}
}
- EachEdgeIt& operator++() {
- if (out_or_in) {
- ++out;
- while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
- while (v.valid() && !out.valid()) {
- ++v;
- if (v.valid()) G->getFirst(out, v);
- while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
- }
- if (!out.valid()) {
- out_or_in=0;
- G->getFirst(v);
- if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
- while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
- while (v.valid() && !in.valid()) {
- ++v;
- if (v.valid()) G->getFirst(in, v);
- while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
- }
- }
- } else {
- ++in;
- while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
- while (v.valid() && !in.valid()) {
- ++v;
- if (v.valid()) G->getFirst(in, v);
- while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
- }
- }
- return *this;
- }
+// EachEdgeIt& operator++() {
+// if (out_or_in) {
+// ++out;
+// while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
+// while (v.valid() && !out.valid()) {
+// ++v;
+// if (v.valid()) G->getFirst(out, v);
+// while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
+// }
+// if (!out.valid()) {
+// out_or_in=0;
+// G->getFirst(v);
+// if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
+// while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
+// while (v.valid() && !in.valid()) {
+// ++v;
+// if (v.valid()) G->getFirst(in, v);
+// while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
+// }
+// }
+// } else {
+// ++in;
+// while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
+// while (v.valid() && !in.valid()) {
+// ++v;
+// if (v.valid()) G->getFirst(in, v);
+// while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
+// }
+// }
+// return *this;
+// }
};
- void getFirst(EachNodeIt& v) const { G->getFirst(v); }
- void getFirst(OutEdgeIt& e, NodeIt v) const {
- e=OutEdgeIt(*G, v, *flow, *capacity);
+ EachNodeIt& getFirst(EachNodeIt& v) const { G->getFirst(v); }
+ OutEdgeIt& getFirst(OutEdgeIt& e, NodeIt v) const {
+ e=OutEdgeIt(*this, v);
}
- void getFirst(EachEdgeIt& e) const {
- e=EachEdgeIt(*G, *flow, *capacity);
+ EachEdgeIt& getFirst(EachEdgeIt& e) const {
+ e=EachEdgeIt(*this);
}
EachNodeIt& next(EachNodeIt& n) const { return G->next(n); }
@@ -566,15 +523,15 @@
if (e.out_or_in) {
NodeIt v=G->aNode(e.out);
++(e.out);
- while( G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
+ while( G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
if (!G->valid(e.out)) {
e.out_or_in=0;
- G->getFirst(e.in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
- while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
+ G->getFirst(e.in, v);
+ while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
}
} else {
++(e.in);
- while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
+ while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
}
return e;
}
@@ -582,30 +539,30 @@
EachEdgeIt& next(EachEdgeIt& e) const {
if (e.out_or_in) {
++(e.out);
- while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
+ while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
while (G->valid(e.v) && !G->valid(e.out)) {
++(e.v);
if (G->valid(e.v)) G->getFirst(e.out, e.v);
- while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
+ while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
}
if (!G->valid(e.out)) {
e.out_or_in=0;
G->getFirst(e.v);
if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt();
- while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
+ while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
while (G->valid(e.v) && !G->valid(e.in)) {
++(e.v);
if (G->valid(e.v)) G->getFirst(e.in, e.v);
- while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
+ while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
}
}
} else {
++(e.in);
- while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
+ while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
while (G->valid(e.v) && !G->valid(e.in)) {
++(e.v);
if (G->valid(e.v)) G->getFirst(e.in, e.v);
- while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
+ while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
}
}
return e;
@@ -642,6 +599,28 @@
bool valid(EdgeIt e) const {
return e.out_or_in ? G->valid(e.out) : G->valid(e.in); }
+ void augment(const EdgeIt& e, Number a) const {
+ if (e.out_or_in)
+ flow->set(e.out, flow->get(e.out)+a);
+ else
+ flow->set(e.in, flow->get(e.in)-a);
+ }
+
+ Number free(const EdgeIt& e) const {
+ if (e.out_or_in)
+ return (capacity->get(e.out)-flow->get(e.out));
+ else
+ return (flow->get(e.in));
+ }
+
+ Number free(OldOutEdgeIt out) const {
+ return (capacity->get(out)-flow->get(out));
+ }
+
+ Number free(OldInEdgeIt in) const {
+ return (flow->get(in));
+ }
+
template<typename T> class NodeMap : public Graph::NodeMap<T> {
public:
NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
@@ -679,6 +658,243 @@
return backward_map.get(e.in);
}
};
+ };
+
+ template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
+ class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
+ protected:
+ ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
+ //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
+ public:
+ ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,
+ const CapacityMap& _capacity) :
+ ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),
+ first_out_edges(*this) /*, dist(*this)*/ {
+ for(EachNodeIt n=this->template first<EachNodeIt>(); this->valid(n); this->next(n)) {
+ OutEdgeIt e;
+ ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(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::NodeIt NodeIt;
+ //typedef typename Graph::EachNodeIt EachNodeIt;
+
+ //typedef typename Graph::EdgeIt EdgeIt;
+ //typedef typename Graph::OutEdgeIt OutEdgeIt;
+ //typedef typename Graph::InEdgeIt InEdgeIt;
+ //typedef typename Graph::SymEdgeIt SymEdgeIt;
+ //typedef typename Graph::EachEdgeIt EachEdgeIt;
+
+ typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
+ typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt;
+
+ typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
+ typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
+ //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
+ //typedef typename Graph::SymEdgeIt SymEdgeIt;
+ //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachEdgeIt EachEdgeIt;
+
+ EachNodeIt& getFirst(EachNodeIt& n) const {
+ return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(n);
+ }
+
+ OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {
+ e=first_out_edges.get(n);
+ return e;
+ }
+
+ //ROSSZ template<typename I> I& getFirst(I& i) const { return getFirst(i); }
+ //ROSSZ template<typename I, typename P> I& getFirst(I& i, const P& p) const {
+ // return getFirst(i, p); }
+
+ //template<typename I> I getNext(const I& i) const {
+ // return graph->getNext(i); }
+ //template<typename I> I& next(I &i) const { return graph->next(i); }
+
+ template< typename It > It first() const {
+ It e; getFirst(e); return e; }
+
+ template< typename It > It first(const NodeIt& v) const {
+ It e; getFirst(e, v); return e; }
+
+ //NodeIt head(const EdgeIt& e) const { return graph->head(e); }
+ //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
+
+ //template<typename I> bool valid(const I& i) const
+ // { return graph->valid(i); }
+
+ //int nodeNum() const { return graph->nodeNum(); }
+ //int edgeNum() const { return graph->edgeNum(); }
+
+ //template<typename I> NodeIt aNode(const I& e) const {
+ // return graph->aNode(e); }
+ //template<typename I> NodeIt bNode(const I& e) const {
+ // return graph->bNode(e); }
+
+ //NodeIt addNode() const { return graph->addNode(); }
+ //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
+ // return graph->addEdge(tail, head); }
+
+ //void erase(const OutEdgeIt& e) {
+ // first_out_edge(this->tail(e))=e;
+ //}
+ void erase(const EdgeIt& e) {
+ OutEdgeIt f(e);
+ next(f);
+ first_out_edges.set(this->tail(e), f);
+ }
+ //template<typename I> void erase(const I& i) const { graph->erase(i); }
+
+ //void clear() const { graph->clear(); }
+
+ template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
+ public:
+ NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
+ ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
+ NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
+ ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
+ };
+
+ template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
+ public:
+ EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
+ ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
+ EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
+ ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
+ };
+ };
+
+ template<typename GraphWrapper>
+ class FilterGraphWrapper {
+ };
+
+ template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
+ class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
+
+ //Graph* graph;
+
+ public:
+ //typedef Graph BaseGraph;
+
+ typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
+ typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt;
+
+ typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
+ typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
+ //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
+ //typedef typename Graph::SymEdgeIt SymEdgeIt;
+ typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachEdgeIt EachEdgeIt;
+
+ //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
+
+ public:
+ FilterGraphWrapper(const Graph& _G, FlowMap& _flow,
+ const CapacityMap& _capacity) :
+ ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this) {
+ }
+
+ OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {
+ ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(e, n);
+ while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e))))
+ ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
+ return e;
+ }
+
+ EachNodeIt& next(EachNodeIt& e) const {
+ return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
+ }
+
+ OutEdgeIt& next(OutEdgeIt& e) const {
+ ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
+ while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e))))
+ ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
+ return e;
+ }
+
+ EachNodeIt& getFirst(EachNodeIt& n) const {
+ return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(n);
+ }
+
+ void erase(const EdgeIt& e) {
+ OutEdgeIt f(e);
+ ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
+ while (valid(f) && (dist.get(tail(f))+1!=dist.get(head(f))))
+ ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
+ first_out_edges.set(this->tail(e), f);
+ }
+
+ //TrivGraphWrapper() : graph(0) { }
+ //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
+
+ //void setGraph(Graph& _graph) { graph = &_graph; }
+ //Graph& getGraph() const { return (*graph); }
+
+ //template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
+ //template<typename I, typename P> I& getFirst(I& i, const P& p) const {
+ // return graph->getFirst(i, p); }
+
+ //template<typename I> I getNext(const I& i) const {
+ // return graph->getNext(i); }
+ //template<typename I> I& next(I &i) const { return graph->next(i); }
+
+ template< typename It > It first() const {
+ It e; getFirst(e); return e; }
+
+ template< typename It > It first(const NodeIt& v) const {
+ It e; getFirst(e, v); return e; }
+
+ //NodeIt head(const EdgeIt& e) const { return graph->head(e); }
+ //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
+
+ //template<typename I> bool valid(const I& i) const
+ // { return graph->valid(i); }
+
+ //template<typename I> void setInvalid(const I &i);
+ //{ return graph->setInvalid(i); }
+
+ //int nodeNum() const { return graph->nodeNum(); }
+ //int edgeNum() const { return graph->edgeNum(); }
+
+ //template<typename I> NodeIt aNode(const I& e) const {
+ // return graph->aNode(e); }
+ //template<typename I> NodeIt bNode(const I& e) const {
+ // return graph->bNode(e); }
+
+ //NodeIt addNode() const { return graph->addNode(); }
+ //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
+ // return graph->addEdge(tail, head); }
+
+ //template<typename I> void erase(const I& i) const { graph->erase(i); }
+
+ //void clear() const { graph->clear(); }
+
+ template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
+ public:
+ NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
+ ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
+ NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
+ ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
+ };
+
+ template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
+ public:
+ EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
+ ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
+ EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
+ ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
+ };
+
+ public:
+ ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
};
diff -r 7949a29a334e -r 27fbd1559fb7 src/work/marci/makefile
--- a/src/work/marci/makefile Thu Mar 11 12:55:50 2004 +0000
+++ b/src/work/marci/makefile Thu Mar 11 14:15:07 2004 +0000
@@ -16,8 +16,8 @@
sinclude .depend
edmonds_karp_demo:
- $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -o edmonds_karp_demo edmonds_karp_demo.cc
- $(CXX3) $(CXXFLAGS) -g -pg -O3 -I. -I.. -o edmonds_karp_demo_prof edmonds_karp_demo.cc
+ $(CXX3) $(CXXFLAGS) -g -O3 -I. -I.. -o edmonds_karp_demo edmonds_karp_demo.cc
+ $(CXX3) $(CXXFLAGS) -g -pg -O3 -I. -I.. -o edmonds_karp_demo_prof edmonds_karp_demo_prof.cc
edmonds_karp_demo_alpar:
$(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../alpar -o edmonds_karp_demo_alpar edmonds_karp_demo_alpar.cc
diff -r 7949a29a334e -r 27fbd1559fb7 src/work/marci_graph_demo.cc
--- a/src/work/marci_graph_demo.cc Thu Mar 11 12:55:50 2004 +0000
+++ b/src/work/marci_graph_demo.cc Thu Mar 11 14:15:07 2004 +0000
@@ -236,13 +236,15 @@
std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
}
std::cout<<std::endl;*/
- max_flow_test.run();
+ //max_flow_test.run();
- std::cout << "maximum flow: "<< std::endl;
- for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
- std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
+ //std::cout << "maximum flow: "<< std::endl;
+ while (max_flow_test.augmentOnShortestPath()) {
+ for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
+ std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
+ }
+ std::cout<<std::endl;
}
- std::cout<<std::endl;
std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
}
/*