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.
import { digl } from '@crinkles/digl';
const edges = [{ source: '1', target: '2' }];
const ranks = digl(edges, { solitary: [] });
// [[['1'], ['2']]]
solitary: string[]
: an array of node IDs (corresponding to the source/target in the edges) that should be solitary within a rank.The algorithm used is based on the GraphViz, but a simplified version. It consists of several steps:
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:
// Note this is a part of the logic
let _score = 0;
if (e1.x > e2.x && e1.t < e2.t) _score++;
const edges: Edge[] = [
{ source: '1', target: '2' },
{ source: '2', target: '3' },
{ source: '2', target: '4' },
{ source: '3', target: '4' },
{ source: '4', target: '5' },
{ source: '5', target: '6' },
{ source: '4', target: '8' },
{ source: '8', target: '5' },
{ source: '3', target: '5' },
{ source: '3', target: '7' },
{ source: '7', target: '9' },
{ source: '9', target: '6' },
{ source: '7', target: '6' },
{ source: '9', target: '10' },
{ source: '10', target: '6' },
];
const result = digl(edges);
// [
// [
// ['1'],
// ['2'],
// ['3'],
// ['4', '7'],
// ['8', '9'],
// ['5', '10'],
// ['6'],
// ]
// ]
const result = digl(edges, { solitary: ['8'] });
// [
// [
// ['1'],
// ['2'],
// ['3'],
// ['4', '7'],
// ['8'],
// ['9'],
// ['5', '10'],
// ['6'],
// ]
// ]
const edges: Edge[] = [
{ source: '1', target: '2' },
{ source: '2', target: '3' },
{ source: '2', target: '4' },
{ source: '1', target: '4' },
{ source: '4', target: '1' },
];
const result = digl(edges);
// [
// [
// ['1'],
// ['2'],
// ['3', '4']
// ]
// ]
const edges: Edge[] = [
{ source: '1', target: '2' },
{ source: '2', target: '3' },
{ source: '2', target: '4' },
{ source: '5', target: '6' },
{ source: '6', target: '7' },
{ source: '6', target: '8' },
];
const result = digl(edges);
// [
// [['1'], ['2'], ['3', '4']],
// [['5'], ['6'], ['7', '8']],
// ]
const edges: Edge[] = [
{ source: '1', target: '2' },
{ source: '2', target: '3' },
{ source: '2', target: '4' },
{ source: '5', target: '6' },
{ source: '6', target: '7' },
{ source: '6', target: '4' },
{ source: '8', target: '9' },
{ source: '9', target: '10' },
{ source: '9', target: '7' },
];
const result = digl(edges);
// [
// [
// ['1', '5', '8'],
// ['2', '6', '9'],
// ['3', '4', '7', '10'],
// ],
// ]
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;
}