Layered layout

/**
 * Laying out a directed graph in layers, so that it reads in one direction: a
 * flow, a pipeline, the dependencies of a build. Each node is given a layer
 * such that its edges point onward; within a layer the nodes are put in the
 * order that crosses the fewest edges; and each is placed, as nearly as its
 * neighbours allow, in line with what it is connected to.
 *
 * Four passes, each linear in the nodes and edges for a fixed number of sweeps:
 *
 * 1. **Direction.** An edge that closes a cycle is taken backwards, and said to
 *    be: a cycle cannot read one way, so one of its edges is drawn against it.
 * 2. **Layers.** A node's layer is one more than the furthest of the nodes that
 *    lead to it — the longest path from a source.
 * 3. **Order.** Sweeping forth and back, each layer is put in the order of the
 *    average place of its neighbours in the layer before: the barycentre
 *    heuristic, which does not always find the fewest crossings but finds few.
 * 4. **Places.** Layers are spaced by their thickest node; within a layer, nodes
 *    are drawn toward the middle of their neighbours without changing order or
 *    coming closer than the gap.
 *
 * Everything is typed arrays indexed by node: nothing is allocated per node or
 * per edge beyond them, and the same graph always gives the same layout.
 */
import type { Graph } from "./topological.ts";

export interface LayeredOptions {
  /** The room between one layer and the next, and between neighbours in a layer. */
  readonly layerGap?: number;
  readonly nodeGap?: number;
  /** Which way the layers run: across the page, or down it. */
  readonly direction?: "right" | "down";
  /** How many times the order and the places are swept forth and back. */
  readonly sweeps?: number;
}

export interface LayeredLayout {
  /** Each node's top-left corner. */
  readonly x: Float64Array;
  readonly y: Float64Array;
  /** Each node's layer, from 0. */
  readonly layer: Int32Array;
  /**
   * For each edge, in the order the graph holds them, whether it is drawn
   * against its direction: an edge that closed a cycle.
   */
  readonly reversed: Uint8Array;
  /** The size of the whole: every node lies within `[0, width] × [0, height]`. */
  readonly width: number;
  readonly height: number;
}

/**
 * The layout of `graph`, whose node `n` is `sizes[2n]` wide and `sizes[2n + 1]`
 * tall.
 */
