# Computing Storyline Visualizations with Few Block Crossings
Thomas C. van Dijk, Fabian Lipp, Peter Markfelder and Alexander Wolff
_Lehrstuhl für Informatik I, Universität Würzburg, Germany_
All implementations are written in C++, with the exception of some "driver" code in Python for Sat. Comparable effort has been put into optimizing each program. Memory usage was not optimized, but there are no flagrant memory inefficiencies.
- Code is available [here](code-release.zip).
- We have compiled the C++11 code with Visual Studio 2017 Community Edition.
- We have run the Python code with Pypy 5.7.1 Python 2.7.13.
# Satisfiability-based algorithm (Sat)
The implementation uses Python to write CNF SAT instances in DIMACS format, to run Minisat on them, and to run the search.
### How to set up
Get a `minisat` executable for your system and put it in `/sat`. See below on how to build Minisat on Windows; in our experience, the Cygwin-based executable available at minisat.se does not work.
### How to use
- Run `[your python] main.py [filename]`, for example `pypy main.py example/star_wars.pcsv`.
### Re: minisat on Windows
Get the Minisat source code from minisat.se. We have used minisat-2.2.0.tar.gz from this location: http://minisat.se/downloads/minisat-2.2.0.tar.gz
Under Visual Studio 2017 Community Edition, the above code does not compile as-is. Solve the following three problems.
1. Visual Studio does not have zlib by default. Find, build and configure it so that Visual Studio sees it when you compile Minisat.
2. Make the following changes to Minisat's `core/Main.cc`, either by hand or by applying our `/minisat4win/Main.cc.patch`.
- Change any `"PRIu64"` to `" PRIu64 "`, since Visual Studio chokes otherwise.
- CPU and memory limitations are implemented in a Linux-specific way and we remove support for this. (These are not used in the experiments.) Remove/comment out the body of the conditional blocks for `mem_lim != INT32_MAX` and `cpu_lim != INT32_MAX`.
- Remove/comment out any calls to `signal` with signals that Windows does not have, such as `signal(SIGXCPU,SIGINT_exit);`. This does not influence our experiments, because of the previous point.
- Measuring peak memory usage is implemented in a Linux-specific way: change as follows. In `printStats`, change to `double mem_used = getPeakRSS();`. Above `printStats`, add:
GetProcessMemoryInfo(GetCurrentProcess(), &info, sizeof(info));
return (size_t)info.PeakWorkingSetSize / (1024*1024);
3. Make the following change to minisat's `utils/ParseUtils.h`, either by hand or by applying our `/minisat4win/ParseUtils.h.patch`.
- Change `static const int buffer_size = 1048576;` to 4096 or some other small number. (Windows, by default, has a smaller stack size and will crash with minisat's default value. Using a smaller read buffer is the simplest fix.)
# Custom exact algorithms: FPT and ItD
The implementation is in straight C++11 without libraries.
See: _Block Crossings in Storyline Visualizations. T. C. van Dijk, M. Fink, N. Fischer, F. Lipp, P. Markfelder, A. Ravsky, S. Suri, A. Wolff. Proceedings of the 24nd Internation Symposium on Graph Drawing. (2016)._
### How to set up
Compile `bcdp.cpp`. You may need to include a compiler flag to compile as C++11, for example `-std=c++11` in older versions of `g++`.
There is no commandline interface. As-is, the program runs some experiments on random graphs.
### How to use
- Look at `main` (bottom of the file) and try to read along.
- Look at `run_FromFile` for an example of how to run the algorithms on a simple file format.
- Look at `run_RandomInstances` for an example of how to automatically run measurements on random instances and write the results to a CSV file. This also writes each instance to a PCSV file so you can run Sat on the same instances.
- Characters are identified by a 0-indexed integer: `typedef uint8_t CharName;`
- A meeting is a set of character ids: `typedef set Meeting;`
- An instance is a vector of meetings: `typedef vector Meetings;`
- With `k` the number of characters and `meetings` the instance, run the FPT algorithm using `dp( k, meetings )`. For more debug output, use `dp` instead.
- Similarly, run ItD using `iterativeDeepening( k, meetings )` or ``.
- Use `random_uniform` and `random_small` to generate random instances.
- Use `Timer` objects to measure time: `double Timer::elapsed()` gives seconds since the object was constructed.
### How to compare with Sat
This program does not read the same input file format as Sat. (This program does not support concurrent meetings, which Sat does.) In order to compare to Sat, proceed as follows.
1. Generate (random) instances in this program.
2. Run FPT and/or ItD on these instances.
3. Use `writePCSV` to write .pcsv files.
4. Run Sat on these files.