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
|
-- 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$
---
-- This table provides algorithms for computing distances between
-- nodes of a graph (in the sense of path lengths).
local PathLengths = {}
-- Namespace
require("pgf.gd.lib").PathLengths = PathLengths
-- Import
local PriorityQueue = require "pgf.gd.lib.PriorityQueue"
---
-- Performs the Dijkstra algorithm to solve the single-source shortes path problem.
--
-- The algorithm computes the shortest paths from |source| to all nodes
-- in the graph. It also generates a table with distance level sets, each of
-- which contain all nodes that have the same corresponding distance to
-- |source|. Finally, a mapping of nodes to their parents along the
-- shortest paths is generated to allow the reconstruction of the paths
-- that were chosen by the Dijkstra algorithm.
--
-- @param graph The graph to compute the shortest paths for.
-- @param source The node to compute the distances to.
--
-- @return A mapping of nodes to their distance to |source|.
-- @return An array of distance level sets. The set at index |i| contains
-- all nodes that have a distance of |i| to |source|.
-- @return A mapping of nodes to their parents to allow the reconstruction
-- of the shortest paths chosen by the Dijkstra algorithm.
--
function PathLengths.dijkstra(graph, source)
local distance = {}
local levels = {}
local parent = {}
local queue = PriorityQueue.new()
-- reset the distance of all nodes and insert them into the priority queue
for _,node in ipairs(graph.nodes) do
if node == source then
distance[node] = 0
parent[node] = nil
queue:enqueue(node, distance[node])
else
distance[node] = #graph.nodes + 1 -- this is about infinity ;)
queue:enqueue(node, distance[node])
end
end
while not queue:isEmpty() do
local u = queue:dequeue()
assert(distance[u] < #graph.nodes + 1, 'the graph is not connected, Dijkstra will not work')
if distance[u] > 0 then
levels[distance[u]] = levels[distance[u]] or {}
table.insert(levels[distance[u]], u)
end
for _,edge in ipairs(u.edges) do
local v = edge:getNeighbour(u)
local alternative = distance[u] + 1
if alternative < distance[v] then
distance[v] = alternative
parent[v] = u
-- update the priority of v
queue:updatePriority(v, distance[v])
end
end
end
return distance, levels, parent
end
---
-- Performs the Floyd-Warshall algorithm to solve the all-source shortes path problem.
--
-- @param graph The graph to compute the shortest paths for.
--
-- @return A distance matrix
--
function PathLengths.floydWarshall(graph)
local distance = {}
local infinity = math.huge
for _,i in ipairs(graph.nodes) do
distance[i] = {}
for _,j in ipairs(graph.nodes) do
distance[i][j] = infinity
end
end
for _,i in ipairs(graph.nodes) do
for _,edge in ipairs(i.edges) do
local j = edge:getNeighbour(i)
distance[i][j] = edge.weight or 1
end
end
for _,k in ipairs(graph.nodes) do
for _,i in ipairs(graph.nodes) do
for _,j in ipairs(graph.nodes) do
distance[i][j] = math.min(distance[i][j], distance[i][k] + distance[k][j])
end
end
end
return distance
end
---
-- Computes the pseudo diameter of a graph.
--
-- The diameter of a graph is the maximum of the shortest paths between
-- any pair of nodes in the graph. A pseudo diameter is an approximation
-- of the diameter that is computed by picking a starting node |u| and
-- finding a node |v| that is farthest away from |u| and has the smallest
-- degree of all nodes that have the same distance to |u|. The algorithm
-- continues with |v| as the new starting node and iteratively tries
-- to find an end node that is generates a larger pseudo diameter.
-- It terminates as soon as no such end node can be found.
--
-- @param graph The graph.
--
-- @return The pseudo diameter of the graph.
-- @return The start node of the corresponding approximation of a maximum
-- shortest path.
-- @return The end node of that path.
--
function PathLengths.pseudoDiameter(graph)
-- find a node with minimum degree
local start_node = graph.nodes[1]
for _,node in ipairs(graph.nodes) do
if node:getDegree() < start_node:getDegree() then
start_node = node
end
end
assert(start_node)
local old_diameter = 0
local diameter = 0
local end_node = nil
while true do
local distance, levels = PathLengths.dijkstra(graph, start_node)
-- the number of levels is the same as the distance of the nodes
-- in the last level to the start node
old_diameter = diameter
diameter = #levels
-- abort if the diameter could not be improved
if diameter == old_diameter then
end_node = levels[#levels][1]
break
end
-- select the node with the smallest degree from the last level as
-- the start node for the next iteration
start_node = levels[#levels][1]
for _,node in ipairs(levels[#levels]) do
if node:getDegree() < start_node:getDegree() then
start_node = node
end
end
assert(start_node)
end
assert(start_node)
assert(end_node)
return diameter, start_node, end_node
end
-- Done
return PathLengths
|