lemon-0.x: src/work/athos/preflow

     1 #ifndef PREFLOW_PUSH_HH

     2 #define PREFLOW_PUSH_HH

     4 #include <algorithm>

     5 #include <list>

     6 #include <vector>

     7 //#include "pf_hiba.hh"

     8 //#include <marci_list_graph.hh>

     9 //#include <marci_graph_traits.hh>

    11 #include <reverse_bfs.hh>

    13 using namespace std;

    15 namespace hugo {

    17   template <typename graph_type, typename T>

    18   class preflow_push {

    20     //Hasznos typedef-ek

    21     typedef typename graph_type::NodeIt NodeIt;

    22     typedef typename graph_type::EdgeIt EdgeIt;

    23     typedef typename graph_type::EachNodeIt EachNodeIt;

    24     typedef typename graph_type::EachEdgeIt EachEdgeIt;

    25     typedef typename graph_type::OutEdgeIt OutEdgeIt;

    26     typedef typename graph_type::InEdgeIt InEdgeIt;

    27     typedef typename graph_type::SymEdgeIt SymEdgeIt;

    31     /*

    32     typedef graph_traits<graph_type>::node_iterator node_iterator;

    33     typedef graph_traits<graph_type>::EdgeIt EdgeIt;

    34     typedef graph_traits<graph_type>::each_node_iterator each_node_iterator;

    35     typedef graph_traits<graph_type>::each_EdgeIt each_EdgeIt;

    36     typedef graph_traits<graph_type>::out_EdgeIt out_EdgeIt;

    37     typedef graph_traits<graph_type>::InEdgeIt InEdgeIt;

    38     typedef graph_traits<graph_type>::sym_EdgeIt sym_EdgeIt;

    39     */

    41     //---------------------------------------------

    42     //Parameters of the algorithm

    43     //---------------------------------------------

    44     //Fully examine an active node until excess becomes 0

    45     enum node_examination_t {examine_full, examine_to_relabel};

    46     //No more implemented yet:, examine_only_one_edge};

    47     node_examination_t node_examination;

    48     //Which implementation to be used

    49     enum implementation_t {impl_fifo, impl_highest_label};

    50     //No more implemented yet:};

    51     implementation_t implementation;

    52     //---------------------------------------------

    53     //Parameters of the algorithm

    54     //---------------------------------------------

    56   private:

    57     //input

    58     graph_type& G;

    59     NodeIt s;

    60     NodeIt t;

    61     typename graph_type::EdgeMap<T> &capacity;

    62     //typename graph_type::EdgeMap<T>  &capacity;

    63     //output

    64     //typename graph_type::EdgeMap<T>

    65     typename graph_type::EdgeMap<T> preflow;

    66     T maxflow_value;

    68     //auxiliary variables for computation

    69     int number_of_nodes;

    72     typename graph_type::NodeMap<int> level;

    73     typename graph_type::NodeMap<T> excess;

    74     //node_property_vector<graph_type, int> level;

    75     //node_property_vector<graph_type, T> excess;

    77     //Number of nodes on each level

    78     vector<int> num_of_nodes_on_level;

    80     //For the FIFO implementation

    81     list<NodeIt> fifo_nodes;

    82     //For 'highest label' implementation

    83     int highest_active;

    84     //int second_highest_active;

    85     vector< list<NodeIt> > active_nodes;

    87   public:

    89     //Constructing the object using the graph, source, sink and capacity vector

    90     preflow_push(

    91 		      graph_type& _G,

    92 		      NodeIt _s,

    93 		      NodeIt _t,

    94 		      typename graph_type::EdgeMap<T> & _capacity)

    95       : G(_G), s(_s), t(_t),

    96 	capacity(_capacity),

    97 	preflow(_G),

    98 	//Counting the number of nodes

    99 	//number_of_nodes(count(G.first<EachNodeIt>())),

   100 	number_of_nodes(G.nodeNum()),

   102 	level(_G),

   103 	excess(_G)//,

   104         // Default constructor: active_nodes()

   105     {

   106       //Simplest parameter settings

   107       node_examination = examine_full;//examine_to_relabel;//

   108       //Which implementation to be usedexamine_full

   109       implementation = impl_highest_label;//impl_fifo;

   111       //

   112       num_of_nodes_on_level.resize(2*number_of_nodes-1);

   113       num_of_nodes_on_level.clear();

   115       switch(implementation){

   116       case impl_highest_label :{

   117 	active_nodes.resize(2*number_of_nodes-1);

   118 	active_nodes.clear();

   119 	break;

   120       }

   121       default:

   122 	break;

   123       }

   125     }

   127     //Returns the value of a maximal flow

   128     T run();

   130     typename graph_type::EdgeMap<T>  getmaxflow(){

   131       return preflow;

   132     }

   135   private:

   136     //For testing purposes only

   137     //Lists the node_properties

   138     void write_property_vector(typename graph_type::NodeMap<T> a,

   139 			       //node_property_vector<graph_type, T> a,

   140 			       char* prop_name="property"){

   141       for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {

   142 	cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a.get(i)<<endl;

   143       }

   144       cout<<endl;

   145     }

   147     //Modifies the excess of the node and makes sufficient changes

   148     void modify_excess(const NodeIt& a ,T v){

   149 	T old_value=excess.get(a);

   150 	excess.set(a,old_value+v);

   151     }

   153     //This private procedure is supposed to modify the preflow on edge j

   154     //by value v (which can be positive or negative as well)

   155     //and maintain the excess on the head and tail

   156     //Here we do not check whether this is possible or not

   157     void modify_preflow(EdgeIt j, const T& v){

   159       //Auxiliary variable

   160       T old_value;

   162       //Modifiyng the edge

   163       old_value=preflow.get(j);

   164       preflow.set(j,old_value+v);

   167       //Modifiyng the head

   168       modify_excess(G.head(j),v);

   170       //Modifiyng the tail

   171       modify_excess(G.tail(j),-v);

   173     }

   175     //Gives the active node to work with

   176     //(depending on the implementation to be used)

   177     NodeIt get_active_node(){

   180       switch(implementation) {

   181       case impl_highest_label : {

   183 	//First need to find the highest label for which there"s an active node

   184 	while( highest_active>=0 && active_nodes[highest_active].empty() ){

   185 	  --highest_active;

   186 	}

   188 	if( highest_active>=0) {

   191 	  NodeIt a=active_nodes[highest_active].front();

   192 	  active_nodes[highest_active].pop_front();

   194 	  return a;

   195 	}

   196 	else {

   197 	  return NodeIt();

   198 	}

   200 	break;

   202       }

   203       case impl_fifo : {

   205 	if( ! fifo_nodes.empty() ) {

   206 	  NodeIt a=fifo_nodes.front();

   207 	  fifo_nodes.pop_front();

   208 	  return a;

   209 	}

   210 	else {

   211 	  return NodeIt();

   212 	}

   213 	break;

   214       }

   215       }

   216       //

   217       return NodeIt();

   218     }

   220     //Puts node 'a' among the active nodes

   221     void make_active(const NodeIt& a){

   222       //s and t never become active

   223       if (a!=s && a!= t){

   224 	switch(implementation){

   225 	case impl_highest_label :

   226 	  active_nodes[level.get(a)].push_back(a);

   227 	  break;

   228 	case impl_fifo :

   229 	  fifo_nodes.push_back(a);

   230 	  break;

   231 	}

   233       }

   235       //Update highest_active label

   236       if (highest_active<level.get(a)){

   237 	highest_active=level.get(a);

   238       }

   240     }

   242     //Changes the level of node a and make sufficent changes

   243     void change_level_to(NodeIt a, int new_value){

   244       int seged = level.get(a);

   245       level.set(a,new_value);

   246       --num_of_nodes_on_level[seged];

   247       ++num_of_nodes_on_level[new_value];

   248     }

   250     //Collection of things useful (or necessary) to do before running

   252     void preprocess(){

   254       //---------------------------------------

   255       //Initialize parameters

   256       //---------------------------------------

   258       //Setting starting preflow, level and excess values to zero

   259       //This can be important, if the algorithm is run more then once

   260       for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {

   261         level.set(i,0);

   262         excess.set(i,0);

   263 	for(OutEdgeIt j=G.template first<OutEdgeIt>(i); j.valid(); ++j)

   264 	  preflow.set(j, 0);

   265       }

   266       num_of_nodes_on_level[0]=number_of_nodes;

   267       highest_active=0;

   268       //---------------------------------------

   269       //Initialize parameters

   270       //---------------------------------------

   273       //------------------------------------

   274       //This is the only part that uses BFS

   275       //------------------------------------

   276       //Setting starting level values using reverse bfs

   277       reverse_bfs<graph_type> rev_bfs(G,t);

   278       rev_bfs.run();

   279       //write_property_vector(rev_bfs.dist,"rev_bfs");

   280       for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {

   281         change_level_to(i,rev_bfs.dist(i));

   282 	//level.put(i,rev_bfs.dist.get(i));

   283       }

   284       //------------------------------------

   285       //This is the only part that uses BFS

   286       //------------------------------------

   289       //Starting level of s

   290       change_level_to(s,number_of_nodes);

   291       //level.put(s,number_of_nodes);

   294       //we push as much preflow from s as possible to start with

   295       for(OutEdgeIt j=G.template first<OutEdgeIt>(s); j.valid(); ++j){

   296 	modify_preflow(j,capacity.get(j) );

   297 	make_active(G.head(j));

   298 	int lev=level.get(G.head(j));

   299 	if(highest_active<lev){

   300 	  highest_active=lev;

   301 	}

   302       }

   303       //cout<<highest_active<<endl;

   304     }

   307     //If the preflow is less than the capacity on the given edge

   308     //then it is an edge in the residual graph

   309     bool is_admissible_forward_edge(OutEdgeIt j, int& new_level){

   311       if (capacity.get(j)>preflow.get(j)){

   312 	if(level.get(G.tail(j))==level.get(G.head(j))+1){

   313 	  return true;

   314 	}

   315 	else{

   316 	  if (level.get(G.head(j)) < new_level)

   317 	    new_level=level.get(G.head(j));

   318 	}

   319       }

   320       return false;

   321     }

   323     //If the preflow is greater than 0 on the given edge

   324     //then the edge reversd is an edge in the residual graph

   325     bool is_admissible_backward_edge(InEdgeIt j, int& new_level){

   327       if (0<preflow.get(j)){

   328 	if(level.get(G.tail(j))==level.get(G.head(j))-1){

   330 	  return true;

   331 	}

   332 	else{

   333 	  if (level.get(G.tail(j)) < new_level)

   334 	    new_level=level.get(G.tail(j));

   335 	}

   337       }

   338       return false;

   339     }

   342   };  //class preflow_push

   344   template<typename graph_type, typename T>

   345     T preflow_push<graph_type, T>::run() {

   347     preprocess();

   348     //write_property_vector(level,"level");

   349     T e,v;

   350     NodeIt a;

   351     while (a=get_active_node(), a.valid()){

   353       //cout<<G.id(a)<<endl;

   354       //write_property_vector(excess,"excess");

   355       //write_property_vector(level,"level");

   358       bool go_to_next_node=false;

   359       e = excess.get(a);

   360       while (!go_to_next_node){

   361 	//Initial value for the new level for the active node we are dealing with

   362 	int new_level=2*number_of_nodes;

   363 	//write_property_vector(excess,"excess");

   364 	//write_property_vector(level,"level");

   365 	//cout<<G.id(a)<<endl;

   366 	//Out edges from node a

   367 	{

   368 	  OutEdgeIt j=G.template first<OutEdgeIt>(a);

   369 	  while (j.valid() && e){

   371 	    if (is_admissible_forward_edge(j,new_level)){

   372 	      v=min(e,capacity.get(j) - preflow.get(j));

   373 	      e -= v;

   374 	      //New node might become active

   375 	      if (excess.get(G.head(j))==0){

   376 		make_active(G.head(j));

   377 	      }

   378 	      modify_preflow(j,v);

   379 	    }

   380 	    ++j;

   381 	  }

   382 	}

   383 	//In edges to node a

   384 	{

   385 	  InEdgeIt j=G.template first<InEdgeIt>(a);

   386 	  while (j.valid() && e){

   387 	    if (is_admissible_backward_edge(j,new_level)){

   388 	      v=min(e,preflow.get(j));

   389 	      e -= v;

   390 	      //New node might become active

   391 	      if (excess.get(G.tail(j))==0){

   392 		make_active(G.tail(j));

   393 	      }

   394 	      modify_preflow(j,-v);

   395 	    }

   396 	    ++j;

   397 	  }

   398 	}

   400 	//if (G.id(a)==999)

   401 	//cout<<new_level<<" e: "<<e<<endl;

   402 	//cout<<G.id(a)<<" "<<new_level<<endl;

   404 	if (0==e){

   405 	  //Saturating push

   406 	  go_to_next_node=true;

   407 	}

   408 	else{//If there is still excess in node a

   410 	  //change_level_to(a,new_level+1);

   412 	  //Level remains empty

   413 	  if (num_of_nodes_on_level[level.get(a)]==1){

   414 	    change_level_to(a,number_of_nodes);

   415 	    //go_to_next_node=True;

   416 	  }

   417 	  else{

   418 	    change_level_to(a,new_level+1);

   419 	    //increase_level(a);

   420 	  }

   425 	  switch(node_examination){

   426 	  case examine_to_relabel:

   427 	    make_active(a);

   429 	    go_to_next_node = true;

   430 	    break;

   431 	  default:

   432 	    break;

   433 	  }

   437 	}//if (0==e)

   438       }

   439     }

   440     maxflow_value = excess.get(t);

   441     return maxflow_value;

   442   }//run

   445 }//namespace hugo

   447 #endif //PREFLOW_PUSH_HH

author	alpar
	Mon, 05 Apr 2004 13:55:55 +0000
changeset 296	09d6d48815a5
parent 105	a3c73e9b9b2e
child 331	f5461f8bc59b
permissions	-rw-r--r--