# Temporal Treemaps Crossing Minimization

This repository contains an appendix, code, experimental data, and an experimental evaluation, for the paper "Improving Temporal Treemaps by Minimizing Crossings"

The code is based on a paper by Köpp and Weinkauf [1] and was adapted to work without the inviwo framework [2]. Furthermore, the original source code of Köpp and Weinkauf contained several bugs which have been fixed. We will later explain them.

## Appendix
The appendix to the original paper can be found in the root folder of this directory in the file `Appendix.pdf`. The document contains a description of an algorithm to decide whether a temporal tree has a combinatorial layout with zero crossings.

## Source code

The source code is located in the `Source Code` directory and can be built and executed as follows.

### Building

To build the source code one has to install and a license a version of the Gurobi ILP solver [3]. Set the environment variable `GUROBI_HOME` (e.g. `/opt/gurobi1001/linux64`) accordingly.

Now use cmake to build an executable, e.g.
- `cd "Source Code"`
- `mkdir build`
- `cd build`
- `cmake ..`
- `cmake --build .`

If Gurobi is not found, you can adjust the `FindGUROBI.cmake` script.

### Executing the program

If the source code was built as described as above, then the executable can be called as follows

- `./TTMCM -fin filein -fout fileout -ALGORITHM [-unweighted]`, where `ALGORITHM` is one of `ILP`, `ILPLE`, `Barycenter`, `BarycenterLE`, `Median`, `MedianLE`, `SA`. `SA` is a version of the algorithm used by Köpp and Weinkauf [1]. The option `-unweighted` to remove the node weights in the output temporal tree.

An example execution could look like 

`./TTMCM -fin ../data/trees/ViscousFingers.ntg -fout output.ntg -ILP`

Input and Output can have the `.ntg` and `.tree` format as used in [1]. The output file contains the same tree as the input, but with a combinatorial layout having few crossings/leaf crossings.

## Bugs in the code of Köpp and Weinkauf

The code of Köpp and Weinkauf [1] contained two bugs that were fixed in this repository. Both of them appear during the deaggreagation of an aggregated temporal tree. This code can be found in the function `Temporaltree::deaggregate`. Note that this function is required to compute the nested tracking graph layout of an aggregated temporal tree and thus to create visualizations.
We describe both bugs below.

- Multiple deaggregations of a temporal tree led to temporal edges going between the vertices of the same time step. This has been fixed.
- The second bug is more severe. When an aggregated temporal tree has an order of leaves associated with it, its deaggregation has to compute an order of leaves for the deaggregated tree. However, in the original implementation of Köpp and Weinkauf this new order did not contain all leaves. We have fixed this by computing an order of the deaggregated tree from the order of the aggregated tree containing all leaves. This order respects all hierarchy constraints and is based on the relative order of leaves in the aggregated tree. 

# Experiments

## Test data
The test data used in the experiments is contained in `data/experiments` and was generated with the `splitinstance` script that is also generated on build.

## Test output
The test output is in `outexperiments`, containing a json file for each test run, that is, a combination of algorithm and instance.

## Evaluation
The plots in the paper, further plots, and other statistical evaluations are in the Jupyter notebook in `analysis`.

---

[1] Wiebke Köpp and Tino Weinkauf, Temporal Treemaps: Static Visualization of Evolving Trees, IEEE Trans. Vis. Comput. Graph., 25(1): 534-543, 2019

[2] https://inviwo.org/

[3] https://www.gurobi.com/