% Copyright 2019 by Renée Ahrens, Olof Frahm, Jens Kluttig, Matthias Schulz, Stephan Schuster
% Copyright 2019 by Till Tantau
% Copyright 2019 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 |graphdrawing| 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, Paths, and Transformations}

\includeluadocumentationof{pgf.gd.model.Coordinate}
\includeluadocumentationof{pgf.gd.model.Path}
\includeluadocumentationof{pgf.gd.lib.Transform}


\subsubsection{Options and Data Storages for Vertices, Arcs, and Digraphs}

Many objects in the graph drawing system have an |options| table attached to
them. These tables will contain the different kinds options specified by the
user for the object. For efficiency reasons, many objects may share the same
options table (since, more often than not, almost all objects have exactly the
same |options| table). For this reason, you cannot store anything in an options
table, indeed, you should never attempt to write anything into an options
table. Instead, you should use a |Storage|.

\includeluadocumentationof{pgf.gd.lib.Storage}


\subsubsection{Events}

\includeluadocumentationof{pgf.gd.lib.Event}


\subsection{Graph Transformations}
\label{section-gd-transformations}

\subsubsection{The Layout Pipeline}

\includeluadocumentationof{pgf.gd.control.LayoutPipeline}


\subsubsection{Hints For Edge Routing}

\includeluadocumentationof{pgf.gd.routing.Hints}


\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}