1.1 --- a/lemon/elevator.h Fri Nov 21 10:41:36 2008 +0000
1.2 +++ b/lemon/elevator.h Fri Nov 21 11:10:25 2008 +0100
1.3 @@ -27,7 +27,8 @@
1.4 ///for labeling items in push-relabel type algorithms.
1.5 ///
1.6
1.7 -#include <test/test_tools.h>
1.8 +#include <lemon/bits/traits.h>
1.9 +
1.10 namespace lemon {
1.11
1.12 ///Class for handling "labels" in push-relabel type algorithms.
1.13 @@ -44,9 +45,9 @@
1.14 ///
1.15 ///\sa LinkedElevator
1.16 ///
1.17 - ///\param Graph the underlying graph type
1.18 + ///\param Graph Type of the underlying graph.
1.19 ///\param Item Type of the items the data is assigned to (Graph::Node,
1.20 - ///Graph::Edge, Graph::UEdge)
1.21 + ///Graph::Arc, Graph::Edge).
1.22 template<class Graph, class Item>
1.23 class Elevator
1.24 {
1.25 @@ -100,15 +101,15 @@
1.26
1.27 ///Constructor with given maximum level.
1.28 ///
1.29 - ///\param g The underlying graph
1.30 - ///\param max_level Set the range of the possible labels to
1.31 - ///[0...\c max_level]
1.32 - Elevator(const Graph &g,int max_level) :
1.33 - _g(g),
1.34 + ///\param graph The underlying graph.
1.35 + ///\param max_level The maximum allowed level.
1.36 + ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
1.37 + Elevator(const Graph &graph,int max_level) :
1.38 + _g(graph),
1.39 _max_level(max_level),
1.40 _item_num(_max_level),
1.41 - _where(g),
1.42 - _level(g,0),
1.43 + _where(graph),
1.44 + _level(graph,0),
1.45 _items(_max_level),
1.46 _first(_max_level+2),
1.47 _last_active(_max_level+2),
1.48 @@ -117,15 +118,15 @@
1.49
1.50 ///Constructor.
1.51 ///
1.52 - ///\param g The underlying graph
1.53 - ///The range of the possible labels is [0...\c max_level],
1.54 + ///\param graph The underlying graph.
1.55 + ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
1.56 ///where \c max_level is equal to the number of labeled items in the graph.
1.57 - Elevator(const Graph &g) :
1.58 - _g(g),
1.59 - _max_level(countItems<Graph, Item>(g)),
1.60 + Elevator(const Graph &graph) :
1.61 + _g(graph),
1.62 + _max_level(countItems<Graph, Item>(graph)),
1.63 _item_num(_max_level),
1.64 - _where(g),
1.65 - _level(g,0),
1.66 + _where(graph),
1.67 + _level(graph,0),
1.68 _items(_max_level),
1.69 _first(_max_level+2),
1.70 _last_active(_max_level+2),
1.71 @@ -167,7 +168,7 @@
1.72 {
1.73 return _first[l+1]-_first[l];
1.74 }
1.75 - ///Return true if the level is empty.
1.76 + ///Return true if level \c l is empty.
1.77 bool emptyLevel(int l) const
1.78 {
1.79 return _first[l+1]-_first[l]==0;
1.80 @@ -182,7 +183,7 @@
1.81 {
1.82 return _last_active[l]-_first[l]+1;
1.83 }
1.84 - ///Return true if there is not active item on level \c l.
1.85 + ///Return true if there is no active item on level \c l.
1.86 bool activeFree(int l) const
1.87 {
1.88 return _last_active[l]<_first[l];
1.89 @@ -201,20 +202,16 @@
1.90
1.91 ///Return a highest level active item.
1.92
1.93 - ///Return a highest level active item.
1.94 - ///
1.95 - ///\return the highest level active item or INVALID if there is no active
1.96 + ///Return a highest level active item or INVALID if there is no active
1.97 ///item.
1.98 Item highestActive() const
1.99 {
1.100 return _highest_active>=0?*_last_active[_highest_active]:INVALID;
1.101 }
1.102
1.103 - ///Return a highest active level.
1.104 + ///Return the highest active level.
1.105
1.106 - ///Return a highest active level.
1.107 - ///
1.108 - ///\return the level of the highest active item or -1 if there is no active
1.109 + ///Return the level of the highest active item or -1 if there is no active
1.110 ///item.
1.111 int highestActiveLevel() const
1.112 {
1.113 @@ -233,7 +230,7 @@
1.114 --_first[++_highest_active];
1.115 }
1.116
1.117 - ///Lift the highest active item.
1.118 + ///Lift the highest active item to the given level.
1.119
1.120 ///Lift the item returned by highestActive() to level \c new_level.
1.121 ///
1.122 @@ -255,14 +252,10 @@
1.123 _highest_active=new_level;
1.124 }
1.125
1.126 - ///Lift the highest active item.
1.127 + ///Lift the highest active item to the top level.
1.128
1.129 ///Lift the item returned by highestActive() to the top level and
1.130 - ///deactivates it.
1.131 - ///
1.132 - ///\warning \c new_level must be strictly higher
1.133 - ///than the current level.
1.134 - ///
1.135 + ///deactivate it.
1.136 void liftHighestActiveToTop()
1.137 {
1.138 const Item li = *_last_active[_highest_active];
1.139 @@ -289,20 +282,18 @@
1.140
1.141 ///@{
1.142
1.143 - ///Returns an active item on level \c l.
1.144 + ///Return an active item on level \c l.
1.145
1.146 - ///Returns an active item on level \c l.
1.147 - ///
1.148 - ///Returns an active item on level \c l or \ref INVALID if there is no such
1.149 + ///Return an active item on level \c l or \ref INVALID if there is no such
1.150 ///an item. (\c l must be from the range [0...\c max_level].
1.151 Item activeOn(int l) const
1.152 {
1.153 return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
1.154 }
1.155
1.156 - ///Lifts the active item returned by \c activeOn() member function.
1.157 + ///Lift the active item returned by \c activeOn(level) by one.
1.158
1.159 - ///Lifts the active item returned by \c activeOn() member function
1.160 + ///Lift the active item returned by \ref activeOn() "activeOn(level)"
1.161 ///by one.
1.162 Item liftActiveOn(int level)
1.163 {
1.164 @@ -312,9 +303,9 @@
1.165 if (level+1>_highest_active) ++_highest_active;
1.166 }
1.167
1.168 - ///Lifts the active item returned by \c activeOn() member function.
1.169 + ///Lift the active item returned by \c activeOn(level) to the given level.
1.170
1.171 - ///Lifts the active item returned by \c activeOn() member function
1.172 + ///Lift the active item returned by \ref activeOn() "activeOn(level)"
1.173 ///to the given level.
1.174 void liftActiveOn(int level, int new_level)
1.175 {
1.176 @@ -331,10 +322,10 @@
1.177 if (new_level>_highest_active) _highest_active=new_level;
1.178 }
1.179
1.180 - ///Lifts the active item returned by \c activeOn() member function.
1.181 + ///Lift the active item returned by \c activeOn(level) to the top level.
1.182
1.183 - ///Lifts the active item returned by \c activeOn() member function
1.184 - ///to the top level.
1.185 + ///Lift the active item returned by \ref activeOn() "activeOn(level)"
1.186 + ///to the top level and deactivate it.
1.187 void liftActiveToTop(int level)
1.188 {
1.189 const Item ai = *_last_active[level];
1.190 @@ -384,18 +375,19 @@
1.191
1.192 ///Move an inactive item to the top but one level (in a dirty way).
1.193
1.194 - ///This function moves an inactive item to the top but one level.
1.195 - ///It makes the underlying datastructure corrupt, so use is only if
1.196 - ///you really know what it is for.
1.197 + ///This function moves an inactive item from the top level to the top
1.198 + ///but one level (in a dirty way).
1.199 + ///\warning It makes the underlying datastructure corrupt, so use it
1.200 + ///only if you really know what it is for.
1.201 ///\pre The item is on the top level.
1.202 void dirtyTopButOne(Item i) {
1.203 _level.set(i,_max_level - 1);
1.204 }
1.205
1.206 - ///Lift all items on and above a level to the top (and deactivate them).
1.207 + ///Lift all items on and above the given level to the top level.
1.208
1.209 - ///This function lifts all items on and above level \c l to \c
1.210 - ///maxLevel(), and also deactivates them.
1.211 + ///This function lifts all items on and above level \c l to the top
1.212 + ///level and deactivates them.
1.213 void liftToTop(int l)
1.214 {
1.215 const Vit f=_first[l];
1.216 @@ -420,18 +412,16 @@
1.217 public:
1.218
1.219 ///\name Initialization
1.220 - ///Using this function you can initialize the levels of the item.
1.221 + ///Using these functions you can initialize the levels of the items.
1.222 ///\n
1.223 - ///This initializatios is started with calling \c initStart().
1.224 - ///Then the
1.225 - ///items should be listed levels by levels statring with the lowest one
1.226 - ///(with level 0). This is done by using \c initAddItem()
1.227 - ///and \c initNewLevel(). Finally \c initFinish() must be called.
1.228 - ///The items not listed will be put on the highest level.
1.229 + ///The initialization must be started with calling \c initStart().
1.230 + ///Then the items should be listed level by level starting with the
1.231 + ///lowest one (level 0) using \c initAddItem() and \c initNewLevel().
1.232 + ///Finally \c initFinish() must be called.
1.233 + ///The items not listed are put on the highest level.
1.234 ///@{
1.235
1.236 ///Start the initialization process.
1.237 -
1.238 void initStart()
1.239 {
1.240 _init_lev=0;
1.241 @@ -449,7 +439,6 @@
1.242 }
1.243
1.244 ///Add an item to the current level.
1.245 -
1.246 void initAddItem(Item i)
1.247 {
1.248 swap(_where[i],_init_num);
1.249 @@ -469,7 +458,6 @@
1.250 }
1.251
1.252 ///Finalize the initialization process.
1.253 -
1.254 void initFinish()
1.255 {
1.256 for(_init_lev++;_init_lev<=_max_level;_init_lev++)
1.257 @@ -500,9 +488,9 @@
1.258 ///
1.259 ///\sa Elevator
1.260 ///
1.261 - ///\param Graph the underlying graph type
1.262 + ///\param Graph Type of the underlying graph.
1.263 ///\param Item Type of the items the data is assigned to (Graph::Node,
1.264 - ///Graph::Edge, Graph::UEdge)
1.265 + ///Graph::Arc, Graph::Edge).
1.266 template <class Graph, class Item>
1.267 class LinkedElevator {
1.268 public:
1.269 @@ -533,9 +521,9 @@
1.270
1.271 ///Constructor with given maximum level.
1.272 ///
1.273 - ///\param g The underlying graph
1.274 - ///\param max_level Set the range of the possible labels to
1.275 - ///[0...\c max_level]
1.276 + ///\param graph The underlying graph.
1.277 + ///\param max_level The maximum allowed level.
1.278 + ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
1.279 LinkedElevator(const Graph& graph, int max_level)
1.280 : _graph(graph), _max_level(max_level), _item_num(_max_level),
1.281 _first(_max_level + 1), _last(_max_level + 1),
1.282 @@ -546,8 +534,8 @@
1.283
1.284 ///Constructor.
1.285 ///
1.286 - ///\param g The underlying graph
1.287 - ///The range of the possible labels is [0...\c max_level],
1.288 + ///\param graph The underlying graph.
1.289 + ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
1.290 ///where \c max_level is equal to the number of labeled items in the graph.
1.291 LinkedElevator(const Graph& graph)
1.292 : _graph(graph), _max_level(countItems<Graph, Item>(graph)),
1.293 @@ -657,7 +645,7 @@
1.294 return num;
1.295 }
1.296
1.297 - ///Return true if there is not active item on level \c l.
1.298 + ///Return true if there is no active item on level \c l.
1.299 bool activeFree(int l) const {
1.300 return _first[l] == INVALID || !_active[_first[l]];
1.301 }
1.302 @@ -675,20 +663,16 @@
1.303
1.304 ///Return a highest level active item.
1.305
1.306 - ///Return a highest level active item.
1.307 - ///
1.308 - ///\return the highest level active item or INVALID if there is no
1.309 - ///active item.
1.310 + ///Return a highest level active item or INVALID if there is no active
1.311 + ///item.
1.312 Item highestActive() const {
1.313 return _highest_active >= 0 ? _first[_highest_active] : INVALID;
1.314 }
1.315
1.316 - ///Return a highest active level.
1.317 + ///Return the highest active level.
1.318
1.319 - ///Return a highest active level.
1.320 - ///
1.321 - ///\return the level of the highest active item or -1 if there is
1.322 - ///no active item.
1.323 + ///Return the level of the highest active item or -1 if there is no active
1.324 + ///item.
1.325 int highestActiveLevel() const {
1.326 return _highest_active;
1.327 }
1.328 @@ -719,7 +703,7 @@
1.329 }
1.330 }
1.331
1.332 - ///Lift the highest active item.
1.333 + ///Lift the highest active item to the given level.
1.334
1.335 ///Lift the item returned by highestActive() to level \c new_level.
1.336 ///
1.337 @@ -747,11 +731,10 @@
1.338 }
1.339 }
1.340
1.341 - ///Lift the highest active to top.
1.342 + ///Lift the highest active item to the top level.
1.343
1.344 ///Lift the item returned by highestActive() to the top level and
1.345 - ///deactivates the item.
1.346 - ///
1.347 + ///deactivate it.
1.348 void liftHighestActiveToTop() {
1.349 Item i = _first[_highest_active];
1.350 _level.set(i, _max_level);
1.351 @@ -773,20 +756,18 @@
1.352
1.353 ///@{
1.354
1.355 - ///Returns an active item on level \c l.
1.356 + ///Return an active item on level \c l.
1.357
1.358 - ///Returns an active item on level \c l.
1.359 - ///
1.360 - ///Returns an active item on level \c l or \ref INVALID if there is no such
1.361 + ///Return an active item on level \c l or \ref INVALID if there is no such
1.362 ///an item. (\c l must be from the range [0...\c max_level].
1.363 Item activeOn(int l) const
1.364 {
1.365 return _active[_first[l]] ? _first[l] : INVALID;
1.366 }
1.367
1.368 - ///Lifts the active item returned by \c activeOn() member function.
1.369 + ///Lift the active item returned by \c activeOn(l) by one.
1.370
1.371 - ///Lifts the active item returned by \c activeOn() member function
1.372 + ///Lift the active item returned by \ref activeOn() "activeOn(l)"
1.373 ///by one.
1.374 Item liftActiveOn(int l)
1.375 {
1.376 @@ -813,10 +794,10 @@
1.377 }
1.378 }
1.379
1.380 - /// \brief Lifts the active item returned by \c activeOn() member function.
1.381 - ///
1.382 - /// Lifts the active item returned by \c activeOn() member function
1.383 - /// to the given level.
1.384 + ///Lift the active item returned by \c activeOn(l) to the given level.
1.385 +
1.386 + ///Lift the active item returned by \ref activeOn() "activeOn(l)"
1.387 + ///to the given level.
1.388 void liftActiveOn(int l, int new_level)
1.389 {
1.390 Item i = _first[l];
1.391 @@ -842,10 +823,10 @@
1.392 }
1.393 }
1.394
1.395 - ///Lifts the active item returned by \c activeOn() member function.
1.396 + ///Lift the active item returned by \c activeOn(l) to the top level.
1.397
1.398 - ///Lifts the active item returned by \c activeOn() member function
1.399 - ///to the top level.
1.400 + ///Lift the active item returned by \ref activeOn() "activeOn(l)"
1.401 + ///to the top level and deactivate it.
1.402 void liftActiveToTop(int l)
1.403 {
1.404 Item i = _first[l];
1.405 @@ -900,18 +881,19 @@
1.406
1.407 ///Move an inactive item to the top but one level (in a dirty way).
1.408
1.409 - ///This function moves an inactive item to the top but one level.
1.410 - ///It makes the underlying datastructure corrupt, so use is only if
1.411 - ///you really know what it is for.
1.412 + ///This function moves an inactive item from the top level to the top
1.413 + ///but one level (in a dirty way).
1.414 + ///\warning It makes the underlying datastructure corrupt, so use it
1.415 + ///only if you really know what it is for.
1.416 ///\pre The item is on the top level.
1.417 void dirtyTopButOne(Item i) {
1.418 _level.set(i, _max_level - 1);
1.419 }
1.420
1.421 - ///Lift all items on and above a level to the top (and deactivate them).
1.422 + ///Lift all items on and above the given level to the top level.
1.423
1.424 - ///This function lifts all items on and above level \c l to \c
1.425 - ///maxLevel(), and also deactivates them.
1.426 + ///This function lifts all items on and above level \c l to the top
1.427 + ///level and deactivates them.
1.428 void liftToTop(int l) {
1.429 for (int i = l + 1; _first[i] != INVALID; ++i) {
1.430 Item n = _first[i];
1.431 @@ -936,18 +918,16 @@
1.432 public:
1.433
1.434 ///\name Initialization
1.435 - ///Using this function you can initialize the levels of the item.
1.436 + ///Using these functions you can initialize the levels of the items.
1.437 ///\n
1.438 - ///This initializatios is started with calling \c initStart().
1.439 - ///Then the
1.440 - ///items should be listed levels by levels statring with the lowest one
1.441 - ///(with level 0). This is done by using \c initAddItem()
1.442 - ///and \c initNewLevel(). Finally \c initFinish() must be called.
1.443 - ///The items not listed will be put on the highest level.
1.444 + ///The initialization must be started with calling \c initStart().
1.445 + ///Then the items should be listed level by level starting with the
1.446 + ///lowest one (level 0) using \c initAddItem() and \c initNewLevel().
1.447 + ///Finally \c initFinish() must be called.
1.448 + ///The items not listed are put on the highest level.
1.449 ///@{
1.450
1.451 ///Start the initialization process.
1.452 -
1.453 void initStart() {
1.454
1.455 for (int i = 0; i <= _max_level; ++i) {
1.456 @@ -962,7 +942,6 @@
1.457 }
1.458
1.459 ///Add an item to the current level.
1.460 -
1.461 void initAddItem(Item i) {
1.462 _level.set(i, _init_level);
1.463 if (_last[_init_level] == INVALID) {
1.464 @@ -987,7 +966,6 @@
1.465 }
1.466
1.467 ///Finalize the initialization process.
1.468 -
1.469 void initFinish() {
1.470 _highest_active = -1;
1.471 }