equal
deleted
inserted
replaced
35 |
35 |
36 ///\ingroup max_flow |
36 ///\ingroup max_flow |
37 ///This class implements a preflow algorithm |
37 ///This class implements a preflow algorithm |
38 ///for the Network Circulation Problem. |
38 ///for the Network Circulation Problem. |
39 ///The exact formulation of this problem is the following. |
39 ///The exact formulation of this problem is the following. |
40 /// \f[\sum_{e\in\rho(v)}x(e)-\sum_{e\in\delta(v)}x(e)\leq delta(v)\quad \forall v\in V \f] |
40 /// \f[\sum_{e\in\rho(v)}x(e)-\sum_{e\in\delta(v)}x(e)\leq -delta(v)\quad \forall v\in V \f] |
41 /// \f[ lo(e)\leq x(e) \leq up(e) \quad \forall e\in E \f] |
41 /// \f[ lo(e)\leq x(e) \leq up(e) \quad \forall e\in E \f] |
42 /// |
42 /// |
43 template<class Graph, |
43 template<class Graph, |
44 class Value, |
44 class Value, |
45 class FlowMap=typename Graph::template EdgeMap<Value>, |
45 class FlowMap=typename Graph::template EdgeMap<Value>, |
93 void init() |
93 void init() |
94 { |
94 { |
95 |
95 |
96 _x=_lo; |
96 _x=_lo; |
97 |
97 |
98 for(NodeIt n(_g);n!=INVALID;++n) _excess[n]=-_delta[n]; |
98 for(NodeIt n(_g);n!=INVALID;++n) _excess[n]=_delta[n]; |
99 |
99 |
100 for(EdgeIt e(_g);e!=INVALID;++e) |
100 for(EdgeIt e(_g);e!=INVALID;++e) |
101 { |
101 { |
102 _excess[_g.target(e)]+=_x[e]; |
102 _excess[_g.target(e)]+=_x[e]; |
103 _excess[_g.source(e)]-=_x[e]; |
103 _excess[_g.source(e)]-=_x[e]; |
118 bool checkX(FT &x) { |
118 bool checkX(FT &x) { |
119 for(EdgeIt e(_g);e!=INVALID;++e) |
119 for(EdgeIt e(_g);e!=INVALID;++e) |
120 if(x[e]<_lo[e]||x[e]>_up[e]) return false; |
120 if(x[e]<_lo[e]||x[e]>_up[e]) return false; |
121 for(NodeIt n(_g);n!=INVALID;++n) |
121 for(NodeIt n(_g);n!=INVALID;++n) |
122 { |
122 { |
123 Value dif=_delta[n]; |
123 Value dif=-_delta[n]; |
124 for(InEdgeIt e(_g,n);e!=INVALID;++e) dif-=x[e]; |
124 for(InEdgeIt e(_g,n);e!=INVALID;++e) dif-=x[e]; |
125 for(OutEdgeIt e(_g,n);e!=INVALID;++e) dif+=x[e]; |
125 for(OutEdgeIt e(_g,n);e!=INVALID;++e) dif+=x[e]; |
126 if(_tol.negative(dif)) return false; |
126 if(_tol.negative(dif)) return false; |
127 } |
127 } |
128 return true; |
128 return true; |
138 bool checkBarrier(GT &bar) |
138 bool checkBarrier(GT &bar) |
139 { |
139 { |
140 Value delta=0; |
140 Value delta=0; |
141 for(NodeIt n(_g);n!=INVALID;++n) |
141 for(NodeIt n(_g);n!=INVALID;++n) |
142 if(bar[n]) |
142 if(bar[n]) |
143 delta+=_delta[n]; |
143 delta-=_delta[n]; |
144 for(EdgeIt e(_g);e!=INVALID;++e) |
144 for(EdgeIt e(_g);e!=INVALID;++e) |
145 { |
145 { |
146 Node s=_g.source(e); |
146 Node s=_g.source(e); |
147 Node t=_g.target(e); |
147 Node t=_g.target(e); |
148 if(bar[s]&&!bar[t]) delta+=_up[e]; |
148 if(bar[s]&&!bar[t]) delta+=_up[e]; |
277 } |
277 } |
278 |
278 |
279 ///Return a barrier |
279 ///Return a barrier |
280 |
280 |
281 ///Barrier is a set \e B of nodes for which |
281 ///Barrier is a set \e B of nodes for which |
282 /// \f[ \sum_{v\in B}delta(v)<\sum_{e\in\rho(B)}lo(e)-\sum_{e\in\delta(B)}up(e) \f] |
282 /// \f[ \sum_{v\in B}-delta(v)<\sum_{e\in\rho(B)}lo(e)-\sum_{e\in\delta(B)}up(e) \f] |
283 ///holds. The existence of a set with this property prooves that a feasible |
283 ///holds. The existence of a set with this property prooves that a feasible |
284 ///flow cannot exists. |
284 ///flow cannot exists. |
285 ///\pre The run() must have been executed, and its return value was -1. |
285 ///\pre The run() must have been executed, and its return value was -1. |
286 ///\sa checkBarrier() |
286 ///\sa checkBarrier() |
287 ///\sa run() |
287 ///\sa run() |