# HG changeset patch
# User alpar
# Date 1169226915 0
# Node ID c06a956a92faf2d99dfaf0300e070945b7bc6729
# Parent  bfcaad2b84e8ba4b6e0f5c1307074bdf445a65ea
elevator.h: A class for handling item labels in push-relabel type algorithms

diff -r bfcaad2b84e8 -r c06a956a92fa lemon/Makefile.am
--- a/lemon/Makefile.am	Fri Jan 12 16:29:06 2007 +0000
+++ b/lemon/Makefile.am	Fri Jan 19 17:15:15 2007 +0000
@@ -50,6 +50,7 @@
 	lemon/dimacs.h \
 	lemon/edge_set.h \
 	lemon/edmonds_karp.h \
+	lemon/elevator.h \
 	lemon/eps.h \
 	lemon/error.h \
 	lemon/fib_heap.h \
diff -r bfcaad2b84e8 -r c06a956a92fa lemon/elevator.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/elevator.h	Fri Jan 19 17:15:15 2007 +0000
@@ -0,0 +1,329 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2006
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_ELEVATOR_H
+#define LEMON_ELEVATOR_H
+
+///\ingroup auxdat
+///\file
+///\brief Elevator class
+///
+///Elevator class implements an efficient data structure
+///for labeling items in push-relabel type algorithms.
+///
+
+#include <test/test_tools.h>
+namespace lemon {
+
+  ///Class for hangling "labels" in push-relabel type algorithms.
+  
+  ///A class for hangling "labels" in push-relabel type algorithms.
+  ///
+  ///\ingroup auxdat
+  ///Using this class you can assign "labels" (nonnegativ integer numbers)
+  ///to the edges or nodes of a graph, manipulate and query them through
+  ///operations typically arising in "push-relabel" type algorithms.
+  ///
+  ///Each item is either \em active or not, and you can also choose a
+  ///highest level active item.
+  ///
+  ///\param Graph the underlying graph type
+  ///\param Item Type of the items the data is assigned to (Graph::Node,
+  ///Graph::Edge, Graph::UEdge)
+  template<class Graph, class Item>
+  class Elevator 
+  {
+  public:
+    typedef typename std::vector<Item>::iterator Vit;
+    typedef DefaultMap<Graph,Item,Vit> VitMap;
+    typedef DefaultMap<Graph,Item,int> IntMap;
+
+    const Graph &_g;
+    int _max_level;
+    int _item_num;
+    VitMap _where;
+    IntMap _level;
+    std::vector<Item> _items;
+    std::vector<Vit> _first;
+    std::vector<Vit> _last_active;
+
+    int _highest_active;
+
+    void copy(Item i, Vit p)
+    {
+      _where[*p=i]=p;
+    }
+    void copy(Vit s, Vit p)
+    {
+      if(s!=p) 
+	{
+	  Item i=*s;
+	  *p=i;
+	  _where[i]=p;
+	}
+    }
+    void swap(Vit i, Vit j)
+    {
+      Item ti=*i;
+      Vit ct = _where[ti];
+      _where[ti]=_where[*i=*j];
+      _where[*j]=ct;
+      *j=ti;
+    }
+    
+    void checkDs() 
+    {
+      for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
+	{
+	  Vit w=_where[i];
+	  int l=_level[i];
+	  check(*w==i,"GEBASZ: CORRUPT DS");
+	  check(_first[l]<=w,"GEBASZ: CORRUPT DS");
+	  check(_first[l+1]>w,"GEBASZ: CORRUPT DS");
+	}
+      check(_highest_active<0 ||
+	    _first[_highest_active]<=_last_active[_highest_active],
+	    "GEBASZ: CORRUPT DS");
+    }
+
+  public:
+    ///Constructor with given maximum level.
+
+    ///Constructor with given maximum level.
+    ///
+    ///\param g The underlying graph
+    ///\param max_level Set the range of the possible labels to
+    ///[0...\c max_level]
+    Elevator(const Graph &g,int max_level) :
+      _g(g),
+      _max_level(max_level),
+      _item_num(_max_level),
+      _where(g),
+      _level(g,0),
+      _items(_max_level),
+      _first(_max_level+2),
+      _last_active(_max_level+2),
+      _highest_active(-1) {}
+    ///Constructor.
+
+    ///Constructor.
+    ///
+    ///\param g The underlying graph
+    ///The range of the possible labels is [0...\c max_level],
+    ///where \c max_level is equal to the number of labeled items in the graph.
+    Elevator(const Graph &g) :
+      _g(g),
+      _max_level(countItems<Graph, Item>(g)),
+      _item_num(_max_level),
+      _where(g),
+      _level(g,0),
+      _items(_max_level),
+      _first(_max_level+2),
+      _last_active(_max_level+2),
+      _highest_active(-1)
+    {
+    }
+  
+    ///Activate item \c i.
+    void activate(Item i)
+    {
+      const int l=_level[i];
+      swap(_where[i],++_last_active[l]);
+      if(l>_highest_active) _highest_active=l;
+    }
+  
+    ///Deactivate item \c i.
+    void deactivate(Item i)  
+    {
+      swap(_where[i],_last_active[_level[i]]--);
+      _last_active[_level[i]]--;
+      while(_highest_active>=0 &&
+	    _last_active[_highest_active]<_first[_highest_active])
+	_highest_active--;
+    }
+
+    ///Query whether item \c i is active
+    bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; }
+    
+    ///Return the level of item \c i.
+    int operator[](Item i) const { return _level[i]; }
+
+    ///Returns an active item on level \c l.
+
+    ///Returns an active item on level \c l.
+    ///
+    ///Returns an active item on level \c l or \ref INVALID if there is no such
+    ///an item. (\c l must be from the range [0...\c max_level].
+    Item operator[](int l) const
+    { 
+      return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
+    }
+
+    ///Return the number of items on level \c l.
+    int &onLevel(int l)
+    {
+      return _first[l+1]-_first[l];
+    }
+    ///Return the number of active items on level \c l.
+    int &activesOnLevel(int l)
+    {
+      return _last_active[l]-_first[l]+1;
+    }
+    ///Return the maximum allowed level.
+    int maxLevel() const 
+    {
+      return _max_level;
+    }    
+
+    ///\name Highest Active Item
+    ///Functions for working with the highest level
+    ///active item.
+
+    ///@{
+
+    ///Return a highest level active item.
+  
+    ///Return a highest level active item.
+    ///
+    ///\return the highest level active item or INVALID if there is no active
+    ///item.
+    Item highestActive() const 
+    {
+      return _highest_active>=0?*_last_active[_highest_active]:INVALID;
+    }
+
+    ///Return a highest active level.
+
+    ///Return a highest active level.
+    ///
+    ///\return the level of the highest active item or -1 if there is no active
+    ///item.
+    Item highestActiveLevel() const 
+    {
+      return _highest_active;
+    }
+
+    ///Lift the highest active item by one.
+
+    ///Lift the item returned by highestActive() by one.
+    ///
+    void liftHighestActive() 
+    {
+      ++_level[*_last_active[_highest_active]];
+      swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
+      --_first[++_highest_active];
+    }
+
+    ///Lift the highest active item.
+
+    ///Lift the item returned by highestActive() to level \c new_level.
+    ///
+    ///
+    void liftHighestActiveTo(int new_level) 
+    {
+      const Item li = *_last_active[_highest_active];
+      
+      copy(--_first[_highest_active+1],_last_active[_highest_active]--);
+      for(int l=_highest_active+1;l<new_level;l++)
+	{
+	  copy(--_first[l+1],_first[l]);
+	  --_last_active[l];
+	}
+      copy(li,_first[new_level]);
+      _level[li]=new_level;
+	  _highest_active=new_level;
+    }
+    
+    ///@}
+    
+  private:
+    int _init_lev;
+    Vit _init_num;
+
+  public:
+
+    ///\name Initialization
+    ///Using this function you can initialize the levels of the item.
+    ///\n
+    ///This initializatios is started with calling \c initStart().
+    ///Then the
+    ///items should be listed levels by levels statring with the lowest one
+    ///(with level 0). This is done by using \c initAddItem()
+    ///and \c initNewLevel(). Finally \c initFinish() must be called.
+    ///The items not listes will be put on the highest level.
+    ///@{
+
+    ///Starts the initialization process.
+
+    void initStart() 
+    {
+      _init_lev=0;
+      _init_num=_items.begin();
+      _first[0]=_items.begin();
+      _last_active[0]=_items.begin()-1;
+      Vit n=_items.begin();
+      for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
+	{
+	  *n=i;
+	  _where[i]=n;
+	  _level[i]=_max_level;
+	  ++n;
+	}
+    }
+
+    ///Add an item to the current level.
+
+    void initAddItem(Item i)
+    { 
+     swap(_where[i],_init_num);
+      _level[i]=_init_lev;
+      ++_init_num;
+    }
+
+    ///Start a new level.
+
+    ///Start a new level.
+    ///It shouldn't be used before the items on level 0 are listed.
+    void initNewLevel() 
+    {
+      _init_lev++;
+      _first[_init_lev]=_init_num;
+      _last_active[_init_lev]=_init_num-1;
+    }
+
+    ///Finalizes the initialization process.
+
+    void initFinish()
+    {
+      for(_init_lev++;_init_lev<=_max_level;_init_lev++)
+	{
+	  _first[_init_lev]=_init_num;
+	  _last_active[_init_lev]=_init_num-1;
+	}
+      _first[_max_level+1]=_items.begin()+_item_num;
+      _last_active[_max_level+1]=_items.begin()+_item_num-1;
+    }
+
+    ///@}
+
+  };
+
+} //END OF NAMESPACE LEMON
+
+#endif
+