Interface Decross<NodeDatum, LinkDatum>

a decrossing operator rearranges the nodes in a layer to minimize decrossings.

A decrossing operator takes a array of layered nodes and reorders them. There is no specific requirement on what the final order should be, but for layouts to look good, most decrossing operators should seek to minimize the number of link crossings, among other constraints.

Minimizing the number of link crossings is an NP-Complete problem, so fully minimizing decrossings optimally can be prohibitively expensive, causing javascript to crash or run forever on large dags. In these instances it may be necessary to use an approximate decrossing minimization. You may also have special constraints around the order of nodes that can be expressed with this operator.

const opt = decrossOpt();
const heuristic = decrossTwoLayer();

function decrossFallback(layers: SugiNode[][]): void {
  try {
    opt(layers);
  } catch {
    heuristic(layers);
  }
}
Copy

function customDecross(layers: SugiNode<{ ord: number }, unknown>[][]): void {
    const vals = new Map<SugiNode, number>();
    for (const layer of layers) {
        for (const node of layer) {
            const { data } = node;
            const val = data.role === "node" ? data.node.data.ord ? (data.link.source.data.ord + data.link.target.data.ord) / 2;
            vals.set(node, val);
        }
    }
    for (const layer of layers) {
        layer.sort((a, b) => vals.get(a)! - vals.get(b)!);
    }
}
Copy