lemon/elevator.h
changeset 598 a3402913cffe
parent 519 c786cd201266
child 581 aa1804409f29
equal deleted inserted replaced
6:5aae4055886e 7:25c16650089f
    44   ///Each item is either \em active or not, and you can also choose a
    44   ///Each item is either \em active or not, and you can also choose a
    45   ///highest level active item.
    45   ///highest level active item.
    46   ///
    46   ///
    47   ///\sa LinkedElevator
    47   ///\sa LinkedElevator
    48   ///
    48   ///
    49   ///\param Graph Type of the underlying graph.
    49   ///\param GR Type of the underlying graph.
    50   ///\param Item Type of the items the data is assigned to (Graph::Node,
    50   ///\param Item Type of the items the data is assigned to (\c GR::Node,
    51   ///Graph::Arc, Graph::Edge).
    51   ///\c GR::Arc or \c GR::Edge).
    52   template<class Graph, class Item>
    52   template<class GR, class Item>
    53   class Elevator
    53   class Elevator
    54   {
    54   {
    55   public:
    55   public:
    56 
    56 
    57     typedef Item Key;
    57     typedef Item Key;
    58     typedef int Value;
    58     typedef int Value;
    59 
    59 
    60   private:
    60   private:
    61 
    61 
    62     typedef Item *Vit;
    62     typedef Item *Vit;
    63     typedef typename ItemSetTraits<Graph,Item>::template Map<Vit>::Type VitMap;
    63     typedef typename ItemSetTraits<GR,Item>::template Map<Vit>::Type VitMap;
    64     typedef typename ItemSetTraits<Graph,Item>::template Map<int>::Type IntMap;
    64     typedef typename ItemSetTraits<GR,Item>::template Map<int>::Type IntMap;
    65 
    65 
    66     const Graph &_g;
    66     const GR &_g;
    67     int _max_level;
    67     int _max_level;
    68     int _item_num;
    68     int _item_num;
    69     VitMap _where;
    69     VitMap _where;
    70     IntMap _level;
    70     IntMap _level;
    71     std::vector<Item> _items;
    71     std::vector<Item> _items;
   103     ///Constructor with given maximum level.
   103     ///Constructor with given maximum level.
   104     ///
   104     ///
   105     ///\param graph The underlying graph.
   105     ///\param graph The underlying graph.
   106     ///\param max_level The maximum allowed level.
   106     ///\param max_level The maximum allowed level.
   107     ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
   107     ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
   108     Elevator(const Graph &graph,int max_level) :
   108     Elevator(const GR &graph,int max_level) :
   109       _g(graph),
   109       _g(graph),
   110       _max_level(max_level),
   110       _max_level(max_level),
   111       _item_num(_max_level),
   111       _item_num(_max_level),
   112       _where(graph),
   112       _where(graph),
   113       _level(graph,0),
   113       _level(graph,0),
   120     ///Constructor.
   120     ///Constructor.
   121     ///
   121     ///
   122     ///\param graph The underlying graph.
   122     ///\param graph The underlying graph.
   123     ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
   123     ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
   124     ///where \c max_level is equal to the number of labeled items in the graph.
   124     ///where \c max_level is equal to the number of labeled items in the graph.
   125     Elevator(const Graph &graph) :
   125     Elevator(const GR &graph) :
   126       _g(graph),
   126       _g(graph),
   127       _max_level(countItems<Graph, Item>(graph)),
   127       _max_level(countItems<GR, Item>(graph)),
   128       _item_num(_max_level),
   128       _item_num(_max_level),
   129       _where(graph),
   129       _where(graph),
   130       _level(graph,0),
   130       _level(graph,0),
   131       _items(_max_level),
   131       _items(_max_level),
   132       _first(_max_level+2),
   132       _first(_max_level+2),
   428       _init_lev=0;
   428       _init_lev=0;
   429       _init_num=&_items[0];
   429       _init_num=&_items[0];
   430       _first[0]=&_items[0];
   430       _first[0]=&_items[0];
   431       _last_active[0]=&_items[0]-1;
   431       _last_active[0]=&_items[0]-1;
   432       Vit n=&_items[0];
   432       Vit n=&_items[0];
   433       for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
   433       for(typename ItemSetTraits<GR,Item>::ItemIt i(_g);i!=INVALID;++i)
   434         {
   434         {
   435           *n=i;
   435           *n=i;
   436           _where.set(i,n);
   436           _where.set(i,n);
   437           _level.set(i,_max_level);
   437           _level.set(i,_max_level);
   438           ++n;
   438           ++n;
   487   ///Each item is either \em active or not, and you can also choose a
   487   ///Each item is either \em active or not, and you can also choose a
   488   ///highest level active item.
   488   ///highest level active item.
   489   ///
   489   ///
   490   ///\sa Elevator
   490   ///\sa Elevator
   491   ///
   491   ///
   492   ///\param Graph Type of the underlying graph.
   492   ///\param GR Type of the underlying graph.
   493   ///\param Item Type of the items the data is assigned to (Graph::Node,
   493   ///\param Item Type of the items the data is assigned to (\c GR::Node,
   494   ///Graph::Arc, Graph::Edge).
   494   ///\c GR::Arc or \c GR::Edge).
   495   template <class Graph, class Item>
   495   template <class GR, class Item>
   496   class LinkedElevator {
   496   class LinkedElevator {
   497   public:
   497   public:
   498 
   498 
   499     typedef Item Key;
   499     typedef Item Key;
   500     typedef int Value;
   500     typedef int Value;
   501 
   501 
   502   private:
   502   private:
   503 
   503 
   504     typedef typename ItemSetTraits<Graph,Item>::
   504     typedef typename ItemSetTraits<GR,Item>::
   505     template Map<Item>::Type ItemMap;
   505     template Map<Item>::Type ItemMap;
   506     typedef typename ItemSetTraits<Graph,Item>::
   506     typedef typename ItemSetTraits<GR,Item>::
   507     template Map<int>::Type IntMap;
   507     template Map<int>::Type IntMap;
   508     typedef typename ItemSetTraits<Graph,Item>::
   508     typedef typename ItemSetTraits<GR,Item>::
   509     template Map<bool>::Type BoolMap;
   509     template Map<bool>::Type BoolMap;
   510 
   510 
   511     const Graph &_graph;
   511     const GR &_graph;
   512     int _max_level;
   512     int _max_level;
   513     int _item_num;
   513     int _item_num;
   514     std::vector<Item> _first, _last;
   514     std::vector<Item> _first, _last;
   515     ItemMap _prev, _next;
   515     ItemMap _prev, _next;
   516     int _highest_active;
   516     int _highest_active;
   523     ///Constructor with given maximum level.
   523     ///Constructor with given maximum level.
   524     ///
   524     ///
   525     ///\param graph The underlying graph.
   525     ///\param graph The underlying graph.
   526     ///\param max_level The maximum allowed level.
   526     ///\param max_level The maximum allowed level.
   527     ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
   527     ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
   528     LinkedElevator(const Graph& graph, int max_level)
   528     LinkedElevator(const GR& graph, int max_level)
   529       : _graph(graph), _max_level(max_level), _item_num(_max_level),
   529       : _graph(graph), _max_level(max_level), _item_num(_max_level),
   530         _first(_max_level + 1), _last(_max_level + 1),
   530         _first(_max_level + 1), _last(_max_level + 1),
   531         _prev(graph), _next(graph),
   531         _prev(graph), _next(graph),
   532         _highest_active(-1), _level(graph), _active(graph) {}
   532         _highest_active(-1), _level(graph), _active(graph) {}
   533 
   533 
   536     ///Constructor.
   536     ///Constructor.
   537     ///
   537     ///
   538     ///\param graph The underlying graph.
   538     ///\param graph The underlying graph.
   539     ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
   539     ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
   540     ///where \c max_level is equal to the number of labeled items in the graph.
   540     ///where \c max_level is equal to the number of labeled items in the graph.
   541     LinkedElevator(const Graph& graph)
   541     LinkedElevator(const GR& graph)
   542       : _graph(graph), _max_level(countItems<Graph, Item>(graph)),
   542       : _graph(graph), _max_level(countItems<GR, Item>(graph)),
   543         _item_num(_max_level),
   543         _item_num(_max_level),
   544         _first(_max_level + 1), _last(_max_level + 1),
   544         _first(_max_level + 1), _last(_max_level + 1),
   545         _prev(graph, INVALID), _next(graph, INVALID),
   545         _prev(graph, INVALID), _next(graph, INVALID),
   546         _highest_active(-1), _level(graph), _active(graph) {}
   546         _highest_active(-1), _level(graph), _active(graph) {}
   547 
   547 
   933 
   933 
   934       for (int i = 0; i <= _max_level; ++i) {
   934       for (int i = 0; i <= _max_level; ++i) {
   935         _first[i] = _last[i] = INVALID;
   935         _first[i] = _last[i] = INVALID;
   936       }
   936       }
   937       _init_level = 0;
   937       _init_level = 0;
   938       for(typename ItemSetTraits<Graph,Item>::ItemIt i(_graph);
   938       for(typename ItemSetTraits<GR,Item>::ItemIt i(_graph);
   939           i != INVALID; ++i) {
   939           i != INVALID; ++i) {
   940         _level.set(i, _max_level);
   940         _level.set(i, _max_level);
   941         _active.set(i, false);
   941         _active.set(i, false);
   942       }
   942       }
   943     }
   943     }