-- Copyright 2012 by Till Tantau -- -- This file may be distributed an/or modified -- -- 1. under the LaTeX Project Public License and/or -- 2. under the GNU Public License -- -- See the file doc/generic/pgf/licenses/LICENSE for more information -- @release $Header$ --- -- A ``layered'' layout of a graph tries to arrange the nodes in -- consecutive horizontal layers (naturally, by rotating the graph, this -- can be changed in to vertical layers) such that edges tend to be only -- between nodes on adjacent layers. Trees, for instance, can always be -- laid out in this way. This method of laying out a graph is especially -- useful for hierarchical graphs. -- -- The method implemented in this library is often called the -- \emph{Sugiyama method}, which is a rather advanced method of -- assigning nodes to layers and positions on these layers. The same -- method is also used in the popular GraphViz program, indeed, the -- implementation in \tikzname\ is based on the same pseudo-code from the -- same paper as the implementation used in GraphViz and both programs -- will often generate the same layout (but not always, as explained -- below). The current implementation is due to Jannis Pohlmann, who -- implemented it as part of his Diploma thesis. Please consult this -- thesis for a detailed explanation of the Sugiyama method and its -- history: -- -- \begin{itemize} -- \item -- Jannis Pohlmann, -- \newblock \emph{Configurable Graph Drawing Algorithms -- for the \tikzname\ Graphics Description Language,} -- \newblock Diploma Thesis, -- \newblock Institute of Theoretical Computer Science, Univerist\"at -- zu L\"ubeck, 2011.\\[.5em] -- \newblock Available online via -- \url{http://www.tcs.uni-luebeck.de/downloads/papers/2011/}\\ \url{2011-configurable-graph-drawing-algorithms-jannis-pohlmann.pdf} -- \\[.5em] -- (Note that since the publication of this thesis some option names -- have been changed. Most noticeably, the option name -- |layered drawing| was changed to |layered layout|, which is somewhat -- more consistent with other names used in the graph drawing -- libraries. Furthermore, the keys for choosing individual -- algorithms for the different algorithm phases, have all changed.) -- \end{itemize} -- -- The Sugiyama methods lays out a graph in five steps: -- \begin{enumerate} -- \item Cycle removal. -- \item Layer assignment (sometimes called node ranking). -- \item Crossing minimization (also referred to as node ordering). -- \item Node positioning (or coordinate assignment). -- \item Edge routing. -- \end{enumerate} -- It turns out that behind each of these steps there lurks an -- NP-complete problem, which means, in practice, that each step is -- impossible to perform optimally for larger graphs. For this reason, -- heuristics and approximation algorithms are used to find a ``good'' -- way of performing the steps. -- -- A distinctive feature of Pohlmann's implementation of the Sugiyama -- method for \tikzname\ is that the algorithms used for each of the -- steps can easily be exchanged, just specify a different option. For -- the user, this means that by specifying a different -- option and thereby using a different heuristic for one of the steps, a -- better layout can often be found. For the researcher, this means that -- one can very easily test new approaches and new heuristics without -- having to implement all of the other steps anew. -- -- @library local layered -- Load declarations from: require "pgf.gd.layered" -- Load algorithms from: require "pgf.gd.layered.Sugiyama" require "pgf.gd.layered.cycle_removal" require "pgf.gd.layered.node_ranking" require "pgf.gd.layered.crossing_minimization" require "pgf.gd.layered.node_positioning" require "pgf.gd.layered.edge_routing"