Linear Orderings of Sparse Graphs

Supplementary web site for the experimental evaluation conducted in my PhD thesis "Linear Orderings of Sparse Graphs", submitted to the Faculty for Computer Science and Mathematics, University of Passau, Germany.

LOP and FAS

Given a directed graph G, the Linear Ordering problem (LO) consists in finding a linear ordering of G’s vertices such that the number of arcs contradicting this ordering are minimum. It is equivalent to the well-known Feedback Arc Set problem (FAS), which asks for a minimum cardinality set of arcs whose removal from the graph makes it acyclic. The decision version of the latter is one of Karp’s 21 -complete problems.

Please see other resources, e.g., the article on Wikipedia or my PhD thesis for further information and references.

Evaluation

We evaluated a set of algorithms for LO experimentally on

  • Cubic, Quartic, Quintic: sparse, -regular graphs with ,
  • Facet: a set of instances generated from fences and Möbius ladders,
  • LOLIB: graphs from LOLIB.

The participating algorithms were

  • Nest: a simple 1-OPT heuristic as described in the thesis that is similar to InsertionSort,
  • ELS: a linear-time heuristic by Eades, Lin, and Smyth,
  • Psi, PsiAlt: two variants of a heuristic developed in the thesis,
  • Fusion: an extension of Psi, also developed in the thesis,
  • ExIn: an exact and fast algorithm on sparse graphs, also developed in the thesis.

Except for ELS and ExIn, the algorithms can start from an initial linear ordering that is either an arbitrary ordering of vertices given by the internal graph representation, the result of ELS, or random.

Instances

The instances in Cubic, Quartic, Quintic, and Facet were generated by a Python program based on the NetworkX package.

For Cubic, Quartic, Quintic, we drew a random undirected 3-, 4-, or 5-regular graph by means of the function networkx.generators.random_graphs.random_regular_graph and afterwards applied a strong orientating algorithm. In half of all cases, we used a random ear decomposition (networkx.generators.orientation.random_strong_orientation with ear_decomposition=networkx.generators.orientation.ear_decomposition), in the other half, we decomposed the graph randomly into both cycles and ears (networkx.generators.orientation.random_strong_orientation with ear_decomposition=networkx.generators.orientation.pseudo_ear_decomposition). The implementations of all orienting routines are contained in the patch set provided below.

For Facet, we created -fences for as well as random Möbius ladders consisting of three to eleven cycles of lengths three and four. The test instances were then obtained from 2-clique sums of these graphs.

The graph format used is an extension of the Sparse6 graph format for directed graphs by adding a further colon and a direction bit for each arc. Whereas Sparse6 is already contained as a format for reading and writing graphs in NetworkX, the implementation of the extension is again part of the patch set. The files contain one graph per line.

Generated test instances: download Cubic download Quartic download Quintic download Facet

NetworkX: Apply this download patch to #0fe9b8d.

Implementation

All algorithms were implemented in C++ and use basic data structures as made available by the STL. The COIN-OR::LEMON graph library provides the network flow algorithm.

The tool that manages the test suite and runs the algorithms is build on the Qt application framework version 5.7. It expects to find a configuration file named .config with the following content:

[system]
hostname = ...

[database]
host = ...
port = ...
db = ...
user = ...
passwd = ...
cacert = ...

where db may either be the name of a MySQL database or the path to a SQLite database file. Irrelevant fields are ignored. Qt’s database drivers for MySQL or SQLite, respectively, must be present on the system.

The algorithms of the evaluation correspond to the following parameters:

  • --nest for Nest,
  • --els for ELS,
  • --psi for Psi,
  • --psicubic for the version of Psi specialized on cubic graphs,
  • --cascade=mblock,elim for PsiAlt,
  • --fusion for Fusion,
  • --sbbrec for ExIn.

The different initializers can be selected using the -i option.

For testing purposes, the implementation also contains an ILP algorithm, which requires the presence of the COIN-OR Open Solver Interface as well as the COIN-OR Linear Programming Solver libraries on the system. Both are also available as packages on most Linux distributions.

With this prerequisites, the download binary should run on most modern Linux x86-64 machines.