lemon/preflow.h
changeset 1764 7dac7356c023
parent 1742 2637b9420d0a
child 1786 a263c131e999
equal deleted inserted replaced
2:88303fe4c91b 3:29635a2a2ccf
    18 #define LEMON_PREFLOW_H
    18 #define LEMON_PREFLOW_H
    19 
    19 
    20 #include <vector>
    20 #include <vector>
    21 #include <queue>
    21 #include <queue>
    22 
    22 
       
    23 #include <lemon/error.h>
    23 #include <lemon/invalid.h>
    24 #include <lemon/invalid.h>
    24 #include <lemon/maps.h>
    25 #include <lemon/maps.h>
    25 #include <lemon/graph_utils.h>
    26 #include <lemon/graph_utils.h>
    26 
    27 
    27 /// \file
    28 /// \file
    86 
    87 
    87     // constants used for heuristics
    88     // constants used for heuristics
    88     static const int H0=20;
    89     static const int H0=20;
    89     static const int H1=1;
    90     static const int H1=1;
    90 
    91 
       
    92   public:
       
    93 
       
    94     ///\ref Exception for the case when s=t.
       
    95 
       
    96     ///\ref Exception for the case when the source equals the target.
       
    97     class InvalidArgument : public lemon::LogicError {
    91     public:
    98     public:
    92 
    99       virtual const char* exceptionName() const {
       
   100 	return "lemon::Preflow::InvalidArgument";
       
   101       }
       
   102     };
       
   103     
       
   104     
    93     ///Indicates the property of the starting flow map.
   105     ///Indicates the property of the starting flow map.
    94 
   106     
    95     ///Indicates the property of the starting flow map.
   107     ///Indicates the property of the starting flow map.
    96     ///The meanings are as follows:
   108     ///The meanings are as follows:
    97     ///- \c ZERO_FLOW: constant zero flow
   109     ///- \c ZERO_FLOW: constant zero flow
    98     ///- \c GEN_FLOW: any flow, i.e. the sum of the in-flows equals to
   110     ///- \c GEN_FLOW: any flow, i.e. the sum of the in-flows equals to
    99     ///the sum of the out-flows in every node except the \e source and
   111     ///the sum of the out-flows in every node except the \e source and
   124       AFTER_NOTHING,
   136       AFTER_NOTHING,
   125       AFTER_PREFLOW_PHASE_1,      
   137       AFTER_PREFLOW_PHASE_1,      
   126       AFTER_PREFLOW_PHASE_2
   138       AFTER_PREFLOW_PHASE_2
   127     };
   139     };
   128     
   140     
   129     protected: 
   141   protected: 
   130       FlowEnum flow_prop;
   142     FlowEnum flow_prop;
   131     StatusEnum status; // Do not needle this flag only if necessary.
   143     StatusEnum status; // Do not needle this flag only if necessary.
   132     
   144     
   133   public: 
   145   public: 
   134     ///The constructor of the class.
   146     ///The constructor of the class.
   135 
   147 
   144     ///flowMap, resp.
   156     ///flowMap, resp.
   145       Preflow(const Graph& _gr, Node _s, Node _t, 
   157       Preflow(const Graph& _gr, Node _s, Node _t, 
   146 	      const CapacityMap& _cap, FlowMap& _f) :
   158 	      const CapacityMap& _cap, FlowMap& _f) :
   147 	_g(&_gr), _source(_s), _target(_t), _capacity(&_cap),
   159 	_g(&_gr), _source(_s), _target(_t), _capacity(&_cap),
   148 	_flow(&_f), _node_num(countNodes(_gr)), level(_gr), excess(_gr,0), 
   160 	_flow(&_f), _node_num(countNodes(_gr)), level(_gr), excess(_gr,0), 
   149 	flow_prop(NO_FLOW), status(AFTER_NOTHING) { }
   161 	flow_prop(NO_FLOW), status(AFTER_NOTHING) { 
   150 
   162 	if ( _source==_target )
       
   163 	  throw InvalidArgument();
       
   164       }
       
   165     
   151 
   166 
   152                                                                               
   167                                                                               
   153     ///Runs the preflow algorithm.  
   168     ///Runs the preflow algorithm.  
   154 
   169 
   155     ///Runs the preflow algorithm.
   170     ///Runs the preflow algorithm.