equal
deleted
inserted
replaced
23 typedef typename Graph::Node Node; |
23 typedef typename Graph::Node Node; |
24 typedef typename Graph::NodeIt NodeIt; |
24 typedef typename Graph::NodeIt NodeIt; |
25 typedef typename Graph::Edge Edge; |
25 typedef typename Graph::Edge Edge; |
26 typedef typename Graph::OutEdgeIt OutEdgeIt; |
26 typedef typename Graph::OutEdgeIt OutEdgeIt; |
27 typedef typename Graph::InEdgeIt InEdgeIt; |
27 typedef typename Graph::InEdgeIt InEdgeIt; |
|
28 typedef typename Graph::EdgeMap<T> CapacityType; |
|
29 |
|
30 typedef ResGraphWrapper<const Graph,int,CapacityType,CapacityType> ResGraphType; |
28 |
31 |
29 |
32 |
30 //--------------------------------------------- |
33 //--------------------------------------------- |
31 //Parameters of the algorithm |
34 //Parameters of the algorithm |
32 //--------------------------------------------- |
35 //--------------------------------------------- |
45 private: |
48 private: |
46 //input |
49 //input |
47 Graph& G; |
50 Graph& G; |
48 Node s; |
51 Node s; |
49 Node t; |
52 Node t; |
50 typename Graph::EdgeMap<T> &capacity; |
53 CapacityType &capacity; |
51 |
54 |
52 //output |
55 //output |
53 typename Graph::EdgeMap<T> preflow; |
56 CapacityType preflow; |
54 T maxflow_value; |
57 T maxflow_value; |
55 |
58 |
56 //auxiliary variables for computation |
59 //auxiliary variables for computation |
57 //The number of the nodes |
60 //The number of the nodes |
58 int number_of_nodes; |
61 int number_of_nodes; |
129 for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) { |
132 for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) { |
130 cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a[i]<<endl; |
133 cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a[i]<<endl; |
131 } |
134 } |
132 cout<<endl; |
135 cout<<endl; |
133 } |
136 } |
134 |
137 /* |
135 //Modifies the excess of the node and makes sufficient changes |
138 //Modifies the excess of the node and makes sufficient changes |
136 void modify_excess(const Node& a ,T v){ |
139 void modify_excess(const Node& a ,T v){ |
137 //T old_value=excess[a]; |
140 //T old_value=excess[a]; |
138 excess[a] += v; |
141 excess[a] += v; |
139 } |
142 } |
153 |
156 |
154 //Modifiyng the tail |
157 //Modifiyng the tail |
155 modify_excess(G.tail(j),-v); |
158 modify_excess(G.tail(j),-v); |
156 |
159 |
157 } |
160 } |
158 |
161 */ |
159 //Gives the active node to work with |
162 //Gives the active node to work with |
160 //(depending on the implementation to be used) |
163 //(depending on the implementation to be used) |
161 Node get_active_node(){ |
164 Node get_active_node(){ |
162 |
165 |
163 |
166 |
376 |
379 |
377 //Initial value for the new level for the active node we are dealing with |
380 //Initial value for the new level for the active node we are dealing with |
378 int new_level=2*number_of_nodes; |
381 int new_level=2*number_of_nodes; |
379 |
382 |
380 |
383 |
|
384 //Out edges from node a |
|
385 { |
|
386 ResGraphType::OutEdgeIt j=res_graph.first(j,a); |
|
387 while (res_graph.valid(j) && e){ |
|
388 if (is_admissible_forward_edge(j,new_level)){ |
|
389 v=min(e,res_graph.resCap(j)); |
|
390 e -= v; |
|
391 //New node might become active |
|
392 if (excess[res_graph.head(j)]==0){ |
|
393 make_active(res_graph.head(j)); |
|
394 } |
|
395 res_graph.augment(j,v); |
|
396 excess[res_graph.tail(j)] -= v; |
|
397 excess[res_graph.head(j)] += v; |
|
398 } |
|
399 res_graph.next(j); |
|
400 } |
|
401 } |
|
402 |
|
403 /* |
381 //Out edges from node a |
404 //Out edges from node a |
382 { |
405 { |
383 OutEdgeIt j=G.template first<OutEdgeIt>(a); |
406 OutEdgeIt j=G.template first<OutEdgeIt>(a); |
384 while (G.valid(j) && e){ |
407 while (G.valid(j) && e){ |
385 |
408 |
409 modify_preflow(j,-v); |
432 modify_preflow(j,-v); |
410 } |
433 } |
411 G.next(j); |
434 G.next(j); |
412 } |
435 } |
413 } |
436 } |
|
437 */ |
414 |
438 |
415 //if (G.id(a)==999) |
439 //if (G.id(a)==999) |
416 //cout<<new_level<<" e: "<<e<<endl; |
440 //cout<<new_level<<" e: "<<e<<endl; |
417 //cout<<G.id(a)<<" "<<new_level<<endl; |
441 //cout<<G.id(a)<<" "<<new_level<<endl; |
418 |
442 |