COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/elevator.h @ 2391:14a343be7a5a

Last change on this file since 2391:14a343be7a5a was 2391:14a343be7a5a, checked in by Alpar Juttner, 12 years ago

Happy New Year to all source files!

File size: 10.4 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
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>
31namespace lemon {
32
33  ///Class for handling "labels" in push-relabel type algorithms.
34 
35  ///A class for handling "labels" in push-relabel type algorithms.
36  ///
37  ///\ingroup auxdat
38  ///Using this class you can assign "labels" (nonnegative 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   
89    void checkDs() const
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        }
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        }
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
150    ///Activate item \c i.
151    ///\pre Item \c i shouldn't be active before.
152    void activate(Item i)
153    {
154      const int l=_level[i];
155      swap(_where[i],++_last_active[l]);
156      if(l>_highest_active) _highest_active=l;
157    }
158 
159    ///Deactivate item \c i.
160
161    ///Deactivate item \c i.
162    ///\pre Item \c i must be active before.
163    void deactivate(Item i) 
164    {
165      swap(_where[i],_last_active[_level[i]]--);
166      while(_highest_active>=0 &&
167            _last_active[_highest_active]<_first[_highest_active])
168        _highest_active--;
169    }
170
171    ///Query whether item \c i is active
172    bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; }
173   
174    ///Return the level of item \c i.
175    int operator[](Item i) const { return _level[i]; }
176
177    ///Returns an active item on level \c l.
178
179    ///Returns an active item on level \c l.
180    ///
181    ///Returns an active item on level \c l or \ref INVALID if there is no such
182    ///an item. (\c l must be from the range [0...\c max_level].
183    Item operator[](int l) const
184    {
185      return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
186    }
187
188    ///Return the number of items on level \c l.
189    int onLevel(int l) const
190    {
191      return _first[l+1]-_first[l];
192    }
193    ///Return the number of items above level \c l.
194    int aboveLevel(int l) const
195    {
196      return _first[_max_level+1]-_first[l+1];
197    }
198    ///Return the number of active items on level \c l.
199    int activesOnLevel(int l) const
200    {
201      return _last_active[l]-_first[l]+1;
202    }
203    ///Return the maximum allowed level.
204    int maxLevel() const
205    {
206      return _max_level;
207    }   
208
209    ///\name Highest Active Item
210    ///Functions for working with the highest level
211    ///active item.
212
213    ///@{
214
215    ///Return a highest level active item.
216 
217    ///Return a highest level active item.
218    ///
219    ///\return the highest level active item or INVALID if there is no active
220    ///item.
221    Item highestActive() const
222    {
223      return _highest_active>=0?*_last_active[_highest_active]:INVALID;
224    }
225
226    ///Return a highest active level.
227
228    ///Return a highest active level.
229    ///
230    ///\return the level of the highest active item or -1 if there is no active
231    ///item.
232    int highestActiveLevel() const
233    {
234      return _highest_active;
235    }
236
237    ///Lift the highest active item by one.
238
239    ///Lift the item returned by highestActive() by one.
240    ///
241    void liftHighestActive()
242    {
243      ++_level[*_last_active[_highest_active]];
244      swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
245      --_first[++_highest_active];
246    }
247
248    ///Lift the highest active item.
249
250    ///Lift the item returned by highestActive() to level \c new_level.
251    ///
252    ///\warning \c new_level must be strictly higher
253    ///than the current level.
254    ///
255    void liftHighestActiveTo(int new_level)
256    {
257      const Item li = *_last_active[_highest_active];
258     
259      copy(--_first[_highest_active+1],_last_active[_highest_active]--);
260      for(int l=_highest_active+1;l<new_level;l++)
261        {
262          copy(--_first[l+1],_first[l]);
263          --_last_active[l];
264        }
265      copy(li,_first[new_level]);
266      _level[li]=new_level;
267      _highest_active=new_level;
268    }
269   
270    ///@}
271   
272    ///Lift an active item to a higher level.
273
274    ///Lift an active item to a higher level.
275    ///\param i The item to be lifted. It must be active.
276    ///\param new_level The new level of \c i. It must be strictly higher
277    ///than the current level.
278    ///
279    void liftTo(Item i, int new_level)
280    {
281      const int lo = _level[i];
282      const Vit w = _where[i];
283
284      copy(_last_active[lo],w);
285      copy(--_first[lo+1],_last_active[lo]--);
286      for(int l=lo+1;l<new_level;l++)
287        {
288          copy(_last_active[l],_first[l]);
289          copy(--_first[l+1],_last_active[l]--);
290        }
291      copy(i,_first[new_level]);
292      _level[i]=new_level;
293      if(new_level>_highest_active) _highest_active=new_level;
294    }
295
296//     void liftToTop(int l)
297//     {
298//       const Vit f=_first[l];
299//       for(int i=l;i<=_max_level;i++)
300//      {
301//        _first[i]=f;
302//        _last_active[i]=f-1;
303//      }
304//       for(Vit i=f;i!=_items.end();++i)
305//      _level[*i]=_max_level;
306//       for(_highest_active=l-1;
307//        _highest_active>=0 &&
308//          _last_active[_highest_active]<_first[_highest_active];
309//        _highest_active--) ;
310//     }
311   
312    ///Lift all nodes on and above a level to the top (and deactivate them).
313
314    ///This function lifts all nodes on and above level \c l to \c maxLevel(),
315    ///and
316    ///also deactivates them.
317    void liftToTop(int l)
318    {
319      const Vit f=_first[l];
320      const Vit tl=_first[_max_level];
321      for(Vit i=f;i!=tl;++i)
322        _level[*i]=_max_level;
323      for(int i=l;i<=_max_level;i++)
324        {
325          _first[i]=f;
326          _last_active[i]=f-1;
327        }
328      for(_highest_active=l-1;
329          _highest_active>=0 &&
330            _last_active[_highest_active]<_first[_highest_active];
331          _highest_active--) ;
332    }
333   
334  private:
335    int _init_lev;
336    Vit _init_num;
337
338  public:
339
340    ///\name Initialization
341    ///Using this function you can initialize the levels of the item.
342    ///\n
343    ///This initializatios is started with calling \c initStart().
344    ///Then the
345    ///items should be listed levels by levels statring with the lowest one
346    ///(with level 0). This is done by using \c initAddItem()
347    ///and \c initNewLevel(). Finally \c initFinish() must be called.
348    ///The items not listed will be put on the highest level.
349    ///@{
350
351    ///Start the initialization process.
352
353    void initStart()
354    {
355      _init_lev=0;
356      _init_num=_items.begin();
357      _first[0]=_items.begin();
358      _last_active[0]=_items.begin()-1;
359      Vit n=_items.begin();
360      for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
361        {
362          *n=i;
363          _where[i]=n;
364          _level[i]=_max_level;
365          ++n;
366        }
367    }
368
369    ///Add an item to the current level.
370
371    void initAddItem(Item i)
372    {
373     swap(_where[i],_init_num);
374      _level[i]=_init_lev;
375      ++_init_num;
376    }
377
378    ///Start a new level.
379
380    ///Start a new level.
381    ///It shouldn't be used before the items on level 0 are listed.
382    void initNewLevel()
383    {
384      _init_lev++;
385      _first[_init_lev]=_init_num;
386      _last_active[_init_lev]=_init_num-1;
387    }
388
389    ///Finalize the initialization process.
390
391    void initFinish()
392    {
393      for(_init_lev++;_init_lev<=_max_level;_init_lev++)
394        {
395          _first[_init_lev]=_init_num;
396          _last_active[_init_lev]=_init_num-1;
397        }
398      _first[_max_level+1]=_items.begin()+_item_num;
399      _last_active[_max_level+1]=_items.begin()+_item_num-1;
400    }
401
402    ///@}
403
404  };
405
406} //END OF NAMESPACE LEMON
407
408#endif
409
Note: See TracBrowser for help on using the repository browser.