COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/elevator.h @ 2346:c06a956a92fa

Last change on this file since 2346:c06a956a92fa was 2346:c06a956a92fa, checked in by Alpar Juttner, 14 years ago

elevator.h: A class for handling item labels in push-relabel type algorithms

File size: 8.1 KB
Line 
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>
31namespace lemon {
32
33  ///Class for hangling "labels" in push-relabel type algorithms.
34 
35  ///A class for hangling "labels" in push-relabel type algorithms.
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   
89    void checkDs()
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      check(_highest_active<0 ||
100            _first[_highest_active]<=_last_active[_highest_active],
101            "GEBASZ: CORRUPT DS");
102    }
103
104  public:
105    ///Constructor with given maximum level.
106
107    ///Constructor with given maximum level.
108    ///
109    ///\param g The underlying graph
110    ///\param max_level Set the range of the possible labels to
111    ///[0...\c max_level]
112    Elevator(const Graph &g,int max_level) :
113      _g(g),
114      _max_level(max_level),
115      _item_num(_max_level),
116      _where(g),
117      _level(g,0),
118      _items(_max_level),
119      _first(_max_level+2),
120      _last_active(_max_level+2),
121      _highest_active(-1) {}
122    ///Constructor.
123
124    ///Constructor.
125    ///
126    ///\param g The underlying graph
127    ///The range of the possible labels is [0...\c max_level],
128    ///where \c max_level is equal to the number of labeled items in the graph.
129    Elevator(const Graph &g) :
130      _g(g),
131      _max_level(countItems<Graph, Item>(g)),
132      _item_num(_max_level),
133      _where(g),
134      _level(g,0),
135      _items(_max_level),
136      _first(_max_level+2),
137      _last_active(_max_level+2),
138      _highest_active(-1)
139    {
140    }
141 
142    ///Activate item \c i.
143    void activate(Item i)
144    {
145      const int l=_level[i];
146      swap(_where[i],++_last_active[l]);
147      if(l>_highest_active) _highest_active=l;
148    }
149 
150    ///Deactivate item \c i.
151    void deactivate(Item i) 
152    {
153      swap(_where[i],_last_active[_level[i]]--);
154      _last_active[_level[i]]--;
155      while(_highest_active>=0 &&
156            _last_active[_highest_active]<_first[_highest_active])
157        _highest_active--;
158    }
159
160    ///Query whether item \c i is active
161    bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; }
162   
163    ///Return the level of item \c i.
164    int operator[](Item i) const { return _level[i]; }
165
166    ///Returns an active item on level \c l.
167
168    ///Returns an active item on level \c l.
169    ///
170    ///Returns an active item on level \c l or \ref INVALID if there is no such
171    ///an item. (\c l must be from the range [0...\c max_level].
172    Item operator[](int l) const
173    {
174      return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
175    }
176
177    ///Return the number of items on level \c l.
178    int &onLevel(int l)
179    {
180      return _first[l+1]-_first[l];
181    }
182    ///Return the number of active items on level \c l.
183    int &activesOnLevel(int l)
184    {
185      return _last_active[l]-_first[l]+1;
186    }
187    ///Return the maximum allowed level.
188    int maxLevel() const
189    {
190      return _max_level;
191    }   
192
193    ///\name Highest Active Item
194    ///Functions for working with the highest level
195    ///active item.
196
197    ///@{
198
199    ///Return a highest level active item.
200 
201    ///Return a highest level active item.
202    ///
203    ///\return the highest level active item or INVALID if there is no active
204    ///item.
205    Item highestActive() const
206    {
207      return _highest_active>=0?*_last_active[_highest_active]:INVALID;
208    }
209
210    ///Return a highest active level.
211
212    ///Return a highest active level.
213    ///
214    ///\return the level of the highest active item or -1 if there is no active
215    ///item.
216    Item highestActiveLevel() const
217    {
218      return _highest_active;
219    }
220
221    ///Lift the highest active item by one.
222
223    ///Lift the item returned by highestActive() by one.
224    ///
225    void liftHighestActive()
226    {
227      ++_level[*_last_active[_highest_active]];
228      swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
229      --_first[++_highest_active];
230    }
231
232    ///Lift the highest active item.
233
234    ///Lift the item returned by highestActive() to level \c new_level.
235    ///
236    ///
237    void liftHighestActiveTo(int new_level)
238    {
239      const Item li = *_last_active[_highest_active];
240     
241      copy(--_first[_highest_active+1],_last_active[_highest_active]--);
242      for(int l=_highest_active+1;l<new_level;l++)
243        {
244          copy(--_first[l+1],_first[l]);
245          --_last_active[l];
246        }
247      copy(li,_first[new_level]);
248      _level[li]=new_level;
249          _highest_active=new_level;
250    }
251   
252    ///@}
253   
254  private:
255    int _init_lev;
256    Vit _init_num;
257
258  public:
259
260    ///\name Initialization
261    ///Using this function you can initialize the levels of the item.
262    ///\n
263    ///This initializatios is started with calling \c initStart().
264    ///Then the
265    ///items should be listed levels by levels statring with the lowest one
266    ///(with level 0). This is done by using \c initAddItem()
267    ///and \c initNewLevel(). Finally \c initFinish() must be called.
268    ///The items not listes will be put on the highest level.
269    ///@{
270
271    ///Starts the initialization process.
272
273    void initStart()
274    {
275      _init_lev=0;
276      _init_num=_items.begin();
277      _first[0]=_items.begin();
278      _last_active[0]=_items.begin()-1;
279      Vit n=_items.begin();
280      for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
281        {
282          *n=i;
283          _where[i]=n;
284          _level[i]=_max_level;
285          ++n;
286        }
287    }
288
289    ///Add an item to the current level.
290
291    void initAddItem(Item i)
292    {
293     swap(_where[i],_init_num);
294      _level[i]=_init_lev;
295      ++_init_num;
296    }
297
298    ///Start a new level.
299
300    ///Start a new level.
301    ///It shouldn't be used before the items on level 0 are listed.
302    void initNewLevel()
303    {
304      _init_lev++;
305      _first[_init_lev]=_init_num;
306      _last_active[_init_lev]=_init_num-1;
307    }
308
309    ///Finalizes the initialization process.
310
311    void initFinish()
312    {
313      for(_init_lev++;_init_lev<=_max_level;_init_lev++)
314        {
315          _first[_init_lev]=_init_num;
316          _last_active[_init_lev]=_init_num-1;
317        }
318      _first[_max_level+1]=_items.begin()+_item_num;
319      _last_active[_max_level+1]=_items.begin()+_item_num-1;
320    }
321
322    ///@}
323
324  };
325
326} //END OF NAMESPACE LEMON
327
328#endif
329
Note: See TracBrowser for help on using the repository browser.