\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{Components}\label{sec:components}
\TODO{write about components and dependencies}
Figure~\ref{fig:components} contains a component diagram that illustrates this.

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

\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 undercut.
    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 undercut.
    Default 40.\\\hline
    dummy & boolean & yes & Iff this is set to yes, 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. \\\hline
    \caption{Node Attributes. < \emph{element type} > is a list.}
    \label{table:node-attributes}
\end{longtable}
\raggedright

\begin{figure}[htp]
    \centering
    \includegraphics[width=\linewidth,trim=0 20cm 0 0,clip]{img/io.pdf}
    \caption[Class diagram of the \enquote{graph.io} package]{Class diagram of the \enquote{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 \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
    \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}
    \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, \enquote{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 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.
    There is one coordinate for each of the four extremal layouts and on coordinate for the combined layout.
\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{graph} is displayed in figure~\ref{fig:graph}.

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


\begin{table}[htp]
    \begin{longtable}{|l|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
    \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.

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:animation_and_bk}.

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

Note that the \enquote{AnimationController} is not a controller in the MVC sense that it processes user input, but in the sense that it \enquote{controls} the execution of steps/stages.
This works the following:
\begin{enumerate}
    \item The main view creates a node placement algorithm (only \enquote{BKNodePlacement} available).
    It sends a controller as a parameter for the constructor.
    \item The algorithm concurrently asks the AnimationController if it should do a forward or backward step.
    \item The AnimationController waits until it knows which action to take (for example if the user pressed the right arrow key).
    Alternatively, if the animation is not paused, then it waits until a specific delay has passed.
    Then it returns to the algorithm which step to take next.
    \item The algorithm potentially calls the step function of other alogrithms while executing one step.
\end{enumerate}

\begin{figure}[htp]
    \centering
    \includegraphics[width=\linewidth,trim=0 13cm 0 0,clip]{img/animation_and_bk.pdf}
    \caption{Class diagram of the packages \enquote{bk} and\enquote{animation}.}
    \label{fig:animation_and_bk}
\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}

The distinguish two kinds of views:
\begin{itemize}
    \item The main window displays four regions for the different extremal layouts while also forwarding keyboard commands to the AnimationController.
    For this we use a JFrame from the Swing library.
    \item \enquote{EdgeView} and \enquote{NodeView} are JPanels, which means they can be drawn onto the JFrame.
    For this they have to know about which part of the graph and which layout they belong to.
\end{itemize}
A class diagram of the packages \enquote{view} and \enquote{main} is displayed in figure~\ref{fig:view}.

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