Theoretical Computer Science / Theoretische Informatik
Institut[e] f(o|ü)r Informati(cs|k), [Universität] Osnabrück [University]
User Tools
Sidebar
Table of Contents
Multi-Level Vertical Ordering / Verticality Optimization
Here, you can find the benchmark sets used in our study of heuristics, as well as, linear, quadratic, and semidefinite programs to solve Multi-level Verticality Optimization problems. Detailed descriptions can be found in the papers:
- M. Chimani, P. Hungerländer. Multi-level Verticality Optimization: Concept, Strategies, and Drawing Scheme. Technical Report TR-FSUJ-CS-AE-11-01. Algorithm Engineering Group, Computer Science, FSU Jena. June 2011.
- M. Chimani, P. Hungerländer. Exact Approaches to Multi-level Vertical Orderings. Technical Report TR-FSUJ-CS-AE-11-02. Algorithm Engineering Group, Computer Science, FSU Jena. June 2011.
Instances
| Description | File |
|---|---|
| MLVO, Proper level graphs, narrow alignment scheme | mlvm.proper.narrow.tar.gz |
| MLVO, Proper level graphs, wide alignment scheme | mlvm.proper.wide.tar.gz |
| MLVO, Non-proper level graphs, narrow alignment scheme | mlvm.nonproper.narrow.tar.gz |
| MLVO, Non-proper level graphs, wide alignment scheme | mlvm.nonproper.wide.tar.gz |
| MLCVO (hence: Proper level graphs, narrow alignment scheme) | mlcvo.tar.gz |
Each package contains all the instances of the groups Polytope, Graphviz, and Other. The node order given in these files is the order of the optimal (or best known) solution, as reported in the paper. You may also be interested in corresponding multi-level crossing minimization results.
Rome graphs and North DAGs instances: identical to the ones of the MLCM study.
Generating Drawings
You may want to use (free for private and academic use, no liability!) the the following python-scripts to generate SVGs from the raw solution files.
- mlvo2svg_p.py generates the directly induced drawing of a proper level graph (cf. also file format below).
- mlvo2svg_np.py and mlvo2svg_np_inverted.py use the drawing algorithm sketched in the above technical report TR-FSUJ-CS-AE-11-01. The latter script uses inverted logic, i.e., bundles the edges with same sink, instead of same source.
File Format
The package-files contain simple text files, each text file is a single instance.
For proper level graphs, the format is as follows:
<Number-of-Levels> <Number-of-Edges-Between-First-and-Second-Level> <Number-of-Edges-Between-Second-and-Third-Level> ... <Number-of-Nodes-on-First-Level> <Type-of-Node-0> <Type-of-Node-1> <Type-of-Node-2> ... <Number-of-Nodes-on-Second-Level> <Type-of-Node-0> <Type-of-Node-1> <Type-of-Node-2> ... ... <Index-of-Node-on-First-Level> <Index-of-Node-on-Second-Level> <Index-of-Node-on-First-Level> <Index-of-Node-on-Second-Level> ... <Index-of-Node-on-Second-Level> <Index-of-Node-on-Third-Level> ...
Thereby, the 2-tuples describe the edges in the graph. The node indices start with 0 on each layer. A node is either of type "1" (original node), "0" (positional dummy) or "-1" (long-edge dummy).
For non-proper level graphs, the format is as follows:
<Number-of-Levels> <Number-of-Edges> <Number-of-Nodes-on-First-Level> <Number-of-Nodes-on-Second-Level> ... <Index-of-Node> <Index-of-Node> ...
Thereby, the 2-tuples describe the edges in the graph. The node indices, starting with 0 on the first layer, are sequential over all layers. A node is either of type "1" (original node), or "0" (positional dummy). The edges are always going from a lower to a higher layer.