export function layeredLayout(
  graph: Graph,
  sizes: ArrayLike<number>,
  { layerGap = 64, nodeGap = 24, direction = "right", sweeps = 4 }: LayeredOptions = {},
): LayeredLayout {
  const { offsets, targets } = graph;
  const count = offsets.length - 1;
  const edgeCount = targets.length;
  if (sizes.length !== count * 2) {
    throw new RangeError(
      `Sizes are a width and a height for each of ${count} nodes, not ${sizes.length} numbers.`,
    );
  }
  const reversed = new Uint8Array(edgeCount);
  const layer = new Int32Array(count);
  const x = new Float64Array(count);
  const y = new Float64Array(count);
  if (count === 0) return { x, y, layer, reversed, width: 0, height: 0 };

  // 1. Direction: a depth-first walk; an edge to a node still being walked closes a cycle.
  const state = new Uint8Array(count); // 0 unseen, 1 on the walk, 2 done
  const stack = new Int32Array(count);
  const cursor = offsets.slice(0, count);
  // The nodes in the order their walks finished, backwards: sources first.
  const order = new Int32Array(count);
  let placed = count;
  for (let root = 0; root < count; root += 1) {
    if (state[root] !== 0) continue;
    let depth = 0;
    stack[0] = root;
    state[root] = 1;
    while (depth >= 0) {
      const node = stack[depth]!;
      const edge = cursor[node]!;
      if (edge < offsets[node + 1]!) {
        cursor[node] = edge + 1;
        const to = targets[edge]!;
        if (state[to] === 1) reversed[edge] = 1;
        else if (state[to] === 0) {
          state[to] = 1;
          depth += 1;
          stack[depth] = to;
        }
      } else {
        state[node] = 2;
        placed -= 1;
        order[placed] = node;
        depth -= 1;
      }
    }
  }

  // 2. Layers: the longest path from a source, over the edges as they now run.
  // `order` has every node after those that lead to it, except by a reversed edge.
  let layers = 0;
  for (let index = 0; index < count; index += 1) {
    const node = order[index]!;
    for (let edge = offsets[node]!; edge < offsets[node + 1]!; edge += 1) {
      const to = targets[edge]!;
      // A reversed edge is not followed — and an edge from a node to itself is one: it leads nowhere.
      if (reversed[edge] === 1) continue;
      if (layer[to]! < layer[node]! + 1) layer[to] = layer[node]! + 1;
    }
    if (layer[node]! + 1 > layers) layers = layer[node]! + 1;
  }
  // A reversed edge needs no more: its source was reached from its target by
  // edges that run forward, so it already lies in a later layer.

  // The nodes of each layer, side by side in one array: layer `l` is `rank[starts[l] … starts[l + 1])`.
  const starts = new Int32Array(layers + 1);
  for (let node = 0; node < count; node += 1) starts[layer[node]! + 1]! += 1;
  for (let l = 0; l < layers; l += 1) starts[l + 1]! += starts[l]!;
  const rank = new Int32Array(count);
  const fill = starts.slice(0, layers);
  // In the order of the walk, so that what is connected starts out together.
  for (let index = 0; index < count; index += 1) {
    const node = order[index]!;
    rank[fill[layer[node]!]!] = node;
    fill[layer[node]!]! += 1;
  }
  // Where each node is in its layer, as a number that can be averaged.
  const place = new Float64Array(count);
  const setPlaces = (l: number) => {
    for (let at = starts[l]!; at < starts[l + 1]!; at += 1) place[rank[at]!] = at - starts[l]!;
  };
  for (let l = 0; l < layers; l += 1) setPlaces(l);

  // The edges the other way about, for the neighbours that lead to a node.
  const inOffsets = new Int32Array(count + 1);
  for (let edge = 0; edge < edgeCount; edge += 1) inOffsets[targets[edge]! + 1]! += 1;
  for (let node = 0; node < count; node += 1) inOffsets[node + 1]! += inOffsets[node]!;
  const sources = new Int32Array(edgeCount);
  const inFill = inOffsets.slice(0, count);
  for (let node = 0; node < count; node += 1) {
    for (let edge = offsets[node]!; edge < offsets[node + 1]!; edge += 1) {
      const to = targets[edge]!;
      sources[inFill[to]!] = node;
      inFill[to]! += 1;
    }
  }

  const key = new Float64Array(count);
  const slots = new Int32Array(count);
  const movers = new Int32Array(count);
  /** The average of `of` over a node's neighbours in earlier layers (`side` −1) or later (`side` 1); `NaN` for none. */
  const mean = (node: number, side: 1 | -1, of: Float64Array): number => {
    let sum = 0;
    let found = 0;
    const own = layer[node]!;
    for (let edge = offsets[node]!; edge < offsets[node + 1]!; edge += 1) {
      const other = targets[edge]!;
      if ((layer[other]! - own) * side > 0) {
        sum += of[other]!;
        found += 1;
      }
    }
    for (let edge = inOffsets[node]!; edge < inOffsets[node + 1]!; edge += 1) {
      const other = sources[edge]!;
      if ((layer[other]! - own) * side > 0) {
        sum += of[other]!;
        found += 1;
      }
    }
    return found === 0 ? Number.NaN : sum / found;
  };

  // 3. Order: each layer by the average place of its neighbours on the side the sweep came from.
  for (let sweep = 0; sweep < sweeps; sweep += 1) {
    const side: 1 | -1 = sweep % 2 === 0 ? -1 : 1;
    for (let step = 1; step < layers; step += 1) {
      const l = side === -1 ? step : layers - 1 - step;
      const from = starts[l]!;
      const to = starts[l + 1]!;
      // A node with no neighbour that side has nothing to say where it goes: it
      // keeps its slot, and the rest are put in order among the slots they held.
      let moving = 0;
      for (let at = from; at < to; at += 1) {
        const node = rank[at]!;
        const average = mean(node, side, place);
        if (Number.isNaN(average)) continue;
        key[node] = average;
        slots[moving] = at;
        movers[moving] = node;
        moving += 1;
      }
      // An insertion sort: layers are short, nearly in order after the first sweep, and it is stable.
      for (let at = 1; at < moving; at += 1) {
        const node = movers[at]!;
        let slot = at;
        while (slot > 0 && key[movers[slot - 1]!]! > key[node]!) {
          movers[slot] = movers[slot - 1]!;
          slot -= 1;
        }
        movers[slot] = node;
      }
      for (let at = 0; at < moving; at += 1) rank[slots[at]!] = movers[at]!;
      setPlaces(l);
    }
  }

  // 4. Places. Along the layers' direction a node is `main` long; across it, `cross`.
  const down = direction === "down";
  const main = (node: number) => sizes[node * 2 + (down ? 1 : 0)]!;
  const cross = (node: number) => sizes[node * 2 + (down ? 0 : 1)]!;
  const along = down ? y : x;
  const across = down ? x : y;

  let offset = 0;
  for (let l = 0; l < layers; l += 1) {
    let thickest = 0;
    for (let at = starts[l]!; at < starts[l + 1]!; at += 1) thickest = Math.max(thickest, main(rank[at]!));
    // Each node in the middle of its layer's thickness.
    for (let at = starts[l]!; at < starts[l + 1]!; at += 1) {
      const node = rank[at]!;
      along[node] = offset + (thickest - main(node)) / 2;
    }
    offset += thickest + (l === layers - 1 ? 0 : layerGap);
  }
  const length = offset;

  // Across: the middle of each node. First packed, each layer centred on zero.
  const centre = new Float64Array(count);
  const onward = new Float64Array(count);
  for (let l = 0; l < layers; l += 1) {
    let at = starts[l]!;
    let edge = 0;
    for (; at < starts[l + 1]!; at += 1) {
      const node = rank[at]!;
      centre[node] = edge + cross(node) / 2;
      edge += cross(node) + nodeGap;
    }
    const shift = (edge - nodeGap) / 2;
    for (at = starts[l]!; at < starts[l + 1]!; at += 1) centre[rank[at]!]! -= shift;
  }
  // Then each drawn toward the middle of its neighbours, and the layer put back
  // in order with its gaps.
  for (let sweep = 0; sweep < sweeps * 2; sweep += 1) {
    const side: 1 | -1 = sweep % 2 === 0 ? -1 : 1;
    for (let step = 1; step < layers; step += 1) {
      const l = side === -1 ? step : layers - 1 - step;
      const from = starts[l]!;
      const to = starts[l + 1]!;
      for (let at = from; at < to; at += 1) {
        const node = rank[at]!;
        const average = mean(node, side, centre);
        key[node] = Number.isNaN(average) ? centre[node]! : average;
      }
      // Kept in order with the gap between, twice: once pushed onward from the
      // start, once pushed back from the end. Each is a layout that holds; so is
      // their average, which leans neither way.
      for (let at = from; at < to; at += 1) {
        const node = rank[at]!;
        let wanted = key[node]!;
        if (at > from) {
          const before = rank[at - 1]!;
          wanted = Math.max(wanted, onward[before]! + cross(before) / 2 + nodeGap + cross(node) / 2);
        }
        onward[node] = wanted;
      }
      for (let at = to - 1; at >= from; at -= 1) {
        const node = rank[at]!;
        let wanted = key[node]!;
        if (at < to - 1) {
          const after = rank[at + 1]!;
          wanted = Math.min(
            wanted,
            centre[after]! * 2 - onward[after]! - cross(after) / 2 - nodeGap - cross(node) / 2,
          );
        }
        // `centre` holds the average; the place pushed back is twice it less the place pushed onward.
        centre[node] = (onward[node]! + wanted) / 2;
      }
    }
  }

  let least = Infinity;
  let most = -Infinity;
  for (let node = 0; node < count; node += 1) {
    least = Math.min(least, centre[node]! - cross(node) / 2);
    most = Math.max(most, centre[node]! + cross(node) / 2);
  }
  for (let node = 0; node < count; node += 1) across[node] = centre[node]! - cross(node) / 2 - least;
  const breadth = most - least;

  return {
    x,
    y,
    layer,
    reversed,
    width: down ? breadth : length,
    height: down ? length : breadth,
  };
}