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
|
-- Copyright 2014 by Ida Bruhns
--
-- This file may be distributed and/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
--- This is a helper class providing different functions that deal with graph
-- distances. This class can be used by engineers and implementers if they
-- need to calculate anything regarding graph distances.
local PathLengths = {}
-- Imports
local PriorityQueue = require "pgf.gd.lib.PriorityQueue"
local Preprocessing = require "pgf.gd.force.jedi.base.Preprocessing"
-- This algorithm conducts a breadth first search on the graph it is given.
--
-- @param ugraph The graph on which the search should be conducted
--
-- @return A table holding every vertex $v$ as key and a table as value. The
-- value table holds all other vertices $u$ as keys and their shortest
-- distance to $v$ as value
function PathLengths:breadthFirstSearch(ugraph)
local distances = {}
local vertices = ugraph.vertices
local arcs = ugraph.arcs
for _,v in ipairs(vertices) do
distances[v] = {}
local dist = distances[v]
for _,w in ipairs(vertices) do
dist[w] = #vertices +1
end
dist[v] = 0
end
local n = 1
local p = Preprocessing.overExactlyNPairs(vertices, arcs, n)
while (#p > 0) do
for _, v in ipairs(p) do
local tab = distances[v.tail]
tab[v.head] = n
end
n = n + 1
p = Preprocessing.overExactlyNPairs(vertices, arcs, n)
end
return(distances)
end
-- This function performs Dijkstra's algorithm on the graph.
--
-- @param ugraph The graph where the paths should be found
-- @param source The source vertex
--
-- @return |distance| A table holding every vertex $v$ as key and a table as
-- value. The value table holds all other vertices $u$ as
-- keys and their shortest distance to $v$ as value
-- @return |levels| A table holding the levels of the graph as keys and a
-- table holding the vertices found on that level as values
-- @return |parent| A tbale holding each vertex as key and it's parent vertex
-- as value
function PathLengths:dijkstra(ugraph, 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 _,v in ipairs(ugraph.vertices) do
if v == source then
distance[v] = 0
parent[v] = nil
queue:enqueue(v, distance[v])
else
distance[v] = #ugraph.vertices + 1 -- this is about infinity ;)
queue:enqueue(v, distance[v])
end
end
while not queue:isEmpty() do
local u = queue:dequeue()
assert(distance[u] < #ugraph.vertices + 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(ugraph:outgoing(u)) do
local v = edge.head
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
-- This function finds the pseudo diameter of the graph, which is the longest
-- shortest path in the graph
--
-- @param ugraph The graph who's pseudo diameter is wanted
--
-- @ return |diameter| The pseudo diameter of the graph
-- @ return |start_node| The start node of the longest shortest path in the
-- graph
-- @ return |end_node| The end node of the longest shortest path in the graph
function PathLengths:pseudoDiameter(ugraph)
-- find a node with minimum degree
local start_node = ugraph.vertices[1]
for _,v in ipairs(ugraph.vertices) do
if #ugraph:incoming(v) + #ugraph:outgoing(v) < #ugraph:incoming(start_node) + #ugraph:outgoing(start_node) then
start_node = v
end
end
assert(start_node)
local old_diameter = 0
local diameter = 0
local end_node = nil
while true do
local distance, levels = self:dijkstra(ugraph, 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 #ugraph:incoming(node)+#ugraph:outgoing(node) < #ugraph:incoming(start_node) + #ugraph:outgoing(start_node) then
start_node = node
end
end
assert(start_node)
end
assert(start_node)
assert(end_node)
return diameter, start_node, end_node
end
return PathLengths
|