summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/lib/PathLengths.lua
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/lib/PathLengths.lua')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/lib/PathLengths.lua209
1 files changed, 209 insertions, 0 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/lib/PathLengths.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/lib/PathLengths.lua
new file mode 100644
index 00000000000..c617cf80d8b
--- /dev/null
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/lib/PathLengths.lua
@@ -0,0 +1,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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/lib/PathLengths.lua,v 1.1 2012/11/27 17:24:26 tantau Exp $
+
+
+
+---
+-- 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 \ No newline at end of file