1.1 --- a/lemon/Makefile.am Fri Jan 12 16:29:06 2007 +0000
1.2 +++ b/lemon/Makefile.am Fri Jan 19 17:15:15 2007 +0000
1.3 @@ -50,6 +50,7 @@
1.4 lemon/dimacs.h \
1.5 lemon/edge_set.h \
1.6 lemon/edmonds_karp.h \
1.7 + lemon/elevator.h \
1.8 lemon/eps.h \
1.9 lemon/error.h \
1.10 lemon/fib_heap.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/elevator.h Fri Jan 19 17:15:15 2007 +0000
2.3 @@ -0,0 +1,329 @@
2.4 +/* -*- C++ -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library
2.7 + *
2.8 + * Copyright (C) 2003-2006
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +#ifndef LEMON_ELEVATOR_H
2.23 +#define LEMON_ELEVATOR_H
2.24 +
2.25 +///\ingroup auxdat
2.26 +///\file
2.27 +///\brief Elevator class
2.28 +///
2.29 +///Elevator class implements an efficient data structure
2.30 +///for labeling items in push-relabel type algorithms.
2.31 +///
2.32 +
2.33 +#include <test/test_tools.h>
2.34 +namespace lemon {
2.35 +
2.36 + ///Class for hangling "labels" in push-relabel type algorithms.
2.37 +
2.38 + ///A class for hangling "labels" in push-relabel type algorithms.
2.39 + ///
2.40 + ///\ingroup auxdat
2.41 + ///Using this class you can assign "labels" (nonnegativ integer numbers)
2.42 + ///to the edges or nodes of a graph, manipulate and query them through
2.43 + ///operations typically arising in "push-relabel" type algorithms.
2.44 + ///
2.45 + ///Each item is either \em active or not, and you can also choose a
2.46 + ///highest level active item.
2.47 + ///
2.48 + ///\param Graph the underlying graph type
2.49 + ///\param Item Type of the items the data is assigned to (Graph::Node,
2.50 + ///Graph::Edge, Graph::UEdge)
2.51 + template<class Graph, class Item>
2.52 + class Elevator
2.53 + {
2.54 + public:
2.55 + typedef typename std::vector<Item>::iterator Vit;
2.56 + typedef DefaultMap<Graph,Item,Vit> VitMap;
2.57 + typedef DefaultMap<Graph,Item,int> IntMap;
2.58 +
2.59 + const Graph &_g;
2.60 + int _max_level;
2.61 + int _item_num;
2.62 + VitMap _where;
2.63 + IntMap _level;
2.64 + std::vector<Item> _items;
2.65 + std::vector<Vit> _first;
2.66 + std::vector<Vit> _last_active;
2.67 +
2.68 + int _highest_active;
2.69 +
2.70 + void copy(Item i, Vit p)
2.71 + {
2.72 + _where[*p=i]=p;
2.73 + }
2.74 + void copy(Vit s, Vit p)
2.75 + {
2.76 + if(s!=p)
2.77 + {
2.78 + Item i=*s;
2.79 + *p=i;
2.80 + _where[i]=p;
2.81 + }
2.82 + }
2.83 + void swap(Vit i, Vit j)
2.84 + {
2.85 + Item ti=*i;
2.86 + Vit ct = _where[ti];
2.87 + _where[ti]=_where[*i=*j];
2.88 + _where[*j]=ct;
2.89 + *j=ti;
2.90 + }
2.91 +
2.92 + void checkDs()
2.93 + {
2.94 + for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
2.95 + {
2.96 + Vit w=_where[i];
2.97 + int l=_level[i];
2.98 + check(*w==i,"GEBASZ: CORRUPT DS");
2.99 + check(_first[l]<=w,"GEBASZ: CORRUPT DS");
2.100 + check(_first[l+1]>w,"GEBASZ: CORRUPT DS");
2.101 + }
2.102 + check(_highest_active<0 ||
2.103 + _first[_highest_active]<=_last_active[_highest_active],
2.104 + "GEBASZ: CORRUPT DS");
2.105 + }
2.106 +
2.107 + public:
2.108 + ///Constructor with given maximum level.
2.109 +
2.110 + ///Constructor with given maximum level.
2.111 + ///
2.112 + ///\param g The underlying graph
2.113 + ///\param max_level Set the range of the possible labels to
2.114 + ///[0...\c max_level]
2.115 + Elevator(const Graph &g,int max_level) :
2.116 + _g(g),
2.117 + _max_level(max_level),
2.118 + _item_num(_max_level),
2.119 + _where(g),
2.120 + _level(g,0),
2.121 + _items(_max_level),
2.122 + _first(_max_level+2),
2.123 + _last_active(_max_level+2),
2.124 + _highest_active(-1) {}
2.125 + ///Constructor.
2.126 +
2.127 + ///Constructor.
2.128 + ///
2.129 + ///\param g The underlying graph
2.130 + ///The range of the possible labels is [0...\c max_level],
2.131 + ///where \c max_level is equal to the number of labeled items in the graph.
2.132 + Elevator(const Graph &g) :
2.133 + _g(g),
2.134 + _max_level(countItems<Graph, Item>(g)),
2.135 + _item_num(_max_level),
2.136 + _where(g),
2.137 + _level(g,0),
2.138 + _items(_max_level),
2.139 + _first(_max_level+2),
2.140 + _last_active(_max_level+2),
2.141 + _highest_active(-1)
2.142 + {
2.143 + }
2.144 +
2.145 + ///Activate item \c i.
2.146 + void activate(Item i)
2.147 + {
2.148 + const int l=_level[i];
2.149 + swap(_where[i],++_last_active[l]);
2.150 + if(l>_highest_active) _highest_active=l;
2.151 + }
2.152 +
2.153 + ///Deactivate item \c i.
2.154 + void deactivate(Item i)
2.155 + {
2.156 + swap(_where[i],_last_active[_level[i]]--);
2.157 + _last_active[_level[i]]--;
2.158 + while(_highest_active>=0 &&
2.159 + _last_active[_highest_active]<_first[_highest_active])
2.160 + _highest_active--;
2.161 + }
2.162 +
2.163 + ///Query whether item \c i is active
2.164 + bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; }
2.165 +
2.166 + ///Return the level of item \c i.
2.167 + int operator[](Item i) const { return _level[i]; }
2.168 +
2.169 + ///Returns an active item on level \c l.
2.170 +
2.171 + ///Returns an active item on level \c l.
2.172 + ///
2.173 + ///Returns an active item on level \c l or \ref INVALID if there is no such
2.174 + ///an item. (\c l must be from the range [0...\c max_level].
2.175 + Item operator[](int l) const
2.176 + {
2.177 + return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
2.178 + }
2.179 +
2.180 + ///Return the number of items on level \c l.
2.181 + int &onLevel(int l)
2.182 + {
2.183 + return _first[l+1]-_first[l];
2.184 + }
2.185 + ///Return the number of active items on level \c l.
2.186 + int &activesOnLevel(int l)
2.187 + {
2.188 + return _last_active[l]-_first[l]+1;
2.189 + }
2.190 + ///Return the maximum allowed level.
2.191 + int maxLevel() const
2.192 + {
2.193 + return _max_level;
2.194 + }
2.195 +
2.196 + ///\name Highest Active Item
2.197 + ///Functions for working with the highest level
2.198 + ///active item.
2.199 +
2.200 + ///@{
2.201 +
2.202 + ///Return a highest level active item.
2.203 +
2.204 + ///Return a highest level active item.
2.205 + ///
2.206 + ///\return the highest level active item or INVALID if there is no active
2.207 + ///item.
2.208 + Item highestActive() const
2.209 + {
2.210 + return _highest_active>=0?*_last_active[_highest_active]:INVALID;
2.211 + }
2.212 +
2.213 + ///Return a highest active level.
2.214 +
2.215 + ///Return a highest active level.
2.216 + ///
2.217 + ///\return the level of the highest active item or -1 if there is no active
2.218 + ///item.
2.219 + Item highestActiveLevel() const
2.220 + {
2.221 + return _highest_active;
2.222 + }
2.223 +
2.224 + ///Lift the highest active item by one.
2.225 +
2.226 + ///Lift the item returned by highestActive() by one.
2.227 + ///
2.228 + void liftHighestActive()
2.229 + {
2.230 + ++_level[*_last_active[_highest_active]];
2.231 + swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
2.232 + --_first[++_highest_active];
2.233 + }
2.234 +
2.235 + ///Lift the highest active item.
2.236 +
2.237 + ///Lift the item returned by highestActive() to level \c new_level.
2.238 + ///
2.239 + ///
2.240 + void liftHighestActiveTo(int new_level)
2.241 + {
2.242 + const Item li = *_last_active[_highest_active];
2.243 +
2.244 + copy(--_first[_highest_active+1],_last_active[_highest_active]--);
2.245 + for(int l=_highest_active+1;l<new_level;l++)
2.246 + {
2.247 + copy(--_first[l+1],_first[l]);
2.248 + --_last_active[l];
2.249 + }
2.250 + copy(li,_first[new_level]);
2.251 + _level[li]=new_level;
2.252 + _highest_active=new_level;
2.253 + }
2.254 +
2.255 + ///@}
2.256 +
2.257 + private:
2.258 + int _init_lev;
2.259 + Vit _init_num;
2.260 +
2.261 + public:
2.262 +
2.263 + ///\name Initialization
2.264 + ///Using this function you can initialize the levels of the item.
2.265 + ///\n
2.266 + ///This initializatios is started with calling \c initStart().
2.267 + ///Then the
2.268 + ///items should be listed levels by levels statring with the lowest one
2.269 + ///(with level 0). This is done by using \c initAddItem()
2.270 + ///and \c initNewLevel(). Finally \c initFinish() must be called.
2.271 + ///The items not listes will be put on the highest level.
2.272 + ///@{
2.273 +
2.274 + ///Starts the initialization process.
2.275 +
2.276 + void initStart()
2.277 + {
2.278 + _init_lev=0;
2.279 + _init_num=_items.begin();
2.280 + _first[0]=_items.begin();
2.281 + _last_active[0]=_items.begin()-1;
2.282 + Vit n=_items.begin();
2.283 + for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
2.284 + {
2.285 + *n=i;
2.286 + _where[i]=n;
2.287 + _level[i]=_max_level;
2.288 + ++n;
2.289 + }
2.290 + }
2.291 +
2.292 + ///Add an item to the current level.
2.293 +
2.294 + void initAddItem(Item i)
2.295 + {
2.296 + swap(_where[i],_init_num);
2.297 + _level[i]=_init_lev;
2.298 + ++_init_num;
2.299 + }
2.300 +
2.301 + ///Start a new level.
2.302 +
2.303 + ///Start a new level.
2.304 + ///It shouldn't be used before the items on level 0 are listed.
2.305 + void initNewLevel()
2.306 + {
2.307 + _init_lev++;
2.308 + _first[_init_lev]=_init_num;
2.309 + _last_active[_init_lev]=_init_num-1;
2.310 + }
2.311 +
2.312 + ///Finalizes the initialization process.
2.313 +
2.314 + void initFinish()
2.315 + {
2.316 + for(_init_lev++;_init_lev<=_max_level;_init_lev++)
2.317 + {
2.318 + _first[_init_lev]=_init_num;
2.319 + _last_active[_init_lev]=_init_num-1;
2.320 + }
2.321 + _first[_max_level+1]=_items.begin()+_item_num;
2.322 + _last_active[_max_level+1]=_items.begin()+_item_num-1;
2.323 + }
2.324 +
2.325 + ///@}
2.326 +
2.327 + };
2.328 +
2.329 +} //END OF NAMESPACE LEMON
2.330 +
2.331 +#endif
2.332 +