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 |
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. |