athos@331: #ifndef HUGO_PREFLOW_PUSH_HH athos@331: #define HUGO_PREFLOW_PUSH_HH athos@36: athos@331: //#include <algorithm> athos@36: #include <list> athos@36: #include <vector> athos@331: #include <queue> athos@36: //#include "pf_hiba.hh" athos@36: //#include <marci_list_graph.hh> athos@77: //#include <marci_graph_traits.hh> athos@331: #include <invalid.h> athos@331: #include <graph_wrapper.h> athos@331: //#include <reverse_bfs.hh> athos@36: athos@36: using namespace std; athos@36: alpar@105: namespace hugo { athos@36: athos@331: template <typename Graph, typename T> athos@36: class preflow_push { athos@36: athos@331: //Useful typedefs athos@331: typedef typename Graph::Node Node; athos@331: typedef typename Graph::NodeIt NodeIt; athos@331: typedef typename Graph::Edge Edge; athos@331: typedef typename Graph::OutEdgeIt OutEdgeIt; athos@331: typedef typename Graph::InEdgeIt InEdgeIt; athos@505: typedef typename Graph::EdgeMap<T> CapacityType; athos@505: athos@505: typedef ResGraphWrapper<const Graph,int,CapacityType,CapacityType> ResGraphType; athos@77: athos@77: athos@36: //--------------------------------------------- athos@36: //Parameters of the algorithm athos@36: //--------------------------------------------- athos@36: //Fully examine an active node until excess becomes 0 athos@36: enum node_examination_t {examine_full, examine_to_relabel}; athos@36: //No more implemented yet:, examine_only_one_edge}; athos@36: node_examination_t node_examination; athos@36: //Which implementation to be used athos@36: enum implementation_t {impl_fifo, impl_highest_label}; athos@36: //No more implemented yet:}; athos@36: implementation_t implementation; athos@36: //--------------------------------------------- athos@36: //Parameters of the algorithm athos@36: //--------------------------------------------- athos@36: athos@36: private: athos@36: //input athos@331: Graph& G; athos@331: Node s; athos@331: Node t; athos@505: CapacityType &capacity; athos@331: athos@36: //output athos@505: CapacityType preflow; athos@36: T maxflow_value; athos@36: athos@36: //auxiliary variables for computation athos@331: //The number of the nodes athos@36: int number_of_nodes; athos@331: //A nodemap for the level athos@331: typename Graph::NodeMap<int> level; athos@331: //A nodemap for the excess athos@331: typename Graph::NodeMap<T> excess; athos@36: athos@36: //Number of nodes on each level athos@36: vector<int> num_of_nodes_on_level; athos@36: athos@36: //For the FIFO implementation athos@331: list<Node> fifo_nodes; athos@36: //For 'highest label' implementation athos@36: int highest_active; athos@36: //int second_highest_active; athos@331: vector< list<Node> > active_nodes; athos@36: athos@36: public: athos@36: athos@36: //Constructing the object using the graph, source, sink and capacity vector athos@36: preflow_push( athos@331: Graph& _G, athos@331: Node _s, athos@331: Node _t, athos@331: typename Graph::EdgeMap<T> & _capacity) athos@36: : G(_G), s(_s), t(_t), athos@36: capacity(_capacity), athos@36: preflow(_G), athos@36: //Counting the number of nodes athos@77: //number_of_nodes(count(G.first<EachNodeIt>())), athos@77: number_of_nodes(G.nodeNum()), athos@77: athos@36: level(_G), athos@36: excess(_G)//, athos@36: // Default constructor: active_nodes() athos@36: { athos@36: //Simplest parameter settings athos@36: node_examination = examine_full;//examine_to_relabel;// athos@36: //Which implementation to be usedexamine_full athos@36: implementation = impl_highest_label;//impl_fifo; athos@36: athos@36: // athos@36: num_of_nodes_on_level.resize(2*number_of_nodes-1); athos@36: num_of_nodes_on_level.clear(); athos@36: athos@36: switch(implementation){ athos@36: case impl_highest_label :{ athos@331: active_nodes.clear(); athos@36: active_nodes.resize(2*number_of_nodes-1); athos@331: athos@36: break; athos@36: } athos@36: default: athos@36: break; athos@36: } athos@36: athos@36: } athos@36: athos@36: //Returns the value of a maximal flow athos@36: T run(); athos@36: athos@331: typename Graph::EdgeMap<T> getmaxflow(){ athos@36: return preflow; athos@36: } athos@36: athos@36: athos@36: private: athos@36: //For testing purposes only athos@36: //Lists the node_properties athos@331: void write_property_vector(typename Graph::NodeMap<T> a, athos@331: //node_property_vector<Graph, T> a, athos@36: char* prop_name="property"){ athos@331: for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) { athos@331: cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a[i]<<endl; athos@36: } athos@36: cout<<endl; athos@36: } athos@505: /* athos@36: //Modifies the excess of the node and makes sufficient changes athos@331: void modify_excess(const Node& a ,T v){ athos@331: //T old_value=excess[a]; athos@331: excess[a] += v; athos@36: } athos@36: athos@36: //This private procedure is supposed to modify the preflow on edge j athos@36: //by value v (which can be positive or negative as well) athos@36: //and maintain the excess on the head and tail athos@36: //Here we do not check whether this is possible or not athos@331: void modify_preflow(Edge j, const T& v){ athos@36: athos@36: //Modifiyng the edge athos@331: preflow[j] += v; athos@36: athos@36: athos@36: //Modifiyng the head athos@36: modify_excess(G.head(j),v); athos@36: athos@36: //Modifiyng the tail athos@36: modify_excess(G.tail(j),-v); athos@36: athos@36: } athos@505: */ athos@36: //Gives the active node to work with athos@36: //(depending on the implementation to be used) athos@331: Node get_active_node(){ athos@119: athos@36: athos@36: switch(implementation) { athos@36: case impl_highest_label : { athos@36: athos@331: //First need to find the highest label for which there's an active node athos@36: while( highest_active>=0 && active_nodes[highest_active].empty() ){ athos@36: --highest_active; athos@36: } athos@36: athos@36: if( highest_active>=0) { athos@119: athos@119: athos@331: Node a=active_nodes[highest_active].front(); athos@36: active_nodes[highest_active].pop_front(); athos@119: athos@36: return a; athos@36: } athos@36: else { athos@331: return INVALID; athos@36: } athos@36: athos@36: break; athos@36: athos@36: } athos@36: case impl_fifo : { athos@36: athos@36: if( ! fifo_nodes.empty() ) { athos@331: Node a=fifo_nodes.front(); athos@36: fifo_nodes.pop_front(); athos@36: return a; athos@36: } athos@36: else { athos@331: return INVALID; athos@36: } athos@36: break; athos@36: } athos@36: } athos@36: // athos@331: return INVALID; athos@36: } athos@36: athos@36: //Puts node 'a' among the active nodes athos@331: void make_active(const Node& a){ athos@36: //s and t never become active athos@36: if (a!=s && a!= t){ athos@36: switch(implementation){ athos@36: case impl_highest_label : athos@331: active_nodes[level[a]].push_back(a); athos@36: break; athos@36: case impl_fifo : athos@36: fifo_nodes.push_back(a); athos@36: break; athos@36: } athos@36: athos@36: } athos@36: athos@36: //Update highest_active label athos@331: if (highest_active<level[a]){ athos@331: highest_active=level[a]; athos@36: } athos@36: athos@36: } athos@36: athos@36: //Changes the level of node a and make sufficent changes athos@331: void change_level_to(Node a, int new_value){ athos@331: int seged = level[a]; athos@77: level.set(a,new_value); athos@36: --num_of_nodes_on_level[seged]; athos@36: ++num_of_nodes_on_level[new_value]; athos@36: } athos@36: athos@36: //Collection of things useful (or necessary) to do before running athos@77: athos@36: void preprocess(){ athos@36: athos@36: //--------------------------------------- athos@36: //Initialize parameters athos@36: //--------------------------------------- athos@36: athos@36: //Setting starting preflow, level and excess values to zero athos@36: //This can be important, if the algorithm is run more then once athos@331: for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) { athos@77: level.set(i,0); athos@77: excess.set(i,0); athos@331: for(OutEdgeIt j=G.template first<OutEdgeIt>(i); G.valid(j); G.next(j)) athos@77: preflow.set(j, 0); athos@36: } athos@36: num_of_nodes_on_level[0]=number_of_nodes; athos@36: highest_active=0; athos@36: //--------------------------------------- athos@36: //Initialize parameters athos@36: //--------------------------------------- athos@36: athos@36: athos@36: //------------------------------------ athos@36: //This is the only part that uses BFS athos@36: //------------------------------------ athos@331: athos@331: /*Reverse_bfs from t, to find the starting level.*/ athos@331: //Copyright: Jacint athos@331: change_level_to(t,0); athos@331: athos@331: std::queue<Node> bfs_queue; athos@331: bfs_queue.push(t); athos@331: athos@331: while (!bfs_queue.empty()) { athos@331: athos@331: Node v=bfs_queue.front(); athos@331: bfs_queue.pop(); athos@331: int l=level[v]+1; athos@331: athos@331: InEdgeIt e; athos@331: for(G.first(e,v); G.valid(e); G.next(e)) { athos@331: Node w=G.tail(e); athos@331: if ( level[w] == number_of_nodes && w != s ) { athos@331: bfs_queue.push(w); athos@331: //Node first=level_list[l]; athos@331: //if ( G.valid(first) ) left.set(first,w); athos@331: //right.set(w,first); athos@331: //level_list[l]=w; athos@331: change_level_to(w, l); athos@331: //level.set(w, l); athos@331: } athos@331: } athos@331: } athos@331: change_level_to(s,number_of_nodes); athos@331: //level.set(s,number_of_nodes); athos@331: athos@331: /* athos@36: //Setting starting level values using reverse bfs athos@331: reverse_bfs<Graph> rev_bfs(G,t); athos@36: rev_bfs.run(); athos@36: //write_property_vector(rev_bfs.dist,"rev_bfs"); athos@331: for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) { athos@36: change_level_to(i,rev_bfs.dist(i)); athos@36: //level.put(i,rev_bfs.dist.get(i)); athos@36: } athos@331: */ athos@36: //------------------------------------ athos@36: //This is the only part that uses BFS athos@36: //------------------------------------ athos@36: athos@36: athos@36: //Starting level of s athos@36: change_level_to(s,number_of_nodes); athos@36: //level.put(s,number_of_nodes); athos@36: athos@36: athos@36: //we push as much preflow from s as possible to start with athos@331: for(OutEdgeIt j=G.template first<OutEdgeIt>(s); G.valid(j); G.next(j)){ athos@331: modify_preflow(j,capacity[j] ); athos@36: make_active(G.head(j)); athos@331: int lev=level[G.head(j)]; athos@36: if(highest_active<lev){ athos@36: highest_active=lev; athos@36: } athos@36: } athos@36: //cout<<highest_active<<endl; athos@36: } athos@36: athos@36: athos@36: //If the preflow is less than the capacity on the given edge athos@36: //then it is an edge in the residual graph athos@331: bool is_admissible_forward_edge(Edge j, int& new_level){ athos@119: athos@331: if (capacity[j]>preflow[j]){ athos@331: if(level[G.tail(j)]==level[G.head(j)]+1){ athos@36: return true; athos@36: } athos@36: else{ athos@331: if (level[G.head(j)] < new_level) athos@331: new_level=level[G.head(j)]; athos@36: } athos@36: } athos@36: return false; athos@36: } athos@36: athos@36: //If the preflow is greater than 0 on the given edge athos@36: //then the edge reversd is an edge in the residual graph athos@331: bool is_admissible_backward_edge(Edge j, int& new_level){ athos@119: athos@331: if (0<preflow[j]){ athos@331: if(level[G.tail(j)]==level[G.head(j)]-1){ athos@119: athos@36: return true; athos@36: } athos@36: else{ athos@331: if (level[G.tail(j)] < new_level) athos@331: new_level=level[G.tail(j)]; athos@36: } athos@36: athos@36: } athos@36: return false; athos@36: } athos@36: athos@36: athos@36: }; //class preflow_push athos@36: athos@331: template<typename Graph, typename T> athos@331: T preflow_push<Graph, T>::run() { athos@331: athos@331: //We need a residual graph athos@331: ResGraphType res_graph(G, preflow, capacity); athos@36: athos@36: preprocess(); athos@119: //write_property_vector(level,"level"); athos@36: T e,v; athos@331: Node a; athos@331: while (a=get_active_node(), G.valid(a)){ athos@119: athos@331: bool go_to_next_node=false; athos@331: e = excess[a]; athos@331: while (!go_to_next_node){ athos@36: athos@77: //Initial value for the new level for the active node we are dealing with athos@77: int new_level=2*number_of_nodes; athos@331: athos@331: athos@36: //Out edges from node a athos@36: { athos@505: ResGraphType::OutEdgeIt j=res_graph.first(j,a); athos@505: while (res_graph.valid(j) && e){ athos@505: if (is_admissible_forward_edge(j,new_level)){ athos@505: v=min(e,res_graph.resCap(j)); athos@505: e -= v; athos@505: //New node might become active athos@505: if (excess[res_graph.head(j)]==0){ athos@505: make_active(res_graph.head(j)); athos@505: } athos@505: res_graph.augment(j,v); athos@505: excess[res_graph.tail(j)] -= v; athos@505: excess[res_graph.head(j)] += v; athos@505: } athos@505: res_graph.next(j); athos@505: } athos@505: } athos@505: athos@505: /* athos@505: //Out edges from node a athos@505: { athos@77: OutEdgeIt j=G.template first<OutEdgeIt>(a); athos@331: while (G.valid(j) && e){ athos@36: athos@36: if (is_admissible_forward_edge(j,new_level)){ athos@331: v=min(e,capacity[j] - preflow[j]); athos@36: e -= v; athos@36: //New node might become active athos@331: if (excess[G.head(j)]==0){ athos@36: make_active(G.head(j)); athos@36: } athos@36: modify_preflow(j,v); athos@36: } athos@331: G.next(j); athos@36: } athos@36: } athos@36: //In edges to node a athos@36: { athos@77: InEdgeIt j=G.template first<InEdgeIt>(a); athos@331: while (G.valid(j) && e){ athos@36: if (is_admissible_backward_edge(j,new_level)){ athos@331: v=min(e,preflow[j]); athos@36: e -= v; athos@36: //New node might become active athos@331: if (excess[G.tail(j)]==0){ athos@36: make_active(G.tail(j)); athos@36: } athos@36: modify_preflow(j,-v); athos@36: } athos@331: G.next(j); athos@36: } athos@36: } athos@505: */ athos@36: athos@119: //if (G.id(a)==999) athos@119: //cout<<new_level<<" e: "<<e<<endl; athos@36: //cout<<G.id(a)<<" "<<new_level<<endl; athos@36: athos@36: if (0==e){ athos@36: //Saturating push athos@36: go_to_next_node=true; athos@36: } athos@36: else{//If there is still excess in node a athos@77: athos@77: //change_level_to(a,new_level+1); athos@77: athos@36: //Level remains empty athos@331: if (num_of_nodes_on_level[level[a]]==1){ athos@36: change_level_to(a,number_of_nodes); athos@36: //go_to_next_node=True; athos@36: } athos@36: else{ athos@36: change_level_to(a,new_level+1); athos@36: //increase_level(a); athos@36: } athos@77: athos@36: athos@36: athos@36: athos@36: switch(node_examination){ athos@36: case examine_to_relabel: athos@36: make_active(a); athos@36: athos@36: go_to_next_node = true; athos@36: break; athos@36: default: athos@36: break; athos@36: } athos@36: athos@36: athos@36: athos@36: }//if (0==e) athos@36: } athos@36: } athos@331: maxflow_value = excess[t]; athos@36: return maxflow_value; athos@36: }//run athos@36: athos@36: alpar@105: }//namespace hugo athos@36: athos@36: #endif //PREFLOW_PUSH_HH