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

http://www1.informatik.uni-wuerzburg.de/en/staff

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 in the src directory.

• 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: src/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.

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. We recommend vcpkg as package manager.
2. Make the following changes to Minisat's core/Main.cc, either by hand or by applying our patch src/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 <windows.h>
     #include <psapi.h>
     size_t getPeakRSS()
     {
     PROCESS_MEMORY_COUNTERS info;
     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 patch /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: src/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 the SAT-based program 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<CharName> Meeting;. It could be interesting to use bitsets instead.
• An instance is a vector of meetings: typedef vector<Meeting> Meetings;
• With k characters and the instance as meetings, run the FPT algorithm using dp<Silent>( k, meetings ). For more debug output, use dp<Verbose> instead.
• Similarly, run ItD using iterativeDeepening<Silent>( k, meetings ) or <Verbose>. (It is probably much slower than dp.)
• 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.