summaryrefslogtreecommitdiff
path: root/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2023-01-16 03:03:27 +0000
committerNorbert Preining <norbert@preining.info>2023-01-16 03:03:27 +0000
commit6f9e1680085e7bb4d258f6f8116369d122e196e1 (patch)
tree9ac0ecb239240d1d672b188f29c1479de215074b /graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface
parentb8345f39630408bb198e7636381ce4240154ca9b (diff)
CTAN sync 202301160303
Diffstat (limited to 'graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface')
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface/InterfaceCore.lua191
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface/InterfaceToAlgorithms.lua968
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface/InterfaceToC.lua78
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface/InterfaceToDisplay.lua1002
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface/Scope.lua92
5 files changed, 2331 insertions, 0 deletions
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface/InterfaceCore.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface/InterfaceCore.lua
new file mode 100644
index 0000000000..8473eb3f10
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface/InterfaceCore.lua
@@ -0,0 +1,191 @@
+-- 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 class provides the core functionality of the interface between
+-- all the different layers (display layer, binding layer, and
+-- algorithm layer). The two classes |InterfaceToAlgorithms| and
+-- |InterfaceToDisplay| use, in particular, the data structures
+-- provided by this class.
+--
+-- @field binding This field stores the ``binding''. The graph drawing
+-- system is ``bound'' to the display layer through such a binding (a
+-- subclass of |Binding|). Such a binding can be thought of as a
+-- ``driver'' in operating systems terminology: It is a small set of
+-- functions needed to adapt the functionality to one specific display
+-- system. Note that the whole graph drawing scope is bound to exactly
+-- one display layer; to use several bindings you need to setup a
+-- completely new Lua instance.
+--
+-- @field scopes This is a stack of graph drawing scopes. All
+-- interface methods refer to the top of this stack.
+--
+-- @field collection_kinds This table stores which collection kinds
+-- have been defined together with their properties.
+--
+-- @field algorithm_classes A table that maps algorithm keys (like
+-- |tree layout| to class objects).
+--
+-- @field keys A lookup table of all declared keys. Each entry of this
+-- table consists of the original entry passed to the |declare|
+-- method. Each of these tables is both index at a number (so you can
+-- iterate over it using |ipairs|) and also via the key's name.
+
+local InterfaceCore = {
+ -- The main binding. Set by |InterfaceToDisplay.bind| method.
+ binding = nil,
+
+ -- The stack of Scope objects.
+ scopes = {},
+
+ -- The collection kinds.
+ collection_kinds = {},
+
+ -- The algorithm classes
+ algorithm_classes = {},
+
+ -- The declared keys
+ keys = {},
+
+ -- The phase kinds
+ phase_kinds = {},
+
+ -- Internals for handling the options stack
+ option_stack = {},
+ option_cache_height = nil,
+ option_initial = {
+ algorithm_phases = {
+ ["preprocessing stack"] = {},
+ ["edge routing stack"] = {},
+ ["postprocessing stack"] = {},
+ }
+ },
+ option_aliases = {
+ [{}] = true -- Remove, once Lua Link Bug is fixed
+ },
+
+ -- Constant strings for special collection kinds.
+ sublayout_kind = "INTERNAL_sublayout_kind",
+ subgraph_node_kind = "INTERNAL_subgraph_node_kind",
+}
+
+-- Namespace
+require("pgf.gd.interface").InterfaceCore = InterfaceCore
+
+
+InterfaceCore.option_initial.__index = InterfaceCore.option_initial
+InterfaceCore.option_initial.algorithm_phases.__index = InterfaceCore.option_initial.algorithm_phases
+
+
+-- Imports
+local Coordinate = require "pgf.gd.model.Coordinate"
+
+
+--- Returns the top scope
+--
+-- @return The current top scope, which is the scope in which
+-- everything should happen right now.
+
+function InterfaceCore.topScope()
+ return assert(InterfaceCore.scopes[#InterfaceCore.scopes], "no graph drawing scope open")
+end
+
+
+
+local factors = {
+ cm=28.45274,
+ mm=2.84526,
+ pt=1.0,
+ bp=1.00374,
+ sp=0.00002,
+ pc=12.0,
+ em=10,
+ ex=4.30554,
+ ["in"]=72.27,
+ dd=1.07,
+ cc=12.8401,
+ [""]=1,
+}
+
+local time_factors = {
+ s=1,
+ ms=0.001,
+ min=60,
+ h=3600
+}
+
+local directions = {
+ down = -90,
+ up = 90,
+ left = 180,
+ right = 0,
+ south = -90,
+ north = 90,
+ west = 180,
+ east = 0,
+ ["north east"] = 45,
+ ["north west"] = 135,
+ ["south east"] = -45,
+ ["south west"] = -135,
+ ["-"] = 0,
+ ["|"] = -90,
+}
+
+---
+-- Converts parameters types. This method is used by both the
+-- algorithm layer as well as the display layer to convert strings
+-- into the different types of parameters. When a parameter
+-- is pushed onto the option stack, you can either provide a value of
+-- the parameter's type; but you can also provide a string. This
+-- string can then be converted by this function to a value of the
+-- correct type.
+--
+-- @param s A parameter value or a string.
+-- @param t The type of the parameter
+--
+-- @return If |s| is not a string, it is just returned. If it is a
+-- string, it is converted to the type |t|.
+
+function InterfaceCore.convert(s,t)
+ if type(s) ~= "string" then
+ return s
+ elseif t == "number" then
+ return tonumber(s)
+ elseif t == "length" then
+ local num, dim = string.match(s, "([%d.]+)(.*)")
+ return tonumber(num) * assert(factors[dim], "unknown unit")
+ elseif t == "time" then
+ local num, dim = string.match(s, "([%d.]+)(.*)")
+ return tonumber(num) * assert(time_factors[dim], "unknown time unit")
+ elseif t == "string" then
+ return s
+ elseif t == "canvas coordinate" or t == "coordinate" then
+ local x, y = string.match(s,"%(([%d.]+)pt,([%d.]+)pt%)")
+ return Coordinate.new(tonumber(x),tonumber(y))
+ elseif t == "boolean" then
+ return s == "true"
+ elseif t == "raw" then
+ return loadstring(s)()
+ elseif t == "direction" then
+ return directions[s] or tonumber(s)
+ elseif t == "nil" or t == nil then
+ return nil
+ else
+ error ("unknown parameter type")
+ end
+end
+
+
+-- Done
+
+return InterfaceCore
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface/InterfaceToAlgorithms.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface/InterfaceToAlgorithms.lua
new file mode 100644
index 0000000000..1187fbc313
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface/InterfaceToAlgorithms.lua
@@ -0,0 +1,968 @@
+-- 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 class provides the interface between the graph drawing system
+-- and algorithms. Another class, |InterfaceToDisplay|, binds the
+-- display layers (like \tikzname\ or a graph drawing editor) to the
+-- graph drawing system ``from the other side''.
+--
+-- The functions declared here can be used by algorithms to
+-- communicate with the graph drawing system, which will usually
+-- forward the ``requests'' of the algorithms to the display layers in
+-- some way. For instance, when you declare a new parameter, this
+-- parameter will become available on the display layer.
+
+local InterfaceToAlgorithms = {}
+
+-- Namespace
+require("pgf.gd.interface").InterfaceToAlgorithms = InterfaceToAlgorithms
+
+
+-- Imports
+local InterfaceCore = require "pgf.gd.interface.InterfaceCore"
+local InterfaceToDisplay = require "pgf.gd.interface.InterfaceToDisplay"
+local InterfaceToC = require "pgf.gd.interface.InterfaceToC"
+
+local LookupTable = require "pgf.gd.lib.LookupTable"
+local LayoutPipeline = require "pgf.gd.control.LayoutPipeline"
+
+local Edge = require "pgf.gd.model.Edge"
+
+local lib = require "pgf.gd.lib"
+
+local doc = require "pgf.gd.doc"
+
+-- Forwards
+
+local declare_handlers
+
+
+
+
+---
+-- Adds a handler for the |declare| function. The |declare|
+-- command is just a ``dispatcher'' to one of many possible
+-- declaration functions. Which function is used, depends on which
+-- fields are present in the table passed to |declare|. For each
+-- registered handler, we call the |test| function. If it returns
+-- neither |nil| nor |false|, the |handler| field of this handler is
+-- called. If it returns |true|, the handler immediately
+-- finishes. Otherwise, the next handler is tried.
+
+function InterfaceToAlgorithms.addHandler(test, handler)
+ table.insert(declare_handlers, 1, { test = test, handler = handler })
+end
+
+
+
+-- Local stuff
+
+local key_metatable = {}
+
+---
+-- This function is the ``work-horse'' for declaring things. It allows
+-- you to specify on the algorithmic layer that a key ``is available''
+-- for use on the display layer. There is just one function for
+-- handling all declarations in order to make the declarations
+-- easy-to-use since you just need to import a single function:
+-- %
+--\begin{codeexample}[code only, tikz syntax=false]
+--local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare
+--\end{codeexample}
+--
+-- You can now use |declare| it as follows: You pass it a table
+-- containing information about the to-be-declared key. The table
+-- \emph{must} have a field |key| whose value is unique and must be a
+-- string. If the value of |key| is, say, |"foo"|, the
+-- parameter can be set on the display layer such as, say, the
+-- \tikzname\ layer, using |/graph drawing/foo|. Here is a typical
+-- example of how a declaration is done:
+-- %
+--\begin{codeexample}[code only, tikz syntax=false]
+-- ---
+-- declare {
+-- key = "electrical charge",
+-- type = "number",
+-- initial = "1.0",
+--
+-- summary = "The ``electrical charge'' is a property...",
+-- documentation = [[...]],
+-- examples = [[...]]
+-- }
+--\end{codeexample}
+--
+-- \medskip\noindent\textbf{Inlining Documentation.}
+-- The three keys |summary|, |documentation| and |examples| are
+-- intended for the display layer to give the users information about
+-- what the key does. The |summary| should be a string that succinctly
+-- describes the option. This text will typically be displayed for
+-- instance as a ``tool tip'' or in an option overview. The
+-- |documentation| optionally provides more information and should be
+-- typeset using \TeX. The |examples| can either be a single string or
+-- an array of strings. Each should be a \tikzname\ example
+-- demonstrating how the key is used.
+--
+-- Note that you can take advantage of the Lua syntax of enclosing
+-- very long multi-line strings in |[[| and |]]|. As a bonus, if the
+-- summary, documentation, or an example starts and ends with a quote,
+-- these two quotes will be stripped. This allows you to enclose the
+-- whole multi-line string (additionally) in quotes, leading to better
+-- syntax highlighting in editors.
+--
+-- \medskip\noindent\textbf{External Documentation.}
+-- It is sometimes more desirable to put the documentation of a key
+-- into an external file. First, this makes the code leaner and, thus,
+-- faster to read (both for humans and for computers). Second, for C
+-- code, it is quite inconvenient to have long strings inside a C
+-- file. In such cases, you can use the |documentation_in| field:
+-- %
+--\begin{codeexample}[code only, tikz syntax=false]
+-- ---
+-- declare {
+-- key = "electrical charge",
+-- type = "number",
+-- initial = "1.0",
+-- documentation_in = "some_filename"
+-- }
+--\end{codeexample}
+--
+-- The |some_filename| must be the name of a Lua file that will be
+-- read ``on demand'', that is, whenever someone tries to access the
+-- documentation, summary, or examples field of the key, this file
+-- will be loaded using |require|. The file should then use
+-- |pgf.gd.doc| to install the missing information in the keys.
+--
+-- \medskip\noindent\textbf{The Use Field.}
+-- When you declare a key, you can provide a |use| field. If present,
+-- you must set it to an array of small tables which have two fields:
+-- %
+-- \begin{itemize}
+-- \item |key| This is the name of another key or a function.
+-- \item |value| This is either a value (like a string or a number) or
+-- a function or |nil|.
+-- \end{itemize}
+--
+-- Here is an example:
+-- %
+--\begin{codeexample}[code only, tikz syntax=false]
+-- ---
+-- declare {
+-- key = "binary tree layout",
+-- use = {
+-- { key = "minimum number of children", value = 2 },
+-- { key = "significant sep", value = 12 },
+-- { key = "tree layout" }
+-- },
+-- summary = "The |binary tree layout| places node...",
+-- documentation = ...,
+-- examples = ...,
+-- }
+--\end{codeexample}
+--
+-- The effect of a |use| field is the following: Whenever the key is
+-- encountered on the option stack, the key is first handled
+-- normally. Then, we iterate over all elements of the |use|
+-- array. For each element, we perform the action as if the |key| of
+-- the array had been set explicitly to the value given by the |value|
+-- field. If the |value| is a function, we pass a different value to
+-- the key, namely the result of applying the function to the value
+-- originally passed to the original key. Here is a typical example:
+-- %
+--\begin{codeexample}[code only, tikz syntax=false]
+-- ---
+-- declare {
+-- key = "level sep",
+-- type = "length",
+-- use = {
+-- { key = "level pre sep", value = function (v) return v/2 end },
+-- { key = "level post sep", value = function (v) return v/2 end }
+-- },
+-- summary = "..."
+-- }
+--\end{codeexample}
+--
+-- Just like the value, the key itself can also be a function. In this
+-- case, the to-be-used key is also computed by applying the function
+-- to the value passed to the original key.
+--
+-- As mentioned at the beginning, |declare| is a work-horse that will call
+-- different internal functions depending on whether you declare a
+-- parameter key or a new algorithm or a collection kind. Which kind
+-- of declaration is being done is detected by the presence of certain
+-- fields in the table passed to |t|. The different kind of
+-- possible declarations are documented in the |declare_...|
+-- functions. Note that these functions are internal and cannot be
+-- called from outside; you must use the |declare| function.
+--
+-- @param t A table contain the field |key| and other fields as
+-- described.
+
+function InterfaceToAlgorithms.declare (t)
+ local keys = InterfaceCore.keys
+
+ -- Sanity check:
+ assert (type(t.key) == "string" and t.key ~= "", "parameter key may not be the empty string")
+ if keys[t.key] or t.keys == "algorithm_phases" then
+ error("parameter '" .. t.key .. "' already declared")
+ end
+
+ for _,h in ipairs (declare_handlers) do
+ if h.test(t) then
+ if h.handler(t) then
+ break
+ end
+ end
+ end
+
+ -- Attach metatable:
+ setmetatable (t, key_metatable)
+
+ -- Set!
+ keys[t.key] = t
+ keys[#keys + 1] = t
+end
+
+
+function key_metatable.__index (key_table, what)
+ if what == "documentation" or what == "summary" or what == "examples" then
+ local doc = rawget(key_table,"documentation_in")
+ if doc then
+ require (doc)
+ return rawget(key_table, what)
+ end
+ end
+end
+
+
+
+---
+-- This function is called by |declare| for ``normal parameter keys'',
+-- which are all keys for which no special field like |algorithm| or
+-- |layer| is declared. You write
+-- %
+--\begin{codeexample}[code only, tikz syntax=false]
+-- ---
+-- declare {
+-- key = "electrical charge",
+-- type = "number",
+-- initial = "1.0",
+--
+-- summary = "The ``electrical charge'' is a property...",
+-- documentation = [[...]],
+-- examples = [[...]]
+-- }
+--\end{codeexample}
+--
+-- When an author writes |my node[electrical charge=5-3]| in the
+-- description of her graph, the object |vertex| corresponding to the
+-- node |my node| will have a field |options| attached to it with
+-- %
+--\begin{codeexample}[code only, tikz syntax=false]
+--vertex.options["electrical charge"] == 2
+--\end{codeexample}
+--
+-- The |type| field does not refer to Lua types. Rather, these types are
+-- sensible types for graph drawing and they are mapped by the higher
+-- layers to Lua types. In detail, the following types are available:
+-- %
+-- \begin{itemize}
+-- \item |number| A dimensionless number. Will be mapped to a normal
+-- Lua |number|. So, when the author writes |foo=5*2|, the |foo| key
+-- of the |options| field of the corresponding object will be set to
+-- |10.0|.
+-- \item |length| A ``dimension'' in the sense of \TeX\ (a number with
+-- a dimension like |cm| attached to it). It is the job of the display
+-- layer to map this to a number in ``\TeX\ points'', that is, to a
+-- multiple of $1/72.27$th of an inch.
+-- \item |time| A ``time'' in the sense of |\pgfparsetime|. Examples
+-- are |6s| or |0.1min| or |6000ms|, all of which will map to |6|.
+-- \item |string| Some text. Will be mapped to a Lua |string|.
+-- \item |canvas coordinate| A position on the canvas. Will be mapped
+-- to a |model.Coordinate|.
+-- \item |boolean| A Boolean value.
+-- \item |raw| Some to-be-executed Lua text.
+-- \item |direction| Normally, an angle; however,
+-- the special values of |down|, |up|, |left|, |right| as well as the
+-- directions |north|, |north west|, and so on are also legal on the
+-- display layer. All of them will be mapped to a number. Furthermore,
+-- a vertical bar (\verb!|!) will be mapped to |-90| and a minus sign
+-- (|-|) will be mapped to |0|.
+-- \item |hidden| A key of this type ``cannot be set'', that is,
+-- users cannot set this key at all. However algorithms can still read
+-- this key and, through the use of |alias|, can use the key as a
+-- handle to another key.
+-- \item |user value| The key stores a Lua user value (userdata). Such
+-- keys can only be set from C since user values cannot be created in
+-- Lua (let alone in \tikzname).
+-- \end{itemize}
+--
+-- If the |type| field is missing, it is automatically set to
+-- |"string"|.
+--
+-- A parameter can have an |initial| value. This value will be used
+-- whenever the parameter has not been set explicitly for an object.
+--
+-- A parameter can have a |default| value. This value will be used as
+-- the parameter value whenever the parameter is explicitly set, but
+-- no value is provided. For a key of type |"boolean"|, if no
+-- |default| is provided, |"true"| will be used automatically.
+--
+-- A parameter can have an |alias| field. This field must be set to
+-- the name of another key or to a function. Whenever you access the
+-- current key and this key is not set, the |alias| key is tried
+-- instead. If it is set, its value will be returned (if the |alias|
+-- key has itself an alias set, this is tried recursively). If the
+-- alias is not set either and neither does it have an initial value,
+-- the |initial| value is used. Note that in case the alias has its
+-- |initial| field set, the |initial| value of the current key will
+-- never be used.
+--
+-- The main purpose of the current key is to allow algorithms to
+-- introduce their own terminology for keys while still having access
+-- to the standard keys. For instance, the |OptimalHierarchyLayout|
+-- class uses the name |layerDistance| for what would be called
+-- |level distance| in the rest of the graph drawing system. In this
+-- case, we can declare the |layerDistance| key as follows:
+-- %
+--\begin{codeexample}[code only, tikz syntax=false]
+-- declare {
+-- key = "layerDistance",
+-- type = "length",
+-- alias = "level distance"
+-- }
+--\end{codeexample}
+--
+-- Inside the algorithm, we can write |...options.layerDistance| and
+-- will get the current value of the |level distance| unless the
+-- |layerDistance| has been set explicitly. Indeed, we might set the
+-- |type| to |hidden| to ensure that \emph{only} the |level distance|
+-- can and must set to set the layerDistance.
+--
+-- Note that there is a difference between |alias| and the |use|
+-- field: Suppose we write
+-- %
+--\begin{codeexample}[code only, tikz syntax=false]
+-- declare {
+-- key = "layerDistance",
+-- type = "length",
+-- use = {
+-- { key = "level distance", value = lib.id }
+-- }
+-- }
+--\end{codeexample}
+--
+-- Here, when you say |layerDistance=1cm|, the |level distance| itself
+-- will be modified. When the |level distance| is set, however, the
+-- |layerDistance| will not be modified.
+--
+-- If the alias is a function, it will be called with the option table
+-- as its parameter. You can thus say things like
+-- %
+--\begin{codeexample}[code only, tikz syntax=false]
+-- declare {
+-- key = "layerDistance",
+-- type = "length",
+-- alias = function (option)
+-- return option["layer pre dist"] + option["layer post dist"]
+-- end
+-- }
+--\end{codeexample}
+--
+-- As a special courtesy to C code, you can also set the key
+-- |alias_function_string|, which allows you to put the function into
+-- a string that is read using |loadstring|.
+--
+-- (You cannot call this function directly, it is included for
+-- documentation purposes only.)
+--
+-- @param t The table originally passed to |declare|.
+
+local function declare_parameter (t)
+
+ t.type = t.type or "string"
+
+ if t.type == "boolean" and t.default == nil then
+ t.default = true
+ end
+
+ -- Normal key
+ assert (type(t.type) == "string", "key type must be a string")
+
+ -- Declare via the hub:
+ if t.type ~= "hidden" then
+ InterfaceCore.binding:declareCallback(t)
+
+ -- Handle initials:
+ if t.initial then
+ InterfaceCore.option_initial[t.key] = InterfaceCore.convert(t.initial, t.type)
+ end
+ end
+
+ if t.alias_function_string and not t.alias then
+ local count = 0
+ t.alias = load (
+ function ()
+ count = count + 1
+ if count == 1 then
+ return "return "
+ elseif count == 2 then
+ return t.alias_function_string
+ else
+ return nil
+ end
+ end)()
+ end
+
+ if t.alias then
+ assert (type(t.alias) == "string" or type(t.alias == "function"), "alias must be a string or a function")
+ InterfaceCore.option_aliases[t.key] = t.alias
+ end
+
+ return true
+end
+
+
+
+
+---
+-- This function is called by |declare| for ``algorithm
+-- keys''. These keys are normally used without a value as in just
+-- |\graph[tree layout]|, but you can optionally pass a value to
+-- them. In this case, this value must be the name of a \emph{phase}
+-- and the algorithm of this phase will be set (and not the
+-- default phase of the key), see the description of phases below for
+-- details.
+--
+-- Algorithm keys are detected by the presence of the field |algorithm|
+-- in the table |t| passed to |declare|. Here is an example of how it
+-- is used:
+-- %
+--\begin{codeexample}[code only, tikz syntax=false]
+-- local ReingoldTilford1981 = {}
+--
+-- ---
+-- declare {
+-- key = "tree layout",
+-- algorithm = ReingoldTilford1981,
+--
+-- preconditions = {
+-- connected = true,
+-- tree = true
+-- },
+--
+-- postconditions = {
+-- upward_oriented = true
+-- },
+--
+-- summary = "The Reingold--Tilford method is...",
+-- documentation = ...,
+-- examples = ...,
+-- }
+--
+-- function ReingoldTilford1981:run()
+-- ...
+-- end
+--\end{codeexample}
+--
+-- The |algorithm| field expects either a table or a string as
+-- value. If you provide a string, then |require| will be applied to
+-- this string to obtain the table; however, this will happen only
+-- when the key is actually used for the first time. This means that
+-- you can declare (numerous) algorithms in a library without these
+-- algorithms actually being loaded until they are needed.
+--
+-- Independently of how the table is obtained, it will be ``upgraded''
+-- to a class by setting its |__index| field and installing a static
+-- |new| function (which takes a table of initial values as
+-- argument). Both these settings will only be done if they have not
+-- yet been performed.
+--
+-- Next, you can specify the fields |preconditions| and
+-- |postconditions|. The preconditions are a table that tell the graph
+-- drawing engine what kind of graphs your algorithm expects. If the
+-- input graph is not of this kind, it will be automatically
+-- transformed to meet this condition. Similarly, the postconditions
+-- tell the engine about properties of your graph after the algorithm
+-- has run. Again, additional transformations may be performed.
+--
+-- You can also specify the field |phase|. This tells the graph
+-- drawing engine which ``phase'' of the graph drawing process your
+-- option applies to. Each time you select an algorithm later on
+-- through use of the algorithm's key, the algorithm for this phase
+-- will be set; algorithms of other phases will not be changed.
+-- For instance, when an algorithm is part of the spanning tree
+-- computation, its phase will be |"spanning tree computation"| and
+-- using its key does not change the main algorithm, but only the
+-- algorithm used during the computation of a spanning tree for the
+-- current graph (in case this is needed by the main algorithm). In
+-- case the |phase| field is missing, the phase |main| is used. Thus,
+-- when no phase field is given, the key will change the main
+-- algorithm used to draw the graph.
+--
+-- Later on, the algorithm set for the current phase can be accessed
+-- through the special |algorithm_phases| field of |options|
+-- tables. The |algorithm_phases| table will contain two fields for each
+-- phase for which some algorithm has been set: One field is the name
+-- of the phase and its value will be the most recently set algorithm
+-- (class) set for this phase. The other field is the name of the
+-- phase followed by |" stack"|. It will contain an array of all
+-- algorithm classes that have been set for this key with the most
+-- recently at the end.
+--
+-- The following example shows the declaration of an algorithm that is
+-- the default for the phase |"spanning tree computation"|:
+-- %
+--\begin{codeexample}[code only, tikz syntax=false]
+-- ---
+-- declare {
+-- key = "breadth first spanning tree",
+-- algorithm = {
+-- run =
+-- function (self)
+-- return SpanningTreeComputation.computeSpanningTree(self.ugraph, false, self.events)
+-- end
+-- },
+-- phase = "spanning tree computation",
+-- phase_default = true,
+-- summary = ...
+-- }
+--\end{codeexample}
+--
+-- The algorithm is called as follows during a run of the main
+-- algorithms:
+-- %
+--\begin{codeexample}[code only, tikz syntax=false]
+-- local graph = ... -- the graph object
+-- local spanning_algorithm_class = graph.options.algorithm_phases["spanning tree computation"]
+-- local spanning_algorithm =
+-- spanning_algorithm_class.new{
+-- ugraph = ugraph,
+-- events = scope.events
+-- }
+-- local spanning_tree = spanning_algorithm:run()
+--\end{codeexample}
+--
+-- If you set the |phase_default| field of |t| to |true|, the algorithm will
+-- be installed as the default algorithm for the phase. This can be
+-- done only once per phase. Furthermore, for such a default algorithm
+-- the |algorithm| key must be table, it may not be a string (in other
+-- words, all default algorithms are loaded immediately). Accessing
+-- the |algorithm_phases| table for a phase for which no algorithm has
+-- been set will result in the default algorithm and the phase stack
+-- will also contain this algorithm; otherwise the phase stack will be empty.
+--
+-- (You cannot call this function directly, it is included for
+-- documentation purposes only.)
+--
+-- @param t The table originally passed to |declare|.
+
+local function declare_algorithm (t)
+ -- Algorithm declaration!
+ assert(type(t.algorithm) == "table" or type(t.algorithm) == "string")
+
+ t.phase = t.phase or "main"
+
+ local function make_class ()
+ local class
+
+ if type(t.algorithm) == "table" then
+ class = lib.class(t.algorithm)
+ else
+ class = lib.class(require(t.algorithm))
+ end
+
+ -- Now, save pre- and postconditions
+ class.preconditions = t.preconditions or {}
+ class.postconditions = t.postconditions or {}
+
+ -- Save phase
+ class.phase = t.phase
+
+ -- Compatibility
+ class.old_graph_model = t.old_graph_model
+
+ return class
+ end
+
+ -- Store this:
+ local store_me
+ if type(t.algorithm) == "table" then
+ store_me = make_class()
+ else
+ store_me = make_class
+ end
+
+ -- Save in the algorithm_classes table:
+ InterfaceCore.algorithm_classes[t.key] = store_me
+
+ assert(t.type == nil, "type may not be set for an algorithm key")
+ t.type = "string"
+
+ -- Install!
+ InterfaceCore.binding:declareCallback(t)
+
+ if t.phase_default then
+ assert (not InterfaceCore.option_initial.algorithm_phases[t.phase],
+ "default algorithm for phase already set")
+ assert (type(store_me) == "table",
+ "default algorithms must be loaded immediately")
+ InterfaceCore.option_initial.algorithm_phases[t.phase] = store_me
+ InterfaceCore.option_initial.algorithm_phases[t.phase .. " stack"] = { store_me }
+ else
+ InterfaceCore.option_initial.algorithm_phases[t.phase .. " stack"] = {
+ dummy = true -- Remove once Lua Link Bug is fixed
+ }
+ end
+
+ return true
+end
+
+
+
+
+---
+-- This function is called by |declare| for ``collection kinds''. They
+-- are detected by the presence of the field |layer|
+-- in the table |t| passed to |declare|. See the class |Collection|
+-- for details on what a collection and a collection kind is.
+--
+-- The |key| field of the table |t| passed to this function is both
+-- the name of the to-be-declared collection kind as well as the key
+-- that is used on the display layer to indicate that a node or edge
+-- belongs to a collection.
+--
+-- \medskip
+-- \noindent\textbf{The Display Layer.}
+-- Let us first have a look at what happens on the display layer:
+-- A key |t.key| is setup on the display layer that, when used inside
+-- a graph drawing scope, starts a new collection of the specified
+-- kind. ``Starts'' means that all nodes and edges mentioned in the
+-- rest of the current option scope will belong to a new collection
+-- of kind |t.key|.
+-- %
+--\begin{codeexample}[code only, tikz syntax=false]
+--declare { key = "hyper", layer = 1 }
+--\end{codeexample}
+-- %
+-- you can say on the \tikzname\ layer
+-- %
+--\begin{codeexample}[code only]
+-- \graph {
+-- a, b, c, d;
+-- { [hyper] a, b, c }
+-- { [hyper] b, c, d }
+-- };
+--\end{codeexample}
+--
+-- In this case, the nodes |a|, |b|, |c| will belong to a collection of
+-- kind |hyper|. The nodes |b|, |c|, and |d| will (also) belong to
+-- another collection of the same kind |hyper|. You can nest
+-- collections; in this case, nodes will belong to several
+-- collections.
+--
+-- The effect of declaring a collection kind on the algorithm layer
+-- it, first of all, that |scope.collections| will have a field named
+-- by the collection kind. This field will store an array that
+-- contains all collections that were declared as part of the
+-- graph. For instance, |collections.hyper| will contain all
+-- hyperedges, each of which is a table with the following fields: The
+-- |vertices| and |edges| fields each contain arrays of all objects
+-- being part of the collection. The |sub| field is an array of
+-- ``subcollections'', that is, all collections that were started
+-- inside another collection. (For the collection kinds |hyper| and
+-- |same layer| this makes no sense, but subgraphs could, for instance,
+-- be nested.)
+--
+-- \medskip
+-- \noindent\textbf{Rendering of Collections.}
+-- For some kinds of collections, it makes sense to \emph{render} them,
+-- but only after the graph drawing algorithm has run. For this
+-- purpose, the binding layer will use a callback for each collection
+-- kind and each collection, see the |Binding| class for details.
+-- Suppose, for instance, you would
+-- like hyperedges to be rendered. In this case, a graph drawing
+-- algorithm should iterate over all collections of type |hyper| and
+-- compute some hints on how to render the hyperedge and store this
+-- information in the |generated_options| table of the hyperedge. Then,
+-- the binding layer will ask the display layer to run some some code
+-- that is able to read key--value pairs passed to
+-- it (which are the key--value pairs of the |generated_options| table)
+-- and use this information to nicely draw the hyperedge.
+--
+-- The number |t.layer| determines in which order the different
+-- collection kinds are rendered.
+--
+-- The last parameter, the layer number, is used to specify the order
+-- in which the different collection kinds are rendered. The higher the
+-- number, the later the collection will be rendered. Thus, if there is
+-- a collection kind with layer number 10 and another with layer number
+-- 20, all collections of the first kind will be rendered first,
+-- followed by all collections of the second kind.
+--
+-- Collections whose layer kinds are non-negative get rendered
+-- \emph{after} the nodes and edges have already been rendered. In
+-- contrast, collections with a negative layer number get shown
+-- ``below'' the nodes and edges.
+--
+-- (You cannot call this function directly, it is included for
+-- documentation purposes only.)
+--
+-- @param t The table originally passed to |declare|.
+
+local function declare_collection_kind (t)
+ assert (type(t.layer) == "number", "layer must be a number")
+
+ local layer = t.layer
+ local kind = t.key
+ local kinds = InterfaceCore.collection_kinds
+ local new_entry = { kind = kind, layer = layer }
+
+ -- Insert into table part:
+ kinds[kind] = new_entry
+
+ -- Insert into array part:
+ local found
+ for i=1,#kinds do
+ if kinds[i].layer > layer or (kinds[i].layer == layer and kinds[i].kind > kind) then
+ table.insert(kinds, i, new_entry)
+ return
+ end
+ end
+
+ kinds[#kinds+1] = new_entry
+
+ -- Bind
+ InterfaceCore.binding:declareCallback(t)
+
+ return true
+end
+
+
+
+-- Build in handlers:
+
+declare_handlers = {
+ { test = function (t) return t.algorithm_written_in_c end, handler = InterfaceToC.declare_algorithm_written_in_c },
+ { test = function (t) return t.algorithm end, handler = declare_algorithm },
+ { test = function (t) return t.layer end, handler = declare_collection_kind },
+ { test = function (t) return true end, handler = declare_parameter }
+}
+
+
+
+
+
+
+
+
+---
+-- Finds a node by its name. This method should be used by algorithms
+-- for which a node name is specified in some option and, thus, needs
+-- to be converted to a vertex object during a run of the algorithm.
+--
+-- @param name A node name
+--
+-- @return The vertex of the given name in the syntactic digraph or
+-- |nil|.
+
+function InterfaceToAlgorithms.findVertexByName(name)
+ return InterfaceCore.topScope().node_names[name]
+end
+
+
+
+
+
+-- Helper function
+local function add_to_collections(collection,where,what)
+ if collection then
+ LookupTable.addOne(collection[where],what)
+ add_to_collections(collection.parent,where,what)
+ end
+end
+
+local unique_count = 1
+
+---
+-- Generate a new vertex in the syntactic digraph. Calling this method
+-- allows algorithms to create vertices that are not present in the
+-- original input graph. Using the graph drawing coroutine, this
+-- function will pass back control to the display layer in order to
+-- render the vertex and, thereby, create precise size information
+-- about it.
+--
+-- Note that creating new vertices in the syntactic digraph while the
+-- algorithm is already running is a bit at odds with the notion of
+-- treating graph drawing as a series of graph transformations: For
+-- instance, when a new vertex is created, the graph will (at least
+-- temporarily) no longer be connected; even though an algorithm may
+-- have requested that it should only be fed connected
+-- graphs. Likewise, more complicated requirements like insisting on
+-- the graph being a tree also cannot be met.
+--
+-- For these reasons, the following happens, when a new vertex is
+-- created using the function:
+-- %
+-- \begin{enumerate}
+-- \item The vertex is added to the syntactic digraph.
+-- \item It is added to all layouts on the current layout stack. When
+-- a graph drawing algorithm is run, it is not necessarily run on the
+-- original syntactic digraph. Rather, a sequence / stack of nested
+-- layouts may currently
+-- be processed and the vertex is added to all of them.
+-- \item The vertex is added to both the |digraph| and the |ugraph| of
+-- the current algorithm.
+-- \end{enumerate}
+--
+-- @param algorithm An algorithm for whose syntactic digraph the node
+-- should be added
+-- @param init A table of initial values for the node that is passed
+-- to |Binding:createVertex|, see that function for details.
+--
+-- @return The newly created node
+--
+function InterfaceToAlgorithms.createVertex(algorithm, init)
+
+ -- Setup
+ local scope = InterfaceCore.topScope()
+ local binding = InterfaceCore.binding
+
+ -- Setup node
+ if not init.name then
+ init.name = "internal@gd@node@" .. unique_count
+ unique_count = unique_count + 1
+ end
+
+ -- Does vertex already exist?
+ assert (not scope.node_names[name], "node already created")
+
+ if not init.shape or init.shape == "none" then
+ init.shape = "rectangle"
+ end
+
+ -- Call binding
+ binding:createVertex(init)
+
+ local v = assert(scope.node_names[init.name], "internal node creation failed")
+
+ -- Add vertex to the algorithm's digraph and ugraph
+ algorithm.syntactic_component:add {v}
+ algorithm.digraph:add {v}
+ algorithm.ugraph:add {v}
+
+ -- Compute bounding boxes:
+ LayoutPipeline.prepareBoundingBoxes(algorithm.rotation_info, algorithm.adjusted_bb, algorithm.digraph, {v})
+
+ -- Add the node to the layout stack:
+ add_to_collections(algorithm.layout, "vertices", v)
+
+ algorithm.layout_graph:add { v }
+
+ return v
+end
+
+
+
+---
+-- Generate a new edge in the syntactic digraph. This method is quite
+-- similar to |createVertex| and has the same effects with respect to
+-- the edge: The edge is added to the syntactic digraph and also to
+-- all layouts on the layout stack. Furthermore, appropriate edges are
+-- added to the |digraph| and the |ugraph| of the algorithm currently
+-- running.
+--
+-- @param algorithm An algorithm for whose syntactic digraph the node should be added
+-- @param tail A syntactic tail vertex
+-- @param head A syntactic head vertex
+-- @param init A table of initial values for the edge.
+--
+-- The following fields are useful for |init|:
+-- %
+-- \begin{itemize}
+-- \item |init.direction| If present, a direction for the edge. Defaults to "--".
+-- \item |init.options| If present, some options for the edge.
+-- \item |init.generated_options| A table that is passed back to the
+-- display layer as a list of key-value pairs in the syntax of
+-- |declare_parameter|.
+-- \end{itemize}
+
+function InterfaceToAlgorithms.createEdge(algorithm, tail, head, init)
+
+ init = init or {}
+
+ -- Setup
+ local scope = InterfaceCore.topScope()
+ local binding = InterfaceCore.binding
+ local syntactic_digraph = algorithm.layout_graph
+ local syntactic_component = algorithm.syntactic_component
+
+ assert (syntactic_digraph:contains(tail) and
+ syntactic_digraph:contains(head),
+ "attempting to create edge between nodes that are not in the syntactic digraph")
+
+ local arc = syntactic_digraph:connect(tail, head)
+
+ local edge = Edge.new {
+ head = head,
+ tail = tail,
+ direction = init.direction or "--",
+ options = init.options or algorithm.layout.options,
+ path = init.path,
+ generated_options = init.generated_options
+ }
+
+ -- Add to arc
+ arc.syntactic_edges[#arc.syntactic_edges+1] = edge
+
+ local s_arc = syntactic_component:connect(tail, head)
+ s_arc.syntactic_edges = arc.syntactic_edges
+
+ -- Create Event
+ local e = InterfaceToDisplay.createEvent ("edge", { arc, #arc.syntactic_edges })
+ edge.event = e
+
+ -- Make part of collections
+ for _,c in ipairs(edge.options.collections) do
+ LookupTable.addOne(c.edges, edge)
+ end
+
+ -- Call binding
+ binding.storage[edge] = {}
+ binding:everyEdgeCreation(edge)
+
+ -- Add edge to digraph and ugraph
+ local direction = edge.direction
+ if direction == "->" then
+ algorithm.digraph:connect(tail, head)
+ elseif direction == "<-" then
+ algorithm.digraph:connect(head, tail)
+ elseif direction == "--" or direction == "<->" then
+ algorithm.digraph:connect(tail, head)
+ algorithm.digraph:connect(head, tail)
+ end
+ algorithm.ugraph:connect(tail, head)
+ algorithm.ugraph:connect(head, tail)
+
+ -- Add edge to layouts
+ add_to_collections(algorithm.layout, "edges", edge)
+
+end
+
+
+
+
+
+-- Done
+
+return InterfaceToAlgorithms
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface/InterfaceToC.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface/InterfaceToC.lua
new file mode 100644
index 0000000000..282727b66a
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface/InterfaceToC.lua
@@ -0,0 +1,78 @@
+-- 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 contains functions that are used (on the Lua side) to
+-- prepare a graph for use in C and, vice versa, to translate back the
+-- results of C to Lua.
+
+local InterfaceToC = {}
+
+-- Imports
+
+local lib = require "pgf.gd.lib"
+
+
+---
+-- This function is called by |declare| for ``algorithm
+-- keys'' where the algorithm is not written in Lua, but rather in the
+-- programming language C. You do not call this function yourself;
+-- |InterfaceFromC.h| will do it for you. Nevertheless, if you
+-- provide a table to |declare| with the field
+-- |algorithm_written_in_c| set, the following happens: The table's
+-- |algorithm| field is set to an algorithm class object whose |run|
+-- method calls the function passed via the
+-- |algorithm_written_in_c| field. It will be called with the
+-- following parameters (in that order):
+-- %
+-- \begin{enumerate}
+-- \item The to-be-laid out digraph. This will not be the whole layout
+-- graph (syntactic digraph) if preprocessing like decomposition into
+-- connected components is used.
+-- \item An array of the digraph's vertices, but with the table part
+-- hashing vertex objects to their indices in the array part.
+-- \item An array of the syntactic edges of the digraph. Like the
+-- array, the table part will hash back the indices of the edge objects.
+-- \item The algorithm object.
+-- \end{enumerate}
+--
+-- @param t The table originally passed to |declare|.
+
+function InterfaceToC.declare_algorithm_written_in_c (t)
+ t.algorithm = {
+ run = function (self)
+ local back_table = lib.icopy(self.ugraph.vertices)
+ for i,v in ipairs(self.ugraph.vertices) do
+ back_table[v] = i
+ end
+ local edges = {}
+ for _,a in ipairs(self.ugraph.arcs) do
+ local b = self.layout_graph:arc(a.tail,a.head)
+ if b then
+ lib.icopy(b.syntactic_edges, edges)
+ end
+ end
+ for i=1,#edges do
+ edges[edges[i]] = i
+ end
+ collectgarbage("stop") -- Remove once Lua Link Bug is fixed
+ t.algorithm_written_in_c (self.digraph, back_table, edges, self)
+ collectgarbage("restart") -- Remove once Lua Link Bug is fixed
+ end
+ }
+end
+
+
+
+-- Done
+
+return InterfaceToC
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface/InterfaceToDisplay.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface/InterfaceToDisplay.lua
new file mode 100644
index 0000000000..23018efcaa
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface/InterfaceToDisplay.lua
@@ -0,0 +1,1002 @@
+-- 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 class provides the interface between a display
+-- layer (like \tikzname\ or a graph editor) and graph drawing
+-- system. Another class, |InterfaceToAlgorithms|, binds the algorithm
+-- layer (which are written in Lua) to the graph drawing system.
+--
+-- The functions declared here are independent of the actual display
+-- layer. Rather, the differences between the layers are encapsulated
+-- by subclasses of the |Binding| class, see that class for
+-- details. Thus, when a new display layer is written, the present
+-- class is \emph{used}, but not \emph{modified}. Instead, only a new
+-- binding is created and all display layer specific interaction is
+-- put there.
+--
+-- The job of this class is to provide convenient methods that can be
+-- called by the display layer. For instance, it provides methods for
+-- starting a graph drawing scope, managing the stack of such scope,
+-- adding a node to a graph and so on.
+
+local InterfaceToDisplay = {}
+
+-- Namespace
+require("pgf.gd.interface").InterfaceToDisplay = InterfaceToDisplay
+
+
+-- Imports
+local InterfaceCore = require "pgf.gd.interface.InterfaceCore"
+local Scope = require "pgf.gd.interface.Scope"
+
+local Binding = require "pgf.gd.bindings.Binding"
+
+local Sublayouts = require "pgf.gd.control.Sublayouts"
+local LayoutPipeline = require "pgf.gd.control.LayoutPipeline"
+
+local Digraph = require "pgf.gd.model.Digraph"
+local Vertex = require "pgf.gd.model.Vertex"
+local Edge = require "pgf.gd.model.Edge"
+local Collection = require "pgf.gd.model.Collection"
+
+local Storage = require "pgf.gd.lib.Storage"
+local LookupTable = require "pgf.gd.lib.LookupTable"
+local Event = require "pgf.gd.lib.Event"
+
+local lib = require "pgf.gd.lib"
+
+
+-- Forward declarations
+local get_current_options_table
+local render_collections
+local push_on_option_stack
+local vertex_created
+
+-- Local objects
+
+local phase_unique = {} -- a unique handle
+local collections_unique = {} -- a unique handle
+local option_cache = nil -- The option cache
+
+
+
+
+---
+-- Initialize the binding. This function is called once by the display
+-- layer at the very beginning. For instance, \tikzname\ does the
+-- following call:
+-- %
+--\begin{codeexample}[code only, tikz syntax=false]
+--InterfaceToDisplay.bind(require "pgf.gd.bindings.BindingToPGF")
+--\end{codeexample}
+--
+-- Inside this call, many standard declarations will be executed, that
+-- is, the declared binding will be used immediately.
+--
+-- Subsequently, the |binding| field of the |InterfaceCore| can be used.
+--
+-- @param class A subclass of |Binding|.
+
+function InterfaceToDisplay.bind(class)
+ assert (not InterfaceCore.binding, "binding already initialized")
+
+ -- Create a new object
+ InterfaceCore.binding = setmetatable({}, class)
+
+ -- Load these libraries, which contain many standard declarations:
+ require "pgf.gd.model.library"
+ require "pgf.gd.control.library"
+end
+
+
+
+
+---
+-- Start a graph drawing scope. Note that this is not the same as
+-- starting a subgraph / sublayout, which are local to a graph drawing
+-- scope: When a new graph drawing scope is started, it is pushed on
+-- top of a stack of graph drawing scopes and all other ``open''
+-- scopes are no longer directly accessible. All method calls to an
+-- |Interface...| object will refer to this newly created scope until
+-- either a new scope is opened or until the current scope is closed
+-- once more.
+--
+-- Each graph drawing scope comes with a syntactic digraph that is
+-- build using methods like |addVertex| or |addEdge|.
+--
+-- @param height The to-be-used height of the options stack. All
+-- options above this height will be popped prior to attacking the
+-- options to the syntactic digraph.
+
+function InterfaceToDisplay.beginGraphDrawingScope(height)
+
+ -- Create a new scope table
+ local scope = Scope.new {}
+
+ -- Setup syntactic digraph:
+ local g = scope.syntactic_digraph
+
+ g.options = get_current_options_table(height)
+ g.syntactic_digraph = g
+ g.scope = scope
+
+ -- Push scope:
+ InterfaceCore.scopes[#InterfaceCore.scopes + 1] = scope
+end
+
+
+
+---
+-- Arranges the current graph using the specified algorithm and options.
+--
+-- This function should be called after the graph drawing scope has
+-- been opened and the syntactic digraph has been completely
+-- specified. It will now start running the algorithm specified
+-- through the |algorithm_phase| options.
+--
+-- Internally, this function creates a coroutine that will run the current graph
+-- drawing algorithm. Coroutines are needed since a graph drawing
+-- algorithm may choose to create a new node. In this case, the
+-- algorithm needs to be suspended and control must be returned back
+-- to the display layer, so that the node can be typeset in order to
+-- determine the precise size information. Once this is done, control
+-- must be passed back to the exact point inside the algorithm where
+-- the node was created. Clearly, all of these actions are exactly
+-- what coroutines are for.
+--
+-- @return Time it took to run the algorithm
+
+function InterfaceToDisplay.runGraphDrawingAlgorithm()
+
+ -- Time things
+ local start = os.clock()
+
+ -- Setup
+ local scope = InterfaceCore.topScope()
+ assert(not scope.coroutine, "coroutine already created for current gd scope")
+
+ -- The actual drawing function
+ local function run ()
+ if #scope.syntactic_digraph.vertices == 0 then
+ -- Nothing needs to be done
+ return
+ end
+
+ LayoutPipeline.run(scope)
+ end
+
+ scope.coroutine = coroutine.create(run)
+
+ -- Run it:
+ InterfaceToDisplay.resumeGraphDrawingCoroutine()
+
+ -- End timing:
+ local stop = os.clock()
+
+ return stop - start
+end
+
+
+---
+-- Resume the graph drawing coroutine.
+--
+-- This function is the work horse of the coroutine management. It
+-- gets called whenever control passes back from the display layer to
+-- the algorithm level. We resume the graph drawing coroutine so that the
+-- algorithm can start/proceed. The tricky part is when the algorithm
+-- yields, but is not done. In this case, the code needed for creating
+-- a new node is passed back to the display layer through the binding,
+-- which must then execute the code and then resuming the coroutine.
+--
+function InterfaceToDisplay.resumeGraphDrawingCoroutine()
+
+ -- Setup
+ local scope = InterfaceCore.topScope()
+ local binding = InterfaceCore.binding
+
+ -- Asserts
+ assert(scope.coroutine, "coroutine not created for current gd scope")
+
+ -- Run
+ local ok, text = coroutine.resume(scope.coroutine)
+ assert(ok, text)
+ if coroutine.status(scope.coroutine) ~= "dead" then
+ -- Ok, ask binding to continue
+ binding:resumeGraphDrawingCoroutine(text)
+ end
+end
+
+
+
+--- Ends the current graph drawing scope.
+--
+function InterfaceToDisplay.endGraphDrawingScope()
+ assert(#InterfaceCore.scopes > 0, "no gd scope open")
+ InterfaceCore.scopes[#InterfaceCore.scopes] = nil -- pop
+end
+
+
+
+
+---
+-- Creates a new vertex in the syntactic graph of the current graph
+-- drawing scope. The display layer should call this function for each
+-- node of the graph. The |name| must be a unique string identifying
+-- the node. The newly created vertex will be added to the syntactic
+-- digraph. The binding function |everyVertexCreation| will then be
+-- called, allowing the binding to store information regarding the newly
+-- created vertex.
+--
+-- For each vertex an event will be created in the event
+-- sequence. This event will have the kind |"node"| and its
+-- |parameter| will be the vertex.
+--
+-- @param name Name of the vertex.
+--
+-- @param shape The shape of the vertex such as |"circle"| or
+-- |"rectangle"|. This shape may help a graph drawing algorithm
+-- figuring out how the node should be placed.
+--
+-- @param path A |Path| object representing the vertex's path.
+--
+-- @param height The to-be-used height of the options stack. All
+-- options above this height will be popped prior to attacking the
+-- options to the syntactic digraph.
+--
+-- @param binding_infos These options are passed to and are specific
+-- to the current |Binding|.
+--
+-- @param anchors A table of anchors (mapping anchor positions to
+-- |Coordinates|).
+
+
+function InterfaceToDisplay.createVertex(name, shape, path, height, binding_infos, anchors)
+
+ -- Setup
+ local scope = InterfaceCore.topScope()
+ local binding = InterfaceCore.binding
+
+ -- Does vertex already exist?
+ local v = scope.node_names[name]
+ assert (not v or not v.created_on_display_layer, "node already created")
+
+ -- Create vertex
+ if not v then
+ v = Vertex.new {
+ name = name,
+ shape = shape,
+ kind = "node",
+ path = path,
+ options = get_current_options_table(height),
+ anchors = anchors,
+ }
+
+ vertex_created(v,scope)
+ else
+ assert(v.kind == "subgraph node", "subgraph node expected")
+ v.shape = shape
+ v.path = path
+ v.anchors = anchors
+ end
+
+ v.created_on_display_layer = true
+
+ -- Call binding
+ binding.storage[v] = binding_infos
+ binding:everyVertexCreation(v)
+end
+
+
+-- This is a helper function
+function vertex_created(v,scope)
+
+ -- Create Event
+ local e = InterfaceToDisplay.createEvent ("node", v)
+ v.event = e
+
+ -- Create name lookup
+ scope.node_names[v.name] = v
+
+ -- Add vertex to graph
+ scope.syntactic_digraph:add {v}
+
+ -- Add to collections
+ for _,c in ipairs(v.options.collections) do
+ LookupTable.addOne(c.vertices, v)
+ end
+
+end
+
+
+
+---
+-- Creates a new vertex in the syntactic graph of the current graph
+-- drawing scope that is a subgraph vertex. Such a vertex
+-- ``surrounds'' the vertices of a subgraph. The special property of a
+-- subgraph node opposed to a normal node is that it is created only
+-- after the subgraph has been laid out. However, the difference to a
+-- collection like |hyper| is that the node is available immediately as
+-- a normal node in the sense that you can connect edges to it.
+--
+-- What happens internally is that subgraph nodes get ``registered''
+-- immediately both on the display level and on the algorithm level,
+-- but the actual node is only created inside the layout pipeline
+-- using a callback of the binding. The present function is used to
+-- perform this registering. The node creation happens when the
+-- innermost layout in which the subgraph node is declared has
+-- finished. For each subgraph node, a collection is created that
+-- contains all vertices (and edges) being part of the subgraph. For
+-- this reason, this method is a |push...| method, since it pushes
+-- something on the options stack.
+--
+-- The |init| parameter will be used during the creation of the node,
+-- see |Binding:createVertex| for details on the fields. Note that
+-- |init.text| is often not displayed for such ``vast'' nodes as those
+-- created for whole subgraphs, but a shape may use it nevertheless
+-- (for instance, one might display this text at the top of the node
+-- or, in case of a \textsc{uml} package, in a special box above the
+-- actual node).
+--
+-- The |init.generated_options| will be augmented by additional
+-- key--value pairs when the vertex is created:
+-- %
+-- \begin{itemize}
+-- \item The key |subgraph point cloud| will have as its value a
+-- string that is be a list of points (without separating commas)
+-- like |"(10pt,20pt)(0pt,0pt)(30pt,40pt)"|, always in
+-- this syntax. The list will contain all points inside the
+-- subgraph. In particular, a bounding box around these points will
+-- encompass all nodes and bend points of the subgraph.
+-- The bounding box of this point cloud is guaranteed to be centered on
+-- the origin.
+-- \item The key |subgraph bounding box width| will have as its value
+-- the width of a bounding box (in \TeX\ points, as a string with the
+-- suffix |"pt"|).
+-- \item The key |subgraph bounding box height| stores the height of a
+-- bounding box.
+-- \end{itemize}
+--
+-- @param name The name of the node.
+-- @param height Height of the options stack. Note that this method
+-- pushes something (namely a collection) on the options stack.
+-- @param info A table passed to |Binding:createVertex|, see that function.
+--
+function InterfaceToDisplay.pushSubgraphVertex(name, height, info)
+
+ -- Setup
+ local scope = InterfaceCore.topScope()
+ local binding = InterfaceCore.binding
+
+ -- Does vertex already exist?
+ assert (not scope.node_names[name], "node already created")
+
+ -- Create vertex
+ local v = Vertex.new {
+ name = name,
+ kind = "subgraph node",
+ options = get_current_options_table(height-1)
+ }
+
+ vertex_created(v,scope)
+
+ -- Store info
+ info.generated_options = info.generated_options or {}
+ info.name = name
+ v.subgraph_info = info
+
+ -- Create collection and link it to v
+ local _, _, entry = InterfaceToDisplay.pushOption(InterfaceCore.subgraph_node_kind, nil, height)
+ v.subgraph_collection = entry.value
+ v.subgraph_collection.subgraph_node = v
+
+ -- Find parent collection in options stack:
+ local collections = v.options.collections
+ for i=#collections,1,-1 do
+ if collections[i].kind == InterfaceCore.sublayout_kind then
+ v.subgraph_collection.parent_layout = collections[i]
+ break
+ end
+ end
+end
+
+
+
+---
+-- Add options for an already existing vertex.
+--
+-- This function allows you to add options to an already existing
+-- vertex. The options that will be added are all options on the
+-- current options stack; they will overwrite existing options of the
+-- same name. For collections, the vertex stays in all collections it
+-- used to, it is only added to all collections that are currently on
+-- the options stack.
+--
+-- @param name Name of the vertex.
+-- @param height The option stack height.
+
+function InterfaceToDisplay.addToVertexOptions(name, height)
+
+ -- Setup
+ local scope = InterfaceCore.topScope()
+
+ -- Does vertex already exist?
+ local v = assert (scope.node_names[name], "node is missing, cannot add options")
+
+ v.options = get_current_options_table(height, v.options)
+
+ -- Add to collections
+ for _,c in ipairs(v.options.collections) do
+ LookupTable.addOne(c.vertices, v)
+ end
+
+end
+
+
+
+
+
+---
+-- Creates a new edge in the syntactic graph of the current graph
+-- drawing scope. The display layer should call this function for each
+-- edge that is created. Both the |from| vertex and the |to| vertex
+-- must exist (have been created through |createVertex|) prior to your
+-- being able to call this function.
+--
+-- After the edge has been created, the binding layer's function
+-- |everyEdgeCreation| will be called, allowing the binding layer to
+-- store information about the edge.
+--
+-- For each edge an event is created, whose kind is |"edge"| and whose
+-- |parameter| is a two-element array whose first entry is the edge's
+-- arc in the syntactic digraph and whose second entry is the position
+-- of the edge in the arc's array of syntactic edges.
+--
+-- @param tail Name of the node the edge begins at.
+-- @param head Name of the node the edge ends at.
+-- @param direction Direction of the edge (e.g. |--| for an undirected edge
+-- or |->| for a directed edge from the first to the second
+-- node).
+-- @param height The option stack height, see for instance |createVertex|.
+--
+-- @param binding_infos These options will be stored in the |storage|
+-- of the vertex at the field index by the binding.
+
+function InterfaceToDisplay.createEdge(tail, head, direction, height, binding_infos)
+
+ -- Setup
+ local scope = InterfaceCore.topScope()
+ local binding = InterfaceCore.binding
+
+ -- Does vertex already exist?
+ local h = scope.node_names[head]
+ local t = scope.node_names[tail]
+ assert (h and t, "attempting to create edge between nodes that are not in the graph")
+
+ -- Create Arc object
+ local arc = scope.syntactic_digraph:connect(t, h)
+
+ -- Create Edge object
+ local edge = Edge.new {
+ head = h,
+ tail = t,
+ direction = direction,
+ options = get_current_options_table(height)
+ }
+
+ -- Add to arc
+ arc.syntactic_edges[#arc.syntactic_edges+1] = edge
+
+ -- Create Event
+ local e = InterfaceToDisplay.createEvent ("edge", { arc, #arc.syntactic_edges })
+ edge.event = e
+
+ -- Make part of collections
+ for _,c in ipairs(edge.options.collections) do
+ LookupTable.addOne(c.edges, edge)
+ end
+
+ -- Call binding
+ binding.storage[edge] = binding_infos
+ binding:everyEdgeCreation(edge)
+
+end
+
+
+
+
+
+---
+-- Push an option to the stack of options.
+--
+-- As a graph is parsed, a stack of ``current options''
+-- is created. To add something to this table, the display layers may
+-- call the method |pushOption|. To pop something from this stack,
+-- just set the |height| value during the next push to the position to
+-- which you actually wish to push something; everything above and
+-- including this position will be popped from the stack.
+--
+-- When an option is pushed, several additional options may also be
+-- pushed, namely whenever the option has a |use| field set. These
+-- additional options may, in turn, also push new options. Because of
+-- this, this function returns a new stack height, representing the
+-- resulting stack height.
+--
+-- In addition to this stack height, this function returns a Boolean
+-- value indicating whether a ``main algorithm phase was set''. This
+-- happens whenever a key is executed (directly or indirectly through
+-- the |use| field) that selects an algorithm for the ``main''
+-- algorithm phase. This information may help the caller to setup the
+-- graph drawing scopes correctly.
+--
+-- @param key A parameter (must be a string).
+-- @param value A value (can be anything). If it is a string, it will
+-- be converted to whatever the key expects.
+-- @param height A stack height at which to insert the key. Everything
+-- above this height will be removed.
+--
+-- @return A new stack height
+-- @return A Boolean that is |true| if the main algorithm phase was
+-- set by the option or one option |use|d by it.
+-- @return The newly created entry on the stack. If more entries are
+-- created through the use of the |use| field, the original entry is
+-- returned nevertheless.
+
+
+function InterfaceToDisplay.pushOption(key, value, height)
+ assert(type(key) == "string", "illegal key")
+
+ local key_record = assert(InterfaceCore.keys[key], "unknown key")
+ local main_phase_set = false
+
+ if value == nil and key_record.default then
+ value = key_record.default
+ end
+
+ -- Find out what kind of key we are pushing:
+
+ if key_record.algorithm then
+ -- Push a phase
+ if type(InterfaceCore.algorithm_classes[key]) == "function" then
+ -- Call the constructor function
+ InterfaceCore.algorithm_classes[key] = InterfaceCore.algorithm_classes[key]()
+ end
+
+ local algorithm = InterfaceCore.algorithm_classes[key]
+
+ assert (algorithm, "algorithm class not found")
+
+ push_on_option_stack(phase_unique,
+ { phase = value or key_record.phase, algorithm = algorithm },
+ height)
+
+ if key_record.phase == "main" then
+ main_phase_set = true
+ end
+
+ elseif key_record.layer then
+ -- Push a collection
+ local stack = InterfaceCore.option_stack
+ local scope = InterfaceCore.topScope()
+
+ -- Get the stack above "height":
+ local options = get_current_options_table(height-1)
+
+ -- Create the collection event
+ local event = InterfaceToDisplay.createEvent ("collection", key)
+
+ -- Create collection object:
+ local collection = Collection.new { kind = key, options = options, event = event }
+
+ -- Store in collections table of current scope:
+ local collections = scope.collections[key] or {}
+ collections[#collections + 1] = collection
+ scope.collections[key] = collections
+
+ -- Build collection tree
+ collection:registerAsChildOf(options.collections[#options.collections])
+
+ -- Push on stack
+ push_on_option_stack(collections_unique, collection, height)
+
+ else
+
+ -- A normal key
+ push_on_option_stack(key, InterfaceCore.convert(value, InterfaceCore.keys[key].type), height)
+
+ end
+
+ local newly_created = InterfaceCore.option_stack[#InterfaceCore.option_stack]
+
+ -- Now, push use keys:
+ local use = key_record.use
+ if key_record.use then
+ local flag
+ for _,u in ipairs(InterfaceCore.keys[key].use) do
+ local use_k = u.key
+ local use_v = u.value
+ if type(use_k) == "function" then
+ use_k = use_k(value)
+ end
+ if type(use_v) == "function" then
+ use_v = use_v(value)
+ end
+ height, flag = InterfaceToDisplay.pushOption(use_k, use_v, height+1)
+ main_phase_set = main_phase_set or flag
+ end
+ end
+
+ return height, main_phase_set, newly_created
+end
+
+
+---
+-- Push a layout on the stack of options. As long as this layout is on
+-- the stack, all vertices and edges will be part of this layout. For
+-- details on layouts, please see |Sublayouts|.
+--
+-- @param height A stack height at which to insert the key. Everything
+-- above this height will be removed.
+
+function InterfaceToDisplay.pushLayout(height)
+ InterfaceToDisplay.pushOption(InterfaceCore.sublayout_kind, nil, height)
+end
+
+
+
+---
+-- Creates an event and adds it to the event string of the current scope.
+--
+-- @param kind Name/kind of the event.
+-- @param parameters Parameters of the event.
+--
+-- @return The newly pushed event
+--
+function InterfaceToDisplay.createEvent(kind, param)
+ local scope = InterfaceCore.topScope()
+ local n = #scope.events + 1
+ local e = Event.new { kind = kind, parameters = param, index = n }
+ scope.events[n] = e
+
+ return e
+end
+
+
+
+---
+-- This method allows you to query the table of all declared keys. It
+-- contains them both as an array and also as a table index by the
+-- keys's names. In particular, you can then iterate over it using
+-- |ipairs| and you can check whether a key is defined by accessing
+-- the table at the key's name. Each entry of the table is the
+-- original table passed to |InterfaceToAlgorithms.declare|.
+--
+-- @return A lookup table of all declared keys.
+
+function InterfaceToDisplay.getDeclaredKeys()
+ return InterfaceCore.keys
+end
+
+
+
+
+---
+-- Renders the graph.
+--
+-- This function is called after the graph has been laid out by the
+-- graph drawing algorithms. It will trigger a sequence of calls to
+-- the binding layer that will, via callbacks, start rendering the
+-- whole graph.
+--
+-- In detail, this function calls:
+-- %
+--\begin{codeexample}[code only, tikz syntax=false]
+--local binding = InterfaceCore.binding
+--
+--binding:renderStart()
+--render_vertices()
+--render_edges()
+--render_collections()
+--binding:renderStop()
+--\end{codeexample}
+--
+-- Here, the |render_...| functions are local, internal functions that are,
+-- nevertheless, documented here.
+--
+-- @param name Returns the algorithm class that has been declared using
+-- |declare| under the given name.
+
+function InterfaceToDisplay.renderGraph()
+ local scope = InterfaceCore.topScope()
+ local syntactic_digraph = scope.syntactic_digraph
+
+ local binding = InterfaceCore.binding
+
+ binding:renderStart()
+ render_vertices(syntactic_digraph.vertices)
+ render_edges(syntactic_digraph.arcs)
+ render_collections(scope.collections)
+ binding:renderStop()
+end
+
+
+
+
+
+---
+-- Render the vertices after the graph drawing algorithm has
+-- finished. This function is local and internal and included only for
+-- documenting the call graph.
+--
+-- When the graph drawing algorithm is done, the interface will start
+-- rendering the vertices by calling appropriate callbacks of the
+-- binding layer.
+--
+-- Consider the following code:
+-- %
+--\begin{codeexample}[code only]
+--\graph [... layout] {
+-- a -- b -- c -- d;
+--};
+--\end{codeexample}
+--
+-- In this case, after the graph drawing algorithm has run, the
+-- present function will call:
+-- %
+--\begin{codeexample}[code only, tikz syntax=false]
+--local binding = InterfaceCore.binding
+--
+--binding:renderVerticesStart()
+--binding:renderVertex(vertex_a)
+--binding:renderVertex(vertex_b)
+--binding:renderVertex(vertex_c)
+--binding:renderVertex(vertex_d)
+--binding:renderVerticesStop()
+--\end{codeexample}
+--
+-- @param vertices An array of all vertices in the syntactic digraph.
+
+function render_vertices(vertices)
+ InterfaceCore.binding:renderVerticesStart()
+ for _,vertex in ipairs(vertices) do
+ InterfaceCore.binding:renderVertex(vertex)
+ end
+ InterfaceCore.binding:renderVerticesStop()
+end
+
+
+---
+-- Render the collections whose layer is not |0|. This local, internal
+-- function is called to render the different collection kinds.
+--
+-- Collection kinds rendered in the order provided by the |layer|
+-- field passed to |declare| during the declaration of the collection
+-- kind, see also |declare_collection|. If several collection kinds
+-- have the same layer, they are rendered in lexicographical ordering
+-- (to ensure that they are always rendered in the same order).
+--
+-- Consider the following code:
+-- %
+--\begin{codeexample}[code only, tikz syntax=false]
+--declare { key = "hyper", layer = 1 }
+--\end{codeexample}
+-- you can say on the \tikzname\ layer
+--\begin{codeexample}[code only]
+--\graph {
+-- a, b, c, d;
+-- { [hyper] a, b, c }
+-- { [hyper] b, c, d }
+--};
+--\end{codeexample}
+--
+-- In this case, after the graph drawing algorithm has run, the
+-- present function will call:
+--
+--\begin{codeexample}[code only, tikz syntax=false]
+--local binding = InterfaceCore.binding
+--
+--binding:renderCollectionStartKind("hyper", 1)
+--binding:renderCollection(collection_containing_abc)
+--binding:renderCollection(collection_containing_bcd)
+--binding:renderCollectionStopKind("hyper", 1)
+--\end{codeexample}
+--
+-- @param collections The |collections| table of the current scope.
+
+function render_collections(collections)
+ local kinds = InterfaceCore.collection_kinds
+ local binding = InterfaceCore.binding
+
+ for i=1,#kinds do
+ local kind = kinds[i].kind
+ local layer = kinds[i].layer
+
+ if layer ~= 0 then
+ binding:renderCollectionStartKind(kind, layer)
+ for _,c in ipairs(collections[kind] or {}) do
+ binding:renderCollection(c)
+ end
+ binding:renderCollectionStopKind(kind, layer)
+ end
+ end
+end
+
+
+---
+-- Render the syntactic edges of a graph after the graph drawing
+-- algorithm has finished. This function is local and internal and included only
+-- for documenting the call graph.
+--
+-- When the graph drawing algorithm is done, the interface will first
+-- rendering the vertices using |render_vertices|, followed by calling
+-- this function, which in turn calls appropriate callbacks to the
+-- binding layer.
+--
+-- Consider the following code:
+-- %
+--\begin{codeexample}[code only]
+-- \graph [... layout] {
+-- a -- b -- c -- d;
+-- };
+--\end{codeexample}
+--
+-- In this case, after the graph drawing algorithm has run, the
+-- present function will call:
+-- %
+--\begin{codeexample}[code only, tikz syntax=false]
+-- local binding = InterfaceCore.binding
+--
+-- binding:renderEdgesStart()
+-- binding:renderEdge(edge_from_a_to_b)
+-- binding:renderEdge(edge_from_b_to_c)
+-- binding:renderEdge(edge_from_c_to_d)
+-- binding:renderEdgesStop()
+--\end{codeexample}
+--
+-- @param arcs The array of arcs of the syntactic digraph.
+
+function render_edges(arcs)
+ InterfaceCore.binding:renderEdgesStart()
+ for _,a in ipairs(arcs) do
+ for _,e in ipairs (a.syntactic_edges) do
+ InterfaceCore.binding:renderEdge(e)
+ end
+ end
+ InterfaceCore.binding:renderEdgesStop()
+end
+
+
+local aliases = InterfaceCore.option_aliases
+local option_initial = InterfaceCore.option_initial
+
+local option_metatable = {
+ __index =
+ function (t, key)
+ local k = aliases[key]
+ if k then
+ local v = (type(k) == "string" and t[k]) or (type(k) == "function" and k(t)) or nil
+ if v ~= nil then
+ return v
+ end
+ end
+ return option_initial[key]
+ end
+}
+
+
+---
+-- Get the current options table.
+--
+-- An option table can be accessed like a normal table; however, there
+-- is a global fallback for this table. If an index is not defined,
+-- the value of this index in the global fallback table is used. (This
+-- reduces the overall amount of option keys that need to be stored
+-- with object.)
+--
+-- (This function is local and internal and included only for documentation
+-- purposes.)
+--
+-- @param height The stack height for which the option table is
+-- required.
+-- @param table If non |nil|, the options will be added to this
+-- table.
+--
+-- @return The option table as described above.
+
+function get_current_options_table (height, table)
+ local stack = InterfaceCore.option_stack
+ assert (height >= 0 and height <= #stack, "height value out of bounds")
+
+ if height == InterfaceCore.option_cache_height and not table then
+ return option_cache
+ else
+ -- Clear superfluous part of stack
+ for i=#stack,height+1,-1 do
+ stack[i] = nil
+ end
+
+ -- Build options table
+ local cache
+ if not table then
+ cache = setmetatable(
+ {
+ algorithm_phases = setmetatable({}, InterfaceCore.option_initial.algorithm_phases),
+ collections = {}
+ }, option_metatable)
+ else
+ cache = lib.copy(table)
+ cache.algorithm_phases = lib.copy(cache.algorithm_phases)
+ cache.collections = lib.copy(cache.collections)
+ end
+
+ local algorithm_phases = cache.algorithm_phases
+ local collections = cache.collections
+ local keys = InterfaceCore.keys
+
+ local function handle (k, v)
+ if k == phase_unique then
+ algorithm_phases[v.phase] = v.algorithm
+ local phase_stack = v.phase .. " stack"
+ local t = rawget(algorithm_phases, phase_stack)
+ if not t then
+ t = algorithm_phases[phase_stack]
+ assert(type(t) == "table", "unknown phase")
+ t = lib.copy(t)
+ algorithm_phases[phase_stack] = t
+ end
+ t[#t + 1] = v.algorithm
+ elseif k == collections_unique then
+ LookupTable.addOne(collections, v)
+ else
+ cache[k] = v
+ end
+ end
+
+ for _,s in ipairs(stack) do
+ handle (s.key, s.value)
+ end
+
+ -- Cache it, if this was not added:
+ if not table then
+ InterfaceCore.option_cache_height = height
+ option_cache = cache
+ end
+
+ return cache
+ end
+end
+
+
+
+-- A helper function
+
+function push_on_option_stack(key, value, height)
+ local stack = InterfaceCore.option_stack
+
+ assert (type(height) == "number" and height > 0 and height <= #stack + 1,
+ "height value out of bounds")
+
+ -- Clear superfluous part of stack
+ for i=#stack,height+1,-1 do
+ stack[i] = nil
+ end
+
+ stack[height] = { key = key, value = value }
+ InterfaceCore.option_cache_height = nil -- invalidate cache
+end
+
+
+
+-- Done
+
+return InterfaceToDisplay
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface/Scope.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface/Scope.lua
new file mode 100644
index 0000000000..a750308e69
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface/Scope.lua
@@ -0,0 +1,92 @@
+-- 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$
+
+
+
+---
+-- In theory, graph drawing algorithms take graphs as input and
+-- output graphs embedded into the plane as output. In practice, however,
+-- the input to a graph drawing algorithm is not ``just'' the
+-- graph. Rather, additional information about the graph, in particular
+-- about the way the user specified the graph, is also important to many
+-- graph drawing algorithms.
+--
+-- The graph drawing system gathers both the original input graph as well
+-- as all additional information that is provided in the graph drawing
+-- scope inside a scope table. The object has a number of fields that
+-- inform an algorithm about the input.
+--
+-- For each graph drawing scope, a new |Scope| object is
+-- created. Graph drawing scopes are kept track of using a stack, but
+-- only the top of this stack is available to the interface classes.
+--
+-- @field syntactic_digraph The syntactic digraph is a digraph that
+-- faithfully encodes the way the input graph is represented
+-- syntactically. However, this does not mean that the syntactic
+-- digraph contains the actual textual representation of the input
+-- graph. Rather, when an edge is specified as, say, |a <- b|, the
+-- syntactic digraph will contains an arc from |a| to |b| with an edge
+-- object attached to it that is labeled as a ``backward''
+-- edge. Similarly, an edge |a -- b| is also stored as a directed arc
+-- from |a| to |b| with the label |--| attached to it. Algorithms will
+-- often be more interested graphs derived from the syntactic digraph
+-- such as its underlying undirected graph. These derived graphs are
+-- made accessible by the graph drawing engine during the preprocessing.
+--
+-- @field events An array of |Event| objects. These objects, see the
+-- |Event| class for details, are created during the parsing of the
+-- input graph.
+--
+-- @field node_names A table that maps the names of nodes to node
+-- objects. Every node must have a unique name.
+--
+-- @field coroutine A Lua coroutine that is used internally to allow
+-- callbacks to the display layer to be issued deep down during a run
+-- of an algorithm.
+--
+-- @field collections The collections specified inside the scope, see
+-- the |Collection| class.
+
+local Scope = {}
+Scope.__index = Scope
+
+-- Namespace
+require("pgf.gd.interface").Scope = Scope
+
+-- Imports
+local lib = require "pgf.gd.lib"
+local Storage = require "pgf.gd.lib.Storage"
+
+local Digraph = require "pgf.gd.model.Digraph"
+
+---
+-- Create a new |Scope| object.
+--
+-- @param initial A table of initial values for the newly created
+-- |Scope| object.
+--
+-- @return The new scope object.
+
+function Scope.new(initial)
+ return setmetatable(lib.copy(initial,
+ {
+ syntactic_digraph = Digraph.new{},
+ events = {},
+ node_names = {},
+ coroutine = nil,
+ collections = {},
+ }), Scope)
+end
+
+
+-- Done
+
+return Scope