summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/jedi/base/PathLengthsFW.lua
blob: cf7cbddc20f4b5f8f5df4a727ef73b5eb3c5f0f9 (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
-- 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