\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 (maybe we will get rid of this assumption later, see~\ref{ch:progress}).
\end{itemize}

\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}.
\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:model}.

\centering
\begin{longtable}{|p{1.8cm}|p{2.3cm}|p{1.7cm}|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. \\\hline
    height & integer & yes & The minimum height of the node.
    The node can be higher if it contains other nodes that need more space. \\\hline
    dummy & boolean & yes & Iff this is set to yes, then the node is a dummy node. \\\hline
    layers & list of lists of nodes & yes & The layers of nodes inside this node (Hierarchy). \\\hline
    edges & list of edges & yes & The edges between nodes whose parent node is this node. \\\hline
    \caption{Node Attributes}
    \label{table:node-attributes}
\end{longtable}

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

\newpage

\TODO{attribute for dummy nodes}
\begin{longtable}{|p{1.8cm}|p{2cm}|p{1.8cm}|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 \enquote{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 \enquote{source} attribute. \\\hline
    \caption{Edge Attributes}
    \label{table:edge-attributes}
\end{longtable}
\raggedright

%\begin{figure}[tp]
%    \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}

\TODO{Kante in beispielJSON}
\begin{figure}
    \begin{lstinputlisting}[language=json,emph={}]{img/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, \enquote{Model}}\label{sec:model}
One feature that is important to us, is to be able to work with hierarchical graphs (cf.\ chapter~\ref{ch:progress}).
Therefore a node not only has edges to other nodes, but also it 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 attributes \enquote{shift},  \enquote{sink},  \enquote{root} and  \enquote{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 \enquote{parent} of a node is the node that contains it in the hierarchy.
    \item The attributes $x$ and $y$ are the coordinates of the node relative to its parent node.
\end{itemize}
Similarly, edges have additional attributes:
\begin{itemize}
    \item \enquote{dummy} specifies whether they are dummy edges.
    \item \enquote{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.
    \item \enquote{bindPoints} is a list of bend points for the edge, including the beginning and end point of the edge.
\end{itemize}

A class diagram of the package \enquote{Model} is displayed in figure~\ref{fig:model}.

\begin{figure}[tp]
    \centering
    \includegraphics[width=\linewidth, trim={0 6cm 0 0}]{img/Model.pdf}
    \caption{Class diagram of the \enquote{Model} package.}
    \label{fig:model}
\end{figure}

\begin{longtable}{|p{2.8cm}|p{10cm}|}
    \hline
    Attribute & Explanation \\\hline\hline
    root & The root node of the block of this node.
    Unique for all nodes in the same block. \\\hline
    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
    shift & The shift of the class that this node belongs to.
    Only used for nodes that are a sink of a class. \\\hline
    \caption{Variables also used by Brandes and Köpf~\cite{brandes_fast_2001}}
    \label{table:bk-variables}
\end{longtable}

\section{The actual algorithm}\label{sec:theActualAlgorithm}
This section assumes that the reader is familiar with the node placement algorithm by Brandes and Köpf~\cite{brandes_fast_2001}.

A \enquote{stage} of the algorithm, interface \enquote{AlgorithmStage}, is an interval during which each step of the algorithm is performed in a similar way.
Each time such a step is performed it returns whether the stage is already finished.
For example, a forward step in the stage of calculating one extremal layout, class \enquote{ExtremalLayoutCalc}, consists of either a step of calculating the blocks, class \enquote{BlockCalc}, or a step of compacting the layout, class \enquote{Compaction}.
All the stages are displayed in class diagram~\ref{fig:animated}.

To be able to undo a step each stage needs to implement methods for both forward and backward steps.

\begin{figure}[tp]
    \centering
    \includegraphics[width=\linewidth, trim={0 9cm 0 0}]{img/Algorithms_Animated.pdf}
    \caption{Class diagram of the package \enquote{Algorithms.Animated}.}
    \label{fig:animated}
\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}

\TODO{Kolja ausfragen}