alpar@2346
|
1 |
/* -*- C++ -*-
|
alpar@2346
|
2 |
*
|
alpar@2346
|
3 |
* This file is a part of LEMON, a generic C++ optimization library
|
alpar@2346
|
4 |
*
|
alpar@2346
|
5 |
* Copyright (C) 2003-2006
|
alpar@2346
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
alpar@2346
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
alpar@2346
|
8 |
*
|
alpar@2346
|
9 |
* Permission to use, modify and distribute this software is granted
|
alpar@2346
|
10 |
* provided that this copyright notice appears in all copies. For
|
alpar@2346
|
11 |
* precise terms see the accompanying LICENSE file.
|
alpar@2346
|
12 |
*
|
alpar@2346
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
alpar@2346
|
14 |
* express or implied, and with no claim as to its suitability for any
|
alpar@2346
|
15 |
* purpose.
|
alpar@2346
|
16 |
*
|
alpar@2346
|
17 |
*/
|
alpar@2346
|
18 |
|
alpar@2346
|
19 |
#ifndef LEMON_ELEVATOR_H
|
alpar@2346
|
20 |
#define LEMON_ELEVATOR_H
|
alpar@2346
|
21 |
|
alpar@2346
|
22 |
///\ingroup auxdat
|
alpar@2346
|
23 |
///\file
|
alpar@2346
|
24 |
///\brief Elevator class
|
alpar@2346
|
25 |
///
|
alpar@2346
|
26 |
///Elevator class implements an efficient data structure
|
alpar@2346
|
27 |
///for labeling items in push-relabel type algorithms.
|
alpar@2346
|
28 |
///
|
alpar@2346
|
29 |
|
alpar@2346
|
30 |
#include <test/test_tools.h>
|
alpar@2346
|
31 |
namespace lemon {
|
alpar@2346
|
32 |
|
alpar@2347
|
33 |
///Class for handling "labels" in push-relabel type algorithms.
|
alpar@2346
|
34 |
|
alpar@2347
|
35 |
///A class for handling "labels" in push-relabel type algorithms.
|
alpar@2346
|
36 |
///
|
alpar@2346
|
37 |
///\ingroup auxdat
|
alpar@2352
|
38 |
///Using this class you can assign "labels" (nonnegative integer numbers)
|
alpar@2346
|
39 |
///to the edges or nodes of a graph, manipulate and query them through
|
alpar@2346
|
40 |
///operations typically arising in "push-relabel" type algorithms.
|
alpar@2346
|
41 |
///
|
alpar@2346
|
42 |
///Each item is either \em active or not, and you can also choose a
|
alpar@2346
|
43 |
///highest level active item.
|
alpar@2346
|
44 |
///
|
alpar@2346
|
45 |
///\param Graph the underlying graph type
|
alpar@2346
|
46 |
///\param Item Type of the items the data is assigned to (Graph::Node,
|
alpar@2346
|
47 |
///Graph::Edge, Graph::UEdge)
|
alpar@2346
|
48 |
template<class Graph, class Item>
|
alpar@2346
|
49 |
class Elevator
|
alpar@2346
|
50 |
{
|
alpar@2346
|
51 |
public:
|
alpar@2346
|
52 |
typedef typename std::vector<Item>::iterator Vit;
|
alpar@2346
|
53 |
typedef DefaultMap<Graph,Item,Vit> VitMap;
|
alpar@2346
|
54 |
typedef DefaultMap<Graph,Item,int> IntMap;
|
alpar@2346
|
55 |
|
alpar@2346
|
56 |
const Graph &_g;
|
alpar@2346
|
57 |
int _max_level;
|
alpar@2346
|
58 |
int _item_num;
|
alpar@2346
|
59 |
VitMap _where;
|
alpar@2346
|
60 |
IntMap _level;
|
alpar@2346
|
61 |
std::vector<Item> _items;
|
alpar@2346
|
62 |
std::vector<Vit> _first;
|
alpar@2346
|
63 |
std::vector<Vit> _last_active;
|
alpar@2346
|
64 |
|
alpar@2346
|
65 |
int _highest_active;
|
alpar@2346
|
66 |
|
alpar@2346
|
67 |
void copy(Item i, Vit p)
|
alpar@2346
|
68 |
{
|
alpar@2346
|
69 |
_where[*p=i]=p;
|
alpar@2346
|
70 |
}
|
alpar@2346
|
71 |
void copy(Vit s, Vit p)
|
alpar@2346
|
72 |
{
|
alpar@2346
|
73 |
if(s!=p)
|
alpar@2346
|
74 |
{
|
alpar@2346
|
75 |
Item i=*s;
|
alpar@2346
|
76 |
*p=i;
|
alpar@2346
|
77 |
_where[i]=p;
|
alpar@2346
|
78 |
}
|
alpar@2346
|
79 |
}
|
alpar@2346
|
80 |
void swap(Vit i, Vit j)
|
alpar@2346
|
81 |
{
|
alpar@2346
|
82 |
Item ti=*i;
|
alpar@2346
|
83 |
Vit ct = _where[ti];
|
alpar@2346
|
84 |
_where[ti]=_where[*i=*j];
|
alpar@2346
|
85 |
_where[*j]=ct;
|
alpar@2346
|
86 |
*j=ti;
|
alpar@2346
|
87 |
}
|
alpar@2346
|
88 |
|
alpar@2348
|
89 |
void checkDs() const
|
alpar@2346
|
90 |
{
|
alpar@2346
|
91 |
for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
|
alpar@2346
|
92 |
{
|
alpar@2346
|
93 |
Vit w=_where[i];
|
alpar@2346
|
94 |
int l=_level[i];
|
alpar@2346
|
95 |
check(*w==i,"GEBASZ: CORRUPT DS");
|
alpar@2346
|
96 |
check(_first[l]<=w,"GEBASZ: CORRUPT DS");
|
alpar@2346
|
97 |
check(_first[l+1]>w,"GEBASZ: CORRUPT DS");
|
alpar@2346
|
98 |
}
|
alpar@2348
|
99 |
for(int l=0;l<=_max_level;++l)
|
alpar@2348
|
100 |
{
|
alpar@2348
|
101 |
check(_first[l]<=_last_active[l]+1,"GEBASZ: CORRUPT DS");
|
alpar@2348
|
102 |
check(_last_active[l]<_first[l+1],"GEBASZ: CORRUPT DS");
|
alpar@2348
|
103 |
check(_first[l]<=_first[l+1],"GEBASZ: CORRUPT DS");
|
alpar@2348
|
104 |
}
|
alpar@2346
|
105 |
check(_highest_active<0 ||
|
alpar@2346
|
106 |
_first[_highest_active]<=_last_active[_highest_active],
|
alpar@2346
|
107 |
"GEBASZ: CORRUPT DS");
|
alpar@2346
|
108 |
}
|
alpar@2346
|
109 |
|
alpar@2346
|
110 |
public:
|
alpar@2346
|
111 |
///Constructor with given maximum level.
|
alpar@2346
|
112 |
|
alpar@2346
|
113 |
///Constructor with given maximum level.
|
alpar@2346
|
114 |
///
|
alpar@2346
|
115 |
///\param g The underlying graph
|
alpar@2346
|
116 |
///\param max_level Set the range of the possible labels to
|
alpar@2346
|
117 |
///[0...\c max_level]
|
alpar@2346
|
118 |
Elevator(const Graph &g,int max_level) :
|
alpar@2346
|
119 |
_g(g),
|
alpar@2346
|
120 |
_max_level(max_level),
|
alpar@2346
|
121 |
_item_num(_max_level),
|
alpar@2346
|
122 |
_where(g),
|
alpar@2346
|
123 |
_level(g,0),
|
alpar@2346
|
124 |
_items(_max_level),
|
alpar@2346
|
125 |
_first(_max_level+2),
|
alpar@2346
|
126 |
_last_active(_max_level+2),
|
alpar@2346
|
127 |
_highest_active(-1) {}
|
alpar@2346
|
128 |
///Constructor.
|
alpar@2346
|
129 |
|
alpar@2346
|
130 |
///Constructor.
|
alpar@2346
|
131 |
///
|
alpar@2346
|
132 |
///\param g The underlying graph
|
alpar@2346
|
133 |
///The range of the possible labels is [0...\c max_level],
|
alpar@2346
|
134 |
///where \c max_level is equal to the number of labeled items in the graph.
|
alpar@2346
|
135 |
Elevator(const Graph &g) :
|
alpar@2346
|
136 |
_g(g),
|
alpar@2346
|
137 |
_max_level(countItems<Graph, Item>(g)),
|
alpar@2346
|
138 |
_item_num(_max_level),
|
alpar@2346
|
139 |
_where(g),
|
alpar@2346
|
140 |
_level(g,0),
|
alpar@2346
|
141 |
_items(_max_level),
|
alpar@2346
|
142 |
_first(_max_level+2),
|
alpar@2346
|
143 |
_last_active(_max_level+2),
|
alpar@2346
|
144 |
_highest_active(-1)
|
alpar@2346
|
145 |
{
|
alpar@2346
|
146 |
}
|
alpar@2346
|
147 |
|
alpar@2346
|
148 |
///Activate item \c i.
|
alpar@2346
|
149 |
void activate(Item i)
|
alpar@2346
|
150 |
{
|
alpar@2346
|
151 |
const int l=_level[i];
|
alpar@2346
|
152 |
swap(_where[i],++_last_active[l]);
|
alpar@2346
|
153 |
if(l>_highest_active) _highest_active=l;
|
alpar@2346
|
154 |
}
|
alpar@2346
|
155 |
|
alpar@2346
|
156 |
///Deactivate item \c i.
|
alpar@2346
|
157 |
void deactivate(Item i)
|
alpar@2346
|
158 |
{
|
alpar@2346
|
159 |
swap(_where[i],_last_active[_level[i]]--);
|
alpar@2346
|
160 |
while(_highest_active>=0 &&
|
alpar@2346
|
161 |
_last_active[_highest_active]<_first[_highest_active])
|
alpar@2346
|
162 |
_highest_active--;
|
alpar@2346
|
163 |
}
|
alpar@2346
|
164 |
|
alpar@2346
|
165 |
///Query whether item \c i is active
|
alpar@2346
|
166 |
bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; }
|
alpar@2346
|
167 |
|
alpar@2346
|
168 |
///Return the level of item \c i.
|
alpar@2346
|
169 |
int operator[](Item i) const { return _level[i]; }
|
alpar@2346
|
170 |
|
alpar@2346
|
171 |
///Returns an active item on level \c l.
|
alpar@2346
|
172 |
|
alpar@2346
|
173 |
///Returns an active item on level \c l.
|
alpar@2346
|
174 |
///
|
alpar@2346
|
175 |
///Returns an active item on level \c l or \ref INVALID if there is no such
|
alpar@2346
|
176 |
///an item. (\c l must be from the range [0...\c max_level].
|
alpar@2346
|
177 |
Item operator[](int l) const
|
alpar@2346
|
178 |
{
|
alpar@2346
|
179 |
return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
|
alpar@2346
|
180 |
}
|
alpar@2346
|
181 |
|
alpar@2346
|
182 |
///Return the number of items on level \c l.
|
alpar@2348
|
183 |
int onLevel(int l) const
|
alpar@2346
|
184 |
{
|
alpar@2346
|
185 |
return _first[l+1]-_first[l];
|
alpar@2346
|
186 |
}
|
alpar@2348
|
187 |
///Return the number of items above level \c l.
|
alpar@2348
|
188 |
int aboveLevel(int l) const
|
alpar@2348
|
189 |
{
|
alpar@2348
|
190 |
return _first[_max_level+1]-_first[l+1];
|
alpar@2348
|
191 |
}
|
alpar@2346
|
192 |
///Return the number of active items on level \c l.
|
alpar@2348
|
193 |
int activesOnLevel(int l) const
|
alpar@2346
|
194 |
{
|
alpar@2346
|
195 |
return _last_active[l]-_first[l]+1;
|
alpar@2346
|
196 |
}
|
alpar@2346
|
197 |
///Return the maximum allowed level.
|
alpar@2346
|
198 |
int maxLevel() const
|
alpar@2346
|
199 |
{
|
alpar@2346
|
200 |
return _max_level;
|
alpar@2346
|
201 |
}
|
alpar@2346
|
202 |
|
alpar@2346
|
203 |
///\name Highest Active Item
|
alpar@2346
|
204 |
///Functions for working with the highest level
|
alpar@2346
|
205 |
///active item.
|
alpar@2346
|
206 |
|
alpar@2346
|
207 |
///@{
|
alpar@2346
|
208 |
|
alpar@2346
|
209 |
///Return a highest level active item.
|
alpar@2346
|
210 |
|
alpar@2346
|
211 |
///Return a highest level active item.
|
alpar@2346
|
212 |
///
|
alpar@2346
|
213 |
///\return the highest level active item or INVALID if there is no active
|
alpar@2346
|
214 |
///item.
|
alpar@2346
|
215 |
Item highestActive() const
|
alpar@2346
|
216 |
{
|
alpar@2346
|
217 |
return _highest_active>=0?*_last_active[_highest_active]:INVALID;
|
alpar@2346
|
218 |
}
|
alpar@2346
|
219 |
|
alpar@2346
|
220 |
///Return a highest active level.
|
alpar@2346
|
221 |
|
alpar@2346
|
222 |
///Return a highest active level.
|
alpar@2346
|
223 |
///
|
alpar@2346
|
224 |
///\return the level of the highest active item or -1 if there is no active
|
alpar@2346
|
225 |
///item.
|
athos@2349
|
226 |
int highestActiveLevel() const
|
alpar@2346
|
227 |
{
|
alpar@2346
|
228 |
return _highest_active;
|
alpar@2346
|
229 |
}
|
alpar@2346
|
230 |
|
alpar@2346
|
231 |
///Lift the highest active item by one.
|
alpar@2346
|
232 |
|
alpar@2346
|
233 |
///Lift the item returned by highestActive() by one.
|
alpar@2346
|
234 |
///
|
alpar@2346
|
235 |
void liftHighestActive()
|
alpar@2346
|
236 |
{
|
alpar@2346
|
237 |
++_level[*_last_active[_highest_active]];
|
alpar@2346
|
238 |
swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
|
alpar@2346
|
239 |
--_first[++_highest_active];
|
alpar@2346
|
240 |
}
|
alpar@2346
|
241 |
|
alpar@2346
|
242 |
///Lift the highest active item.
|
alpar@2346
|
243 |
|
alpar@2346
|
244 |
///Lift the item returned by highestActive() to level \c new_level.
|
alpar@2346
|
245 |
///
|
alpar@2348
|
246 |
///\warning \c new_level must be strictly higher
|
alpar@2348
|
247 |
///than the current level.
|
alpar@2346
|
248 |
///
|
alpar@2346
|
249 |
void liftHighestActiveTo(int new_level)
|
alpar@2346
|
250 |
{
|
alpar@2346
|
251 |
const Item li = *_last_active[_highest_active];
|
alpar@2346
|
252 |
|
alpar@2346
|
253 |
copy(--_first[_highest_active+1],_last_active[_highest_active]--);
|
alpar@2346
|
254 |
for(int l=_highest_active+1;l<new_level;l++)
|
alpar@2346
|
255 |
{
|
alpar@2346
|
256 |
copy(--_first[l+1],_first[l]);
|
alpar@2346
|
257 |
--_last_active[l];
|
alpar@2346
|
258 |
}
|
alpar@2346
|
259 |
copy(li,_first[new_level]);
|
alpar@2346
|
260 |
_level[li]=new_level;
|
alpar@2348
|
261 |
_highest_active=new_level;
|
alpar@2346
|
262 |
}
|
alpar@2346
|
263 |
|
alpar@2346
|
264 |
///@}
|
alpar@2346
|
265 |
|
alpar@2348
|
266 |
///Lift an active item to a higher level.
|
alpar@2348
|
267 |
|
alpar@2348
|
268 |
///Lift an active item to a higher level.
|
alpar@2350
|
269 |
///\param i The item to be lifted. It must be active.
|
alpar@2350
|
270 |
///\param new_level The new level of \c i. It must be strictly higher
|
alpar@2348
|
271 |
///than the current level.
|
alpar@2348
|
272 |
///
|
alpar@2348
|
273 |
void liftTo(Item i, int new_level)
|
alpar@2348
|
274 |
{
|
alpar@2348
|
275 |
const int lo = _level[i];
|
alpar@2348
|
276 |
const Vit w = _where[i];
|
alpar@2348
|
277 |
|
alpar@2348
|
278 |
copy(_last_active[lo],w);
|
alpar@2348
|
279 |
copy(--_first[lo+1],_last_active[lo]--);
|
alpar@2348
|
280 |
for(int l=lo+1;l<new_level;l++)
|
alpar@2348
|
281 |
{
|
alpar@2348
|
282 |
copy(_last_active[l],_first[l]);
|
alpar@2348
|
283 |
copy(--_first[l+1],_last_active[l]--);
|
alpar@2348
|
284 |
}
|
alpar@2348
|
285 |
copy(i,_first[new_level]);
|
alpar@2348
|
286 |
_level[i]=new_level;
|
alpar@2348
|
287 |
if(new_level>_highest_active) _highest_active=new_level;
|
alpar@2348
|
288 |
}
|
alpar@2348
|
289 |
|
alpar@2348
|
290 |
// void liftToTop(int l)
|
alpar@2348
|
291 |
// {
|
alpar@2348
|
292 |
// const Vit f=_first[l];
|
alpar@2348
|
293 |
// for(int i=l;i<=_max_level;i++)
|
alpar@2348
|
294 |
// {
|
alpar@2348
|
295 |
// _first[i]=f;
|
alpar@2348
|
296 |
// _last_active[i]=f-1;
|
alpar@2348
|
297 |
// }
|
alpar@2348
|
298 |
// for(Vit i=f;i!=_items.end();++i)
|
alpar@2348
|
299 |
// _level[*i]=_max_level;
|
alpar@2348
|
300 |
// for(_highest_active=l-1;
|
alpar@2348
|
301 |
// _highest_active>=0 &&
|
alpar@2348
|
302 |
// _last_active[_highest_active]<_first[_highest_active];
|
alpar@2348
|
303 |
// _highest_active--) ;
|
alpar@2348
|
304 |
// }
|
alpar@2348
|
305 |
|
alpar@2348
|
306 |
///Lift all nodes on and above a level to the top (and deactivate them).
|
alpar@2348
|
307 |
|
alpar@2348
|
308 |
///This function lifts all nodes on and above level \c l to \c maxLevel(),
|
alpar@2348
|
309 |
///and
|
alpar@2348
|
310 |
///also deactivates them.
|
alpar@2348
|
311 |
void liftToTop(int l)
|
alpar@2348
|
312 |
{
|
alpar@2348
|
313 |
const Vit f=_first[l];
|
alpar@2348
|
314 |
const Vit tl=_first[_max_level];
|
alpar@2348
|
315 |
for(Vit i=f;i!=tl;++i)
|
alpar@2348
|
316 |
_level[*i]=_max_level;
|
alpar@2348
|
317 |
for(int i=l;i<=_max_level;i++)
|
alpar@2348
|
318 |
{
|
alpar@2348
|
319 |
_first[i]=f;
|
alpar@2348
|
320 |
_last_active[i]=f-1;
|
alpar@2348
|
321 |
}
|
alpar@2348
|
322 |
for(_highest_active=l-1;
|
alpar@2348
|
323 |
_highest_active>=0 &&
|
alpar@2348
|
324 |
_last_active[_highest_active]<_first[_highest_active];
|
alpar@2348
|
325 |
_highest_active--) ;
|
alpar@2348
|
326 |
}
|
alpar@2348
|
327 |
|
alpar@2346
|
328 |
private:
|
alpar@2346
|
329 |
int _init_lev;
|
alpar@2346
|
330 |
Vit _init_num;
|
alpar@2346
|
331 |
|
alpar@2346
|
332 |
public:
|
alpar@2346
|
333 |
|
alpar@2346
|
334 |
///\name Initialization
|
alpar@2346
|
335 |
///Using this function you can initialize the levels of the item.
|
alpar@2346
|
336 |
///\n
|
alpar@2346
|
337 |
///This initializatios is started with calling \c initStart().
|
alpar@2346
|
338 |
///Then the
|
alpar@2346
|
339 |
///items should be listed levels by levels statring with the lowest one
|
alpar@2346
|
340 |
///(with level 0). This is done by using \c initAddItem()
|
alpar@2346
|
341 |
///and \c initNewLevel(). Finally \c initFinish() must be called.
|
alpar@2348
|
342 |
///The items not listed will be put on the highest level.
|
alpar@2346
|
343 |
///@{
|
alpar@2346
|
344 |
|
alpar@2348
|
345 |
///Start the initialization process.
|
alpar@2346
|
346 |
|
alpar@2346
|
347 |
void initStart()
|
alpar@2346
|
348 |
{
|
alpar@2346
|
349 |
_init_lev=0;
|
alpar@2346
|
350 |
_init_num=_items.begin();
|
alpar@2346
|
351 |
_first[0]=_items.begin();
|
alpar@2346
|
352 |
_last_active[0]=_items.begin()-1;
|
alpar@2346
|
353 |
Vit n=_items.begin();
|
alpar@2346
|
354 |
for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
|
alpar@2346
|
355 |
{
|
alpar@2346
|
356 |
*n=i;
|
alpar@2346
|
357 |
_where[i]=n;
|
alpar@2346
|
358 |
_level[i]=_max_level;
|
alpar@2346
|
359 |
++n;
|
alpar@2346
|
360 |
}
|
alpar@2346
|
361 |
}
|
alpar@2346
|
362 |
|
alpar@2346
|
363 |
///Add an item to the current level.
|
alpar@2346
|
364 |
|
alpar@2346
|
365 |
void initAddItem(Item i)
|
alpar@2346
|
366 |
{
|
alpar@2346
|
367 |
swap(_where[i],_init_num);
|
alpar@2346
|
368 |
_level[i]=_init_lev;
|
alpar@2346
|
369 |
++_init_num;
|
alpar@2346
|
370 |
}
|
alpar@2346
|
371 |
|
alpar@2346
|
372 |
///Start a new level.
|
alpar@2346
|
373 |
|
alpar@2346
|
374 |
///Start a new level.
|
alpar@2346
|
375 |
///It shouldn't be used before the items on level 0 are listed.
|
alpar@2346
|
376 |
void initNewLevel()
|
alpar@2346
|
377 |
{
|
alpar@2346
|
378 |
_init_lev++;
|
alpar@2346
|
379 |
_first[_init_lev]=_init_num;
|
alpar@2346
|
380 |
_last_active[_init_lev]=_init_num-1;
|
alpar@2346
|
381 |
}
|
alpar@2346
|
382 |
|
alpar@2348
|
383 |
///Finalize the initialization process.
|
alpar@2346
|
384 |
|
alpar@2346
|
385 |
void initFinish()
|
alpar@2346
|
386 |
{
|
alpar@2346
|
387 |
for(_init_lev++;_init_lev<=_max_level;_init_lev++)
|
alpar@2346
|
388 |
{
|
alpar@2346
|
389 |
_first[_init_lev]=_init_num;
|
alpar@2346
|
390 |
_last_active[_init_lev]=_init_num-1;
|
alpar@2346
|
391 |
}
|
alpar@2346
|
392 |
_first[_max_level+1]=_items.begin()+_item_num;
|
alpar@2346
|
393 |
_last_active[_max_level+1]=_items.begin()+_item_num-1;
|
alpar@2346
|
394 |
}
|
alpar@2346
|
395 |
|
alpar@2346
|
396 |
///@}
|
alpar@2346
|
397 |
|
alpar@2346
|
398 |
};
|
alpar@2346
|
399 |
|
alpar@2346
|
400 |
} //END OF NAMESPACE LEMON
|
alpar@2346
|
401 |
|
alpar@2346
|
402 |
#endif
|
alpar@2346
|
403 |
|