Pigra (pixelated graphs) is a GUI-based tool for creating grid-based representations of a graph using integer linear programming (ILP). In a grid-based representation each vertex and each edge of a graph can be described by a set of grid cells. Pigra allows to easily combine pre-defined ILP-constraints in order to model grid-based graph representations. Additionally, in case that the set of pre-defined constraints are not sufficient, the user may adapt existing or define further constraints
using the simple, mathematically oriented language PGL (pixelated graphs language),
which we have introduced for this purpose.
Typical grid-based graph representations that can be handled by Pigra are
- pathwidth
- bandwidth
- optimum st-orientation
- minimum area bar visibility representation
- minimum area bar k-visibility representation
- boxicity-k testing
Pigra is closely related to the project GDSAT. More information about the theoretical background is given in [1].
Download
You can download the source here pigra.tar.gz
A package for debian user, compiled under debian testing Jessie: pigra_1.0.deb
Unfortunatley debian testing only provides a package for antlr3c version 3.2, but we need version 3.4. Download it from: http://www.antlr3.org/download/C/
and since gurobi is not provided by any package, download it from here: http://www.gurobi.com/
You will need to create an account and get a license as an Academic user.
Finallz you need to move the following folder to ~/.local/share. In it you find the predefined Macros: kit_iti_wagner.tar.gz
It is tested under Linux and hopefully soon windows. tutorial.pdf provides you with a small tutorial and reference. It is still wip and we hope to complete it soon. If you want just a quick overview of the PGL-Syntax: cheatsheet.pdf. Additionally, you can download the following poster, which gives a short overview of the tool: Poster.
Contact
In case of questions please contact Thomas Bläsius or Benjamin Niedermann.
Publication
| [1] | T. Biedl, T. Bläsius, B. Niedermann, M. Nöllenburg, R. Prutkin, I. Rutter: Using ILP/SAT to determine pathwidth, visibility representations, and other grid-based graph drawings In: Proceedings of the 21st International Symposium on Graph Drawing (GD'13), Lecture Notes in Computer Science. Springer, 2014. To appear. Full version is available at http://arxiv.org/abs/1308.6778 |