\section{Assumptions}\label{sec:assumptions}
The following assumptions are made for the implementation of the node placement algorithm:
\begin{itemize}
    \item There are no hyperedges.
    \item There are no port constraints.
    \item There are no labels.
    \item There are no cross-hierarchy edges.
    \item No edges over multiple layers (the previous phases should have added dummy nodes).
    \item Graphs are connected (see below).
\end{itemize}

Regarding the last assumption, we found an example where for a disconnected graph the algorithm behaved incorrectly.
Maybe we will get rid of this assumption later, see chapter~\ref{ch:progress}.
This example is included in the appendix (figures~\ref{fig:error_disconnected_img} and~\ref{fig:error_disconnected}).


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

\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}\label{sec:systemRequirements}
\begin{table}[ht]
	\centering
    \small
    \begin{longtable}{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 × 768 resolution & 1920 x 1080 resolution \\
        \rowcolor{gray!25}
        CPU & capable of running java applications & faster is better \\
        GPU & not any & not any\\
        \rowcolor{gray!25}
        Internet connection & not any & not any\\
        \\
	\end{longtable}
	\caption{System Requirements}
	\label{table:systemRequirements}
\end{table}


\section{Software Dependencies}\label{sec:softwareDependencies}
\begin{table}[ht]
	\centering
    \small
    \begin{longtable}{l l p{6cm}}
        \rowcolor{gray!50}
		\textbf{Dependency} & \textbf{Version} \\
		Java & $\geq8$ \\
        \rowcolor{gray!25}
        JSON-java~\ref{leary_json-java:_2018} & \\
        Eclipse Layout Kernel~\ref{noauthor_elk:_2018} & \\
	\end{longtable}
	\caption[Software Dependencies]{Software Dependencies. If no version is given, all should work and the latest is recommended.}
	\label{table:softwareDependencies}
\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}.

\centering
\begin{longtable}{|l|l|l|p{8.5cm}|}
    \hline
    Attribute & Type & Optional & Explanation \\\hline\hline
    name & string & yes & If not omitted, this must be unique for a given parent node. \\\hline
    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.\\\hline
    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.\\\hline
    dummy & boolean & yes & Iff this is explicitly set to true, then the node is a dummy node. \\\hline
    layers & < < node > > & yes & The layers of nodes inside this node (Hierarchy). \\\hline
    edges & < edge > & yes & The edges between nodes whose parent node is this node. Also see section~\ref{sec:assumptions}. \\\hline
    \caption[Node Attributes]{Node Attributes. < \emph{element type} > is a list.}
    \label{table:node-attributes}
\end{longtable}
\raggedright

\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{table}[htp]
    \centering
    \begin{longtable}{|l|l|l|p{8.5cm}|}
        \hline
        Attribute & Type & Optional & Explanation \\\hline\hline
        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. \\\hline
        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. \\\hline
    \end{longtable}
    \caption{Edge Attributes}
    \label{table:edge-attributes}
\end{table}

%\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.}
    \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 (cf.\ chapter~\ref{ch:progress}).
Therefore a node can contain other nodes and edges.
So far this is similar to what we described in section~\ref{sec:inputFileFormat}.
Additionally, 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.

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.

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=\linewidth,trim=0 7cm 0 0,clip]{img/graph.pdf}
    \caption{Class diagram of the \code{graph} package.}
    \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}.

For the execution of the \code{CodeLine}s a \code{PseudoCodeProcessor} interacts with its own \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}.


\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.}
    \label{fig:processor}
\end{figure}


\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{lane} of the class \code{JLayeredPane} and a \code{menue} of the class \code{JPanel}.
    The main window itself is a \code{JFrame} from the Swing library.
    \item The \code{lane} display the current status of the graph.
    \item The \code{menue} display \code{NiceButton}s and pseudocode.
    \item \code{EdgeView} and \code{NodeView} are \code{JPanel}s, which means they can be drawn onto the \code{JFrame}.
    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 For rendering the pseudocode we use a \code{PseudoCodeRenderer} that is a \code{DefaultTreeCellRenderer}.
    For example, it sets line numbers and highlights selected code lines.
    \item A \code{RenderHelper} that contains some additional utility functions for the views.
\end{itemize}
A class diagram of the packages \code{view} and \code{main} is displayed in figure~\ref{fig:view}.

\begin{figure}[htp]
    \centering
    \includegraphics[width=0.9\linewidth,trim=0 8cm 0 0,clip]{img/main_and_view.pdf}
    \caption{Class diagram of the packages \code{view} and \code{main}.}
    \label{fig:view}
\end{figure}