1.1 --- a/src/work/athos/preflow_push_wogw.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,463 +0,0 @@
1.4 -#ifndef LEMON_PREFLOW_PUSH_HH
1.5 -#define LEMON_PREFLOW_PUSH_HH
1.6 -
1.7 -//#include <algorithm>
1.8 -#include <list>
1.9 -#include <vector>
1.10 -#include <queue>
1.11 -//#include "pf_hiba.hh"
1.12 -//#include <marci_list_graph.hh>
1.13 -//#include <marci_graph_traits.hh>
1.14 -#include <invalid.h>
1.15 -//#include <reverse_bfs.hh>
1.16 -
1.17 -using namespace std;
1.18 -
1.19 -namespace lemon {
1.20 -
1.21 - template <typename Graph, typename T>
1.22 - class preflow_push {
1.23 -
1.24 - //Useful typedefs
1.25 - typedef typename Graph::Node Node;
1.26 - typedef typename Graph::NodeIt NodeIt;
1.27 - typedef typename Graph::Edge Edge;
1.28 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.29 - typedef typename Graph::InEdgeIt InEdgeIt;
1.30 -
1.31 -
1.32 - //---------------------------------------------
1.33 - //Parameters of the algorithm
1.34 - //---------------------------------------------
1.35 - //Fully examine an active node until excess becomes 0
1.36 - enum node_examination_t {examine_full, examine_to_relabel};
1.37 - //No more implemented yet:, examine_only_one_edge};
1.38 - node_examination_t node_examination;
1.39 - //Which implementation to be used
1.40 - enum implementation_t {impl_fifo, impl_highest_label};
1.41 - //No more implemented yet:};
1.42 - implementation_t implementation;
1.43 - //---------------------------------------------
1.44 - //Parameters of the algorithm
1.45 - //---------------------------------------------
1.46 -
1.47 - private:
1.48 - //input
1.49 - Graph& G;
1.50 - Node s;
1.51 - Node t;
1.52 - typename Graph::EdgeMap<T> &capacity;
1.53 -
1.54 - //output
1.55 - typename Graph::EdgeMap<T> preflow;
1.56 - T maxflow_value;
1.57 -
1.58 - //auxiliary variables for computation
1.59 - //The number of the nodes
1.60 - int number_of_nodes;
1.61 - //A nodemap for the level
1.62 - typename Graph::NodeMap<int> level;
1.63 - //A nodemap for the excess
1.64 - typename Graph::NodeMap<T> excess;
1.65 -
1.66 - //Number of nodes on each level
1.67 - vector<int> num_of_nodes_on_level;
1.68 -
1.69 - //For the FIFO implementation
1.70 - list<Node> fifo_nodes;
1.71 - //For 'highest label' implementation
1.72 - int highest_active;
1.73 - //int second_highest_active;
1.74 - vector< list<Node> > active_nodes;
1.75 -
1.76 - public:
1.77 -
1.78 - //Constructing the object using the graph, source, sink and capacity vector
1.79 - preflow_push(
1.80 - Graph& _G,
1.81 - Node _s,
1.82 - Node _t,
1.83 - typename Graph::EdgeMap<T> & _capacity)
1.84 - : G(_G), s(_s), t(_t),
1.85 - capacity(_capacity),
1.86 - preflow(_G),
1.87 - //Counting the number of nodes
1.88 - //number_of_nodes(count(G.first<EachNodeIt>())),
1.89 - number_of_nodes(G.nodeNum()),
1.90 -
1.91 - level(_G),
1.92 - excess(_G)//,
1.93 - // Default constructor: active_nodes()
1.94 - {
1.95 - //Simplest parameter settings
1.96 - node_examination = examine_full;//examine_to_relabel;//
1.97 - //Which implementation to be usedexamine_full
1.98 - implementation = impl_highest_label;//impl_fifo;
1.99 -
1.100 - //
1.101 - num_of_nodes_on_level.resize(2*number_of_nodes-1);
1.102 - num_of_nodes_on_level.clear();
1.103 -
1.104 - switch(implementation){
1.105 - case impl_highest_label :{
1.106 - active_nodes.clear();
1.107 - active_nodes.resize(2*number_of_nodes-1);
1.108 -
1.109 - break;
1.110 - }
1.111 - default:
1.112 - break;
1.113 - }
1.114 -
1.115 - }
1.116 -
1.117 - //Returns the value of a maximal flow
1.118 - T run();
1.119 -
1.120 - typename Graph::EdgeMap<T> getmaxflow(){
1.121 - return preflow;
1.122 - }
1.123 -
1.124 -
1.125 - private:
1.126 - //For testing purposes only
1.127 - //Lists the node_properties
1.128 - void write_property_vector(typename Graph::NodeMap<T> a,
1.129 - //node_property_vector<Graph, T> a,
1.130 - char* prop_name="property"){
1.131 - for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) {
1.132 - cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a[i]<<endl;
1.133 - }
1.134 - cout<<endl;
1.135 - }
1.136 -
1.137 - //Modifies the excess of the node and makes sufficient changes
1.138 - void modify_excess(const Node& a ,T v){
1.139 - //T old_value=excess[a];
1.140 - excess[a] += v;
1.141 - }
1.142 -
1.143 - //This private procedure is supposed to modify the preflow on edge j
1.144 - //by value v (which can be positive or negative as well)
1.145 - //and maintain the excess on the target and source
1.146 - //Here we do not check whether this is possible or not
1.147 - void modify_preflow(Edge j, const T& v){
1.148 -
1.149 - //Modifiyng the edge
1.150 - preflow[j] += v;
1.151 -
1.152 -
1.153 - //Modifiyng the target
1.154 - modify_excess(G.target(j),v);
1.155 -
1.156 - //Modifiyng the source
1.157 - modify_excess(G.source(j),-v);
1.158 -
1.159 - }
1.160 -
1.161 - //Gives the active node to work with
1.162 - //(depending on the implementation to be used)
1.163 - Node get_active_node(){
1.164 -
1.165 -
1.166 - switch(implementation) {
1.167 - case impl_highest_label : {
1.168 -
1.169 - //First need to find the highest label for which there's an active node
1.170 - while( highest_active>=0 && active_nodes[highest_active].empty() ){
1.171 - --highest_active;
1.172 - }
1.173 -
1.174 - if( highest_active>=0) {
1.175 -
1.176 -
1.177 - Node a=active_nodes[highest_active].front();
1.178 - active_nodes[highest_active].pop_front();
1.179 -
1.180 - return a;
1.181 - }
1.182 - else {
1.183 - return INVALID;
1.184 - }
1.185 -
1.186 - break;
1.187 -
1.188 - }
1.189 - case impl_fifo : {
1.190 -
1.191 - if( ! fifo_nodes.empty() ) {
1.192 - Node a=fifo_nodes.front();
1.193 - fifo_nodes.pop_front();
1.194 - return a;
1.195 - }
1.196 - else {
1.197 - return INVALID;
1.198 - }
1.199 - break;
1.200 - }
1.201 - }
1.202 - //
1.203 - return INVALID;
1.204 - }
1.205 -
1.206 - //Puts node 'a' among the active nodes
1.207 - void make_active(const Node& a){
1.208 - //s and t never become active
1.209 - if (a!=s && a!= t){
1.210 - switch(implementation){
1.211 - case impl_highest_label :
1.212 - active_nodes[level[a]].push_back(a);
1.213 - break;
1.214 - case impl_fifo :
1.215 - fifo_nodes.push_back(a);
1.216 - break;
1.217 - }
1.218 -
1.219 - }
1.220 -
1.221 - //Update highest_active label
1.222 - if (highest_active<level[a]){
1.223 - highest_active=level[a];
1.224 - }
1.225 -
1.226 - }
1.227 -
1.228 - //Changes the level of node a and make sufficent changes
1.229 - void change_level_to(Node a, int new_value){
1.230 - int seged = level[a];
1.231 - level.set(a,new_value);
1.232 - --num_of_nodes_on_level[seged];
1.233 - ++num_of_nodes_on_level[new_value];
1.234 - }
1.235 -
1.236 - //Collection of things useful (or necessary) to do before running
1.237 -
1.238 - void preprocess(){
1.239 -
1.240 - //---------------------------------------
1.241 - //Initialize parameters
1.242 - //---------------------------------------
1.243 -
1.244 - //Setting starting preflow, level and excess values to zero
1.245 - //This can be important, if the algorithm is run more then once
1.246 - for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) {
1.247 - level.set(i,0);
1.248 - excess.set(i,0);
1.249 - for(OutEdgeIt j=G.template first<OutEdgeIt>(i); G.valid(j); G.next(j))
1.250 - preflow.set(j, 0);
1.251 - }
1.252 - num_of_nodes_on_level[0]=number_of_nodes;
1.253 - highest_active=0;
1.254 - //---------------------------------------
1.255 - //Initialize parameters
1.256 - //---------------------------------------
1.257 -
1.258 -
1.259 - //------------------------------------
1.260 - //This is the only part that uses BFS
1.261 - //------------------------------------
1.262 -
1.263 - /*Reverse_bfs from t, to find the starting level.*/
1.264 - //Copyright: Jacint
1.265 - change_level_to(t,0);
1.266 -
1.267 - std::queue<Node> bfs_queue;
1.268 - bfs_queue.push(t);
1.269 -
1.270 - while (!bfs_queue.empty()) {
1.271 -
1.272 - Node v=bfs_queue.front();
1.273 - bfs_queue.pop();
1.274 - int l=level[v]+1;
1.275 -
1.276 - InEdgeIt e;
1.277 - for(G.first(e,v); G.valid(e); G.next(e)) {
1.278 - Node w=G.source(e);
1.279 - if ( level[w] == number_of_nodes && w != s ) {
1.280 - bfs_queue.push(w);
1.281 - //Node first=level_list[l];
1.282 - //if ( G.valid(first) ) left.set(first,w);
1.283 - //right.set(w,first);
1.284 - //level_list[l]=w;
1.285 - change_level_to(w, l);
1.286 - //level.set(w, l);
1.287 - }
1.288 - }
1.289 - }
1.290 - change_level_to(s,number_of_nodes);
1.291 - //level.set(s,number_of_nodes);
1.292 -
1.293 - /*
1.294 - //Setting starting level values using reverse bfs
1.295 - reverse_bfs<Graph> rev_bfs(G,t);
1.296 - rev_bfs.run();
1.297 - //write_property_vector(rev_bfs.dist,"rev_bfs");
1.298 - for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) {
1.299 - change_level_to(i,rev_bfs.dist(i));
1.300 - //level.put(i,rev_bfs.dist.get(i));
1.301 - }
1.302 - */
1.303 - //------------------------------------
1.304 - //This is the only part that uses BFS
1.305 - //------------------------------------
1.306 -
1.307 -
1.308 - //Starting level of s
1.309 - change_level_to(s,number_of_nodes);
1.310 - //level.put(s,number_of_nodes);
1.311 -
1.312 -
1.313 - //we push as much preflow from s as possible to start with
1.314 - for(OutEdgeIt j=G.template first<OutEdgeIt>(s); G.valid(j); G.next(j)){
1.315 - modify_preflow(j,capacity[j] );
1.316 - make_active(G.target(j));
1.317 - int lev=level[G.target(j)];
1.318 - if(highest_active<lev){
1.319 - highest_active=lev;
1.320 - }
1.321 - }
1.322 - //cout<<highest_active<<endl;
1.323 - }
1.324 -
1.325 -
1.326 - //If the preflow is less than the capacity on the given edge
1.327 - //then it is an edge in the residual graph
1.328 - bool is_admissible_forward_edge(Edge j, int& new_level){
1.329 -
1.330 - if (capacity[j]>preflow[j]){
1.331 - if(level[G.source(j)]==level[G.target(j)]+1){
1.332 - return true;
1.333 - }
1.334 - else{
1.335 - if (level[G.target(j)] < new_level)
1.336 - new_level=level[G.target(j)];
1.337 - }
1.338 - }
1.339 - return false;
1.340 - }
1.341 -
1.342 - //If the preflow is greater than 0 on the given edge
1.343 - //then the edge reversd is an edge in the residual graph
1.344 - bool is_admissible_backward_edge(Edge j, int& new_level){
1.345 -
1.346 - if (0<preflow[j]){
1.347 - if(level[G.source(j)]==level[G.target(j)]-1){
1.348 -
1.349 - return true;
1.350 - }
1.351 - else{
1.352 - if (level[G.source(j)] < new_level)
1.353 - new_level=level[G.source(j)];
1.354 - }
1.355 -
1.356 - }
1.357 - return false;
1.358 - }
1.359 -
1.360 -
1.361 - }; //class preflow_push
1.362 -
1.363 - template<typename Graph, typename T>
1.364 - T preflow_push<Graph, T>::run() {
1.365 -
1.366 - preprocess();
1.367 - //write_property_vector(level,"level");
1.368 - T e,v;
1.369 - Node a;
1.370 - while (a=get_active_node(), G.valid(a)){
1.371 -
1.372 - //cout<<G.id(a)<<endl;
1.373 - //write_property_vector(excess,"excess");
1.374 - //write_property_vector(level,"level");
1.375 -
1.376 -
1.377 - bool go_to_next_node=false;
1.378 - e = excess[a];
1.379 - while (!go_to_next_node){
1.380 - //Initial value for the new level for the active node we are dealing with
1.381 - int new_level=2*number_of_nodes;
1.382 - //write_property_vector(excess,"excess");
1.383 - //write_property_vector(level,"level");
1.384 - //cout<<G.id(a)<<endl;
1.385 - //Out edges from node a
1.386 - {
1.387 - OutEdgeIt j=G.template first<OutEdgeIt>(a);
1.388 - while (G.valid(j) && e){
1.389 -
1.390 - if (is_admissible_forward_edge(j,new_level)){
1.391 - v=min(e,capacity[j] - preflow[j]);
1.392 - e -= v;
1.393 - //New node might become active
1.394 - if (excess[G.target(j)]==0){
1.395 - make_active(G.target(j));
1.396 - }
1.397 - modify_preflow(j,v);
1.398 - }
1.399 - G.next(j);
1.400 - }
1.401 - }
1.402 - //In edges to node a
1.403 - {
1.404 - InEdgeIt j=G.template first<InEdgeIt>(a);
1.405 - while (G.valid(j) && e){
1.406 - if (is_admissible_backward_edge(j,new_level)){
1.407 - v=min(e,preflow[j]);
1.408 - e -= v;
1.409 - //New node might become active
1.410 - if (excess[G.source(j)]==0){
1.411 - make_active(G.source(j));
1.412 - }
1.413 - modify_preflow(j,-v);
1.414 - }
1.415 - G.next(j);
1.416 - }
1.417 - }
1.418 -
1.419 - //if (G.id(a)==999)
1.420 - //cout<<new_level<<" e: "<<e<<endl;
1.421 - //cout<<G.id(a)<<" "<<new_level<<endl;
1.422 -
1.423 - if (0==e){
1.424 - //Saturating push
1.425 - go_to_next_node=true;
1.426 - }
1.427 - else{//If there is still excess in node a
1.428 -
1.429 - //change_level_to(a,new_level+1);
1.430 -
1.431 - //Level remains empty
1.432 - if (num_of_nodes_on_level[level[a]]==1){
1.433 - change_level_to(a,number_of_nodes);
1.434 - //go_to_next_node=True;
1.435 - }
1.436 - else{
1.437 - change_level_to(a,new_level+1);
1.438 - //increase_level(a);
1.439 - }
1.440 -
1.441 -
1.442 -
1.443 -
1.444 - switch(node_examination){
1.445 - case examine_to_relabel:
1.446 - make_active(a);
1.447 -
1.448 - go_to_next_node = true;
1.449 - break;
1.450 - default:
1.451 - break;
1.452 - }
1.453 -
1.454 -
1.455 -
1.456 - }//if (0==e)
1.457 - }
1.458 - }
1.459 - maxflow_value = excess[t];
1.460 - return maxflow_value;
1.461 - }//run
1.462 -
1.463 -
1.464 -}//namespace lemon
1.465 -
1.466 -#endif //PREFLOW_PUSH_HH