1.1 --- a/src/work/edmonds_karp.h Wed Mar 17 16:10:33 2004 +0000
1.2 +++ b/src/work/edmonds_karp.h Wed Mar 17 17:04:41 2004 +0000
1.3 @@ -564,10 +564,10 @@
1.4 typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.5 for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.6 if (S->get(s)) {
1.7 - Number f=0;
1.8 + Number u=0;
1.9 for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.10 - f+=flow->get(e);
1.11 - if (f<1) {
1.12 + u+=flow->get(e);
1.13 + if (u<1) {
1.14 res_bfs.pushAndSetReached(s);
1.15 pred.set(s, AugEdge(INVALID));
1.16 }
1.17 @@ -589,10 +589,15 @@
1.18 } else {
1.19 free.set(w, res_graph.free(e));
1.20 }
1.21 - if (T->get(res_graph.head(e))) {
1.22 - n=res_graph.head(e);
1.23 - _augment=true;
1.24 - break;
1.25 + n=res_graph.head(e);
1.26 + if (T->get(n)) {
1.27 + Number u=0;
1.28 + for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
1.29 + u+=flow->get(f);
1.30 + if (u<1) {
1.31 + _augment=true;
1.32 + break;
1.33 + }
1.34 }
1.35 }
1.36
1.37 @@ -620,7 +625,27 @@
1.38 // typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.39 // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
1.40
1.41 -// bfs.pushAndSetReached(s);
1.42 +
1.43 +
1.44 +
1.45 +
1.46 +// //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.47 +// for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.48 +// if (S->get(s)) {
1.49 +// Number u=0;
1.50 +// for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.51 +// u+=flow->get(e);
1.52 +// if (u<1) {
1.53 +// res_bfs.pushAndSetReached(s);
1.54 +// //pred.set(s, AugEdge(INVALID));
1.55 +// }
1.56 +// }
1.57 +// }
1.58 +
1.59 +
1.60 +
1.61 +
1.62 +// //bfs.pushAndSetReached(s);
1.63 // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
1.64 // while ( !bfs.finished() ) {
1.65 // AugOutEdgeIt e=bfs;
1.66 @@ -712,94 +737,132 @@
1.67
1.68 // return _augment;
1.69 // }
1.70 -// bool augmentOnBlockingFlow2() {
1.71 -// bool _augment=false;
1.72 + bool augmentOnBlockingFlow2() {
1.73 + bool _augment=false;
1.74
1.75 -// //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
1.76 -// typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
1.77 -// typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
1.78 -// typedef typename EAugGraph::Edge EAugEdge;
1.79 + //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
1.80 + typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
1.81 + typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
1.82 + typedef typename EAugGraph::Edge EAugEdge;
1.83
1.84 -// EAugGraph res_graph(*G, *flow, *capacity);
1.85 + EAugGraph res_graph(*G, *flow, *capacity);
1.86
1.87 -// //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
1.88 -// BfsIterator4<
1.89 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
1.90 -// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
1.91 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
1.92 + //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
1.93 + BfsIterator4<
1.94 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
1.95 + typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
1.96 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
1.97 +
1.98 +
1.99 + //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.100 + for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.101 + if (S->get(s)) {
1.102 + Number u=0;
1.103 + for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.104 + u+=flow->get(e);
1.105 + if (u<1) {
1.106 + bfs.pushAndSetReached(s);
1.107 + //pred.set(s, AugEdge(INVALID));
1.108 + }
1.109 + }
1.110 + }
1.111 +
1.112
1.113 -// bfs.pushAndSetReached(s);
1.114 + //bfs.pushAndSetReached(s);
1.115
1.116 -// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
1.117 -// NodeMap<int>& dist=res_graph.dist;
1.118 + typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
1.119 + NodeMap<int>& dist=res_graph.dist;
1.120
1.121 -// while ( !bfs.finished() ) {
1.122 -// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
1.123 -// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.124 -// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.125 -// }
1.126 -// ++bfs;
1.127 -// } //computing distances from s in the residual graph
1.128 + while ( !bfs.finished() ) {
1.129 + typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
1.130 + if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.131 + dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.132 + }
1.133 + ++bfs;
1.134 + } //computing distances from s in the residual graph
1.135
1.136 -// bool __augment=true;
1.137 + bool __augment=true;
1.138
1.139 -// while (__augment) {
1.140 + while (__augment) {
1.141
1.142 -// __augment=false;
1.143 -// //computing blocking flow with dfs
1.144 -// typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
1.145 -// DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
1.146 -// dfs(res_graph);
1.147 -// typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
1.148 -// pred.set(s, EAugEdge(INVALID));
1.149 -// //invalid iterators for sources
1.150 + __augment=false;
1.151 + //computing blocking flow with dfs
1.152 + typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
1.153 + DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
1.154 + dfs(res_graph);
1.155 + typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);
1.156 + //pred.set(s, EAugEdge(INVALID));
1.157 + //invalid iterators for sources
1.158
1.159 -// typename EAugGraph::NodeMap<Number> free(res_graph);
1.160 + typename EAugGraph::NodeMap<Number> free(res_graph);
1.161
1.162 -// dfs.pushAndSetReached(s);
1.163 -// while (!dfs.finished()) {
1.164 -// ++dfs;
1.165 -// if (res_graph.valid(EAugOutEdgeIt(dfs))) {
1.166 -// if (dfs.isBNodeNewlyReached()) {
1.167 +
1.168 + //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.169 + for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.170 + if (S->get(s)) {
1.171 + Number u=0;
1.172 + for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.173 + u+=flow->get(e);
1.174 + if (u<1) {
1.175 + dfs.pushAndSetReached(s);
1.176 + //pred.set(s, AugEdge(INVALID));
1.177 + }
1.178 + }
1.179 + }
1.180 +
1.181 +
1.182 +
1.183 + //dfs.pushAndSetReached(s);
1.184 + typename EAugGraph::Node n;
1.185 + while (!dfs.finished()) {
1.186 + ++dfs;
1.187 + if (res_graph.valid(EAugOutEdgeIt(dfs))) {
1.188 + if (dfs.isBNodeNewlyReached()) {
1.189
1.190 -// typename EAugGraph::Node v=res_graph.aNode(dfs);
1.191 -// typename EAugGraph::Node w=res_graph.bNode(dfs);
1.192 + typename EAugGraph::Node v=res_graph.aNode(dfs);
1.193 + typename EAugGraph::Node w=res_graph.bNode(dfs);
1.194
1.195 -// pred.set(w, EAugOutEdgeIt(dfs));
1.196 -// if (res_graph.valid(pred.get(v))) {
1.197 -// free.set(w, std::min(free.get(v), res_graph.free(dfs)));
1.198 -// } else {
1.199 -// free.set(w, res_graph.free(dfs));
1.200 -// }
1.201 -
1.202 -// if (w==t) {
1.203 -// __augment=true;
1.204 -// _augment=true;
1.205 -// break;
1.206 -// }
1.207 -// } else {
1.208 -// res_graph.erase(dfs);
1.209 -// }
1.210 -// }
1.211 + pred.set(w, EAugOutEdgeIt(dfs));
1.212 + if (res_graph.valid(pred.get(v))) {
1.213 + free.set(w, std::min(free.get(v), res_graph.free(dfs)));
1.214 + } else {
1.215 + free.set(w, res_graph.free(dfs));
1.216 + }
1.217 +
1.218 + n=w;
1.219 + if (T->get(w)) {
1.220 + Number u=0;
1.221 + for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
1.222 + u+=flow->get(f);
1.223 + if (u<1) {
1.224 + __augment=true;
1.225 + _augment=true;
1.226 + break;
1.227 + }
1.228 + }
1.229 + } else {
1.230 + res_graph.erase(dfs);
1.231 + }
1.232 + }
1.233
1.234 -// }
1.235 + }
1.236
1.237 -// if (__augment) {
1.238 -// typename EAugGraph::Node n=t;
1.239 -// Number augment_value=free.get(t);
1.240 -// while (res_graph.valid(pred.get(n))) {
1.241 -// EAugEdge e=pred.get(n);
1.242 -// res_graph.augment(e, augment_value);
1.243 -// n=res_graph.tail(e);
1.244 -// if (res_graph.free(e)==0)
1.245 -// res_graph.erase(e);
1.246 -// }
1.247 -// }
1.248 + if (__augment) {
1.249 + // typename EAugGraph::Node n=t;
1.250 + Number augment_value=free.get(n);
1.251 + while (res_graph.valid(pred.get(n))) {
1.252 + EAugEdge e=pred.get(n);
1.253 + res_graph.augment(e, augment_value);
1.254 + n=res_graph.tail(e);
1.255 + if (res_graph.free(e)==0)
1.256 + res_graph.erase(e);
1.257 + }
1.258 + }
1.259
1.260 -// }
1.261 + }
1.262
1.263 -// return _augment;
1.264 -// }
1.265 + return _augment;
1.266 + }
1.267 void run() {
1.268 //int num_of_augmentations=0;
1.269 while (augmentOnShortestPath()) {
2.1 --- a/src/work/marci/max_bipartite_matching_demo.cc Wed Mar 17 16:10:33 2004 +0000
2.2 +++ b/src/work/marci/max_bipartite_matching_demo.cc Wed Mar 17 17:04:41 2004 +0000
2.3 @@ -4,8 +4,11 @@
2.4 #include <vector>
2.5 #include <cstdlib>
2.6
2.7 -//#include <LEDA/graph.h>
2.8 -//#include <leda_graph_wrapper.h>
2.9 +#include <LEDA/graph.h>
2.10 +#include <LEDA/mcb_matching.h>
2.11 +#include <LEDA/list.h>
2.12 +
2.13 +#include <leda_graph_wrapper.h>
2.14 #include <list_graph.h>
2.15 #include <dimacs.h>
2.16 #include <time_measure.h>
2.17 @@ -36,14 +39,15 @@
2.18 using namespace hugo;
2.19
2.20 using std::cout;
2.21 +using std::cin;
2.22 using std::endl;
2.23
2.24 int main() {
2.25 -// leda::graph g;
2.26 -// typedef LedaGraphWrapper<leda::graph> Graph;
2.27 -// Graph G(g);
2.28 - typedef ListGraph Graph;
2.29 - Graph G;
2.30 + leda::graph g;
2.31 + typedef LedaGraphWrapper<leda::graph> Graph;
2.32 + Graph G(g);
2.33 +// typedef ListGraph Graph;
2.34 +// Graph G;
2.35
2.36 typedef Graph::Node Node;
2.37 typedef Graph::NodeIt NodeIt;
2.38 @@ -58,44 +62,53 @@
2.39 std::vector<Node> s_nodes;
2.40 std::vector<Node> t_nodes;
2.41
2.42 - for(int i=0; i<4; ++i) {
2.43 + int a;
2.44 + cout << "number of nodes in the first color class=";
2.45 + cin >> a;
2.46 + int b;
2.47 + cout << "number of nodes in the second color class=";
2.48 + cin >> b;
2.49 + int m;
2.50 + cout << "number of edges=";
2.51 + cin >> m;
2.52 +
2.53 +
2.54 + for(int i=0; i<a; ++i) {
2.55 s_nodes.push_back(G.addNode());
2.56 }
2.57 - for(int i=0; i<4; ++i) {
2.58 + for(int i=0; i<a; ++i) {
2.59 t_nodes.push_back(G.addNode());
2.60 }
2.61 random_init();
2.62 - for(int i=0; i<6; ++i) {
2.63 - G.addEdge(s_nodes[random(4)], t_nodes[random(4)]);
2.64 + for(int i=0; i<m; ++i) {
2.65 + G.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
2.66 }
2.67
2.68 +// G.addEdge(s_nodes[1], t_nodes[5-4]);
2.69 +// G.addEdge(s_nodes[1], t_nodes[5-4]);
2.70 +// G.addEdge(s_nodes[1], t_nodes[4-4]);
2.71 +// G.addEdge(s_nodes[1], t_nodes[4-4]);
2.72 // G.addEdge(s_nodes[2], t_nodes[4-4]);
2.73 -// G.addEdge(s_nodes[2], t_nodes[7-4]);
2.74 -// G.addEdge(s_nodes[2], t_nodes[4-4]);
2.75 -// G.addEdge(s_nodes[3], t_nodes[6-4]);
2.76 -// G.addEdge(s_nodes[3], t_nodes[5-4]);
2.77 -// G.addEdge(s_nodes[3], t_nodes[5-4]);
2.78 +// G.addEdge(s_nodes[3], t_nodes[4-4]);
2.79
2.80
2.81 Graph::NodeMap<bool> s_map(G); //false
2.82 Graph::NodeMap<bool> t_map(G); //false
2.83
2.84 - for(int i=0; i<4; ++i) {
2.85 - s_map.set(s_nodes[i], true);
2.86 - t_map.set(t_nodes[i], true);
2.87 - }
2.88 + for(int i=0; i<a; ++i) s_map.set(s_nodes[i], true);
2.89 + for(int i=0; i<b; ++i) t_map.set(t_nodes[i], true);
2.90
2.91 - cout << "bfs and dfs iterator demo on the directed graph" << endl;
2.92 - for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) {
2.93 - cout << G.id(n) << ": ";
2.94 - cout << "out edges: ";
2.95 - for(OutEdgeIt e=G.first<OutEdgeIt>(n); G.valid(e); G.next(e))
2.96 - cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
2.97 - cout << "in edges: ";
2.98 - for(InEdgeIt e=G.first<InEdgeIt>(n); G.valid(e); G.next(e))
2.99 - cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
2.100 - cout << endl;
2.101 - }
2.102 +// cout << "bfs and dfs iterator demo on the directed graph" << endl;
2.103 +// for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) {
2.104 +// cout << G.id(n) << ": ";
2.105 +// cout << "out edges: ";
2.106 +// for(OutEdgeIt e=G.first<OutEdgeIt>(n); G.valid(e); G.next(e))
2.107 +// cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
2.108 +// cout << "in edges: ";
2.109 +// for(InEdgeIt e=G.first<InEdgeIt>(n); G.valid(e); G.next(e))
2.110 +// cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
2.111 +// cout << endl;
2.112 +// }
2.113
2.114
2.115 {
2.116 @@ -107,31 +120,95 @@
2.117 ts.reset();
2.118
2.119 MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
2.120 - //max_flow_test.augmentWithBlockingFlow<Graph>();
2.121 int i=0;
2.122 while (max_flow_test.augmentOnShortestPath()) {
2.123 -// for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
2.124 -// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
2.125 -// }
2.126 -// std::cout<<std::endl;
2.127 +// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
2.128 +// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
2.129 +// std::cout<<std::endl;
2.130 ++i;
2.131 }
2.132
2.133 - std::cout << "maximum matching: "<< std::endl;
2.134 - for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
2.135 - if (flow.get(e))
2.136 - std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
2.137 - std::cout<<std::endl;
2.138 - std::cout << "edges which are not in this maximum matching: "<< std::endl;
2.139 - for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
2.140 - if (!flow.get(e))
2.141 - std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
2.142 - std::cout<<std::endl;
2.143 +// std::cout << "maximum matching: "<< std::endl;
2.144 +// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
2.145 +// if (flow.get(e))
2.146 +// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
2.147 +// std::cout<<std::endl;
2.148 +// std::cout << "edges which are not in this maximum matching: "<< std::endl;
2.149 +// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
2.150 +// if (!flow.get(e))
2.151 +// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
2.152 +// std::cout<<std::endl;
2.153
2.154 std::cout << "elapsed time: " << ts << std::endl;
2.155 std::cout << "number of augmentation phases: " << i << std::endl;
2.156 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.157 }
2.158 +
2.159 + {
2.160 + std::cout << "on-the-fly max bipartite matching demo (Hopcroft-Karp) on wrapped leda graph..." << std::endl;
2.161 + Graph::EdgeMap<int> flow(G); //0 flow
2.162 + Graph::EdgeMap<int> cap(G, 1);
2.163 +
2.164 + Timer ts;
2.165 + ts.reset();
2.166 +
2.167 + MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
2.168 + int i=0;
2.169 + while (max_flow_test.augmentOnBlockingFlow2()) {
2.170 +// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
2.171 +// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
2.172 +// std::cout<<std::endl;
2.173 + ++i;
2.174 + }
2.175 +
2.176 +// std::cout << "maximum matching: "<< std::endl;
2.177 +// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
2.178 +// if (flow.get(e))
2.179 +// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
2.180 +// std::cout<<std::endl;
2.181 +// std::cout << "edges which are not in this maximum matching: "<< std::endl;
2.182 +// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
2.183 +// if (!flow.get(e))
2.184 +// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
2.185 +// std::cout<<std::endl;
2.186 +
2.187 + std::cout << "elapsed time: " << ts << std::endl;
2.188 + std::cout << "number of augmentation phases: " << i << std::endl;
2.189 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.190 + }
2.191 +
2.192 + {
2.193 + std::cout << "max bipartite matching (LEDA)..." << std::endl;
2.194 + //Graph::EdgeMap<int> flow(G); //0 flow
2.195 + //Graph::EdgeMap<int> cap(G, 1);
2.196 +
2.197 + Timer ts;
2.198 + ts.reset();
2.199 +
2.200 + //MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
2.201 + //int i=0;
2.202 + //while (max_flow_test.augmentOnShortestPath()) { ++i; }
2.203 +
2.204 + leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING(g);
2.205 +
2.206 +
2.207 +// std::cout << "maximum matching: "<< std::endl;
2.208 +// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
2.209 +// if (flow.get(e))
2.210 +// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
2.211 +// std::cout<<std::endl;
2.212 +// std::cout << "edges which are not in this maximum matching: "<< std::endl;
2.213 +// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
2.214 +// if (!flow.get(e))
2.215 +// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
2.216 +// std::cout<<std::endl;
2.217 +
2.218 +
2.219 + std::cout << "elapsed time: " << ts << std::endl;
2.220 + //std::cout << "number of augmentation phases: " << i << std::endl;
2.221 + std::cout << "flow value: "<< l.size() << std::endl;
2.222 + }
2.223 +
2.224
2.225
2.226 return 0;