Genetic Algorithm Graph Layout — single-chain graphs
Genetic algorithms provide an expressive, but slow, way to automatically lay out a graph. They suffer when the number of nodes are high (though there are powerful workarounds for certain graph topologies) but they are extremely good when resolution of multiple constraints is required over a small number of nodes and arcs — a common scenario for business-meaningful graphs.
>This example employs a genetic algorithm to lay out a single-chain graph — i.e. a graph in which the nodes form a simple unbranching sequence from start to end. While this use case sounds trivial, and doesn’t arise very often (because it’s usually possible to just position the nodes in a straight line), it’s actually a very good test for a layout algorithm.
Settings:
Data:
The genetic algorithm, in this case, is set up to:
- Force the start and end nodes to be at the left and right edges of the diagram.
- Snap all node locations to a grid
- Prefer layouts that keep the nodes vertically positioned more or less in the middle of the diagram
- Optionally, prefer the clump the nodes on the left or right side of the diagram.
Within these constraints, the challenge the algorithm faces is to find a compact arrangement of nodes that connects the two sides of the diagram
with a non-crossing path. I find that the pleasantness of the result, or lack of it, offers some insight into the metaparameters of the genetic algorithm.
While single-chain graphs aren’t usually interesting by themselves, a number of problems in the layout of complex graphs become easier if there is a way to
lay out a single-chain graph to fill a specific space.
