PGF/TikZ Manual

The TikZ and PGF Packages
Manual for version 3.1.10

Graph Drawing

38 The Display Layer

by Till Tantau

You do not need to read this section in order to write new graph drawing algorithms. It is of interest only to those wishing to write programs that wish to “use” the graph drawing system in a similar way that TikZ does for laying out graphs that are generated and then passed down from the program to the graph drawing system.

38.1 Introduction: The Interplay of the Different Layers

The job of the graph drawing system is to run graph drawing algorithms on graphs. Since graph drawing is useful in many different contexts, not only in the context of TikZ for which the present system was originally developed, the graph drawing system was designed in such a way that it can be used independently of TikZ. To achieve this, the display layer provides an interface via which an arbitrary program (TikZ, a graph editor, a command line interface, etc.) “talk” to the graph drawing system.

To better understand how this works, let us consider the following setup:

  • • A program would like to communicate with the graph drawing system. It is written in Java and its job is to analyse social networks. This software would like to use graph drawing to produce drawings of some “social graphs” arising from its analyses. This software will be called “the display system” in the following.

  • • There are two algorithms that the display system would like to apply to the graphs its produces. Let us call these algorithms “A” and “B”. However, the display system would also, ideally, wish to make it possible that its user chooses other algorithms “C” that are not necessarily part of its binary.

  • • The display system has internally generated a “social graph” that it would now like to draw.

For this setup, the communication between the different layers of the graph drawing system is as follows:

  • 1. The display system, being written in Java, must embed Lua to use the graph drawing system.

  • 2. The display system must initialize the graph drawing system. For this, it must use require on the file InterfaceToDisplay, which, as the name suggests, contains the interface between the display system and the graph drawing system.

    It must also create a so-called “binding” between the graph drawing system and the display layer. See Section 39 for more information on bindings.

  • 3. The display system now needs to load the declarations of the algorithms A and B. For this, it just needs to apply require to the files in which the algorithms reside. This will cause the declare function to be called. This function is declared by InterfaceToAlgorithms and allows files to declare that certain algorithms and options are now available.

    Once this is done, the graph drawing system is fully initialized and can be used.

  • 4. Later on, the display system wishes to lay out a social graph. Note that this is known as “drawing the graph” in the graph drawing community, even though this only means the coordinates are computed for the nodes of the graph. The actual “rendering” of the graph on the display is the job of the display system (hence the name “display layer”).

  • 5. To start the layout process, the display system calls the function beginGraphDrawingScope of the class InterfaceToDisplay.

  • 6. Next, for each vertex the function createVertex of the interface class must be called and similarly for each edge. These calls will cause an internal model of the graph to be created on the algorithm layer. Options that are attached to nodes and edges are also communicated to the graph drawing system through function calls like pushOption.

  • 7. When the graph is fully specified, the method runGraphDrawingAlgorithm must be called, which is once more a method of the interface class. This function will internally discern which algorithms have been chosen (via options) and invoke the code of the appropriate algorithms.

  • 8. Next, the function renderGraph must be called. Its job is to “communicate back” which coordinates have been computed. It will use the binding for this communication, see Section 39.

  • 9. Finally, by calling endGraphDrawingScope, the resources needed for the layout process for the social graph are freed once more.

A few points may be noteworthy:

  • • The whole communication between the display system and the graph drawing system goes through the interface class via function calls. This makes it easy to communicate with display system whose internal model of graphs is quite different from the one used in Lua (as is certainly the case for , but also the “social graph” mentioned above need not even exist as a separate entity inside the display system).

    The display system should only rely on the interface class. All communication has to go through this class, the display system may not access the internals of the internally constructed graphs directly.

  • • New algorithms can be loaded at runtime, as long as the require method is supported.

  • • The display system can also use the interface class to query which algorithms and which options are available in principle (and display this information to the user). The display system can even get access the documentation of the options at runtime since the documentation is stored in fields of the declared options.

In the following, we first present a simple display system other than TikZ. The remainder of the section then encompasses a documentation of the different functions of the class InterfaceToDisplay.

38.2 An Example Display System

In the following, we present the code of a very simple display system written in Lua (another such display system is TikZ itself, but the minimal system will allow us to focus on what is really needed). You will also find it in pgf.gd.examples.ASCIIDisplayer.

