The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.
The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.
The ResGraphAdaptor is based on this composition.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_LINEAR_HEAP_H
20 #define LEMON_LINEAR_HEAP_H
24 ///\brief Binary Heap implementation.
34 /// \brief A Linear Heap implementation.
36 /// This class implements the \e linear \e heap data structure. A \e heap
37 /// is a data structure for storing items with specified values called \e
38 /// priorities in such a way that finding the item with minimum priority is
39 /// efficient. The linear heap is very simple implementation, it can store
40 /// only integer priorities and it stores for each priority in the [0..C]
41 /// range a list of items. So it should be used only when the priorities
42 /// are small. It is not intended to use as dijkstra heap.
44 /// \param _Item Type of the items to be stored.
45 /// \param _ItemIntMap A read and writable Item int map, used internally
46 /// to handle the cross references.
47 /// \param minimize If the given parameter is true then the heap gives back
48 /// the lowest priority.
49 template <typename _Item, typename _ItemIntMap, bool minimize = true >
55 typedef std::pair<Item, Prio> Pair;
56 typedef _ItemIntMap ItemIntMap;
58 /// \brief Type to represent the items states.
60 /// Each Item element have a state associated to it. It may be "in heap",
61 /// "pre heap" or "post heap". The latter two are indifferent from the
62 /// heap's point of view, but may be useful to the user.
64 /// The ItemIntMap \e should be initialized in such way that it maps
65 /// PRE_HEAP (-1) to any element to be put in the heap...
73 /// \brief The constructor.
76 /// \param _index should be given to the constructor, since it is used
77 /// internally to handle the cross references. The value of the map
78 /// should be PRE_HEAP (-1) for each element.
79 explicit LinearHeap(ItemIntMap &_index) : index(_index), minimal(0) {}
81 /// The number of items stored in the heap.
83 /// \brief Returns the number of items stored in the heap.
84 int size() const { return data.size(); }
86 /// \brief Checks if the heap stores no items.
88 /// Returns \c true if and only if the heap stores no items.
89 bool empty() const { return data.empty(); }
91 /// \brief Make empty this heap.
93 /// Make empty this heap.
95 for (int i = 0; i < (int)data.size(); ++i) {
96 index[data[i].item] = -2;
98 data.clear(); first.clear(); minimal = 0;
103 void relocate_last(int idx) {
104 if (idx + 1 < (int)data.size()) {
105 data[idx] = data.back();
106 if (data[idx].prev != -1) {
107 data[data[idx].prev].next = idx;
109 first[data[idx].value] = idx;
111 if (data[idx].next != -1) {
112 data[data[idx].next].prev = idx;
114 index[data[idx].item] = idx;
119 void unlace(int idx) {
120 if (data[idx].prev != -1) {
121 data[data[idx].prev].next = data[idx].next;
123 first[data[idx].value] = data[idx].next;
125 if (data[idx].next != -1) {
126 data[data[idx].next].prev = data[idx].prev;
131 if ((int)first.size() <= data[idx].value) {
132 first.resize(data[idx].value + 1, -1);
134 data[idx].next = first[data[idx].value];
135 if (data[idx].next != -1) {
136 data[data[idx].next].prev = idx;
138 first[data[idx].value] = idx;
143 /// \brief Insert a pair of item and priority into the heap.
145 /// Adds \c p.first to the heap with priority \c p.second.
146 /// \param p The pair to insert.
147 void push(const Pair& p) {
148 push(p.first, p.second);
151 /// \brief Insert an item into the heap with the given priority.
153 /// Adds \c i to the heap with priority \c p.
154 /// \param i The item to insert.
155 /// \param p The priority of the item.
156 void push(const Item &i, const Prio &p) {
157 int idx = data.size();
159 data.push_back(LinearItem(i, p));
166 /// \brief Returns the item with minimum priority.
168 /// This method returns the item with minimum priority.
169 /// \pre The heap must be nonempty.
171 while (first[minimal] == -1) {
174 return data[first[minimal]].item;
177 /// \brief Returns the minimum priority.
179 /// It returns the minimum priority.
180 /// \pre The heap must be nonempty.
182 while (first[minimal] == -1) {
188 /// \brief Deletes the item with minimum priority.
190 /// This method deletes the item with minimum priority from the heap.
191 /// \pre The heap must be non-empty.
193 while (first[minimal] == -1) {
196 int idx = first[minimal];
197 index[data[idx].item] = -2;
202 /// \brief Deletes \c i from the heap.
204 /// This method deletes item \c i from the heap, if \c i was
205 /// already stored in the heap.
206 /// \param i The item to erase.
207 void erase(const Item &i) {
209 index[data[idx].item] = -2;
215 /// \brief Returns the priority of \c i.
217 /// This function returns the priority of item \c i.
218 /// \pre \c i must be in the heap.
219 /// \param i The item.
220 Prio operator[](const Item &i) const {
222 return data[idx].value;
225 /// \brief \c i gets to the heap with priority \c p independently
226 /// if \c i was already there.
228 /// This method calls \ref push(\c i, \c p) if \c i is not stored
229 /// in the heap and sets the priority of \c i to \c p otherwise.
230 /// \param i The item.
231 /// \param p The priority.
232 void set(const Item &i, const Prio &p) {
236 } else if (p > data[idx].value) {
243 /// \brief Decreases the priority of \c i to \c p.
245 /// This method decreases the priority of item \c i to \c p.
246 /// \pre \c i must be stored in the heap with priority at least \c
247 /// p relative to \c Compare.
248 /// \param i The item.
249 /// \param p The priority.
250 void decrease(const Item &i, const Prio &p) {
260 /// \brief Increases the priority of \c i to \c p.
262 /// This method sets the priority of item \c i to \c p.
263 /// \pre \c i must be stored in the heap with priority at most \c
264 /// p relative to \c Compare.
265 /// \param i The item.
266 /// \param p The priority.
267 void increase(const Item &i, const Prio &p) {
274 /// \brief Returns if \c item is in, has already been in, or has
275 /// never been in the heap.
277 /// This method returns PRE_HEAP if \c item has never been in the
278 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
279 /// otherwise. In the latter case it is possible that \c item will
280 /// get back to the heap again.
281 /// \param i The item.
282 state_enum state(const Item &i) const {
284 if (idx >= 0) idx = 0;
285 return state_enum(idx);
288 /// \brief Sets the state of the \c item in the heap.
290 /// Sets the state of the \c item in the heap. It can be used to
291 /// manually clear the heap when it is important to achive the
292 /// better time complexity.
293 /// \param i The item.
294 /// \param st The state. It should not be \c IN_HEAP.
295 void state(const Item& i, state_enum st) {
299 if (state(i) == IN_HEAP) {
312 LinearItem(const Item& _item, int _value)
313 : item(_item), value(_value) {}
322 std::vector<int> first;
323 std::vector<LinearItem> data;
326 }; // class LinearHeap
329 template <typename _Item, typename _ItemIntMap>
330 class LinearHeap<_Item, _ItemIntMap, false> {
335 typedef std::pair<Item, Prio> Pair;
336 typedef _ItemIntMap ItemIntMap;
346 explicit LinearHeap(ItemIntMap &_index) : index(_index), maximal(-1) {}
348 int size() const { return data.size(); }
349 bool empty() const { return data.empty(); }
352 for (int i = 0; i < (int)data.size(); ++i) {
353 index[data[i].item] = -2;
355 data.clear(); first.clear(); maximal = -1;
360 void relocate_last(int idx) {
361 if (idx + 1 != (int)data.size()) {
362 data[idx] = data.back();
363 if (data[idx].prev != -1) {
364 data[data[idx].prev].next = idx;
366 first[data[idx].value] = idx;
368 if (data[idx].next != -1) {
369 data[data[idx].next].prev = idx;
371 index[data[idx].item] = idx;
376 void unlace(int idx) {
377 if (data[idx].prev != -1) {
378 data[data[idx].prev].next = data[idx].next;
380 first[data[idx].value] = data[idx].next;
382 if (data[idx].next != -1) {
383 data[data[idx].next].prev = data[idx].prev;
388 if ((int)first.size() <= data[idx].value) {
389 first.resize(data[idx].value + 1, -1);
391 data[idx].next = first[data[idx].value];
392 if (data[idx].next != -1) {
393 data[data[idx].next].prev = idx;
395 first[data[idx].value] = idx;
401 void push(const Pair& p) {
402 push(p.first, p.second);
405 void push(const Item &i, const Prio &p) {
406 int idx = data.size();
408 data.push_back(LinearItem(i, p));
410 if (data[idx].value > maximal) {
411 maximal = data[idx].value;
416 while (first[maximal] == -1) {
419 return data[first[maximal]].item;
423 while (first[maximal] == -1) {
430 while (first[maximal] == -1) {
433 int idx = first[maximal];
434 index[data[idx].item] = -2;
439 void erase(const Item &i) {
441 index[data[idx].item] = -2;
446 Prio operator[](const Item &i) const {
448 return data[idx].value;
451 void set(const Item &i, const Prio &p) {
455 } else if (p > data[idx].value) {
462 void decrease(const Item &i, const Prio &p) {
472 void increase(const Item &i, const Prio &p) {
479 state_enum state(const Item &i) const {
481 if (idx >= 0) idx = 0;
482 return state_enum(idx);
485 void state(const Item& i, state_enum st) {
489 if (state(i) == IN_HEAP) {
502 LinearItem(const Item& _item, int _value)
503 : item(_item), value(_value) {}
512 std::vector<int> first;
513 std::vector<LinearItem> data;
516 }; // class LinearHeap