diff options
author | Karl Berry <karl@freefriends.org> | 2014-02-27 00:01:50 +0000 |
---|---|---|
committer | Karl Berry <karl@freefriends.org> | 2014-02-27 00:01:50 +0000 |
commit | 90ae413a94da014dbf7a6a8ab584f7c668483a5a (patch) | |
tree | 4e0528a2b2fb2004988e7fc804ea2f1354f1f5d5 /Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-gd-algorithm-layer.tex | |
parent | 800cc56380d1edfe567a6a66bef13e8950eb2b0c (diff) |
pgf 3.0.0
git-svn-id: svn://tug.org/texlive/trunk@33057 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-gd-algorithm-layer.tex')
-rw-r--r-- | Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-gd-algorithm-layer.tex | 851 |
1 files changed, 851 insertions, 0 deletions
diff --git a/Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-gd-algorithm-layer.tex b/Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-gd-algorithm-layer.tex new file mode 100644 index 00000000000..b02a61319cb --- /dev/null +++ b/Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-gd-algorithm-layer.tex @@ -0,0 +1,851 @@ +% Copyright 2010 by Renée Ahrens, Olof Frahm, Jens Kluttig, Matthias Schulz, Stephan Schuster +% Copyright 2011 by Till Tantau +% Copyright 2011 by Jannis Pohlmann +% +% This file may be distributed and/or modified +% +% 1. under the LaTeX Project Public License and/or +% 2. under the GNU Free Documentation License. +% +% See the file doc/generic/pgf/licenses/LICENSE for more details. + + +\section{The Algorithm Layer} + +\label{section-gd-algorithm-layer} + +\noindent{\emph{by Till Tantau}} + +\ifluatex\else This section of the manual can only be typeset using Lua\TeX.\expandafter\endinput\fi + +\subsection{Overview} + +The present section is addressed at readers interested in implementing +new graph drawing algorithms for the graph drawing system. Obviously, +in order to do so, you need to have an algorithm in mind and also some +programming skills; but fortunately only in the Lua programming +language: Even though the graph drawing system was originally +developed as an extension of \tikzname, is has been restructured so +that the ``algorithm layer'' where you define algorithms is +scrupulously separated from \tikzname. In particular, an algorithm +declared and implemented on this layer can be used in with every ``display +layers,'' see Section~\ref{section-gd-display-layer}, without change. Nevertheless, in +the following we will use the \tikzname\ display layer and syntax in +our examples. + +Normally, new graph drawing algorithms can and must be implemented in +the Lua programming language, which is a small, easy-to-learn (and +quite beautiful) language integrated into current versions of +\TeX. However, as explained in Section~\ref{section-algorithms-in-c}, +you can also implement algorithms in C or C++ (and, possibly, in the +future also in other languages), but this comes at a great cost +concerning portability. In the present section, I assume that you are +only interested in writing an algorithm using Lua. + +In the following, after a small ``hello world'' example of graph +drawing and a discussion of technical details like +how to name files so that \TeX\ will find them, we have a look at the +main parts of the algorithm layer: + +\begin{itemize} +\item Section~\ref{section-gd-namespaces} gives and overview of the + available namespaces and also of naming conventions used in the + graph drawing system. +\item Section~\ref{section-gd-gd-scope} explores what graph + drawing scopes ``look like on the algorithm layer.'' As the graph + of a graph drawing scope is being parsed on the display layer, a lot + of information is gathered: The nodes and edges of the graph are + identified and the + object-oriented model is built, but other information is also + collected. For instance, a sequence of \emph{events} is created + during the parsing process. As another example, numerous kinds of + \emph{collections} may be identified by the parser. The parsed graph + together with the event sequence and the collections are all + gathered in a single table, called the \emph{scope table} of the + current graph drawing scope. Algorithms can access this table to + retrieve information that goes beyond the ``pure'' graph model. + + One entry in this table is of particular importance: The + \emph{syntactic digraph.} While most graph drawing + algorithms are not really interested in the ``details'' of how a + graph was specified, for some algorithms it makes a big difference + whether you write |a -> b| or |b <- a| in your specification of the + graph. These algorithms can access the ``fine details'' of how the + input graph was specified through the syntactic digraph; all other + algorithms can access their |digraph| or |ugraph| fields and do not + have to worry about the difference between |a -> b| and |b <- a|. +\item Section~\ref{section-gd-models} explains the object-oriented + model of graphs used throughout the graph drawing system. Graph + drawing algorithms do not get the ``raw'' specification used by the + user to specify a graph (like |{a -> {b,c}}| in the |graph| + syntax). Instead, what a graph drawing algorithm sees is ``just'' a + graph object that provides methods for accessing the vertices and + arcs. +\item Section~\ref{section-gd-transformations} explains how the + information in the graph drawing scope is processed. One might + expect that we simply run the algorithm selected by the user; + however, things are more involved in practice. When the layout of a + graph needs to be computed, only very few algorithms will actually + be able to compute positions for the nodes of \emph{every} + graph. For instance, most algorithms implicitly assume that the + input graph is connected; algorithms for computing layouts for trees + assume that the input is, well, a tree; and so on. For this reason, + graph drawing algorithms will not actually need the original input + graph as their input, but some \emph{transformed} version of + it. Indeed, \emph{all} graph drawing algorithms are treated as graph + transformations by the graph drawing engine. + + This section explains how transformations are chosen and which + transformations are applied by default. +\item Section~\ref{section-gd-interface-to-algorithms} documents the + interface-to-algorithm class. This interface encapsulates all that + an algorithm ``sees'' of the graph drawing system (apart from the + classes in |model| and |lib|). +\item Section~\ref{section-gd-examples} provides a number of complete + examples that show how graph drawing algorithms can, actually, be + implemented. +\item Section~\ref{section-gd-libs} documents the different + libraries functions that come with the graph drawing engine. For + instance, there are library functions for computing the (path) + distance of nodes in a graph; a parameter that is needed by some + algorithms. +\end{itemize} + + + +\subsection{Getting Started} + +In this section, a ``hello world'' example of a graph +drawing algorithm is given, followed by an overview of the +organization of the whole engine. + + +\subsubsection{The Hello World of Graph Drawing} + +Let us start our tour of the algorithm layer with a ``hello world'' +version of graph drawing: An algorithm that simply places all nodes of +a graph in a circle of a fixed radius. Naturally, this is not a +particularly impressive or intelligent graph drawing algorithm; but +neither is the classical ``hello world''$\dots$\ Here is a minimal +version of the needed code (this is not the typical way of formulating +the code, but it is the shortest; we will have a look at the more +standard and verbose way in a moment): + +\begin{codeexample}[code only, tikz syntax=false] +pgf.gd.interface.InterfaceToAlgorithms.declare { + key = "very simple demo layout", + algorithm = { + run = + function (self) + local alpha = (2 * math.pi) / #self.ugraph.vertices + for i,vertex in ipairs(self.ugraph.vertices) do + vertex.pos.x = math.cos(i * alpha) * 25 + vertex.pos.y = math.sin(i * alpha) * 25 + end + end + } +} +\end{codeexample} +\directlua{ +pgf.gd.interface.InterfaceToAlgorithms.declare { + key = "very simple demo layout", + algorithm = { + run = + function (self) + local alpha = (2 * math.pi) / \luaescapestring{#}self.ugraph.vertices + for i,vertex in ipairs(self.ugraph.vertices) do + vertex.pos.x = math.cos(i * alpha) * 25 + vertex.pos.y = math.sin(i * alpha) * 25 + end + end + } +} +} + +This code \emph {declares} a new algorithm (|very simple demo layout|) +and includes an implementation of the algorithm (through the |run| +field of the |algorithm| field). When the |run| method is called, the +|self| parameter will contain the to-be-drawn graph in its |ugraph| +field. It is now the job of the code to modify the positions of the +vertices in this graph (in the example, this is done by assigning +values to |vertex.pos.x| and |vertex.pos.y|). + +In order to actually \emph{use} the algorithm, the above code first +needs to be executed somehow. For \tikzname, one can just call +|\directlua| on it or put it in a file and then use |\directlua| plus +|require| (a better alternative) or you put it in a file like +|simpledemo.lua| and use |\usegdlibrary{simpledemo}| (undoubtedly the +``best'' way). For another display layer, like a graphical editor, the +code could also be executed through the use of |require|. + +Executing the code ``just'' declares the algorithm, this is what the +|declare| function does. Inside some internal tables, the algorithm +layer will store the fact that a |very simple demo layout| is now +available. The algorithm layer will also communicate with the display +layer through the binding layer to advertise this fact to the +``user.'' In the case of \tikzname, this means that the option key +|very simple demo layout| becomes available at this point and we can +use it like this: + +\begin{codeexample}[] +\tikz [very simple demo layout] + \graph { f -> c -> e -> a -> {b -> {c, d, f}, e -> b}}; +\end{codeexample} + +It turns out, that our little algorithm is already more powerful than +one might expect. Consider the following example: +\begin{codeexample}[] +\tikz [very simple demo layout, componentwise] + \graph { + 1 -> 2 ->[orient=right] 3 -> 1; + a -- b --[orient=45] c -- d -- a; + }; +\end{codeexample} + +Note that, in our algorithm, we ``just'' put all nodes on a circle +around the origin. Nevertheless, the graph gets decomposed into two +connected components, the components are rotated so that the edge from +node |2| to node |3| goes from left to right and the edge from |b| to +|c| goes up at an angle of $45^\circ$, and the components are placed +next to each other so that some spacing is achieved. + +The ``magic'' that achieves all this behind the scenes is called +``graph transformations.'' They will heavily pre- and postprocess the +input and output of graph drawing algorithms to achieve the above +results. + +Naturally, some algorithms may not wish their inputs and/or +outputs to be ``tampered'' with. An algorithm can easily configure +which transformations should be applied, by passing appropriate options +to |declare|. + + +\subsubsection{Declaring an Algorithm} + +Let us now have a look at how one would ``really'' implement the +example algorithm. First of all, we place our algorithm in a +separate file called, say, |ExampleLayout.lua|. This way, by putting +it in a separate file, all display layers can easily install the +algorithm at runtime by saying |require "ExampleLayout"|. + +Next, the |declare| function is needed quite often, so it makes sense +to create a short local name for it: + +\begin{codeexample}[code only, tikz syntax=false] +-- This is the file ExampleLayout.lua +local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare +\end{codeexample} + +The |declare| function is the work-horse of the algorithm layer. It +takes a table that contains at least a |key| field, which must be a +unique string, and some other fields that specify in more detail what +kind of key is declared. Once declared through a call of |declare|, +the ``key'' can be used on the display layer. + +For declaring an algorithm, the table passed to |declare| must contain +a field |algorithm|. This field, in turn, must (normally) be set to a +table that will become the algorithm class. In the above example, our +algorithm was so simple that we could place the whole definition of +the class inside the call of |declare|, but normally the class is +defined in more detail after the call to |declare|: + +\begin{codeexample}[code only, tikz syntax=false] +local ExampleClass = {} -- A local variable holding the class table + +declare { + key = "very simple demo layout", + algorithm = ExampleClass +} + +function ExampleClass:run () + local alpha = (2 * math.pi) / #self.ugraph.vertices + ... +end +\end{codeexample} + +The effect of the |declare| will be that the table stored in +|ExampleClass| is setup to form a class in the sense of +object-oriented programming. In particular, a static |new| function +is installed. + +Now, whenever the user uses the key |very simple demo layout| on a +graph, at some point the graph drawing engine will create a new +instance of the |ExampleClass| using |new| and will then call the +|run| method of this class. The class can have any number of other +methods, but |new| and |run| are the only ones directly called by the +graph drawing system. + + +\subsubsection{The Run Method} + +The |run| method of an algorithm classes lies at the heart of any +graph drawing algorithm. This method will be called whenever a graph +needs to be laid out. Upon this call, the |self| object will have +some important fields set: +\begin{itemize} +\item |ugraph| This stands for ``undirected graph'' and is the + ``undirected'' version of the to-be-laid out graph. In this graph, + whenever there is an arc between $u$ and $v$, there is also an arc + between $v$ and $u$. It is obtained by considering the syntactic + digraph and then ``forgetting'' about the actual direction of the + edges. + + When you have set certain |preconditions| in your algorithm class, + like |connected=true|, the |ugraph| will satisfy these + conditions. In particular, the |ugraph| typically will not be the + underlying undirected graph of the complete syntactic digraph, but + rather of some part of it. The use of (sub)layouts will also modify + the syntactic digraph is fancy ways. + + Refer to this graph whenever your algorithm is ``most comfortable'' + with an undirected graph, as is the case for instance for most + force-base algorithms. +\item |digraph| This stands for ``directed graph'' and is the + ``semantically directed'' version of the to-be-laid out + graph. Basically, when happens is that reverse edges in the + syntactic digraph (an edge like |b <- a|) will yield an |Arc| from + |a| to |b| in the |digraph| while they yield a |b| to |a| arc and + edge in the syntactic digraph. Also, undirected edges like |a -- b| + are replaced by directed edges in both directions between the + vertices. +\item |scope| The graph drawing scope. +\item |layout| The layout object for this graph. This is a collection + of kind |layout|. +\end{itemize} + + +\subsubsection{Loading Algorithms on Demand} + +In order to use the |very simple demo layout| on the display layer, +|declare| must have been called for this key. However, we just saw +that the |declare| function takes the actual class table as parameter +and, thus, whenever an algorithm is declared, it is also completely +loaded and compiled at this point. + +This is not always desirable. A user may wish to include a number of +libraries in order to declare a large number of potentially useful +algorithms, but will not actually use all of them. Indeed, at least +for large, complex algorithms, it is preferable that the algorithm's +code is loaded only when the algorithm is used for the first time. + +Such a ``loading of algorithms on demand'' is supported through the +option of setting the |algorithm| field in a |declare| to a +string. This string must now be the file name of a Lua file that +contains the code of the actual algorithm. When the key is actually +used for the first time, this file will be loaded. It must return a +table that will be plugged into the |algorithm| field; so subsequent +usages of the key will not load the file again. + +The net effect of all this is that you can place implementations of +algorithms in files separate from interface files that just contain +the |declare| commands for these algorithms. You will typically do +this only for rather large algorithms. + +For our example, the code would look like this: + +\begin{codeexample}[code only, tikz syntax=false] +-- File ExampleLayout.lua +local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare +declare { + key = "very simple demo layout", + algorithm = "ExampleLayoutImplementation" +} +\end{codeexample} + +\begin{codeexample}[code only, tikz syntax=false] +-- File ExampleLayoutImplementation.lua +local ExampleClass = {} +function ExampleClass:run () + local alpha = (2 * math.pi) / #self.ugraph.vertices + ... +end +return ExampleClass +\end{codeexample} + + +\subsubsection{Declaring Options} + +Let us now make our example algorithm a bit more ``configurable''. For +this, we use |declare| once more, but instead of the |algorithm| +field, we use a |type| field. This tells the display layer that the +key is not used to select an algorithm, but to configure ``something'' +about the graph or about nodes or edges. + +In our example, we may wish to configure the radius of the graph. So, +we introduce a |radius| key (actually, this key already exists, so we +would not need to declare it, but let us do so anyway for example +purposes): + +\begin{codeexample}[code only, tikz syntax=false] +declare { + key = "radius", + type = "length", + initial = "25pt" +} +\end{codeexample} + +This tells the display layer that there is now an option called +|radius|, that users set it to some ``length'', and that if it is not +set at all, then the 25pt should be used. + +To access what the user has specified for this key, an algorithm can +access the |options| field of a graph, vertex, or arc at the +key's name: + +\begin{codeexample}[code only, tikz syntax=false] + vertex.pos.x = math.cos(i * alpha) * vertex.options.radius + vertex.pos.y = math.sin(i * alpha) * vertex.options.radius +\end{codeexample} + + + +\subsubsection{Adding Inline Documentation} + +You should always document the keys you |declare|. For this, the +|declare| function allows you to add three fields to its argument +table: +\begin{itemize} +\item |summary| This should be a string that succinctly summarizes the + effect this key has. The idea is that this text will be shown as a + ``tooltip'' in a graphical editor or will be printed out by a + command line tool when a user requests help about the key. + You can profit from using Lua's |[[| and |]]| syntax for specifying + multi-line strings. + + Also, when the file containing the key is parsed for + this manual, this text will be shown. +\item |documentation| When present, this field contains a more + extensive documentation of the key. It will also be shown in this + manual, but typically not as a tool tip. +\item |examples| This should either be a single string or an array of + strings. Each string should be an example demonstrating how the key + is used in \tikzname. They will all be included in the manual, each + surrounded by a |codeexample| environment. +\end{itemize} + +Let us augment our |radius| key with some documentation. The three +dashes before the |declare| are only needed when the declaration is +part of this manual and they will trigger an inclusion of the key in +the manual. + +\begin{codeexample}[code only, tikz syntax=false] +--- +declare { + key = "radius", + type = "length", + initial = "25pt", + summary = [[ + Specifies the radius of a circle on which the nodes are placed when + the |very simple example layout| is used. Each vertex can have a + different radius. + ]], + examples = [[ + \tikz \graph [very simple example layout, radius=2cm] { + a -- b -- c -- d -- e; + }; + ]] +} +\end{codeexample} + +As a courtesy, all of the strings given in the documentation can start +and end with quotation marks, which will be removed. (This helps +syntax highlighting with editors that do not recognize the |[[| to |]]| +syntax.) Also, the indentation of the strings is removed (we compute +the minimum number of leading spaces on any line and remove this many +spaces from all lines). + + + +\subsubsection{Adding External Documentation} +\label{section-gd-documentation-in} + +As an alternative to inlining documentation, you can also store the +documentation of keys in a separate file that is loaded only when the +documentation is actually accessed. Since this happens only rarely +(for instance, not at all, when \tikzname\ is run, except for this +manual), this will save time and space. Also, for C code, it is +impractical to store multi-line documentation strings directly in the C +file. + +In order to store documentation externally, instead of the |summary|, +|documentation|, and |examples| keys, you provide the key +|documentation_in|. The |documentation_in| key must be set +to a string that is input using |require|. + +In detail, when someone tries to access the |summary|, |documentation|, or +|examples| field of a key and these keys are not (yet) defined, the +system checks whether the |documentation_in| key is set. If so, we +apply |require| to the string stored in this field. The file loaded in +this way can now setup the missing fields of the current key and, +typically, also of all other keys defined in the same file as the +current key. For this purpose, it is advisable to use the |pgf.gd.doc| +class: + +\includeluadocumentationof{pgf.gd.doc} + +As a longer example, consider the following declarations: + +\begin{codeexample}[code only, tikz syntax=false] +--- +declare { + key = "very simple demo layout", + algorithm = ExampleClass, + documentation_in = "documentation_file" +} + +--- +declare { + key = "radius", + type = "length", + initial = "25", + documentation_in = "documentation_file" +} +\end{codeexample} + +The file |documentation_file.lua| would look like this: + +\begin{codeexample}[code only, tikz syntax=false] +-- File documentation_file.lua +local key = require 'pgf.gd.doc'.key +local documentation = require 'pgf.gd.doc'.documentation +local summary = require 'pgf.gd.doc'.summary +local example = require 'pgf.gd.doc'.example + +key "very simple demo layout" +documentation "This layout is a very simple layout that, ..." + +key "radius" +summary "Specifies the radius of a circle on which the nodes are placed." +documentation +[[ +This key can be used together with |very simple example layout|. An +important feature ist that... +]] +example +[[ +\tikz \graph [very simple example layout, radius=2cm] +{ a -- b -- c -- d -- e; }; +]] +\end{codeexample} + + + + +\subsection{Namespaces and File Names} + +\label{section-gd-namespaces} + +\subsubsection{Namespaces} + +All parts of the graph drawing library reside in the Lua ``namespace'' +|pgf.gd|, which is itself a ``sub-namespace'' of |pgf|. For your own +algorithms, you are free to place them in whatever namespace you like; +only for the official distribution of \pgfname\ everything has been +put into the correct namespace. + +Let us now have a more detailed look at these namespaces. A namespace +is just a Lua table, and sub-namespaces are just subtables of +namespace tables. Following the Java convention, namespaces are in +lowercase letters. The following namespaces are part of the core of +the graph drawing engine: +\begin{itemize} +\item |pgf| This namespace is the main namespace of \pgfname. Other + parts of \pgfname\ and \tikzname\ that also employ Lua should put an + entry into this table. Since, currently, only the graph drawing + engine adheres to this rule, this namespace is declared inside the + graph drawing directory, but this will change. + + The |pgf| table is the \emph{only} entry into the global table of + Lua generated by the graph drawing engine (or, \pgfname, for that + matter). If you intend to extend the graph drawing engine, do not + even \emph{think} of polluting the global namespace. You will be + fined. +\item |pgf.gd| This namespace is the main namespace of the graph drawing + engine, including the object-oriented models of graphs and the + layout pipeline. Algorithms that are part of the + distribution are also inside this namespace, but if you write your + own algorithms you do not need place them inside this + namespace. (Indeed, you probably should not before they are made + part of the official distribution.) +\item |pgf.gd.interface| This namespace handles, on the one hand, the + communication between the algorithm layer and the binding layer and, + on the other hand, the communication between the display layer + (\tikzname) and the binding layer. +\item |pgf.gd.binding| So-called ``bindings'' between display layers + and the graph drawing system reside in this namespace. +\item |pgf.gd.lib| Numerous useful classes that ``make an algorithm's + your life easier'' are collected in this namespace. Examples are a + class for decomposing a graph into connected components or a class + for computing the ideal distance between two sibling nodes in a + tree, taking all sorts of rotations and separation parameters into + account. +\item |pgf.gd.model| This namespace contains all Lua classes that are + part of the object-oriented model of graphs employed + throughout the graph drawing engine. For readers familiar with the + model--view--controller pattern: This is the namespace containing + the model-part of this pattern. +\item |pgf.gd.control| This namespace contains the ``control logic'' + of the graph drawing system. It will transform graphs according to + rules, disassemble layouts and sublayouts and will call the + appropriate algorithms. For readers still familiar with the + model--view--controller pattern: This is the namespace containing + the control-part of this pattern. +\item |pgf.gd.trees| This namespace contains classes that are useful + for dealing with graphs that are trees. In particular, it contains a + class for computing a spanning tree of an arbitrary connected graph; + an operation that is an important preprocessing step for many + algorithms. + + In addition to providing ``utility functions for trees,'' the + namespace \emph{also} includes actual algorithms for computing graph + layouts like |pgf.gd.trees.ReingoldTilford1981|. It may seem to be a + bit of an ``impurity'' that a namespace mixes utility classes and + ``real'' algorithms, but experience has shown that it is better to + keep things together in this way. + + Concluding the analogy to the model--view--controller pattern, a + graph drawing algorithm is, in a loose sense, the ``view'' part of + the pattern. +\item |pgf.gd.layered| This namespace provides classes and functions + for ``layered'' layouts; the Sugiyama layout method being the most + well-known one. Again, the namespace contains both algorithms to be + used by a user and utility functions. +\item |pgf.gd.force| Collects force-based algorithms and, again, also + utility functions and classes. +\item |pgf.gd.examples| Contains some example algorithms. They are + \emph{not} intended to be used directly, rather they should serve as + inspirations for readers wishing to implement their own algorithms. +\end{itemize} + +There are further namespaces that also reside in the |pgf.gd| +namespace, these namespaces are used to organize different graph +drawing algorithms into categories. + +In Lua, similarly to Java, when a class |SomeClass| is part of, say, +the namespace |pgf.gd.example|, it is customary to put the class's +code in a file |SomeClass.lua| and then put this class in a directory +|example|, that is a subdirectory of a directory |gd|, which is in +turn a subdirectory of a directory |pgf|. When you write +\texttt{require "pgf.gd.example.SomeClass"} the so-called +\emph{loader} will turn this into a request for the file +\texttt{pgf/gd/example/SomeClass.lua} (for Unix systems). + + + +\subsubsection{Defining and Using Namespaces and Classes} + +There are a number of rules concerning the structure and naming of +namespaces as well as the naming of files. Let us start with the +rules for naming namespaces, classes, and functions. They follow the +``Java convention'': + +\begin{enumerate} +\item A namespace is a short lowercase |word|. +\item A function in a namespace is in |lowercase_with_underscores_between_words|. +\item A class name is in |CamelCaseWithAnUppercaseFirstLetter|. +\item A class method name is in |camelCaseWithALowercaseFirstLetter|. +\end{enumerate} + +From Lua's point of view, every namespace and every class is just a +table. However, since these tables will be loaded using Lua's +|require| function, each namespace and each class must be placed +inside a separate file (unless you modify the |package.loaded| table, +but, then, you know what you are doing anyway). Inside such a file, you +should first declare a local variable whose name is the name of the +namespace or class that you intend to define and then assign a +(possibly empty) table to this variable: +\begin{codeexample}[code only, tikz syntax=false] +-- File pgf.gd.example.SomeClass.lua: +local SomeClass = {} +\end{codeexample} +Next, you should add your class to the encompassing namespace. This is +achieved as follows: +\begin{codeexample}[code only, tikz syntax=false] +require("pgf.gd.example").SomeClass = SomeClass +\end{codeexample} +The reason this works is that the |require| will return the table that +is the namespace |pgf.gd.example|. So, inside this namespace, the +|SomeClass| field will be filled with the table stored in the local +variable of the same name -- which happens to be the table +representing the class. + +At the end of the file, you must write +\begin{codeexample}[code only, tikz syntax=false] +return SomeClass +\end{codeexample} +This ensures that the table that is defined in this file gets stored +by Lua in the right places. Note that you need and should not use +Lua's |module| command. The reason is that this command has +disappeared in the new version of Lua and that it is not really +needed. + +Users of your class can import and use your class by writing: +\begin{codeexample}[code only, tikz syntax=false] +... +local SomeClass = require "pgf.gd.examples.SomeClass" +... +\end{codeexample} + + + + +\subsection{The Graph Drawing Scope} + +\label{section-gd-gd-scope} + +\includeluadocumentationof{pgf.gd.interface.Scope} + + + +\subsection{The Model Classes} + +\label{section-gd-models} + +All that a graph drawing algorithm will ``see'' of the graph specified +by the user is a ``graph object.'' Such an object is an +object-oriented model of the user's graph that no longer encodes the +specific way in which the user specified the graph; it only encodes +which nodes and edges are present. For instance, the \tikzname\ graph +specification +\begin{codeexample}[code only] +graph { a -- {b, c} } +\end{codeexample} +\noindent and the graph specification +\begin{codeexample}[code only] +node (a) { a } +child { node (b) {b} } +child { node (c) {c} } +\end{codeexample} +will generate exactly the same graph object. + +\begin{luanamespace}{pgf.gd.}{model} + This namespace contains the classes modeling graphs, + nodes, and edges. Also, the |Coordinate| class is found here, since + coordinates are also part of the modeling. +\end{luanamespace} + + +\subsubsection{Directed Graphs (Digraphs)} + +Inside the graph drawing engine, the only model of a graph that is +available treats graphs as +\begin{enumerate} +\item directed (all edges have a designated head and a designated + tail) and +\item simple (there can be at most one edge between any pair of + nodes). +\end{enumerate} +These two properties may appear to be somewhat at odds with what users +can specify as graphs and with what some graph drawing algorithms +might expect as input. For instance, suppose a user writes +\begin{codeexample}[code only] +graph { a -- b --[red] c, b --[green, bend right] c } +\end{codeexample} +In this case, it seems that the input graph for a graph drawing +algorithm should actually be an \emph{undirected} graph in which there +are \emph{multiple} edges (namely $2$) between |b| and~|c|. +Nevertheless, the graph drawing engine will turn the user's input a +directed simple graph in ways described later. You do not need to +worry that information gets lost during this process: The +\emph{syntactic digraph,} which is available to graph drawing +algorithms on request, stores all the information about which edges +are present in the original input graph. + +The main reasons for only considering directed, simple graphs are speed +and simplicity: The implementation of these graphs has been optimized so +that all operations on these graphs have a guaranteed running time +that is small in practice. + +\includeluadocumentationof{pgf.gd.model.Digraph} + +\subsubsection{Vertices} + +\includeluadocumentationof{pgf.gd.model.Vertex} + +\subsubsection{Arcs} +\label{section-gd-arc-model} + +\includeluadocumentationof{pgf.gd.model.Arc} + +\subsubsection{Edges} + +\includeluadocumentationof{pgf.gd.model.Edge} + +\subsubsection{Collections} + +\includeluadocumentationof{pgf.gd.model.Collection} + +\subsubsection{Coordinates and Transformations} + +\includeluadocumentationof{pgf.gd.model.Coordinate} +\includeluadocumentationof{pgf.gd.lib.Transform} + +\subsubsection{Options and Data Storages for Vertices, Arcs, and Digraphs} + +\includeluadocumentationof{pgf.gd.lib.Storage} + +\subsubsection{Events} + + +\includeluadocumentationof{pgf.gd.lib.Event} + + + +\subsection{Graph Transformations} + +\label{section-gd-transformations} + +\includeluadocumentationof{pgf.gd.control.LayoutPipeline} + + + +\subsection{The Interface To Algorithms} + +\label{section-gd-interface-to-algorithms} + +\includeluadocumentationof{pgf.gd.interface.InterfaceToAlgorithms} + + + + + +\subsection{Examples of Implementations of Graph Drawing Algorithms} +\label{section-gd-examples} + +\includeluadocumentationof{pgf.gd.examples.library} +\includeluadocumentationof{pgf.gd.examples.SimpleDemo} +\includeluadocumentationof{pgf.gd.examples.SimpleEdgeDemo} +\includeluadocumentationof{pgf.gd.examples.SimpleHuffman} + + + + +\subsection{Support Libraries} + +\label{section-gd-libs} + +The present section lists a number of general-purpose libraries that +are used by different algorithms. + +\subsubsection{Basic Functions} + +\includeluadocumentationof{pgf} + +\includeluadocumentationof{pgf.gd.lib} + +\subsubsection{Lookup Tables} + +\includeluadocumentationof{pgf.gd.lib.LookupTable} + +\subsubsection{Computing Distances in Graphs} + +\emph{Still needs to be ported to digraph classes!} + +%\includeluadocumentationof{pgf.gd.lib.PathLengths} + +\subsubsection{Priority Queues} + +\includeluadocumentationof{pgf.gd.lib.PriorityQueue} + + + |