DIGL: JavaScript Directed Graph auto-layout algorithm

A small JavaScript library that allows you to create visual layout of directed graphs (e.g. state machines), with minimum effort. The algorithm/heuristic is loosely based on the workings of GraphViz.

## Getting started

You can configure a layout machine, by using the`layout`

function with a configuration object. This returns a `function`

that can be used to determine the positions of the based, based on a set of `nodes`

, `edges`

, and a starting node.```
import { digl } from '@crinkles/digl';
const machine = digl({ shortestPath: false, addEmptySpots: false });
const edges = [{ source: '1', target: '2' }];
const ranks = machine.get('1', edges);
// [['1'], ['2']]
const score = machine.score('1', edges);
// 0
```

## Configuration

`shortestPath: boolean`

: order nodes in the graph based on the shortest path they are from the root, or the longest path.`addEmptySpots: boolean`

: try to add empty spots in the ranks further optimize the graph.`solitary: string[]`

: an array of node IDs (corresponding to the source/target in the edges) that should be solitary within a rank.

## How it works

The algorithm used is based on the GraphViz, but a simplified version. It consists of several steps:- Place each node in a
*rank*from the starting point, where the starting node is 'rank 0' - Score the graph based on the initial ranks (e.g. based on the number of expected crossing edges)
- Switch nodes within/between ranks, and see if we improve the score of the graph
- If we improved the score, repeat step 3 for a maximum of X iterations, if we did not improve the score, we found a (local) optimum
- Based on the final ranks, determine the positions of each node

A

*rank*is a list of nodes that can be accessed within X steps from the starting node (e.g. rank 1 means 1 step away from the start). Step 3 allows for different implementations (e.g. switching nodes row-based vs. column-based) to find the best (local) result.

### Determine the 'initial ranks'

Step one of the algorithm is to determine the initial ranks of the graph. This is achieved by combining several different techniques, and create an ordered list of ranks.- Get all the paths based on the starting node, using a
*depth-first search*tree-traversal algorithm (note: it ignores already visited nodes within a path to avoid loops). - Use a n algorithm to determine the longest or shortest (based on the config) possible route from the start node, disregarding loops. The length of the found longest route for each node is used as the corresponding
*rank*of the node. - Order all nodes within a rank, based on its occurance in the longest paths, i.e. nodes in longer paths are placed higher in a rank compared to nodes in a shorter path. The resulting ranks are the initial ranks of the algorithm of this package.

```
// get all paths DFS algorithm
function getAllPaths(nodeId, edges, path = [], paths = []) {
const children = edges.filter((e) => e.source === nodeId);
if (path.includes(nodeId) || !children || children.length === 0)
paths.push([...path, nodeId]);
else
children.map((c) => getAllPaths(c.target, edges, [...path, nodeId], paths));
return paths.sort();
}
```

### Score the graph based on its ranks

All 'ranks' can be scored with a number. The represents the number of visual crossing edges a graph based on the ranks will have, plus the amount of edges crossing over a node. Therefore, the lower the score, the better. The scores are determined by:- Counting all edges that have a source and target within a single rank, which are not adjecent to each other in the rank.
- Go through all combinations of ranks, and:

```
// Note this is a part of the logic
let _score = 0;
if (e1.x > e2.x && e1.t < e2.t) _score++;
```

### Optimize the node order in each rank

Improving the ranks to find a local optimum is achieved with the following heuristic:- Copy
`ranks`

into`_ranks`

; - Cycle through each rank of
`_ranks`

with index`i`

; - Within
`_rank[i]`

, cycle through the nodes, with index`j`

, except the last node; - Swap the values of
`_rank[i][j]`

and`_rank[i][j + 1]`

; - Compare the score of the swapped situation with the non-swapped situation;
- If the score
*did not worsen*, apply the swapping to`_ranks`

. Repeat step 1 or 2; - When finished, see of the score of
`_ranks`

is an improvement compared to the score of`ranks`

; - If so, replace
`ranks`

with`_ranks`

and repeat step 1 (for a maximum of 10 times). If not, return`ranks`

.

### Example positioning algorithm

```
export default function positioning(
config: Config,
nodes: Node[],
ranks: Rank[]
): Layout {
const _nodes: PositionedNode[] = [];
const _h = config.orientation === 'horizontal';
ranks.forEach((r, i) => {
const xStart = _h
? 2 * config.width * i
: -0.5 * (r.length - 1) * 2 * config.width;
const yStart = _h
? -0.5 * (r.length - 1) * 2 * config.height
: 2 * config.height * i;
r.forEach((nodeId, nIndex) => {
const _node: Node = nodes.find((n) => n.id == nodeId) as Node;
if (!_node) return;
const x = _h ? xStart : xStart + 2 * config.width * nIndex;
const y = _h ? yStart + 2 * config.height * nIndex : yStart;
_nodes.push({ ..._node, x, y });
});
});
return _nodes;
}
```