summaryrefslogtreecommitdiff
path: root/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib
diff options
context:
space:
mode:
Diffstat (limited to 'graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib')
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Bezier.lua160
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/DepthFirstSearch.lua125
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Direct.lua95
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Event.lua98
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/LookupTable.lua111
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/PathLengths.lua209
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/PriorityQueue.lua342
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Simplifiers.lua279
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Stack.lua61
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Storage.lua110
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Transform.lua120
11 files changed, 1710 insertions, 0 deletions
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Bezier.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Bezier.lua
new file mode 100644
index 0000000000..e4fe21d942
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Bezier.lua
@@ -0,0 +1,160 @@
+-- Copyright 2013 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 library offers a number of methods for working with Bezi\'er
+-- curves.
+
+local Bezier = {}
+
+-- Namespace
+require("pgf.gd.lib").Bezier = Bezier
+
+
+-- Imports
+
+local Coordinate = require 'pgf.gd.model.Coordinate'
+
+
+---
+-- Compute a point ``along a curve at a time''. You provide the four
+-- coordinates of the curve and a time. You get a point on the curve
+-- as return value as well as the two support vector for curve
+-- before this point and two support vectors for the curve after the
+-- point.
+--
+-- For speed reasons and in order to avoid superfluous creation of
+-- lots of tables, all values are provided and returned as pairs of
+-- values rather than as |Coordinate| objects.
+--
+-- @param ax The coordinate where the curve starts.
+-- @param ay
+-- @param bx The first support point.
+-- @param by
+-- @param cx The second support point.
+-- @param cy
+-- @param dx The coordinate where the curve ends.
+-- @param dy
+-- @param t A time (a number).
+--
+-- @return The point |p| on the curve at time |t| ($x$-part).
+-- @return The point |p| on the curve at time |t| ($y$-part).
+-- @return The first support point of the curve between |a| and |p| ($x$-part).
+-- @return The first support point of the curve between |a| and |p| ($y$-part).
+-- @return The second support point of the curve between |a| and |p| ($x$-part).
+-- @return The second support point of the curve between |a| and |p| ($y$-part).
+-- @return The first support point of the curve between |p| and |d| ($x$-part).
+-- @return The first support point of the curve between |p| and |d| ($y$-part).
+-- @return The second support point of the curve between |p| and |d| ($x$-part).
+-- @return The second support point of the curve between |p| and |d| ($y$-part).
+
+function Bezier.atTime(ax,ay,bx,by,cx,cy,dx,dy,t)
+
+ local s = 1-t
+
+ local ex, ey = ax*s + bx*t, ay*s + by*t
+ local fx, fy = bx*s + cx*t, by*s + cy*t
+ local gx, gy = cx*s + dx*t, cy*s + dy*t
+
+ local hx, hy = ex*s + fx*t, ey*s + fy*t
+ local ix, iy = fx*s + gx*t, fy*s + gy*t
+
+ local jx, jy = hx*s + ix*t, hy*s + iy*t
+
+ return jx, jy, ex, ey, hx, hy, ix, iy, gx, gy
+end
+
+
+---
+-- The ``coordinate version'' of the |atTime| function, where both the
+-- parameters and the return values are coordinate objects.
+
+function Bezier.atTimeCoordinates(a,b,c,d,t)
+ local jx, jy, ex, ey, hx, hy, ix, iy, gx, gy =
+ Bezier.atTime(a.x,a.y,b.x,b.y,c.x,c.y,d.x,d.y,t)
+
+ return
+ Coordinate.new(jx, jy),
+ Coordinate.new(ex, ey),
+ Coordinate.new(hx, hy),
+ Coordinate.new(ix, iy),
+ Coordinate.new(gx, gy)
+end
+
+
+---
+-- Computes the support points of a Bezier curve based on two points
+-- on the curves at certain times.
+--
+-- @param from The start point of the curve
+-- @param p1 A first point on the curve
+-- @param t1 A time when this point should be reached
+-- @param p2 A second point of the curve
+-- @param t2 A time when this second point should be reached
+-- @param to The end of the curve
+--
+-- @return sup1 A first support point of the curve
+-- @return sup2 A second support point of the curve
+
+function Bezier.supportsForPointsAtTime(from, p1, t1, p2, t2, to)
+
+ local s1 = 1 - t1
+ local s2 = 1 - t2
+
+ local f1a = s1^3
+ local f1b = t1 * s1^2 * 3
+ local f1c = t1^2 * s1 * 3
+ local f1d = t1^3
+
+ local f2a = s2^3
+ local f2b = t2 * s2^2 * 3
+ local f2c = t2^2 * s2 * 3
+ local f2d = t2^3
+
+ -- The system:
+ -- p1.x - from.x * f1a - to.x * f1d = sup1.x * f1b + sup2.x * f1c
+ -- p2.x - from.x * f2a - to.x * f2d = sup1.x * f2b + sup2.x * f2c
+ --
+ -- p1.y - from.y * f1a - to.y * f1d = sup1.y * f1b + sup2.y * f1c
+ -- p2.y - from.y * f2a - to.y * f2d = sup1.y * f2b + sup2.y * f2c
+
+ local a = f1b
+ local b = f1c
+ local c = p1.x - from.x * f1a - to.x * f1d
+ local d = f2b
+ local e = f2c
+ local f = p2.x - from.x * f2a - to.x * f2d
+
+ local det = a*e - b*d
+ local x1 = -(b*f - e*c)/det
+ local x2 = -(c*d - a*f)/det
+
+ local c = p1.y - from.y * f1a - to.y * f1d
+ local f = p2.y - from.y * f2a - to.y * f2d
+
+ local det = a*e - b*d
+ local y1 = -(b*f - e*c)/det
+ local y2 = -(c*d - a*f)/det
+
+ return Coordinate.new(x1,y1), Coordinate.new(x2,y2)
+
+end
+
+
+
+
+
+
+-- Done
+
+return Bezier \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/DepthFirstSearch.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/DepthFirstSearch.lua
new file mode 100644
index 0000000000..564b8f6839
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/DepthFirstSearch.lua
@@ -0,0 +1,125 @@
+-- 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$
+
+
+
+--- The DepthFirstSearch class implements a generic depth first function. It does not
+-- require that it is run on graphs, but can be used for anything where a visit function and
+-- a complete function is available.
+
+local DepthFirstSearch = {}
+DepthFirstSearch.__index = DepthFirstSearch
+
+-- Namespace
+require("pgf.gd.lib").DepthFirstSearch = DepthFirstSearch
+
+-- Imports
+local Stack = require "pgf.gd.lib.Stack"
+
+
+
+-- TT: TODO Jannis: Please document...
+
+function DepthFirstSearch.new(init_func, visit_func, complete_func)
+ local dfs = {
+ init_func = init_func,
+ visit_func = visit_func,
+ complete_func = complete_func,
+
+ stack = Stack.new(),
+ discovered = {},
+ visited = {},
+ completed = {},
+ }
+ setmetatable(dfs, DepthFirstSearch)
+ return dfs
+end
+
+
+
+function DepthFirstSearch:run()
+ self:reset()
+ self.init_func(self)
+
+ while self.stack:getSize() > 0 do
+ local data = self.stack:peek()
+
+ if not self:getVisited(data) then
+ if self.visit_func then
+ self.visit_func(self, data)
+ end
+ else
+ if self.complete_func then
+ self.complete_func(self, data)
+ end
+ self:setCompleted(data, true)
+ self.stack:pop()
+ end
+ end
+end
+
+
+
+function DepthFirstSearch:reset()
+ self.discovered = {}
+ self.visited = {}
+ self.completed = {}
+ self.stack = Stack.new()
+end
+
+
+
+function DepthFirstSearch:setDiscovered(data, discovered)
+ self.discovered[data] = discovered
+end
+
+
+
+function DepthFirstSearch:getDiscovered(data)
+ return self.discovered[data]
+end
+
+
+
+function DepthFirstSearch:setVisited(data, visited)
+ self.visited[data] = visited
+end
+
+
+
+function DepthFirstSearch:getVisited(data)
+ return self.visited[data]
+end
+
+
+
+function DepthFirstSearch:setCompleted(data, completed)
+ self.completed[data] = completed
+end
+
+
+
+function DepthFirstSearch:getCompleted(data)
+ return self.completed[data]
+end
+
+
+
+function DepthFirstSearch:push(data)
+ self.stack:push(data)
+end
+
+
+
+-- Done
+
+return DepthFirstSearch \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Direct.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Direct.lua
new file mode 100644
index 0000000000..81728a1a44
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Direct.lua
@@ -0,0 +1,95 @@
+-- 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$
+
+
+
+--- Direct is a class that collects algorithms for computing new
+-- versions of a graph where arcs point in certain directions.
+
+local Direct = {}
+
+-- Namespace
+require("pgf.gd.lib").Direct = Direct
+
+-- Imports
+local Digraph = require "pgf.gd.model.Digraph"
+
+
+--- Compute a digraph from a syntactic digraph.
+--
+-- This function takes a syntactic digraph and compute a new digraph
+-- where all arrow point in the "semantic direction" of the syntactic
+-- arrows. For instance, while "a <- b" will cause an arc from a to be
+-- to be added to the syntactic digraph, calling this function will
+-- return a digraph in which there is an arc from b to a rather than
+-- the other way round. In detail, "a <- b" is translated as just
+-- described, "a -> b" yields an arc from a to b as expected, "a <-> b"
+-- and "a -- b" yield arcs in both directions and, finally, "a -!- b"
+-- yields no arc at all.
+--
+-- @param syntactic_digraph A syntactic digraph, usually the "input"
+-- graph as specified syntactically be the user.
+--
+-- @return A new "semantic" digraph object.
+
+function Direct.digraphFromSyntacticDigraph(syntactic_digraph)
+ local digraph = Digraph.new(syntactic_digraph) -- copy
+
+ -- Now go over all arcs of the syntactic_digraph and turn them into
+ -- arcs with the correct direction in the digraph:
+ for _,a in ipairs(syntactic_digraph.arcs) do
+ for _,m in ipairs(a.syntactic_edges) do
+ local direction = m.direction
+ if direction == "->" then
+ digraph:connect(a.tail, a.head)
+ elseif direction == "<-" then
+ digraph:connect(a.head, a.tail)
+ elseif direction == "--" or direction == "<->" then
+ digraph:connect(a.tail, a.head)
+ digraph:connect(a.head, a.tail)
+ end
+ -- Case -!-: No edges...
+ end
+ end
+
+ return digraph
+end
+
+
+--- Turn an arbitrary graph into a directed graph
+--
+-- Takes a digraph as input and returns its underlying undirected
+-- graph, coded as a digraph. This means that between any two vertices
+-- if there is an arc in one direction, there is also one in the other.
+--
+-- @param digraph A directed graph
+--
+-- @return The underlying undirected graph of digraph.
+
+function Direct.ugraphFromDigraph(digraph)
+ local ugraph = Digraph.new(digraph)
+
+ -- Now go over all arcs of the syntactic_digraph and turn them into
+ -- arcs with the correct direction in the digraph:
+ for _,a in ipairs(digraph.arcs) do
+ ugraph:connect(a.head,a.tail)
+ ugraph:connect(a.tail,a.head)
+ end
+
+ return ugraph
+end
+
+
+
+
+-- Done
+
+return Direct
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Event.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Event.lua
new file mode 100644
index 0000000000..880796ce97
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Event.lua
@@ -0,0 +1,98 @@
+-- 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$
+
+
+
+---
+-- Events are used to communicate ``interesting'' events from the
+-- parser to the graph drawing algorithms.
+--
+-- As a syntactic description of some graph is being parsed, vertices,
+-- arcs, and a digraph object representing this graph get
+-- constructed. However, even though syntactic annotations such as
+-- options for the vertices and arcs are attached to them and can be
+-- accessed through the graph objects, some syntactic information is
+-- neither represented in the digraph object nor in the vertices and
+-- the arcs. A typical example is a ``missing'' node in a tree: Since
+-- it is missing, there is neither a vertex object nor arc objects
+-- representing it. It is also not a global option of the graph.
+--
+-- For these reasons, in addition to the digraph object itself,
+-- additional information can be passed by a parser to graph drawing
+-- algorithms through the means of events. Each |Event| consists of a
+-- |kind| field, which is just some string, and a |parameters| field,
+-- which stores additional, kind-specific information. As a graph is
+-- being parsed, a string of events is accumulated and is later on
+-- available through the |events| field of the graph drawing scope.
+--
+-- The following events are created during the parsing process by the
+-- standard parsers of \tikzname:
+-- %
+-- \begin{itemize}
+-- \item[|node|] When a node of the input graph has been parsed and
+-- a |Vertex| object has been created for it, an event with kind
+-- |node| is created. The |parameter| of this event is the
+-- just-created vertex.
+--
+-- The same kind of event is used to indicate ``missing'' nodes. In
+-- this case, the |parameters| field is |nil|.
+-- \item[|edge|] When an edge of the input graph has been parsed, an
+-- event is created of kind |edge|. The |parameters| field will store
+-- an array with two entries: The first is the |Arc| object whose
+-- |syntactic_edges| field stores the |edge|. The second is the index
+-- of the edge inside the |syntactic_edges| field.
+-- \item[|begin|]
+-- Signals the beginning of a group, which will be ended with a
+-- corresponding |end| event later on. The |parameters| field will
+-- indicate the kind of group. Currently, only the string
+-- |"descendants"| is used as |parameters|, indicating the start of
+-- several nodes that are descendants of a given node. This
+-- information can be used by algorithms for reconstructing the
+-- input structure of trees.
+-- \item[|end|] Signals the end of a group begun by a |begin| event
+-- earlier on.
+-- \end{itemize}
+--
+-- @field kind A string representing the kind of the events.
+-- @field parameters Kind-specific parameters.
+-- @field index A number that stores the events logical position in
+-- the sequence of events. The number need not be an integer array
+-- index.
+--
+local Event = {}
+Event.__index = Event
+
+
+-- Namespace
+require("pgf.gd.lib").Event = Event
+
+
+
+---
+-- Create a new event object
+--
+-- @param initial Initial fields of the new event.
+--
+-- @return The new object
+
+function Event.new(values)
+ local new = {}
+ for k,v in pairs(values) do
+ new[k] = v
+ end
+ return setmetatable(new, Event)
+end
+
+
+
+-- done
+
+return Event \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/LookupTable.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/LookupTable.lua
new file mode 100644
index 0000000000..fc2043d523
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/LookupTable.lua
@@ -0,0 +1,111 @@
+-- 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 two utility functions for managing ``lookup
+-- tables''. Such a table is a mixture of an array and a hashtable:
+-- It stores (only) tables. Each table is stored once in a normal
+-- array position. Additionally, the lookup table is also indexed at
+-- the position of the table (used as a key) and this position is set
+-- to |true|. This means that you can test whether a table |t| is in the
+-- lookup table |l| simply by testing whether |l[t]| is true.
+--
+local LookupTable = {}
+
+-- Namespace
+require("pgf.gd.lib").LookupTable = LookupTable
+
+
+
+---
+-- Add all elements in the |array| to a lookup table. If an element of
+-- the array is already present in the table, it will not be added
+-- again.
+--
+-- This operation takes time $O(|\verb!array!|)$.
+--
+-- @param l Lookup table
+-- @param array An array of to-be-added tables.
+
+function LookupTable.add(l, array)
+ for i=1,#array do
+ local t = array[i]
+ if not l[t] then
+ l[t] = true
+ l[#l + 1] = t
+ end
+ end
+end
+
+
+---
+-- Add one element to a lookup table. If it is already present in the
+-- table, it will not be added again.
+--
+-- This operation takes time $O(1)$.
+--
+-- @param l Lookup table
+-- @param e The to-be-added element.
+
+function LookupTable.addOne(l, e)
+ if not l[e] then
+ l[e] = true
+ l[#l + 1] = e
+ end
+end
+
+
+---
+-- Remove tables from a lookup table.
+--
+-- Note that this operation is pretty expensive insofar as it will
+-- always cost a traversal of the whole lookup table. However, this is
+-- also the maximum cost, even when a lot of entries need to be
+-- deleted. Thus, it is much better to ``pool'' multiple remove
+-- operations in a single one.
+--
+-- This operation takes time $O(\max\{|\verb!array!|, |\verb!l!|\})$.
+--
+-- @param l Lookup table
+-- @param t An array of to-be-removed tables.
+
+function LookupTable.remove(l, array)
+ -- Step 1: Mark all to-be-deleted entries
+ for i=1,#array do
+ local t = array[i]
+ if l[t] then
+ l[t] = false
+ end
+ end
+
+ -- Step 2: Collect garbage...
+ local target = 1
+ for i=1,#l do
+ local t = l[i]
+ if l[t] == false then
+ l[t] = nil
+ else
+ l[target] = t
+ target = target + 1
+ end
+ end
+ for i=#l,target,-1 do
+ l[i] = nil
+ end
+end
+
+
+
+-- Done
+
+return LookupTable \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/PathLengths.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/PathLengths.lua
new file mode 100644
index 0000000000..4bfa896ef9
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/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$
+
+
+
+---
+-- 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 \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/PriorityQueue.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/PriorityQueue.lua
new file mode 100644
index 0000000000..3fd29cdb74
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/PriorityQueue.lua
@@ -0,0 +1,342 @@
+-- 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$
+
+
+
+---
+-- A PriorityQueue supports operations for quickly finding the minimum from a set of elements
+--
+-- Its implementation is based on (simplified) Fibonacci heaps.
+local PriorityQueue = {}
+PriorityQueue.__index = PriorityQueue
+
+
+-- Namespace
+local lib = require "pgf.gd.lib"
+lib.PriorityQueue = PriorityQueue
+
+
+
+-- Local declarations
+local FibonacciHeap = {}
+local FibonacciHeapNode = {}
+
+
+
+
+--- Creates a new priority queue
+--
+-- @return The newly created queue
+
+function PriorityQueue.new()
+ local queue = {
+ heap = FibonacciHeap.new(),
+ nodes = {},
+ values = {},
+ }
+ setmetatable(queue, PriorityQueue)
+ return queue
+end
+
+
+
+--- Add an element with a certain priority to the queue
+--
+-- @param value An object
+-- @param priority Its priority
+
+function PriorityQueue:enqueue(value, priority)
+ local node = self.heap:insert(priority)
+ self.nodes[value] = node
+ self.values[node] = value
+end
+
+
+
+--- Removes the element with the minimum priority from the queue
+--
+-- @return The element with the minimum priority
+
+function PriorityQueue:dequeue()
+ local node = self.heap:extractMinimum()
+
+ if node then
+ local value = self.values[node]
+ self.nodes[value] = nil
+ self.values[node] = nil
+ return value
+ else
+ return nil
+ end
+end
+
+
+
+--- Lower the priority of an element of a queue
+--
+-- @param value An object
+-- @param priority A new priority, which must be lower than the old priority
+
+function PriorityQueue:updatePriority(value, priority)
+ local node = self.nodes[value]
+ assert(node, 'updating the priority of ' .. tostring(value) .. ' failed because it is not in the priority queue')
+ self.heap:updateValue(node, priority)
+end
+
+
+
+--- Tests, whether the queue is empty
+--
+-- @return True, if the queue is empty
+
+function PriorityQueue:isEmpty()
+ return #self.heap.trees == 0
+end
+
+
+
+
+
+
+-- Internals: An implementation of Fibonacci heaps.
+FibonacciHeap.__index = FibonacciHeap
+
+
+function FibonacciHeap.new()
+ local heap = {
+ trees = trees or {},
+ minimum = nil,
+ }
+ setmetatable(heap, FibonacciHeap)
+ return heap
+end
+
+
+
+function FibonacciHeap:insert(value)
+ local node = FibonacciHeapNode.new(value)
+ local heap = FibonacciHeap.new()
+ table.insert(heap.trees, node)
+ self:merge(heap)
+ return node
+end
+
+
+
+function FibonacciHeap:merge(other)
+ for _, tree in ipairs(other.trees) do
+ table.insert(self.trees, tree)
+ end
+ self:updateMinimum()
+end
+
+
+
+function FibonacciHeap:extractMinimum()
+ if self.minimum then
+ local minimum = self:removeTableElement(self.trees, self.minimum)
+
+ for _, child in ipairs(minimum.children) do
+ child.root = child
+ table.insert(self.trees, child)
+ end
+
+ local same_degrees_found = true
+ while same_degrees_found do
+ same_degrees_found = false
+
+ local degrees = {}
+
+ for _, root in ipairs(self.trees) do
+ local degree = root:getDegree()
+
+ if degrees[degree] then
+ if root.value < degrees[degree].value then
+ self:linkRoots(root, degrees[degree])
+ else
+ self:linkRoots(degrees[degree], root)
+ end
+
+ degrees[degree] = nil
+ same_degrees_found = true
+ break
+ else
+ degrees[degree] = root
+ end
+ end
+ end
+
+ self:updateMinimum()
+
+ return minimum
+ end
+end
+
+
+
+function FibonacciHeap:updateValue(node, value)
+ local old_value = node.value
+ local new_value = value
+
+ if new_value <= old_value then
+ self:decreaseValue(node, value)
+ else
+ assert(false, 'FibonacciHeap:increaseValue is not implemented yet')
+ end
+end
+
+
+
+function FibonacciHeap:decreaseValue(node, value)
+ assert(value <= node.value)
+
+ node.value = value
+
+ if node.value < node.parent.value then
+ local parent = node.parent
+ self:cutFromParent(node)
+
+ if not parent:isRoot() then
+ if parent.marked then
+ self:cutFromParent(parent)
+ else
+ parent.marked = true
+ end
+ end
+ end
+
+ if node.value < self.minimum.value then
+ self.minimum = node
+ end
+end
+
+
+
+function FibonacciHeap:delete(node)
+ self:decreaseValue(node, -math.huge)
+ self:extractMinimum()
+end
+
+
+
+function FibonacciHeap:linkRoots(root, child)
+ child.root = root
+ child.parent = root
+
+ child = self:removeTableElement(self.trees, child)
+ table.insert(root.children, child)
+
+ return root
+end
+
+
+
+function FibonacciHeap:cutFromParent(node)
+ local parent = node.parent
+
+ node.root = node
+ node.parent = node
+ node.marked = false
+
+ node = self:removeTableElement(parent.children, node)
+ table.insert(self.trees, node)
+end
+
+
+
+function FibonacciHeap:updateMinimum()
+ self.minimum = self.trees[1]
+
+ for _, root in ipairs(self.trees) do
+ if root.value < self.minimum.value then
+ self.minimum = root
+ end
+ end
+end
+
+
+
+function FibonacciHeap:removeTableElement(input_table, element)
+ for i = 1, #input_table do
+ if input_table[i] == element then
+ return table.remove(input_table, i)
+ end
+ end
+end
+
+
+
+
+-- Now come the nodes
+
+FibonacciHeapNode.__index = FibonacciHeapNode
+
+function FibonacciHeapNode.new(value, root, parent)
+ local node = {
+ value = value,
+ children = {},
+ marked = false,
+ root = nil,
+ parent = nil,
+ }
+ setmetatable(node, FibonacciHeapNode)
+
+ if root then
+ node.root = root
+ node.parent = parent
+ else
+ node.root = node
+ node.parent = node
+ end
+
+ return node
+end
+
+function FibonacciHeapNode:addChild(value)
+ local child = FibonacciHeapNode.new(value, self.root, self)
+ table.insert(self.children, child)
+end
+
+function FibonacciHeapNode:getDegree()
+ return #self.children
+end
+
+
+
+function FibonacciHeapNode:setRoot(root)
+ self.root = root
+
+ if root == self then
+ self.parent = root
+ end
+
+ if #self.children > 0 then
+ for _, child in ipairs(self.children) do
+ child.root = root
+ end
+ end
+end
+
+
+
+function FibonacciHeapNode:isRoot()
+ return self.root == self
+end
+
+
+
+
+
+
+-- done
+
+return PriorityQueue \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Simplifiers.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Simplifiers.lua
new file mode 100644
index 0000000000..bcb7276190
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Simplifiers.lua
@@ -0,0 +1,279 @@
+-- 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$
+
+
+
+--- The Simplifiers class is a singleton object.
+-- Its methods allow implement methods for simplifying graphs, for instance
+-- for removing loops or multiedges or computing spanning trees.
+
+local Simplifiers = {}
+
+-- Namespace
+local lib = require "pgf.gd.lib"
+lib.Simplifiers = Simplifiers
+
+
+
+
+-- Imports
+
+local Edge = require "pgf.gd.deprecated.Edge"
+local Node = require "pgf.gd.deprecated.Node"
+
+
+
+
+
+--- Algorithm to classify edges of a DFS search tree.
+--
+-- TODO Jannis: document this algorithm as soon as it is completed and bug-free.
+-- TT: Replace this algorithm by something else, perhaps?
+--
+function Simplifiers:classifyEdges(graph)
+ local discovered = {}
+ local visited = {}
+ local recursed = {}
+ local completed = {}
+
+ local tree_and_forward_edges = {}
+ local cross_edges = {}
+ local back_edges = {}
+
+ local stack = {}
+
+ local function push(node)
+ table.insert(stack, node)
+ end
+
+ local function peek()
+ return stack[#stack]
+ end
+
+ local function pop()
+ return table.remove(stack)
+ end
+
+ local initial_nodes = graph.nodes
+
+ for i=#initial_nodes,1,-1 do
+ local node = initial_nodes[i]
+ push(node)
+ discovered[node] = true
+ end
+
+ while #stack > 0 do
+ local node = peek()
+ local edges_to_traverse = {}
+
+ visited[node] = true
+
+ if not recursed[node] then
+ recursed[node] = true
+
+ local out_edges = node:getOutgoingEdges()
+ for _,edge in ipairs(out_edges) do
+ local neighbour = edge:getNeighbour(node)
+
+ if not discovered[neighbour] then
+ table.insert(tree_and_forward_edges, edge)
+ table.insert(edges_to_traverse, edge)
+ else
+ if not completed[neighbour] then
+ if not visited[neighbour] then
+ table.insert(tree_and_forward_edges, edge)
+ table.insert(edges_to_traverse, edge)
+ else
+ table.insert(back_edges, edge)
+ end
+ else
+ table.insert(cross_edges, edge)
+ end
+ end
+ end
+
+ if #edges_to_traverse == 0 then
+ completed[node] = true
+ pop()
+ else
+ for i=#edges_to_traverse,1,-1 do
+ local neighbour = edges_to_traverse[i]:getNeighbour(node)
+ discovered[neighbour] = true
+ push(neighbour)
+ end
+ end
+ else
+ completed[node] = true
+ pop()
+ end
+ end
+
+ return tree_and_forward_edges, cross_edges, back_edges
+end
+
+
+
+
+
+--
+--
+-- Loops and Multiedges
+--
+--
+
+
+--- Remove all loops from a graph
+--
+-- This method will remove all loops from a graph.
+--
+-- @param algorithm An algorithm object
+
+function Simplifiers:removeLoopsOldModel(algorithm)
+ local graph = algorithm.graph
+ local loops = {}
+
+ for _,edge in ipairs(graph.edges) do
+ if edge:getHead() == edge:getTail() then
+ loops[#loops+1] = edge
+ end
+ end
+
+ for i=1,#loops do
+ graph:deleteEdge(loops[i])
+ end
+
+ graph[algorithm].loops = loops
+end
+
+
+
+--- Restore loops that were previously removed.
+--
+-- @param algorithm An algorithm object
+
+function Simplifiers:restoreLoopsOldModel(algorithm)
+ local graph = algorithm.graph
+
+ for _,edge in ipairs(graph[algorithm].loops) do
+ graph:addEdge(edge)
+ edge:getTail():addEdge(edge)
+ end
+
+ graph[algorithm].loops = nil
+end
+
+
+
+
+--- Remove all multiedges.
+--
+-- Every multiedge of the graph will be replaced by a single edge.
+--
+-- @param algorithm An algorithm object
+
+function Simplifiers:collapseMultiedgesOldModel(algorithm, collapse_action)
+ local graph = algorithm.graph
+ local collapsed_edges = {}
+ local node_processed = {}
+
+ for _,node in ipairs(graph.nodes) do
+ node_processed[node] = true
+
+ local multiedge = {}
+
+ local function handle_edge (edge)
+
+ local neighbour = edge:getNeighbour(node)
+
+ if not node_processed[neighbour] then
+ if not multiedge[neighbour] then
+ multiedge[neighbour] = Edge.new{ direction = Edge.RIGHT }
+ collapsed_edges[multiedge[neighbour]] = {}
+ end
+
+ if collapse_action then
+ collapse_action(multiedge[neighbour], edge, graph)
+ end
+
+ table.insert(collapsed_edges[multiedge[neighbour]], edge)
+ end
+ end
+
+ for _,edge in ipairs(node:getIncomingEdges()) do
+ handle_edge(edge)
+ end
+
+ for _,edge in ipairs(node:getOutgoingEdges()) do
+ handle_edge(edge)
+ end
+
+ for neighbour, multiedge in pairs(multiedge) do
+
+ if #collapsed_edges[multiedge] <= 1 then
+ collapsed_edges[multiedge] = nil
+ else
+ for _,subedge in ipairs(collapsed_edges[multiedge]) do
+ graph:deleteEdge(subedge)
+ end
+
+ multiedge:addNode(node)
+ multiedge:addNode(neighbour)
+
+ graph:addEdge(multiedge)
+ end
+ end
+ end
+
+ graph[algorithm].collapsed_edges = collapsed_edges
+end
+
+
+--- Expand multiedges that were previously collapsed
+--
+-- @param algorithm An algorithm object
+
+function Simplifiers:expandMultiedgesOldModel(algorithm)
+ local graph = algorithm.graph
+ for multiedge, subedges in pairs(graph[algorithm].collapsed_edges) do
+ assert(#subedges >= 2)
+
+ graph:deleteEdge(multiedge)
+
+ for _,edge in ipairs(subedges) do
+
+ -- Copy bend points
+ for _,p in ipairs(multiedge.bend_points) do
+ edge.bend_points[#edge.bend_points+1] = p:copy()
+ end
+
+ -- Copy options
+ for k,v in pairs(multiedge.algorithmically_generated_options) do
+ edge.algorithmically_generated_options[k] = v
+ end
+
+ for _,node in ipairs(edge.nodes) do
+ node:addEdge(edge)
+ end
+
+ graph:addEdge(edge)
+ end
+ end
+
+ graph[algorithm].collapsed_edges = nil
+end
+
+
+
+
+
+-- Done
+
+return Simplifiers
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Stack.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Stack.lua
new file mode 100644
index 0000000000..75084b6e38
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Stack.lua
@@ -0,0 +1,61 @@
+-- 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$
+
+
+--- A Stack is a very simple wrapper around an array
+--
+--
+
+local Stack = {}
+Stack.__index = Stack
+
+
+-- Namespace
+require("pgf.gd.lib").Stack = Stack
+
+
+--- Create a new stack
+function Stack.new()
+ local stack = {}
+ setmetatable(stack, Stack)
+ return stack
+end
+
+
+--- Push an element on top of the stack
+function Stack:push(data)
+ self[#self+1] = data
+end
+
+
+--- Inspect (but not pop) the top element of a stack
+function Stack:peek()
+ return self[#self]
+end
+
+
+--- Pop an element from the top of the stack
+function Stack:pop()
+ return table.remove(self, #self)
+end
+
+
+--- Get the height of the stack
+function Stack:getSize()
+ return #self
+end
+
+
+
+-- done
+
+return Stack \ No newline at end of file
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Storage.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Storage.lua
new file mode 100644
index 0000000000..e029fdf7ff
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Storage.lua
@@ -0,0 +1,110 @@
+-- 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$
+
+
+
+---
+-- A storage is an object that, as the name suggests, allows you to
+-- ``store stuff concerning objects.'' Basically, it behaves like
+-- table having weak keys, which means that once the objects for which
+-- you ``store stuff'' go out of scope, they are also removed from the
+-- storage. Also, you can specify that for each object of the storage
+-- you store a table. In this case, there is no need to initialize
+-- this table for each object; rather, when you write into such a
+-- table and it does not yet exist, it is created ``on the fly''.
+--
+-- The typical way you use storages is best explained with the
+-- following example: Suppose you want to write a depth-first search
+-- algorithm for a graph. This algorithm might wish to mark all nodes
+-- it has visited. It could just say |v.marked = true|, but this might
+-- clash with someone else also using the |marked| key. The solution is
+-- to create a |marked| storage. The algorithm can first say
+--\begin{codeexample}[code only, tikz syntax=false]
+--local marked = Storage.new()
+--\end{codeexample}
+-- and then say
+--\begin{codeexample}[code only, tikz syntax=false]
+--marked[v] = true
+--\end{codeexample}
+-- to mark its objects. The |marked| storage object does not need to
+-- be created locally inside a function, you can declare it as a local
+-- variable of the whole file; nevertheless, the entries for vertices
+-- no longer in use get removed automatically. You can also make it a
+-- member variable of the algorithm class, which allows you make the
+-- information about which objects are marked globally
+-- accessible.
+--
+-- Now suppose the algorithm would like to store even more stuff in
+-- the storage. For this, we might use a table and can use the fact
+-- that a storage will automatically create a table when necessary:
+--\begin{codeexample}[code only, tikz syntax=false]
+--local info = Storage.newTableStorage()
+--
+--info[v].marked = true -- the "info[v]" table is
+-- -- created automatically here
+--
+--info[v].foo = "bar"
+--\end{codeexample}
+-- Again, once |v| goes out of scope, both it and the info table will
+-- removed.
+
+local Storage = {}
+
+-- Namespace
+require("pgf.gd.lib").Storage = Storage
+
+
+-- The simple metatable
+
+local SimpleStorageMetaTable = { __mode = "k" }
+
+-- The advanced metatable for table storages:
+
+local TableStorageMetaTable = {
+ __mode = "k",
+ __index =
+ function(t, k)
+ local new = {}
+ rawset(t, k, new)
+ return new
+ end
+}
+
+
+---
+-- Create a new storage object.
+--
+-- @return A new |Storage| instance.
+
+function Storage.new()
+ return setmetatable({}, SimpleStorageMetaTable)
+end
+
+
+---
+-- Create a new storage object which will install a table for every
+-- entry automatically.
+--
+-- @return A new |Storage| instance.
+
+function Storage.newTableStorage()
+ return setmetatable({}, TableStorageMetaTable)
+end
+
+
+
+
+
+
+
+-- Done
+
+return Storage
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Transform.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Transform.lua
new file mode 100644
index 0000000000..7695b1b239
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/Transform.lua
@@ -0,0 +1,120 @@
+-- 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$
+
+
+---
+-- The |Transform| table provides a set of static methods for
+-- creating and handling canvas transformation matrices. Such a matrix
+-- is actually just an array of six numbers. The idea is that
+-- ``applying'' an array { a, b, c, d, e, f } a vector $(x,y)$ will
+-- yield the new vector $(ax+by+e,cx+dy+f)$. For details on how such
+-- matrices work, see Section~\ref{section-transform-cm}
+--
+local Transform = {}
+
+
+-- Namespace
+
+require("pgf.gd.model").Transform = Transform
+
+
+--- Creates a new transformation array.
+--
+-- @param a First component
+-- @param b Second component
+-- @param c Third component
+-- @param d Fourth component
+-- @param x The x shift
+-- @param y The y shift
+--
+-- @return A transformation object.
+--
+function Transform.new(a,b,c,d,x,y)
+ return { a, b, c, d, x, y }
+end
+
+
+--- Creates a new transformation object that represents a shift.
+--
+-- @param x An x-shift
+-- @param y A y-shift
+--
+-- @return A transformation object
+--
+function Transform.new_shift(x,y)
+ return { 1, 0, 0, 1, x, y }
+end
+
+
+--- Creates a new transformation object that represents a rotation.
+--
+-- @param angle An angle
+--
+-- @return A transformation object
+--
+function Transform.new_rotation(angle)
+ local c = math.cos(angle)
+ local s = math.sin(angle)
+ return { c, -s, s, c, 0, 0 }
+end
+
+
+--- Creates a new transformation object that represents a scaling.
+--
+-- @param x The horizontal scaling
+-- @param y The vertical scaling (if missing, the horizontal scaling is used)
+--
+-- @return A transformation object
+--
+function Transform.new_scaling(x_scale, y_scale)
+ return { x_scale, 0, 0, y_scale or x_scale, 0, 0 }
+end
+
+
+
+
+---
+-- Concatenate two transformation matrices, returning the new one.
+--
+-- @param a The first transformation
+-- @param b The second transformation
+--
+-- @return The transformation representing first applying |b| and then
+-- applying |a|.
+--
+function Transform.concat(a,b)
+ local a1, a2, a3, a4, a5, a6, b1, b2, b3, b4, b5, b6 =
+ a[1], a[2], a[3], a[4], a[5], a[6], b[1], b[2], b[3], b[4], b[5], b[6]
+ return { a1*b1 + a2*b3, a1*b2 + a2*b4,
+ a3*b1 + a4*b3, a3*b2 + a4*b4,
+ a1*b5 + a2*b6 + a5, a3*b5 + a4*b6 + a6 }
+end
+
+
+
+---
+-- Inverts a transformation matrix.
+--
+-- @param t The transformation.
+--
+-- @return The inverted transformation
+--
+function Transform.invert(t)
+ local t1, t2, t3, t4 = t[1], t[2], t[3], t[4]
+ local idet = 1/(t1*t4 - t2*t3)
+
+ return { t4*idet, -t2*idet, -t3*idet, t1*idet, -t[5], -t[6] }
+end
+
+
+-- Done
+
+return Transform