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