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_BIN_HEAP_H
20 #define LEMON_BIN_HEAP_H
24 ///\brief Binary Heap implementation.
34 /// A Binary Heap implementation.
36 ///This class implements the \e binary \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. \c Compare specifies the ordering of the priorities. In a heap
40 ///one can change the priority of an item, add or erase an item, etc.
42 ///\param Item Type of the items to be stored.
43 ///\param Prio Type of the priority of the items.
44 ///\param ItemIntMap A read and writable Item int map, used internally
45 ///to handle the cross references.
46 ///\param Compare A class for the ordering of the priorities. The
47 ///default is \c std::less<Prio>.
51 template <typename Item, typename Prio, typename ItemIntMap,
52 typename Compare = std::less<Prio> >
56 typedef Item ItemType;
57 // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
58 typedef Prio PrioType;
59 typedef std::pair<ItemType,PrioType> PairType;
60 typedef ItemIntMap ItemIntMapType;
61 typedef Compare PrioCompare;
63 /// \brief Type to represent the items states.
65 /// Each Item element have a state associated to it. It may be "in heap",
66 /// "pre heap" or "post heap". The latter two are indifferent from the
67 /// heap's point of view, but may be useful to the user.
69 /// The ItemIntMap \e should be initialized in such way that it maps
70 /// PRE_HEAP (-1) to any element to be put in the heap...
78 std::vector<PairType> data;
83 /// \brief The constructor.
86 /// \param _iim should be given to the constructor, since it is used
87 /// internally to handle the cross references. The value of the map
88 /// should be PRE_HEAP (-1) for each element.
89 explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
91 /// \brief The constructor.
94 /// \param _iim should be given to the constructor, since it is used
95 /// internally to handle the cross references. The value of the map
96 /// should be PRE_HEAP (-1) for each element.
98 /// \param _comp The comparator function object.
99 BinHeap(ItemIntMap &_iim, const Compare &_comp)
100 : iim(_iim), comp(_comp) {}
103 /// The number of items stored in the heap.
105 /// \brief Returns the number of items stored in the heap.
106 int size() const { return data.size(); }
108 /// \brief Checks if the heap stores no items.
110 /// Returns \c true if and only if the heap stores no items.
111 bool empty() const { return data.empty(); }
113 /// \brief Make empty this heap.
115 /// Make empty this heap.
117 for (int i = 0; i < (int)data.size(); ++i) {
118 iim.set(data[i].first, POST_HEAP);
124 static int parent(int i) { return (i-1)/2; }
125 static int second_child(int i) { return 2*i+2; }
126 bool less(const PairType &p1, const PairType &p2) const {
127 return comp(p1.second, p2.second);
130 int bubble_up(int hole, PairType p);
131 int bubble_down(int hole, PairType p, int length);
133 void move(const PairType &p, int i) {
139 int n = data.size()-1;
141 iim.set(data[h].first, POST_HEAP);
143 bubble_down(h, data[n], n);
150 /// \brief Insert a pair of item and priority into the heap.
152 /// Adds \c p.first to the heap with priority \c p.second.
153 /// \param p The pair to insert.
154 void push(const PairType &p) {
160 /// \brief Insert an item into the heap with the given heap.
162 /// Adds \c i to the heap with priority \c p.
163 /// \param i The item to insert.
164 /// \param p The priority of the item.
165 void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
167 /// \brief Returns the item with minimum priority relative to \c Compare.
169 /// This method returns the item with minimum priority relative to \c
171 /// \pre The heap must be nonempty.
173 return data[0].first;
176 /// \brief Returns the minimum priority relative to \c Compare.
178 /// It returns the minimum priority relative to \c Compare.
179 /// \pre The heap must be nonempty.
181 return data[0].second;
184 /// \brief Deletes the item with minimum priority relative to \c Compare.
186 /// This method deletes the item with minimum priority relative to \c
187 /// Compare from the heap.
188 /// \pre The heap must be non-empty.
193 /// \brief Deletes \c i from the heap.
195 /// This method deletes item \c i from the heap, if \c i was
196 /// already stored in the heap.
197 /// \param i The item to erase.
198 void erase(const Item &i) {
203 /// \brief Returns the priority of \c i.
205 /// This function returns the priority of item \c i.
206 /// \pre \c i must be in the heap.
207 /// \param i The item.
208 Prio operator[](const Item &i) const {
210 return data[idx].second;
213 /// \brief \c i gets to the heap with priority \c p independently
214 /// if \c i was already there.
216 /// This method calls \ref push(\c i, \c p) if \c i is not stored
217 /// in the heap and sets the priority of \c i to \c p otherwise.
218 /// \param i The item.
219 /// \param p The priority.
220 void set(const Item &i, const Prio &p) {
225 else if( comp(p, data[idx].second) ) {
226 bubble_up(idx, PairType(i,p));
229 bubble_down(idx, PairType(i,p), data.size());
233 /// \brief Decreases the priority of \c i to \c p.
235 /// This method decreases the priority of item \c i to \c p.
236 /// \pre \c i must be stored in the heap with priority at least \c
237 /// p relative to \c Compare.
238 /// \param i The item.
239 /// \param p The priority.
240 void decrease(const Item &i, const Prio &p) {
242 bubble_up(idx, PairType(i,p));
245 /// \brief Increases the priority of \c i to \c p.
247 /// This method sets the priority of item \c i to \c p.
248 /// \pre \c i must be stored in the heap with priority at most \c
249 /// p relative to \c Compare.
250 /// \param i The item.
251 /// \param p The priority.
252 void increase(const Item &i, const Prio &p) {
254 bubble_down(idx, PairType(i,p), data.size());
257 /// \brief Returns if \c item is in, has already been in, or has
258 /// never been in the heap.
260 /// This method returns PRE_HEAP if \c item has never been in the
261 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
262 /// otherwise. In the latter case it is possible that \c item will
263 /// get back to the heap again.
264 /// \param i The item.
265 state_enum state(const Item &i) const {
269 return state_enum(s);
272 /// \brief Sets the state of the \c item in the heap.
274 /// Sets the state of the \c item in the heap. It can be used to
275 /// manually clear the heap when it is important to achive the
276 /// better time complexity.
277 /// \param i The item.
278 /// \param st The state. It should not be \c IN_HEAP.
279 void state(const Item& i, state_enum st) {
283 if (state(i) == IN_HEAP) {
296 template <typename K, typename V, typename M, typename C>
297 int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
298 int par = parent(hole);
299 while( hole>0 && less(p,data[par]) ) {
300 move(data[par],hole);
308 template <typename K, typename V, typename M, typename C>
309 int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
310 int child = second_child(hole);
311 while(child < length) {
312 if( less(data[child-1], data[child]) ) {
315 if( !less(data[child], p) )
317 move(data[child], hole);
319 child = second_child(hole);
322 if( child<length && less(data[child], p) ) {
323 move(data[child], hole);
334 #endif // LEMON_BIN_HEAP_H