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

Introduction

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.
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. Directory: /sat

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.

minisat on Windows

Get the Minisat source code from minisat.se. We have used minisat-2.2.0.tar.gz from this location. Under Visual Studio 2017 Community Edition, the above code does not compile as-is. Solve the following three problems.

Visual Studio does not have zlib by default. Find, build and configure it so that Visual Studio sees it when you compile Minisat.
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:
```
#include 
#include 
size_t getPeakRSS()
{
        PROCESS_MEMORY_COUNTERS info;
        GetProcessMemoryInfo(GetCurrentProcess(), &info, sizeof(info));
        return (size_t)info.PeakWorkingSetSize / (1024*1024);
}
```
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). Directory: /exact

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.

Generate (random) instances in this program.
Run FPT and/or ItD on these instances.
Use writePCSV to write .pcsv files.
Run Sat on these files.

Imprint + Privacy Policy | Privacy Disclaimer