diff options
author | Norbert Preining <norbert@preining.info> | 2023-01-16 03:03:27 +0000 |
---|---|---|
committer | Norbert Preining <norbert@preining.info> | 2023-01-16 03:03:27 +0000 |
commit | 6f9e1680085e7bb4d258f6f8116369d122e196e1 (patch) | |
tree | 9ac0ecb239240d1d672b188f29c1479de215074b /graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface | |
parent | b8345f39630408bb198e7636381ce4240154ca9b (diff) |
CTAN sync 202301160303
Diffstat (limited to 'graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/interface')
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 |