1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
|
-- Copyright 2011 by Jannis Pohlmann
-- Copyright 2012 by Till Tantau
--
-- This file may be distributed an/or modified
--
-- 1. under the LaTeX Project Public License and/or
-- 2. under the GNU Public License
--
-- See the file doc/generic/pgf/licenses/LICENSE for more information
-- @release $Header: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/lib/PriorityQueue.lua,v 1.1 2012/11/27 17:24:26 tantau Exp $
---
-- A PriorityQueue supports operations for quickly finding the minimum from a set of elements
--
-- Its implementation is based on (simplified) Fibonacci heaps.
local PriorityQueue = {}
PriorityQueue.__index = PriorityQueue
-- Namespace
local lib = require "pgf.gd.lib"
lib.PriorityQueue = PriorityQueue
-- Local declarations
local FibonacciHeap = {}
local FibonacciHeapNode = {}
--- Creates a new priority queue
--
-- @return The newly created queue
function PriorityQueue.new()
local queue = {
heap = FibonacciHeap.new(),
nodes = {},
values = {},
}
setmetatable(queue, PriorityQueue)
return queue
end
--- Add an element with a certain priority to the queue
--
-- @param value An object
-- @param priority Its priority
function PriorityQueue:enqueue(value, priority)
local node = self.heap:insert(priority)
self.nodes[value] = node
self.values[node] = value
end
--- Removes the element with the minimum priority from the queue
--
-- @return The element with the minimum priority
function PriorityQueue:dequeue()
local node = self.heap:extractMinimum()
if node then
local value = self.values[node]
self.nodes[value] = nil
self.values[node] = nil
return value
else
return nil
end
end
--- Lower the priority of an element of a queue
--
-- @param value An object
-- @param priority A new priority, which must be lower than the old priority
function PriorityQueue:updatePriority(value, priority)
local node = self.nodes[value]
assert(node, 'updating the priority of ' .. tostring(value) .. ' failed because it is not in the priority queue')
self.heap:updateValue(node, priority)
end
--- Tests, whether the queue is empty
--
-- @return True, if the queue is empty
function PriorityQueue:isEmpty()
return #self.heap.trees == 0
end
-- Internals: An implementation of fibonacci heaps.
FibonacciHeap.__index = FibonacciHeap
function FibonacciHeap.new()
local heap = {
trees = trees or {},
minimum = nil,
}
setmetatable(heap, FibonacciHeap)
return heap
end
function FibonacciHeap:insert(value)
local node = FibonacciHeapNode.new(value)
local heap = FibonacciHeap.new()
table.insert(heap.trees, node)
self:merge(heap)
return node
end
function FibonacciHeap:merge(other)
for _, tree in ipairs(other.trees) do
table.insert(self.trees, tree)
end
self:updateMinimum()
end
function FibonacciHeap:extractMinimum()
if self.minimum then
local minimum = self:removeTableElement(self.trees, self.minimum)
for _, child in ipairs(minimum.children) do
child.root = child
table.insert(self.trees, child)
end
local same_degrees_found = true
while same_degrees_found do
same_degrees_found = false
local degrees = {}
for _, root in ipairs(self.trees) do
local degree = root:getDegree()
if degrees[degree] then
if root.value < degrees[degree].value then
self:linkRoots(root, degrees[degree])
else
self:linkRoots(degrees[degree], root)
end
degrees[degree] = nil
same_degrees_found = true
break
else
degrees[degree] = root
end
end
end
self:updateMinimum()
return minimum
end
end
function FibonacciHeap:updateValue(node, value)
local old_value = node.value
local new_value = value
if new_value <= old_value then
self:decreaseValue(node, value)
else
assert(false, 'FibonacciHeap:increaseValue is not implemented yet')
end
end
function FibonacciHeap:decreaseValue(node, value)
assert(value <= node.value)
node.value = value
if node.value < node.parent.value then
local parent = node.parent
self:cutFromParent(node)
if not parent:isRoot() then
if parent.marked then
self:cutFromParent(parent)
else
parent.marked = true
end
end
end
if node.value < self.minimum.value then
self.minimum = node
end
end
function FibonacciHeap:delete(node)
self:decreaseValue(node, -math.huge)
self:extractMinimum()
end
function FibonacciHeap:linkRoots(root, child)
child.root = root
child.parent = root
child = self:removeTableElement(self.trees, child)
table.insert(root.children, child)
return root
end
function FibonacciHeap:cutFromParent(node)
local parent = node.parent
node.root = node
node.parent = node
node.marked = false
node = self:removeTableElement(parent.children, node)
table.insert(self.trees, node)
end
function FibonacciHeap:updateMinimum()
self.minimum = self.trees[1]
for _, root in ipairs(self.trees) do
if root.value < self.minimum.value then
self.minimum = root
end
end
end
function FibonacciHeap:removeTableElement(input_table, element)
for i = 1, #input_table do
if input_table[i] == element then
return table.remove(input_table, i)
end
end
end
-- Now come the nodes
FibonacciHeapNode.__index = FibonacciHeapNode
function FibonacciHeapNode.new(value, root, parent)
local node = {
value = value,
children = {},
marked = false,
root = nil,
parent = nil,
}
setmetatable(node, FibonacciHeapNode)
if root then
node.root = root
node.parent = parent
else
node.root = node
node.parent = node
end
return node
end
function FibonacciHeapNode:addChild(value)
local child = FibonacciHeapNode.new(value, self.root, self)
table.insert(self.children, child)
end
function FibonacciHeapNode:getDegree()
return #self.children
end
function FibonacciHeapNode:setRoot(root)
self.root = root
if root == self then
self.parent = root
end
if #self.children > 0 then
for _, child in ipairs(self.children) do
child.root = root
end
end
end
function FibonacciHeapNode:isRoot()
return self.root == self
end
-- done
return PriorityQueue
|