Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
PQ.h
Go to the documentation of this file.
1
33#pragma once
34
36#include <ogdf/basic/basic.h>
39
40#include <functional>
41#include <unordered_map>
42
43namespace ogdf {
44namespace matching_blossom {
45
49template<typename E, typename TWeight, typename C = std::less<TWeight>,
50 template<typename, class> class Impl = PairingHeap>
52 : public PrioritizedQueue<E, TWeight, C, Impl>,
53 public KeyIteratorContainer<E, typename PrioritizedQueue<E, TWeight, C, Impl>::Handle> {
54protected:
57 using Handle = typename SuperQueue::Handle;
58
59 std::unordered_map<E, Handle> m_handles;
60
61public:
63
65 bool contains(const E& element) const { return m_handles.find(element) != m_handles.end(); }
66
67 /*
68 * Returns the priority of the key.
69 * Note that the behaviour is undefined if the key is not present.
70 */
71 TWeight priority(const E& element) const {
72 auto it = m_handles.find(element);
73 OGDF_ASSERT(it != m_handles.end());
74 return this->value(it->second).priority();
75 }
76
81 void push(const E& element, const TWeight priority) {
82 OGDF_ASSERT(!contains(element));
83 m_handles[element] = SuperQueue::push(element, priority);
84 }
85
87 void pop() {
90 }
91
97 void decrease(const E& element, const TWeight priority) {
98 Handle pos = m_handles[element];
100 }
101
103 void merge(ThisQueue& other) {
104 SuperQueue::merge(other);
105 for (auto entry : other.m_handles) {
106 m_handles[entry.first] = entry.second;
107 }
108 other.m_handles.clear();
109 }
110
112 void clear() {
114 m_handles.clear();
115 }
116
119 void remove(const E& e) {
120 OGDF_ASSERT(this->contains(e));
121 this->decrease(e, -infinity<TWeight>());
122 OGDF_ASSERT(this->topElement() == e);
123 this->pop();
124 }
125};
126
127}
128}
Implementation of pairing heap data structure.
Priority queue interface wrapping various heaps.
Basic declarations, included by all source files.
void pop()
Removes the top element from the heap.
const T & value(handle pos) const
Returns the priority of that handle.
void merge(PriorityQueue &other)
Merges in enqueued values of other queue.
void clear()
Removes all the entries from the queue.
Dummy class for scoped iteration of a std::unordered_map.
Definition utils.h:112
A custom priority queue for the blossom algorithm, based on the PrioritizedMapQueue....
Definition PQ.h:53
void remove(const E &e)
Remove e from the queue by decreasing its priority to the minimum. e must be present in the queue; if...
Definition PQ.h:119
void clear()
Removes all elements from this queue.
Definition PQ.h:112
TWeight priority(const E &element) const
Definition PQ.h:71
bool contains(const E &element) const
Returns whether this queue contains that key.
Definition PQ.h:65
void push(const E &element, const TWeight priority)
Adds a new element to the queue.
Definition PQ.h:81
void decrease(const E &element, const TWeight priority)
Decreases the priority of the given element.
Definition PQ.h:97
typename SuperQueue::Handle Handle
Definition PQ.h:57
void pop()
Removes the topmost element from the queue.
Definition PQ.h:87
std::unordered_map< E, Handle > m_handles
Definition PQ.h:59
void merge(ThisQueue &other)
Merge this Priority Queue with another one. The other queue is cleared afterwards.
Definition PQ.h:103
Defines a queue for handling prioritized elements.
const E & topElement() const
Returns the topmost element in the queue.
Handle push(const E &element, const P &priority)
Pushes a new element with the respective priority to the queue.
typename SuperQueue::handle Handle
The type of handle for accessing the elements of this queue.
void decrease(Handle pos, const P &priority)
Utility functions and classes regarding map access and iteration.
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:52
The namespace for all OGDF objects.