The job of this display system is to parse a string that encodes a graph and to call the appropriate functions of InterfaceToDisplay to lay out the graph. The actual calls for rendering the graph are part of the binding, which is documented in Section 39.4.

The syntax of the to-be-laid-out graph is a reduced version of TikZ’s graph syntax: The string must start with graph[algorithm’s name]{ and end with }. Between the braces, all lines must either be of the form node name; or name 1->name 2; with optional spaces around the node names.

Let us now have a look at what we must do to use the graph drawing system. First, we load some libraries and initialize the binding (see Section 39.4 for details on the binding; we can ignore it for now).


local InterfaceToDisplay = require "pgf.gd.interface.InterfaceToDisplay"
InterfaceToDisplay.bind(require "pgf.gd.examples.BindingToASCII")

-- Load two libraries that define graph drawing algorithms. We can do this only *after* the binding
-- has been created since they call the declare function internally.
require "pgf.gd.layered.library"
require "pgf.gd.force.library"

Now comes some preparation code that starts a graph drawing scope and sets up the algorithm to the string provided between the square brackets:


local algorithm = io.read():match("%s*graph%s*%[(.-)%]")

InterfaceToDisplay.pushPhase(algorithm, "main", 1)

InterfaceToDisplay.pushOption("level distance", 6, 2)
InterfaceToDisplay.pushOption("sibling distance", 8, 3)
InterfaceToDisplay.beginGraphDrawingScope(3)
InterfaceToDisplay.pushLayout(4)

The numbers 1 to 4 are the positions on the options stack at which the options should be placed. See the description of pushOption for more details.

We are now ready to create the vertices and edges via a very simple parser:


for line in io.lines() do
if line:match("}") then break elseif line:find("-") then
local n1, dir, n2 = string.match(line, "^%s*(.-)%s*(-.)%s*(.-)%s*;")
InterfaceToDisplay.createEdge(n1, n2, dir, 4)
else
local n1 = string.match(line, "^%s*(.-)%s*;")
InterfaceToDisplay.createVertex(n1, "rectangle", nil, 4)
end
end

The graph is now completely constructed inside the graph drawing system. We can now invoke the algorithms:


InterfaceToDisplay.runGraphDrawingAlgorithm()
InterfaceToDisplay.renderGraph()
InterfaceToDisplay.endGraphDrawingScope()

We can now run the resulting file using the Lua interpreter. If we provide the input shown on the left, we get the output shown on the right:

Input given to ASCIIDisplayer:

graph [layered layout] {
  Alice;
  Bob;
  Charly;
  Dave;
  Eve;
  Fritz;
  George;
  Alice -> Bob;
  Alice -> Charly;
  Charly -> Dave;
  Bob -> Dave;
  Dave -> Eve;
  Eve -> Fritz;
  Fritz -> Alice;
  George -> Eve;
  George -> Fritz;
  Alice -> George;
}

Output produced by ASCIIDisplayer:

 Alice
                   .......
                 .. . . .
            ... . . .
         ... .. . ..
      .. . . .
 Charly Bob . .
     .. . . .
        . . . .
         . . . .
          .. . . .
            .. . .
           Dave George .
               .. . ... .
                  . . .. .
                   . . ...
                    .. . . ...
                      .. . ..
                      Eve . ..
                         .. . ..
                            . . .
                             . . .
                               .. . ..
                                 ...
                                Fritz

