lemon-0.x: src/work/jacint/preflow_push_hl.h@87623302a68f (annotated)

jacint@72	1	// -- C++ --
jacint@72	2	/*
jacint@72	3	preflow_push_hl.hh
jacint@72	4	by jacint.
jacint@72	5	Runs the highest label variant of the preflow push algorithm with
jacint@72	6	running time O(n^2\sqrt(m)).
jacint@72	7
jacint@72	8	Member functions:
jacint@72	9
jacint@72	10	void run() : runs the algorithm
jacint@72	11
jacint@72	12	The following functions should be used after run() was already run.
jacint@72	13
jacint@72	14	T maxflow() : returns the value of a maximum flow
jacint@72	15
jacint@72	16	T flowonEdge(Edge_iterator e) : for a fixed maximum flow x it returns x(e)
jacint@72	17
jacint@72	18	EdgeMap<graph_type, T> allflow() : returns the fixed maximum flow x
jacint@72	19
jacint@72	20	NodeMap<graph_type, bool> mincut() : returns a
jacint@72	21	characteristic vector of a minimum cut. (An empty level
jacint@72	22	in the algorithm gives a minimum cut.)
jacint@72	23	*/
jacint@72	24
jacint@72	25	#ifndef PREFLOW_PUSH_HL_H
jacint@72	26	#define PREFLOW_PUSH_HL_H
jacint@72	27
jacint@72	28	#include <algorithm>
jacint@72	29	#include <vector>
jacint@72	30	#include <stack>
jacint@72	31
jacint@72	32	#include <reverse_bfs.hh>
jacint@72	33
jacint@72	34	namespace marci {
jacint@72	35
jacint@72	36	template <typename Graph, typename T, typename FlowMap, typename CapacityMap>
jacint@72	37	class preflow_push_hl {
jacint@72	38
jacint@72	39	typedef typename Graph::NodeIt NodeIt;
jacint@72	40	typedef typename Graph::EdgeIt EdgeIt;
jacint@72	41	typedef typename Graph::EachNodeIt EachNodeIt;
jacint@72	42	typedef typename Graph::OutEdgeIt OutEdgeIt;
jacint@72	43	typedef typename Graph::InEdgeIt InEdgeIt;
jacint@72	44	typedef typename Graph::EachEdgeIt EachEdgeIt;
jacint@72	45
jacint@72	46
jacint@72	47	Graph& G;
jacint@72	48	NodeIt s;
jacint@72	49	NodeIt t;
jacint@72	50	Graph::EdgeMap<T> flow;
jacint@72	51	Graph::EdgeMap<T> capacity;
jacint@72	52	T value;
jacint@72	53	Graph::NodeMap<bool> mincutvector;
jacint@72	54
jacint@72	55
jacint@72	56	public:
jacint@72	57
jacint@72	58	preflow_push_hl(Graph& _G, NodeIt _s, NodeIt _t,
jacint@72	59	Graph::EdgeMap<T>& _capacity) :
jacint@72	60	G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), mincutvector(_G, true) { }
jacint@72	61
jacint@72	62
jacint@72	63
jacint@72	64
jacint@72	65	/*
jacint@72	66	The run() function runs the highest label preflow-push,
jacint@72	67	running time: O(n^2\sqrt(m))
jacint@72	68	*/
jacint@72	69	void run() {
jacint@72	70
jacint@72	71	Graph::NodeMap<int> level(G); //level of Node
jacint@72	72	Graph::NodeMap<T> excess(G); //excess of Node
jacint@72	73
jacint@72	74	int n=G.nodeNum(); //number of Nodes
jacint@72	75	int b=n;
jacint@72	76	/b is a bound on the highest level of an active Node. In the beginning it is at most n-2./
jacint@72	77
jacint@72	78	std::vector<std::stack<NodeIt> > stack(2*n-1); //Stack of the active Nodes in level i.
jacint@72	79
jacint@72	80
jacint@72	81
jacint@72	82
jacint@72	83	/Reverse_bfs from t, to find the starting level./
jacint@72	84
jacint@72	85	reverse_bfs<list_graph> bfs(G, t);
jacint@72	86	bfs.run();
jacint@72	87	for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) {
jacint@72	88	level.set(v, bfs.dist(v));
jacint@72	89	//std::cout << "the level of " << v << " is " << bfs.dist(v);
jacint@72	90	}
jacint@72	91
jacint@72	92	/The level of s is fixed to n/
jacint@72	93	level.set(s,n);
jacint@72	94
jacint@72	95
jacint@72	96
jacint@72	97
jacint@72	98
jacint@72	99	/* Starting flow. It is everywhere 0 at the moment. */
jacint@72	100
jacint@72	101	for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i)
jacint@72	102	{
jacint@72	103	NodeIt w=G.head(i);
jacint@72	104	flow.set(i, capacity.get(i));
jacint@72	105	stack[bfs.dist(w)].push(w);
jacint@72	106	excess.set(w, capacity.get(i));
jacint@72	107	}
jacint@72	108
jacint@72	109
jacint@72	110	/*
jacint@72	111	End of preprocessing
jacint@72	112	*/
jacint@72	113
jacint@72	114
jacint@72	115
jacint@72	116	/*
jacint@72	117	Push/relabel on the highest level active Nodes.
jacint@72	118	*/
jacint@72	119
jacint@72	120	/While there exists active Node./
jacint@72	121	while (b) {
jacint@72	122
jacint@72	123	/We decrease the bound if there is no active Node of level b./
jacint@72	124	if (stack[b].empty()) {
jacint@72	125	--b;
jacint@72	126	} else {
jacint@72	127
jacint@72	128	NodeIt w=stack[b].top(); //w is the highest label active Node.
jacint@72	129	stack[b].pop(); //We delete w from the stack.
jacint@72	130
jacint@72	131	int newlevel=2*n-2; //In newlevel we maintain the next level of w.
jacint@72	132
jacint@72	133	for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
jacint@72	134	NodeIt v=G.head(e);
jacint@72	135	/e is the Edge wv./
jacint@72	136
jacint@72	137	if (flow.get(e)<capacity.get(e)) {
jacint@72	138	/e is an Edge of the residual graph /
jacint@72	139
jacint@72	140	if(level.get(w)==level.get(v)+1) {
jacint@72	141	/Push is allowed now/
jacint@72	142
jacint@72	143	if (capacity.get(e)-flow.get(e) > excess.get(w)) {
jacint@72	144	/A nonsaturating push./
jacint@72	145
jacint@72	146	if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
jacint@72	147	/v becomes active./
jacint@72	148
jacint@72	149	flow.set(e, flow.get(e)+excess.get(w));
jacint@72	150	excess.set(v, excess.get(v)+excess.get(w));
jacint@72	151	excess.set(w,0);
jacint@72	152	//std::cout << w << " " << v <<" elore elen nonsat pump " << std::endl;
jacint@72	153	break;
jacint@72	154	} else {
jacint@72	155	/A saturating push./
jacint@72	156
jacint@72	157	if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
jacint@72	158	/v becomes active./
jacint@72	159
jacint@72	160	excess.set(v, excess.get(v)+capacity.get(e)-flow.get(e));
jacint@72	161	excess.set(w, excess.get(w)-capacity.get(e)+flow.get(e));
jacint@72	162	flow.set(e, capacity.get(e));
jacint@72	163	//std::cout << w<<" " <<v<<" elore elen sat pump " << std::endl;
jacint@72	164	if (excess.get(w)==0) break;
jacint@72	165	/If w is not active any more, then we go on to the next Node./
jacint@72	166
jacint@72	167	} // if (capacity.get(e)-flow.get(e) > excess.get(w))
jacint@72	168	} // if(level.get(w)==level.get(v)+1)
jacint@72	169
jacint@72	170	else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
jacint@72	171
jacint@72	172	} //if (flow.get(e)<capacity.get(e))
jacint@72	173
jacint@72	174	} //for(OutEdgeIt e=G.first_OutEdge(w); e.valid(); ++e)
jacint@72	175
jacint@72	176
jacint@72	177
jacint@72	178	for(InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
jacint@72	179	NodeIt v=G.tail(e);
jacint@72	180	/e is the Edge vw./
jacint@72	181
jacint@72	182	if (excess.get(w)==0) break;
jacint@72	183	/It may happen, that w became inactive in the first for cycle./
jacint@72	184	if(flow.get(e)>0) {
jacint@72	185	/e is an Edge of the residual graph /
jacint@72	186
jacint@72	187	if(level.get(w)==level.get(v)+1) {
jacint@72	188	/Push is allowed now/
jacint@72	189
jacint@72	190	if (flow.get(e) > excess.get(w)) {
jacint@72	191	/A nonsaturating push./
jacint@72	192
jacint@72	193	if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
jacint@72	194	/v becomes active./
jacint@72	195
jacint@72	196	flow.set(e, flow.get(e)-excess.get(w));
jacint@72	197	excess.set(v, excess.get(v)+excess.get(w));
jacint@72	198	excess.set(w,0);
jacint@72	199	//std::cout << v << " " << w << " vissza elen nonsat pump " << std::endl;
jacint@72	200	break;
jacint@72	201	} else {
jacint@72	202	/A saturating push./
jacint@72	203
jacint@72	204	if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
jacint@72	205	/v becomes active./
jacint@72	206
jacint@72	207	excess.set(v, excess.get(v)+flow.get(e));
jacint@72	208	excess.set(w, excess.get(w)-flow.get(e));
jacint@72	209	flow.set(e,0);
jacint@72	210	//std::cout << v <<" " << w << " vissza elen sat pump " << std::endl;
jacint@72	211	if (excess.get(w)==0) { break;}
jacint@72	212	} //if (flow.get(e) > excess.get(v))
jacint@72	213	} //if(level.get(w)==level.get(v)+1)
jacint@72	214
jacint@72	215	else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
jacint@72	216
jacint@72	217
jacint@72	218	} //if (flow.get(e)>0)
jacint@72	219
jacint@72	220	} //for
jacint@72	221
jacint@72	222
jacint@72	223	if (excess.get(w)>0) {
jacint@72	224	level.set(w,++newlevel);
jacint@72	225	stack[newlevel].push(w);
jacint@72	226	b=newlevel;
jacint@72	227	//std::cout << "The new level of " << w << " is "<< newlevel <<std::endl;
jacint@72	228	}
jacint@72	229
jacint@72	230
jacint@72	231	} //else
jacint@72	232
jacint@72	233	} //while(b)
jacint@72	234
jacint@72	235	value = excess.get(t);
jacint@72	236	/Max flow value./
jacint@72	237
jacint@72	238
jacint@72	239
jacint@72	240
jacint@72	241	} //void run()
jacint@72	242
jacint@72	243
jacint@72	244
jacint@72	245
jacint@72	246
jacint@72	247	/*
jacint@72	248	Returns the maximum value of a flow.
jacint@72	249	*/
jacint@72	250
jacint@72	251	T maxflow() {
jacint@72	252	return value;
jacint@72	253	}
jacint@72	254
jacint@72	255
jacint@72	256
jacint@72	257	/*
jacint@72	258	For the maximum flow x found by the algorithm, it returns the flow value on Edge e, i.e. x(e).
jacint@72	259	*/
jacint@72	260
jacint@72	261	T flowonEdge(EdgeIt e) {
jacint@72	262	return flow.get(e);
jacint@72	263	}
jacint@72	264
jacint@72	265
jacint@72	266
jacint@72	267	/*
jacint@72	268	Returns the maximum flow x found by the algorithm.
jacint@72	269	*/
jacint@72	270
jacint@72	271	EdgeMap<graph_type, T> allflow() {
jacint@72	272	return flow;
jacint@72	273	}
jacint@72	274
jacint@72	275
jacint@72	276
jacint@72	277	/*
jacint@72	278	Returns a minimum cut by using a reverse bfs from t in the residual graph.
jacint@72	279	*/
jacint@72	280
jacint@72	281	NodeMap<graph_type, bool> mincut() {
jacint@72	282
jacint@72	283	std::queue<NodeIt> queue;
jacint@72	284
jacint@72	285	mincutvector.set(t,false);
jacint@72	286	queue.push(t);
jacint@72	287
jacint@72	288	while (!queue.empty()) {
jacint@72	289	NodeIt w=queue.front();
jacint@72	290	queue.pop();
jacint@72	291
jacint@72	292	for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
jacint@72	293	NodeIt v=G.tail(e);
jacint@72	294	if (mincutvector.get(v) && flow.get(e) < capacity.get(e) ) {
jacint@72	295	queue.push(v);
jacint@72	296	mincutvector.set(v, false);
jacint@72	297	}
jacint@72	298	} // for
jacint@72	299
jacint@72	300	for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
jacint@72	301	NodeIt v=G.head(e);
jacint@72	302	if (mincutvector.get(v) && flow.get(e) > 0 ) {
jacint@72	303	queue.push(v);
jacint@72	304	mincutvector.set(v, false);
jacint@72	305	}
jacint@72	306	} // for
jacint@72	307
jacint@72	308	}
jacint@72	309
jacint@72	310	return mincutvector;
jacint@72	311
jacint@72	312	}
jacint@72	313
jacint@72	314
jacint@72	315	};
jacint@72	316	}//namespace marci
jacint@72	317	#endif
jacint@72	318
jacint@72	319
jacint@72	320
jacint@72	321

author	marci
	Mon, 16 Feb 2004 11:29:48 +0000
changeset 75	87623302a68f
child 78	ecc1171307be
permissions	-rw-r--r--