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