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 } |