NodeShuffler/doc/chapter/2architecture.tex

\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 chapter~\ref{ch:progress}).
\end{itemize}


\section{Overview}\label{sec:components}
The \code{main} package contains an executable class \code{Main}.
This classes main method reads a graph from a file using the \code{graph.io} package and then creates a MainView.
The view then instantiates a \code{BKNodePlacement} algorithm and runs it.
The \code{BKNodePlacement} repeatedly asks the \code{AnimationController} if a step should be done (this is further explained in section~\ref{sec:theActualAlgorithm}).
It uses \code{LayeredGraphNode}s and \code{LayeredGraphEdge}s.
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 packages.

\begin{figure}[htp]
    \centering
    \includegraphics[width=\linewidth,trim=0 11cm 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{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}
    \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}.

\begin{figure}[htp]
    \centering
    \includegraphics[width=\linewidth,trim=0 10cm 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.

A stage of the algorithm, interface \code{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 or a breakpoint has been reached.
For example, a forward step in the stage of calculating one extremal layout, \code{ExtremalLayoutCalc}, consists of either a step of calculating the blocks, \code{BlockCalc}, or a step of compacting the layout, \code{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 \code{AnimationController} 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).
    It sends an \code{AnimationController} as a parameter for the constructor.
    \item The algorithm concurrently asks the \code{AnimationController} 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{AnimationController} waits until it knows which action to take (for example if the user pressed Alt + Right arrow key).
    Alternatively, if the animation is not paused, it waits until a specific delay has passed.
    Then it returns to the algorithm which step to take next.
    \item The algorithm potentially calls one the step methods of other stages while executing one step.
\end{enumerate}

\begin{figure}[htp]
    \centering
    \includegraphics[width=\linewidth,trim=0 11cm 0 0,clip]{img/animation_and_bk.pdf}
    \caption{Class diagram of the packages \code{bk} and \code{animation}.
    For better readability the class \code{PseudoCodeNode} has been omitted.}
    \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}

\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=\linewidth,trim=0 19cm 0 0,clip]{img/view.pdf}
    \caption{Class diagram of the packages \code{view} and \code{main}.}
    \label{fig:view}
\end{figure}