summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/lib/PathLengths.lua
blob: 4bfa896ef953eec799764c6da91e2275c5f30e6f (plain)
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 shortest 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 shortest 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