athos@36: #ifndef PREFLOW_PUSH_HH
athos@36: #define PREFLOW_PUSH_HH
athos@36:
athos@36: #include <algorithm>
athos@36: #include <list>
athos@36: #include <vector>
athos@36: //#include "pf_hiba.hh"
athos@36: //#include <marci_list_graph.hh>
athos@77: //#include <marci_graph_traits.hh>
athos@77:
athos@119: #include <reverse_bfs.hh>
athos@36:
athos@36: using namespace std;
athos@36:
alpar@105: namespace hugo {
athos@36:
athos@36: template <typename graph_type, typename T>
athos@36: class preflow_push {
athos@36:
athos@36: //Hasznos typedef-ek
athos@77: typedef typename graph_type::NodeIt NodeIt;
athos@77: typedef typename graph_type::EdgeIt EdgeIt;
athos@77: typedef typename graph_type::EachNodeIt EachNodeIt;
athos@77: typedef typename graph_type::EachEdgeIt EachEdgeIt;
athos@77: typedef typename graph_type::OutEdgeIt OutEdgeIt;
athos@77: typedef typename graph_type::InEdgeIt InEdgeIt;
athos@77: typedef typename graph_type::SymEdgeIt SymEdgeIt;
athos@77:
athos@77:
athos@77:
athos@77: /*
athos@36: typedef graph_traits<graph_type>::node_iterator node_iterator;
athos@77: typedef graph_traits<graph_type>::EdgeIt EdgeIt;
athos@36: typedef graph_traits<graph_type>::each_node_iterator each_node_iterator;
athos@77: typedef graph_traits<graph_type>::each_EdgeIt each_EdgeIt;
athos@77: typedef graph_traits<graph_type>::out_EdgeIt out_EdgeIt;
athos@77: typedef graph_traits<graph_type>::InEdgeIt InEdgeIt;
athos@77: typedef graph_traits<graph_type>::sym_EdgeIt sym_EdgeIt;
athos@77: */
athos@36:
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@36: graph_type& G;
athos@77: NodeIt s;
athos@77: NodeIt t;
athos@77: typename graph_type::EdgeMap<T> &capacity;
athos@77: //typename graph_type::EdgeMap<T> &capacity;
athos@36: //output
athos@77: //typename graph_type::EdgeMap<T>
athos@77: typename graph_type::EdgeMap<T> preflow;
athos@36: T maxflow_value;
athos@36:
athos@36: //auxiliary variables for computation
athos@36: int number_of_nodes;
athos@77:
athos@77:
athos@77: typename graph_type::NodeMap<int> level;
athos@77: typename graph_type::NodeMap<T> excess;
athos@77: //node_property_vector<graph_type, int> level;
athos@77: //node_property_vector<graph_type, 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@77: list<NodeIt> fifo_nodes;
athos@36: //For 'highest label' implementation
athos@36: int highest_active;
athos@36: //int second_highest_active;
athos@77: vector< list<NodeIt> > 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@36: graph_type& _G,
athos@77: NodeIt _s,
athos@77: NodeIt _t,
athos@77: typename graph_type::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@36: active_nodes.resize(2*number_of_nodes-1);
athos@36: active_nodes.clear();
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@77: typename graph_type::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@77: void write_property_vector(typename graph_type::NodeMap<T> a,
athos@77: //node_property_vector<graph_type, T> a,
athos@36: char* prop_name="property"){
athos@77: for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
athos@36: cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a.get(i)<<endl;
athos@36: }
athos@36: cout<<endl;
athos@36: }
athos@36:
athos@36: //Modifies the excess of the node and makes sufficient changes
athos@77: void modify_excess(const NodeIt& a ,T v){
athos@36: T old_value=excess.get(a);
athos@77: excess.set(a,old_value+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@77: void modify_preflow(EdgeIt j, const T& v){
athos@36:
athos@36: //Auxiliary variable
athos@36: T old_value;
athos@36:
athos@36: //Modifiyng the edge
athos@36: old_value=preflow.get(j);
athos@77: preflow.set(j,old_value+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@36:
athos@36: //Gives the active node to work with
athos@36: //(depending on the implementation to be used)
athos@77: NodeIt get_active_node(){
athos@119:
athos@36:
athos@36: switch(implementation) {
athos@36: case impl_highest_label : {
athos@36:
athos@36: //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@77: NodeIt 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@77: return NodeIt();
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@77: NodeIt a=fifo_nodes.front();
athos@36: fifo_nodes.pop_front();
athos@36: return a;
athos@36: }
athos@36: else {
athos@77: return NodeIt();
athos@36: }
athos@36: break;
athos@36: }
athos@36: }
athos@36: //
athos@77: return NodeIt();
athos@36: }
athos@36:
athos@36: //Puts node 'a' among the active nodes
athos@77: void make_active(const NodeIt& 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@36: active_nodes[level.get(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@36: if (highest_active<level.get(a)){
athos@36: highest_active=level.get(a);
athos@36: }
athos@36:
athos@36: }
athos@36:
athos@36: //Changes the level of node a and make sufficent changes
athos@77: void change_level_to(NodeIt a, int new_value){
athos@36: int seged = level.get(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@77: for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
athos@77: level.set(i,0);
athos@77: excess.set(i,0);
athos@77: for(OutEdgeIt j=G.template first<OutEdgeIt>(i); j.valid(); ++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@36: //Setting starting level values using reverse bfs
athos@36: reverse_bfs<graph_type> rev_bfs(G,t);
athos@36: rev_bfs.run();
athos@36: //write_property_vector(rev_bfs.dist,"rev_bfs");
athos@77: for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
athos@36: change_level_to(i,rev_bfs.dist(i));
athos@36: //level.put(i,rev_bfs.dist.get(i));
athos@36: }
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@77: for(OutEdgeIt j=G.template first<OutEdgeIt>(s); j.valid(); ++j){
athos@36: modify_preflow(j,capacity.get(j) );
athos@36: make_active(G.head(j));
athos@36: int lev=level.get(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@77: bool is_admissible_forward_edge(OutEdgeIt j, int& new_level){
athos@119:
athos@36: if (capacity.get(j)>preflow.get(j)){
athos@36: if(level.get(G.tail(j))==level.get(G.head(j))+1){
athos@36: return true;
athos@36: }
athos@36: else{
athos@36: if (level.get(G.head(j)) < new_level)
athos@36: new_level=level.get(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@77: bool is_admissible_backward_edge(InEdgeIt j, int& new_level){
athos@119:
athos@36: if (0<preflow.get(j)){
athos@36: if(level.get(G.tail(j))==level.get(G.head(j))-1){
athos@119:
athos@36: return true;
athos@36: }
athos@36: else{
athos@36: if (level.get(G.tail(j)) < new_level)
athos@36: new_level=level.get(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@36: template<typename graph_type, typename T>
athos@36: T preflow_push<graph_type, T>::run() {
athos@36:
athos@36: preprocess();
athos@119: //write_property_vector(level,"level");
athos@36: T e,v;
athos@77: NodeIt a;
athos@36: while (a=get_active_node(), a.valid()){
athos@119:
athos@36: //cout<<G.id(a)<<endl;
athos@36: //write_property_vector(excess,"excess");
athos@36: //write_property_vector(level,"level");
athos@36:
athos@36:
athos@36: bool go_to_next_node=false;
athos@36: e = excess.get(a);
athos@36: while (!go_to_next_node){
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@77: //write_property_vector(excess,"excess");
athos@77: //write_property_vector(level,"level");
athos@77: //cout<<G.id(a)<<endl;
athos@36: //Out edges from node a
athos@36: {
athos@77: OutEdgeIt j=G.template first<OutEdgeIt>(a);
athos@36: while (j.valid() && e){
athos@36:
athos@36: if (is_admissible_forward_edge(j,new_level)){
athos@36: v=min(e,capacity.get(j) - preflow.get(j));
athos@36: e -= v;
athos@36: //New node might become active
athos@36: if (excess.get(G.head(j))==0){
athos@36: make_active(G.head(j));
athos@36: }
athos@36: modify_preflow(j,v);
athos@36: }
athos@36: ++j;
athos@36: }
athos@36: }
athos@36: //In edges to node a
athos@36: {
athos@77: InEdgeIt j=G.template first<InEdgeIt>(a);
athos@36: while (j.valid() && e){
athos@36: if (is_admissible_backward_edge(j,new_level)){
athos@36: v=min(e,preflow.get(j));
athos@36: e -= v;
athos@36: //New node might become active
athos@36: if (excess.get(G.tail(j))==0){
athos@36: make_active(G.tail(j));
athos@36: }
athos@36: modify_preflow(j,-v);
athos@36: }
athos@36: ++j;
athos@36: }
athos@36: }
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@36: if (num_of_nodes_on_level[level.get(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@36: maxflow_value = excess.get(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