38.3 The Interface to Display Systems

  • function InterfaceToDisplay.bind(class)

  • Initialize the binding. This function is called once by the display layer at the very beginning. For instance, TikZ does the following call:


    InterfaceToDisplay.bind(require "pgf.gd.bindings.BindingToPGF")

    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.

    Parameters: 1. class A subclass of Binding.

  • function InterfaceToDisplay.beginGraphDrawingScope(height)

  • 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.

    Parameters: 1. 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.runGraphDrawingAlgorithm()

  • 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.

    Returns: 1. Time it took to run the algorithm

  • function InterfaceToDisplay.resumeGraphDrawingCoroutine()

  • 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.endGraphDrawingScope()

  • Ends the current graph drawing scope.

  • function InterfaceToDisplay.createVertex(name, shape, path, height, binding_infos, anchors)

  • 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.

    Parameters: 1. name Name of the vertex.

    2. 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.

    3. path A Path object representing the vertex’s path.

    4. 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.

    5. binding_infos These options are passed to and are specific to the current Binding.

    6. anchors A table of anchors (mapping anchor positions to Coordinates).

  • function InterfaceToDisplay.pushSubgraphVertex(name, height, info)

  • 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 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:

    • • 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.

    • • The key subgraph bounding box width will have as its value the width of a bounding box (in points, as a string with the suffix "pt").

    • • The key subgraph bounding box height stores the height of a bounding box.

    Parameters: 1. name The name of the node. 2. height Height of the options stack. Note that this method pushes something (namely a collection) on the options stack. 3. info A table passed to Binding:createVertex, see that function.

  • function InterfaceToDisplay.addToVertexOptions(name, height)

  • 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.

    Parameters: 1. name Name of the vertex. 2. height The option stack height.

  • function InterfaceToDisplay.createEdge(tail, head, direction, height, binding_infos)

  • 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.

    Parameters: 1. tail Name of the node the edge begins at. 2. head Name of the node the edge ends at. 3. direction Direction of the edge (e.g. -- for an undirected edge or -> for a directed edge from the first to the second node). 4. height The option stack height, see for instance createVertex.

    5. binding_infos These options will be stored in the storage of the vertex at the field index by the binding.

  • function InterfaceToDisplay.pushOption(key, value, height)

  • 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.

    Parameters: 1. key A parameter (must be a string). 2. value A value (can be anything). If it is a string, it will be converted to whatever the key expects. 3. height A stack height at which to insert the key. Everything above this height will be removed.

    Returns: 1. A new stack height

    Returns: 1. A Boolean that is true if the main algorithm phase was set by the option or one option used by it.

    Returns: 1. 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.pushLayout(height)

  • 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.

    Parameters: 1. height A stack height at which to insert the key. Everything above this height will be removed.

  • function InterfaceToDisplay.createEvent(kind, param)

  • Creates an event and adds it to the event string of the current scope.

    Parameters: 1. kind Name/kind of the event. 2. parameters Parameters of the event.

    Returns: 1. The newly pushed event

  • function InterfaceToDisplay.getDeclaredKeys()

  • 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.

    Returns: 1. A lookup table of all declared keys.

  • function InterfaceToDisplay.renderGraph()

  • 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:


    local binding = InterfaceCore.binding

    binding:renderStart()
    render_vertices()
    render_edges()
    render_collections()
    binding:renderStop()

    Here, the render_... functions are local, internal functions that are, nevertheless, documented here.

    Parameters: 1. name Returns the algorithm class that has been declared using declare under the given name.

  • function render_vertices(vertices)

  • 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:


    \graph [... layout] {
    a -- b -- c -- d;
    };

    In this case, after the graph drawing algorithm has run, the present function will call:


    local binding = InterfaceCore.binding

    binding:renderVerticesStart()
    binding:renderVertex(vertex_a)
    binding:renderVertex(vertex_b)
    binding:renderVertex(vertex_c)
    binding:renderVertex(vertex_d)
    binding:renderVerticesStop()

    Parameters: 1. vertices An array of all vertices in the syntactic digraph.

  • function render_collections(collections)

  • 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:


    declare { key = "hyper", layer = 1 }

    you can say on the TikZ layer


    \graph {
    a, b, c, d;
    { [hyper] a, b, c }
    { [hyper] b, c, d }
    };

    In this case, after the graph drawing algorithm has run, the present function will call:


    local binding = InterfaceCore.binding

    binding:renderCollectionStartKind("hyper", 1)
    binding:renderCollection(collection_containing_abc)
    binding:renderCollection(collection_containing_bcd)
    binding:renderCollectionStopKind("hyper", 1)

    Parameters: 1. collections The collections table of the current scope.

  • function render_edges(arcs)

  • 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:


    \graph [... layout] {
    a -- b -- c -- d;
    };

    In this case, after the graph drawing algorithm has run, the present function will call:


    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()

    Parameters: 1. arcs The array of arcs of the syntactic digraph.

  • function get_current_options_table(height, table)

  • 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.)

    Parameters: 1. height The stack height for which the option table is required. 2. table If non nil, the options will be added to this table.

    Returns: 1. The option table as described above.