diff options
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.lua | 209 |
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 |