Added this in order to prevent losing it.
1 #ifndef LEMON_PREFLOW_PUSH_HH
2 #define LEMON_PREFLOW_PUSH_HH
8 //#include "pf_hiba.hh"
9 //#include <marci_list_graph.hh>
10 //#include <marci_graph_traits.hh>
12 //#include <reverse_bfs.hh>
18 template <typename Graph, typename T>
22 typedef typename Graph::Node Node;
23 typedef typename Graph::NodeIt NodeIt;
24 typedef typename Graph::Edge Edge;
25 typedef typename Graph::OutEdgeIt OutEdgeIt;
26 typedef typename Graph::InEdgeIt InEdgeIt;
29 //---------------------------------------------
30 //Parameters of the algorithm
31 //---------------------------------------------
32 //Fully examine an active node until excess becomes 0
33 enum node_examination_t {examine_full, examine_to_relabel};
34 //No more implemented yet:, examine_only_one_edge};
35 node_examination_t node_examination;
36 //Which implementation to be used
37 enum implementation_t {impl_fifo, impl_highest_label};
38 //No more implemented yet:};
39 implementation_t implementation;
40 //---------------------------------------------
41 //Parameters of the algorithm
42 //---------------------------------------------
49 typename Graph::EdgeMap<T> &capacity;
52 typename Graph::EdgeMap<T> preflow;
55 //auxiliary variables for computation
56 //The number of the nodes
58 //A nodemap for the level
59 typename Graph::NodeMap<int> level;
60 //A nodemap for the excess
61 typename Graph::NodeMap<T> excess;
63 //Number of nodes on each level
64 vector<int> num_of_nodes_on_level;
66 //For the FIFO implementation
67 list<Node> fifo_nodes;
68 //For 'highest label' implementation
70 //int second_highest_active;
71 vector< list<Node> > active_nodes;
75 //Constructing the object using the graph, source, sink and capacity vector
80 typename Graph::EdgeMap<T> & _capacity)
81 : G(_G), s(_s), t(_t),
84 //Counting the number of nodes
85 //number_of_nodes(count(G.first<EachNodeIt>())),
86 number_of_nodes(G.nodeNum()),
90 // Default constructor: active_nodes()
92 //Simplest parameter settings
93 node_examination = examine_full;//examine_to_relabel;//
94 //Which implementation to be usedexamine_full
95 implementation = impl_highest_label;//impl_fifo;
98 num_of_nodes_on_level.resize(2*number_of_nodes-1);
99 num_of_nodes_on_level.clear();
101 switch(implementation){
102 case impl_highest_label :{
103 active_nodes.clear();
104 active_nodes.resize(2*number_of_nodes-1);
114 //Returns the value of a maximal flow
117 typename Graph::EdgeMap<T> getmaxflow(){
123 //For testing purposes only
124 //Lists the node_properties
125 void write_property_vector(typename Graph::NodeMap<T> a,
126 //node_property_vector<Graph, T> a,
127 char* prop_name="property"){
128 for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) {
129 cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a[i]<<endl;
134 //Modifies the excess of the node and makes sufficient changes
135 void modify_excess(const Node& a ,T v){
136 //T old_value=excess[a];
140 //This private procedure is supposed to modify the preflow on edge j
141 //by value v (which can be positive or negative as well)
142 //and maintain the excess on the target and source
143 //Here we do not check whether this is possible or not
144 void modify_preflow(Edge j, const T& v){
150 //Modifiyng the target
151 modify_excess(G.target(j),v);
153 //Modifiyng the source
154 modify_excess(G.source(j),-v);
158 //Gives the active node to work with
159 //(depending on the implementation to be used)
160 Node get_active_node(){
163 switch(implementation) {
164 case impl_highest_label : {
166 //First need to find the highest label for which there's an active node
167 while( highest_active>=0 && active_nodes[highest_active].empty() ){
171 if( highest_active>=0) {
174 Node a=active_nodes[highest_active].front();
175 active_nodes[highest_active].pop_front();
188 if( ! fifo_nodes.empty() ) {
189 Node a=fifo_nodes.front();
190 fifo_nodes.pop_front();
203 //Puts node 'a' among the active nodes
204 void make_active(const Node& a){
205 //s and t never become active
207 switch(implementation){
208 case impl_highest_label :
209 active_nodes[level[a]].push_back(a);
212 fifo_nodes.push_back(a);
218 //Update highest_active label
219 if (highest_active<level[a]){
220 highest_active=level[a];
225 //Changes the level of node a and make sufficent changes
226 void change_level_to(Node a, int new_value){
227 int seged = level[a];
228 level.set(a,new_value);
229 --num_of_nodes_on_level[seged];
230 ++num_of_nodes_on_level[new_value];
233 //Collection of things useful (or necessary) to do before running
237 //---------------------------------------
238 //Initialize parameters
239 //---------------------------------------
241 //Setting starting preflow, level and excess values to zero
242 //This can be important, if the algorithm is run more then once
243 for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) {
246 for(OutEdgeIt j=G.template first<OutEdgeIt>(i); G.valid(j); G.next(j))
249 num_of_nodes_on_level[0]=number_of_nodes;
251 //---------------------------------------
252 //Initialize parameters
253 //---------------------------------------
256 //------------------------------------
257 //This is the only part that uses BFS
258 //------------------------------------
260 /*Reverse_bfs from t, to find the starting level.*/
262 change_level_to(t,0);
264 std::queue<Node> bfs_queue;
267 while (!bfs_queue.empty()) {
269 Node v=bfs_queue.front();
274 for(G.first(e,v); G.valid(e); G.next(e)) {
276 if ( level[w] == number_of_nodes && w != s ) {
278 //Node first=level_list[l];
279 //if ( G.valid(first) ) left.set(first,w);
280 //right.set(w,first);
282 change_level_to(w, l);
287 change_level_to(s,number_of_nodes);
288 //level.set(s,number_of_nodes);
291 //Setting starting level values using reverse bfs
292 reverse_bfs<Graph> rev_bfs(G,t);
294 //write_property_vector(rev_bfs.dist,"rev_bfs");
295 for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) {
296 change_level_to(i,rev_bfs.dist(i));
297 //level.put(i,rev_bfs.dist.get(i));
300 //------------------------------------
301 //This is the only part that uses BFS
302 //------------------------------------
305 //Starting level of s
306 change_level_to(s,number_of_nodes);
307 //level.put(s,number_of_nodes);
310 //we push as much preflow from s as possible to start with
311 for(OutEdgeIt j=G.template first<OutEdgeIt>(s); G.valid(j); G.next(j)){
312 modify_preflow(j,capacity[j] );
313 make_active(G.target(j));
314 int lev=level[G.target(j)];
315 if(highest_active<lev){
319 //cout<<highest_active<<endl;
323 //If the preflow is less than the capacity on the given edge
324 //then it is an edge in the residual graph
325 bool is_admissible_forward_edge(Edge j, int& new_level){
327 if (capacity[j]>preflow[j]){
328 if(level[G.source(j)]==level[G.target(j)]+1){
332 if (level[G.target(j)] < new_level)
333 new_level=level[G.target(j)];
339 //If the preflow is greater than 0 on the given edge
340 //then the edge reversd is an edge in the residual graph
341 bool is_admissible_backward_edge(Edge j, int& new_level){
344 if(level[G.source(j)]==level[G.target(j)]-1){
349 if (level[G.source(j)] < new_level)
350 new_level=level[G.source(j)];
358 }; //class preflow_push
360 template<typename Graph, typename T>
361 T preflow_push<Graph, T>::run() {
364 //write_property_vector(level,"level");
367 while (a=get_active_node(), G.valid(a)){
369 //cout<<G.id(a)<<endl;
370 //write_property_vector(excess,"excess");
371 //write_property_vector(level,"level");
374 bool go_to_next_node=false;
376 while (!go_to_next_node){
377 //Initial value for the new level for the active node we are dealing with
378 int new_level=2*number_of_nodes;
379 //write_property_vector(excess,"excess");
380 //write_property_vector(level,"level");
381 //cout<<G.id(a)<<endl;
382 //Out edges from node a
384 OutEdgeIt j=G.template first<OutEdgeIt>(a);
385 while (G.valid(j) && e){
387 if (is_admissible_forward_edge(j,new_level)){
388 v=min(e,capacity[j] - preflow[j]);
390 //New node might become active
391 if (excess[G.target(j)]==0){
392 make_active(G.target(j));
401 InEdgeIt j=G.template first<InEdgeIt>(a);
402 while (G.valid(j) && e){
403 if (is_admissible_backward_edge(j,new_level)){
406 //New node might become active
407 if (excess[G.source(j)]==0){
408 make_active(G.source(j));
410 modify_preflow(j,-v);
417 //cout<<new_level<<" e: "<<e<<endl;
418 //cout<<G.id(a)<<" "<<new_level<<endl;
422 go_to_next_node=true;
424 else{//If there is still excess in node a
426 //change_level_to(a,new_level+1);
428 //Level remains empty
429 if (num_of_nodes_on_level[level[a]]==1){
430 change_level_to(a,number_of_nodes);
431 //go_to_next_node=True;
434 change_level_to(a,new_level+1);
441 switch(node_examination){
442 case examine_to_relabel:
445 go_to_next_node = true;
456 maxflow_value = excess[t];
457 return maxflow_value;
463 #endif //PREFLOW_PUSH_HH