\section{Assumptions}\label{sec:assumptions}
Our implementation makes the folliowing assumptions:
\begin{enumerate}
    \item \label{itm:hyperedges} There are no hyperedges.
    \item \label{itm:constraints} There are no port constraints.
    \item \label{itm:labels} There are no labels.
    \item \label{itm:cross-hierarchy-edges} There are no cross-hierarchy edges
    \item \label{itm:multi-layer-edge} No edges over multiple layers (the previous phases should add dummy nodes).
    \item \label{itm:connected} Graphs are connected.
\end{enumerate}

Assumptions~\ref{itm:hyperedges},~\ref{itm:constraints} and~\ref{itm:labels} were made just to make it easier for us by reducing the complexity of the task.
Assumption~\ref{itm:cross-hierarchy-edges} was made because these are not possible with the Sugiyama approach.

Regarding assumption~\ref{itm:connected}, we found an example where for a disconnected graph the algorithm behaved incorrectly.
This example is included in the appendix (figure~\ref{fig:error_disconnected}).


\section{Known Issues}\label{sec:knownIssues}
Only the most important unsolved issues are listed here.
For a complete list, see \url{http://gogs.koljastrohm-games.com/GraphDrawer/NodeShuffler/issues}.
\begin{itemize}
    \item[\done] The most important issues were solved.
\end{itemize}


\section{Overview}\label{sec:components}
The \code{main} package contains an executable class \code{Main}.
This classes \code{main} method reads a graph from a file using the \code{graph.io} package and then creates a \code{MainView}.
It is also possible to create a \code{MainView} directly from an \code{ElkNode}.
The view then creates the pseudo code for a \code{BKNodePlacement} algorithm and instantiates a \code{PseudoCodeProcessor} to run it.
The \code{PseudoCodeProcessor} repeatedly asks an associated \code{ProcessController} if and what kind of step should be done (this is further explained in section~\ref{sec:theActualAlgorithm}).
Meanwhile the view displays the same \code{LayeredGraphNode}s and \code{LayeredGraphEdge}s on the screen.

Figure~\ref{fig:components} contains a component diagram that illustrates these dependencies of the different packages.

Advantages of our architecture include:
\begin{itemize}
    \item It is possible to open multiple windows for different graphs.
    This happens already, for example, when loading a graph from a file or when generating a new random graph.
    \item Modularity, since the class \code{BKNodePlacement} can be replaced by other node placement algorithms.
    Minor changes to the internal data structure might be necessary.
    \item Abstraction: When implementing an algorithm there is no need to worry about making \enquote{step over} or \enquote{step out} commands.
    Also it is not necessary to define how to undo a step (except for some rare cases), although we do not keep a list of states: This would cost too much Memory (10~743 steps for the graph in figure~\ref{fig:originalpapergraph}).
\end{itemize}

\begin{figure}[htp]
    \centering
    \includegraphics[width=0.8\linewidth,trim=0 1cm 0 0,clip]{img/components.pdf}
    \caption[Component diagram]{Component diagram visualizing the architecture of \appname. Each component resembles a java package.}
    \label{fig:components}
\end{figure}


\section{System Requirements and Software Dependencies}\label{sec:systemRequirements}
The software \appname\ relies on is listed in table~\ref{table:softwareDependencies}.
The requirements to any system running \appname\ are demanded in table~\ref{table:systemRequirements}.

\begin{table}[htp]
    \centering
    \small
    \begin{tabular}{l p{1cm} p{6cm}}
        \rowcolor{gray!50}
        \textbf{Dependency} && \textbf{Version} \\
        Java && $\geq8$ \\
        \rowcolor{gray!25}
        JSON-java~\cite{leary_json-java:_2018} && \\
        Eclipse Layout Kernel~\cite{noauthor_elk:_2018} && \\
        \\
    \end{tabular}
    \caption[Software Dependencies]{Software Dependencies. If no version is given, all should work and the latest is recommended.}
    \label{table:softwareDependencies}
\end{table}

\begin{table}[htp]
    \centering
    \small
    \begin{tabular}{l l p{6cm}}
        \rowcolor{gray!50}
        \textbf{Requirement} & \textbf{Minimum} & \textbf{Recommended} \\
        Free disk space & 150MB & 150MB \\
        \rowcolor{gray!25}
        Free RAM & 300MB (single window) & More for multiple windows/graphs \\
        \rowcolor{gray!25}
        & & At least 2 GB for running the automatic tests. \\
        Display & $1024 \times 768$ resolution & $1920 \times 1080$ resolution \\
        \rowcolor{gray!25}
        CPU & capable of running java applications & faster is better \\
        GPU & capable of 2D rendering & rendering in $1920 \times 1080$ resolution\\
        \rowcolor{gray!25}
        Internet connection & not any & not any\\
        \\
    \end{tabular}
    \caption{System Requirements}
    \label{table:systemRequirements}
\end{table}

\section{Input File Format}\label{sec:inputFileFormat}
The input to \appname\ is a JSON file.
An example is displayed in figure~\ref{fig:json-example}.
The structure is as follows:
\begin{itemize}
    \item The object in the JSON file is a node.
    \item A node has the attributes that are displayed in table~\ref{table:node-attributes}.
    \item An edge has the attributes that are displayed in table~\ref{table:edge-attributes}.
    \item Any additional attributes not listed here are ignored.
    For example they can be used as comment fields, to make the file more readable.
\end{itemize}
For parsing the JSON file the JSON-java library~\cite{leary_json-java:_2018} is used.
The classes for reading and writing those JSON files are displayed in figure~\ref{fig:io}.
The internal representation of graphs is further explained in the section~\ref{sec:graph}.

\begin{table}[htp]
    \centering
    \small
    \begin{tabular}{l l l p{8.5cm}}
        \rowcolor{gray!50}
        \textbf{Attribute} & \textbf{Type} & \textbf{Optional} & \textbf{Explanation} \\
        source & string & no & The name of the source of this edge.
        Must be a node with the same parent node as the node specified by the \code{target} attribute. \\
        \rowcolor{gray!25}
        target & string & no & The name of the target of this edge.
        Must be a node with the same parent node as the node specified by the \code{source} attribute. \\
    \end{tabular}
    \caption{Edge Attributes}
    \label{table:edge-attributes}
\end{table}

\begin{table}[htp]
    \centering
    \small
    \begin{tabular}{l l l p{8.5cm}}
        \rowcolor{gray!50}
        \textbf{Attribute} & \textbf{Type} & \textbf{Optional} & \textbf{Explanation} \\
        name & string & yes & If not omitted, this must be unique for a given parent node. \\
        \rowcolor{gray!25}
        width & integer & yes & The minimum width of the node.
        The node can be wider if it contains other nodes that need more space.
        If the whole layout is too large, it is resized, such that all nodes are proportionately shrunk: In that case the minimum width can be exceeded after the shrinking.
        Default 40.\\
        height & integer & yes & The minimum height of the node.
        The node can be higher if it contains other nodes that need more space.
        If the whole layout is too large, it is resized, such that all nodes are proportionately shrunk: In that case the minimum height can be exceeded after the shrinking.
        Default 40.\\
        \rowcolor{gray!25}
        dummy & boolean & yes & Iff this is explicitly set to true, then the node is a dummy node. This attribute is necessary, because we expect previous stages to have eliminated multilayer edges, see section~\ref{sec:assumptions}. \\
        layers & < < node > > & yes & The layers of nodes inside this node (Hierarchy). \\
        \rowcolor{gray!25}
        edges & < edge > & yes & The edges between nodes whose parent node is this node. \\\\
    \end{tabular}
    \caption[Node Attributes]{Node Attributes. < \emph{element type} > is a list.}
    \label{table:node-attributes}
\end{table}

\begin{figure}[htp]
    \centering
    \includegraphics[width=\linewidth,trim=0 26cm 0 0,clip]{img/io.pdf}
    \caption[Class diagram of the \code{graph.io} package]{Class diagram of the \code{graph.io} package, containing utilities for reading and writing graphs.}
    \label{fig:io}
\end{figure}

%\begin{figure}[htp]
%    \centering
%    \includegraphics[width=0.9\textwidth]{img/json.png}
%    \caption[Input file format]{Input file format illustrated as a HERM diagram}
%    \label{fig:iff}
%\end{figure}

\begin{figure}[htp]
    \begin{lstinputlisting}[language=json,emph={}]{src/graph.json}
    \end{lstinputlisting}
    \caption[Example input file]{Example input file that is understood by \appname.
    The graph is also displayed in figure~\ref{fig:full-application-example}.}
    \label{fig:json-example}
\end{figure}


\section{Internal graph representation, \code{graph}}\label{sec:graph}
One feature that is important to us, is to be able to work with hierarchical graphs.
Therefore a node can contain other nodes and edges.
In addition to the variables described in section~\ref{sec:inputFileFormat}, there are multiple attributes that are used during the computation or as output variables.
\begin{itemize}
    \item The \member{parent} of a node is the node that contains it in the hierarchy.
    \item \member{dummy} specifies whether this node is a dummy node.
    \item \member{name} is the name of the node.
    \item The attributes \member{shift}, \member{sink},  \member{root} and  \member{align} correspond to the variables used by Brandes and Köpf~\cite{brandes_fast_2001}.
    %They are summarized in table~\ref{table:bk-variables}.
    \item The attribute \member{xUndef} determines whether the x coordinate of the node has already been assigned a value.
    \item The attributes \member{x} and \member{y} are the coordinates of the node relative to its \member{parent}.
    \item The attributes \member{w} and \member{h} are the width and height of the node.
    \item The attributes \member{color} is the color in which the node is displayed.
    \item The attribute \member{selected} is used to highlight the node that is currently active in each layout.
\end{itemize}
The last six bullet points are available separately for each of the four extremal layouts.
The last four bullet points are also separately available for the combined layout.
To achieve this, they are stored in the internal classes \code{LayoutInfo} and \code{CombinedLayoutInfo}.

Similarly, edges have the following attributes in addition to those given through the JSON format:
\begin{itemize}
    \item \member{dummyEdge} specifies whether they are edges between two dummy nodes.
    \item \member{bindPoints} is a list of bend points for the edge, including the beginning and end point of the edge.
    \item \member{reversed} specifies if this edge was reversed earlier (not used by \appname).
    \item \member{graph} is the node that contains the edges (hierarchy).
    \item \member{conflicted} corresponds to the variable used by Brandes and Köpf~\cite{brandes_fast_2001} and indicates that this edge won't be drawn vertically.
\end{itemize}
The last bullet point is available separately for each of the four extremal layouts and for the combined layout.

The user has to make sure that each graph meets the requirements in section~\ref{sec:assumptions}, we do not check them and wrong usage might result in errors.

A class diagram of the package \code{graph} is displayed in figure~\ref{fig:graph}.
There you will find some less important (from a documentation point of view) attributes that were not listed here.

\begin{figure}[htp]
    \centering
    \includegraphics[width=0.95\linewidth,trim=0 2cm 0 0,clip]{img/graph.pdf}
    \caption[Class diagram of the \code{graph} package]{Class diagram of the \code{graph} package. Getters, setters and constructors are omitted.
    The package \code{graph.io} is displayed in figure~\ref{fig:io}}
    \label{fig:graph}
\end{figure}

%\begin{table}[htp]
%    \begin{longtable}{|l|p{10cm}|}
%        \hline
%        Attribute & Explanation \\\hline\hline
%        \member{root} & The root node of the block of this node.
%        Unique for all nodes in the same block. \\\hline
%        \member{sink} & The topmost sink in the block graph that can be reached from the block that this node belongs to.
%        Only used for nodes that are the root of a block.
%        Unique for all nodes in the same class. \\\hline
%        \member{shift} & The shift of the class that this node belongs to.
%        Only used for nodes that are a sink of a class. \\\hline
%        \member{align} & The next node in the same block as this node.
%        The \member{align} of the last node in the block is the root node of the block again.\\\hline
%    \end{longtable}
%    \caption{Variables also used by Brandes and Köpf~\cite{brandes_fast_2001}}
%    \label{table:bk-variables}
%\end{table}


\section{The actual algorithm}\label{sec:theActualAlgorithm}
This section expects the reader to be familiar with the node placement algorithm by Brandes and Köpf~\cite{brandes_fast_2001}.
We recommend section 3.2.1 of Carstens~\cite{carstens_node_2012} for a detailed explanation, although Carstens uses some terms differently than Brandes and Köpf and draws the graph from left to right.
By these means our implementation is oriented more towards the original paper by Brandes and Köpf~\cite{brandes_fast_2001}.

The \enquote{stages} of the algorithm, located in the package \code{bk}, represent intervals during which each step of the algorithm is performed in a similar way.
These stages, however, do not run the algorithm, but instead create lines of pseudocode, class \code{PseudoCodeNode}, that can be executed (don't be mislead by the term pseudocode!).
More precisely, each \code{PseudoCodeNode} is a line of code that can be displayed and contains a \code{CodeLine} that can be executed.
The \code{PseudoCodeNode}s are arranged hierarchically to form a whole pseudocode tree.
All the stages are displayed in class diagram~\ref{fig:bk} while the different kinds of \code{CodeLine}s are listed in class diagram~\ref{fig:codeline}.
This separation was made to distinguish viewable \code{PseudoCodeNode}s from executable \code{CodeLine}s.

For the execution of the \code{CodeLine}s a \code{PseudoCodeProcessor} interacts with its own \newline\code{ProcessController} and \code{Memory}.
Note that the \code{ProcessController} is not a controller in the MVC sense that it processes user input, but in the sense that it \emph{controls} the execution of steps/stages.
This works the following:
\begin{enumerate}
    \item The \code{MainView} creates a node placement algorithm (only \code{BKNodePlacement} available) and a \code{PseudoCodeProcessor} to run it.
    \item The processor concurrently asks its associated \code{ProcessController} if it should do a forward or backward step and if that is a \enquote{step into}, \enquote{step over} or \enquote{step out}.
    \item The \code{ProcessController} waits until it knows which action to take (for example if the user pressed Alt + Right arrow key, see chapter~\ref{ch:ui}).
    Alternatively, if the animation is not paused, it waits until a specific delay has passed.
    Then it returns to the processor which step to take next.
    \item Depending on the return value, the processor executes one or multiple lines of code in forwards or backwards direction.
\end{enumerate}
A class diagrams for the \code{processor} package is displayed in figure~\ref{fig:processor}.


\section{View}\label{sec:view}
This section only covers the software architecture regarding the views.
For an explanation of what is actually displayed, see chapter~\ref{ch:ui}

\begin{itemize}
    \item The main window displays a \code{JLayeredPane} on the left where the graph is shown and a \code{menu} of the class \code{JPanel} on the right, where \code{NiceButton}s and \code{PseudoCodeNode}s are located.
    The main window itself is a \code{JFrame} from the Swing library.
    \item Additionally a legend, class \code{LegendView}, that is another \code{JPanel} is displayed on the bottom.
    \item The \code{PseudoCodeNode}s are rendered by the \code{PseudoCodeRenderer} class.
    For example, this class highlights selected code lines.
    \item \code{EdgeView} and \code{NodeView} are \code{JPanel}s, which means they can be drawn onto the \code{JLayeredPane}.
    For this they have to know about which part of the graph and which layout they belong to (some attributes).
    \item A \code{NiceButton} is a \code{JButton} that has an image on it.
    \item Next to the \code{PseudoCodeRenderer} is an object of the class \code{PseudoCodeLines}, that extends \code{JComponent}.
    \item A \code{RenderHelper} that contains some additional utility functions for the views.
    \item Dialogs like the \code{OptionsDialog} and the \code{RandomGraphDialog} are \code{JDialog}s.
\end{itemize}
A class diagram of the package \code{view} is displayed in figure~\ref{fig:view}.

\begin{figure}[htp]
    \centering
    \includegraphics[width=\linewidth,trim=0 11cm 0 0,clip]{img/main_and_view.pdf}
    \caption[Class diagram of the packages \code{view} and \code{main}]{Class diagram of the packages \code{view} and \code{main}.
    Getters, setters and contructors are not omitted because most of them perform nontrivial computations.}
    \label{fig:view}
\end{figure}

\begin{figure}[htp]
    \centering
    \includegraphics[width=\linewidth,trim=0 11cm 0 0,clip]{img/bk.pdf}
    \caption{Class diagram of the \code{bk} package.}
    \label{fig:bk}
\end{figure}

\begin{figure}[htp]
    \centering
    \includegraphics[width=\linewidth,trim=0 25cm 0 0,clip]{img/codeline.pdf}
    \caption{Class diagram of the \code{codeline} package.}
    \label{fig:codeline}
\end{figure}

\begin{figure}[htp]
    \centering
    \includegraphics[width=\linewidth,trim=0 5cm 0 0,clip]{img/processor.pdf}
    \caption[Class diagram of the \code{processor} package.]{Class diagram of the \code{processor} package.
    Constructors and trivial getters and setters are omitted.}
    \label{fig:processor}
\end{figure}