Unique selling point

plag-mangler can automatically produce pretty layouts of some subset of planar graphs, given a planar embedding.

There is a good chance it will work well for graphs that arise as the board in board games; that was my own use case. For other kinds of planar graphs, messing with the cost function parameters may well help.

Capabilities

• Read and write its own .plag format which describes a planar graph including a planar embedding
• Write out a list of faces, with the edges for each face.
• Make a connected graph biconnected by adding edges; make a a biconnected graph triconnected likewise; remove added edges.
• Keep track of outer faces, and outer vertices; and update outer status of one from the other.
• Join multiple contiguous outer faces by cutting edges and/or introducing new vertices (effectively, by replicating the notional point at infinity).
• Compute the dual.
• Compute a Planar Canonical Order of a triangulated graph using an algorithm inspired by work by: Goossen Kant; De Fraysseix, Pach & Pollack; and Chrobak & Payne.
• Compute a straight line drawing of a triangulated graph using the algorithm of Chrobak & Payne (using the implementation in Boost). The resulting drawing is generally terrifically ugly.
• Attempt to make a provided straight line drawing pretty by moving the vertices according to a cost function built into plag-mangler. We use Steven G. Johnson's very useful NLopt library, including its Sbplx algorithm (NLopt's implementation of T. Rowan's Subplex algorithm) and the Augmented Lagrangian method from Andrew R. Conn, Nicholas I. M. Gould, and Philippe L. Toint. The result works well in my 50-odd vertex case.
• Attempt to use the GNU Scientific Library's simulated annealing functions for the same purpose. In my tests this did not work at all even in trivial examples.
• Generate graphivz output useful for debugging. (The plag-mangler planar library can perhaps be made to generate better graphviz output by writing suitable utility code.)
• Visual display of optimisation progress using a PyQt program.

Current limitations (contributions very welcome!)

• Handles only connected graphs. Furthermore cannot even check whether the input graph is connected.
• Hideously awful command line interface.
• Missing documentation, notably command line usage, library API, and layout optimiser usage.
• Data model does not support general key/value vertex/edge/face properties; everything I wanted I hardcoded in.
• No way to specify cost function parameters etc. on the command line or in a config file - they are baked in. See optimise.rs.
• No function to compute a planar embedding; you must provide one. (It would probably be possible to add a call to Boost's planarity test and planar embedding code.) OTOH in many applications you wanted a specific embedding anyway so then you have to specify it.
• IME graph structures which are valid graphs but which do not meet the algorithmm's preconditions can sometimes cause Boost graph algorithms to segfault. We would inherit bugs of this kind.
• Error reporting is clumsy and uninformative.

Dependencies

• You will need, installed in the appropriate system paths:
  • boost
  • nlopt [1]
• You will need the following Rust crates which are not even in Debian buster:
  • rc-dlist-deque
  • nlopt (the Rust bindings for nlopt) [2]
• The use of GSL (both the C library, and the Rust glue crate) is optional. The GSL code did not work for me but I am loathe to delete it in case someone has a use for it.

[1] I used a version of nlopt which at the time of writing was not yet in Debian. The issue requesting the new upstream is here https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=923037 and also contains my own ad-hoc git branch of nlopt.

[2] You probably need 0.4.0 of the rust-nlopt library. In any case you need this bugfix: https://github.com/jesskfullwood/rust-nlopt/pull/1

Instructions

Run make to build. (The build is done by having make run cargo, rather than the other way around.)

That generates the utility program target/{release,debug}/plag-mangler

You will need to make a .plag file somehow. There are some in the examples directory. There is file format documentation.

You will have to infer the command line syntax from reading src/main.rs. Broadly speaking it is a sequence of verbs in CAPS with parameters for filenames etc.

To run the layout optimiser, you will want the release build as the debug build will probably be too slow on nontrivial graphs. Visual debugging of the optimiser is possible with qtdebug/vtrace. See the top of that script for an example rune.

Licence

plag-mangler as a whole is:

• Copyright (C) 2019 Ian Jackson
• Copyright (C) 2007 Aaron Windsor

plag-mangler is free software: you can redistribute it and/or modify it under the terms of the GNU Affero General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more details.

You should have received a copy of the GNU Affero General Public License along with this program. If not, see <http://www.gnu.org/licenses/>.

Within the source code is a file derived from a Boost example file which was distributed under the Boost Software License, Version 1.0. See boost/glue.cpp for its original licence grant and warranty disclaimer.

When you build plag-mangler, the resulting binaries will also contain code from nlopt (variously MIT/LGPL-2.1+/BSD-3-clause/GPL-3+), nlopt-rust (MIT), Rust crates libc, arrayvec and nodrop (MIT), Rust rc-dlist-deque (AGPLv3+) and maybe also GSL, rust-GSL (GPLv3+) and c_vec (dual Apache-2.0/MIT). The resulting licence is AGPLv3+ and you must comply with the AGPLv3+ for the whole program, so possibly you will have to release modified versios of any of these (and other) dependencies, and also of anything you build around plag-mangler.