Graphs

/**
 * A graph as data: nodes that have ports, and edges that join one port to
 * another — a flow, a pipeline, a diagram. Everything here works on ids and
 * values, never on elements: what may be connected, what a change is and how it
 * is undone, and where a layout would put things.
 *
 * - **Ports say what they accept.** A port may only give (`out`) or only take
 *   (`in`), carry a `type` that must match the other end's, and hold at most so
 *   many edges. A connection that breaks a rule is refused, with the reason.
 *   An edge always runs from a port that gives to one that takes, whichever it
 *   was drawn from.
 * - **Changes are values.** Putting in, taking out, moving and replacing are
 *   each a value that can be applied, and turned about to undo it. Taking a
 *   node out takes its edges out in the same change, so that one undo brings
 *   both back.
 * - **Layout is a change too.** `autoLayout` gives the moves that would lay
 *   the graph out in layers; applying them is the owner's choice. Run after
 *   every change (`keepLaidOut`), placement is live: it follows the graph.
 * - **A pinned node stays where it is.** No layout moves a node that is pinned
 *   or locked, and what a layout does move is put clear of it. A node moved by
 *   hand while the layout is live becomes pinned: the hand is believed.
 */
import type { Rect } from "../algorithms/geometry.ts";
import { rectsEqual } from "../algorithms/geometry.ts";
import { layeredLayout } from "../algorithms/layered-layout.ts";
import type { LayeredOptions } from "../algorithms/layered-layout.ts";
import { affectedBy, graphFrom } from "../algorithms/topological.ts";

export type PortSide = "left" | "right" | "top" | "bottom";

export interface GraphPort {
  readonly id: string;
  /** The side of its node it sits on, and so the way an edge leaves it. */
  readonly side: PortSide;
  /** Whether edges only arrive here, or only leave. Left out, either. */
  readonly direction?: "in" | "out" | undefined;
  /** What it carries. Two ports that each say, and say differently, are not connected. */
  readonly type?: string | undefined;
  /** The most edges it holds. */
  readonly limit?: number | undefined;
  /** Where along its side it sits, from 0 to 1. Left out, the ports of a side share it evenly. */
  readonly at?: number | undefined;
}

export interface GraphNode {
  readonly id: string;
  readonly rect: Rect;
  readonly ports: readonly GraphPort[];
  /** Held where it is against any layout; still moved by hand. */
  readonly pinned?: boolean | undefined;
  /** Held against everything. */
  readonly locked?: boolean | undefined;
}

/** A port, named by its node and itself. */
export interface PortRef {
  readonly node: string;
  readonly port: string;
}

export interface GraphEdge {
  readonly id: string;
  /** The port it leaves, and the port it arrives at. */
  readonly source: PortRef;
  readonly target: PortRef;
  /** What it says of itself — what it carries, when it runs — shown along it. */
  readonly label?: string | undefined;
}

export interface GraphData<N extends GraphNode = GraphNode, E extends GraphEdge = GraphEdge> {
  readonly nodes: readonly N[];
  readonly edges: readonly E[];
}

/** A port as one string, for an attribute or a key; `portRef` reads it back. */
export function portKey(ref: PortRef): string {
  return `${encodeURIComponent(ref.node)}/${encodeURIComponent(ref.port)}`;
}

export function portRef(key: string): PortRef {
  const slash = key.indexOf("/");
  return { node: decodeURIComponent(key.slice(0, slash)), port: decodeURIComponent(key.slice(slash + 1)) };
}

export function samePort(a: PortRef, b: PortRef): boolean {
  return a.node === b.node && a.port === b.port;
}

/** The port a reference names, with its node; `null` when either is not there. */
export function findPort<N extends GraphNode>(
  graph: GraphData<N>,
  ref: PortRef,
): { readonly node: N; readonly port: GraphPort } | null {
  const node = graph.nodes.find((each) => each.id === ref.node);
  const port = node?.ports.find((each) => each.id === ref.port);
  return node === undefined || port === undefined ? null : { node, port };
}

/**
 * Where a port is on the plane — or on `rect`, where its node is shown elsewhere
 * for a while — on its side of its node, at its own place along
 * it, or sharing the side evenly with the others there.
 */
export function portPoint(
  node: GraphNode,
  portId: string,
  rect: Rect = node.rect,
): { x: number; y: number; side: PortSide } | null {
  const port = node.ports.find((each) => each.id === portId);
  if (port === undefined) return null;
  let along = port.at;
  if (along === undefined) {
    const beside = node.ports.filter((each) => each.side === port.side);
    along = (beside.indexOf(port) + 1) / (beside.length + 1);
  }
  const { x, y, width, height } = rect;
  switch (port.side) {
    case "left":
      return { x, y: y + height * along, side: port.side };
    case "right":
      return { x: x + width, y: y + height * along, side: port.side };
    case "top":
      return { x: x + width * along, y, side: port.side };
    case "bottom":
      return { x: x + width * along, y: y + height, side: port.side };
  }
}

/** The edges at a node, or at one of its ports: those that arrive, and those that leave. */
export function edgesAt<E extends GraphEdge>(
  graph: GraphData<GraphNode, E>,
  node: string,
  port?: string,
): { readonly incoming: E[]; readonly outgoing: E[] } {
  const at = (ref: PortRef) => ref.node === node && (port === undefined || ref.port === port);
  return {
    incoming: graph.edges.filter((edge) => at(edge.target)),
    outgoing: graph.edges.filter((edge) => at(edge.source)),
  };
}

/** Why two ports may not be connected. */
export type Refusal = "missing" | "same-node" | "direction" | "type" | "duplicate" | "full" | "cycle";

export interface ConnectRules {
  /** Refuse an edge that would close a cycle. */
  readonly acyclic?: boolean | undefined;
  /** Allow an edge from a node to itself. */
  readonly selfLoops?: boolean | undefined;
  /** An edge being moved to another port: it is not counted against a limit, nor as a duplicate. */
  readonly replacing?: string | undefined;
  /** A further rule of the application's own, asked last: whether this source may feed this target. */
  readonly accepts?: ((source: GraphPort, target: GraphPort) => boolean) | undefined;
}

/**
 * Which of two ports an edge between them leaves: the one that only gives, or
 * the other of one that only takes; where neither says, the first. `null` when
 * both only give, or both only take.
 */
export function orient(
  from: PortRef,
  fromPort: GraphPort,
  to: PortRef,
  toPort: GraphPort,
): { readonly source: PortRef; readonly target: PortRef } | null {
  const a = fromPort.direction;
  const b = toPort.direction;
  if (a !== undefined && a === b) return null;
  return a === "in" || b === "out" ? { source: to, target: from } : { source: from, target: to };
}

/** What a question about connecting from one port is asked against, worked out once. */
interface Asking {
  readonly from: PortRef;
  readonly fromPort: GraphPort;
  readonly held: ReadonlyMap<string, number>;
  readonly joined: ReadonlySet<string>;
  /** The nodes that lead to the one asked from, and those it leads to; `null` where cycles are allowed. */
  readonly before: ReadonlySet<string> | null;
  readonly after: ReadonlySet<string> | null;
}

function reach(nodes: readonly GraphNode[], pairs: number[], from: number): Set<string> {
  const graph = graphFrom(nodes.length, pairs);
  // Any order serves: only which nodes are reached is read.
  const order = Int32Array.from({ length: nodes.length }, (_, index) => index);
  return new Set(Array.from(affectedBy(graph, order, [from]), (index) => nodes[index]!.id));
}

function ask(graph: GraphData, from: PortRef, rules: ConnectRules): Asking | null {
  const found = findPort(graph, from);
  if (found === null) return null;
  const held = new Map<string, number>();
  const joined = new Set<string>();
  for (const edge of graph.edges) {
    if (edge.id === rules.replacing) continue;
    for (const end of [edge.source, edge.target]) {
      const key = portKey(end);
      held.set(key, (held.get(key) ?? 0) + 1);
    }
    joined.add(`${portKey(edge.source)} ${portKey(edge.target)}`);
  }
  let before: Set<string> | null = null;
  let after: Set<string> | null = null;
  if (rules.acyclic === true) {
    const index = new Map(graph.nodes.map((node, at) => [node.id, at]));
    const onward: number[] = [];
    const back: number[] = [];
    for (const edge of graph.edges) {
      const source = index.get(edge.source.node);
      const target = index.get(edge.target.node);
      if (edge.id === rules.replacing || source === undefined || target === undefined) continue;
      onward.push(source, target);
      back.push(target, source);
    }
    const start = index.get(from.node)!;
    after = reach(graph.nodes, onward, start);
    before = reach(graph.nodes, back, start);
  }
  return { from, fromPort: found.port, held, joined, before, after };
}

function judge(graph: GraphData, asking: Asking, to: PortRef, rules: ConnectRules): Refusal | null {
  const found = findPort(graph, to);
  if (found === null) return "missing";
  const { from, fromPort } = asking;
  if (from.node === to.node && (rules.selfLoops !== true || from.port === to.port)) return "same-node";
  const way = orient(from, fromPort, to, found.port);
  if (way === null) return "direction";
  const outward = way.source === from;
  const source = outward ? fromPort : found.port;
  const target = outward ? found.port : fromPort;
  if (source.type !== undefined && target.type !== undefined && source.type !== target.type) return "type";
  if (asking.joined.has(`${portKey(way.source)} ${portKey(way.target)}`)) return "duplicate";
  for (const [ref, port] of [
    [from, fromPort],
    [to, found.port],
  ] as const) {
    if (port.limit !== undefined && (asking.held.get(portKey(ref)) ?? 0) >= port.limit) return "full";
  }
  // An edge onward closes a cycle when its target already leads back; an edge back, when its source is already led to.
  const closes = outward ? asking.before : asking.after;
  if (closes !== null && closes.has(to.node)) return "cycle";
  if (rules.accepts !== undefined && !rules.accepts(source, target)) return "type";
  return null;
}

/** Why an edge between two ports is refused, or `null` when it may be made. */
export function refusal(
  graph: GraphData,
  from: PortRef,
  to: PortRef,
  rules: ConnectRules = {},
): Refusal | null {
  const asking = ask(graph, from, rules);
  return asking === null ? "missing" : judge(graph, asking, to, rules);
}

/** Every port an edge from `from` may be taken to, in the order of the nodes and of their ports. */
export function connectable(graph: GraphData, from: PortRef, rules: ConnectRules = {}): PortRef[] {
  const asking = ask(graph, from, rules);
  if (asking === null) return [];
  const found: PortRef[] = [];
  for (const node of graph.nodes) {
    for (const port of node.ports) {
      const to = { node: node.id, port: port.id };
      if (judge(graph, asking, to, rules) === null) found.push(to);
    }
  }
  return found;
}

/** Something at its place in a list: the place it was taken from, or is put back at. */
export interface Placed<T> {
  readonly at: number;
  readonly item: T;
}

/** Something that took another's place: the same id, another value. */
export interface Replaced<T> {
  readonly item: T;
  readonly previous: T;
}

/** A node's move: which, where it is now, and where it was. */
export interface GraphMove {
  readonly id: string;
  readonly rect: Rect;
  readonly previous: Rect;
}

export type GraphChange<N extends GraphNode = GraphNode, E extends GraphEdge = GraphEdge> =
  | {
      readonly kind: "insert" | "remove";
      /** In the order of their places: for a removal, each place as it was before any was taken. */
      readonly nodes: ReadonlyArray<Placed<N>>;
      readonly edges: ReadonlyArray<Placed<E>>;
    }
  | { readonly kind: "move"; readonly moves: readonly GraphMove[] }
  | {
      readonly kind: "replace";
      readonly nodes: ReadonlyArray<Replaced<N>>;
      readonly edges: ReadonlyArray<Replaced<E>>;
    };

function putIn<T>(list: readonly T[], placed: ReadonlyArray<Placed<T>>): readonly T[] {
  if (placed.length === 0) return list;
  const next = list.slice();
  for (const { at, item } of placed) next.splice(Math.min(Math.max(at, 0), next.length), 0, item);
  return next;
}

function takeOut<T extends { readonly id: string }>(
  list: readonly T[],
  placed: ReadonlyArray<Placed<T>>,
): readonly T[] {
  if (placed.length === 0) return list;
  const going = new Set(placed.map((each) => each.item.id));
  const next = list.filter((each) => !going.has(each.id));
  return next.length === list.length ? list : next;
}

function swap<T extends { readonly id: string }>(
  list: readonly T[],
  replaced: ReadonlyArray<Replaced<T>>,
): readonly T[] {
  if (replaced.length === 0) return list;
  const by = new Map(replaced.map(({ item }) => [item.id, item]));
  let changed = false;
  const next = list.map((each) => {
    const item = by.get(each.id);
    if (item === undefined || item === each) return each;
    changed = true;
    return item;
  });
  return changed ? next : list;
}

/** The graph after a change. What the change does not touch is the same objects; a change that changes nothing gives the same graph. */
export function applyGraphChange<N extends GraphNode, E extends GraphEdge>(
  graph: GraphData<N, E>,
  change: GraphChange<N, E>,
): GraphData<N, E> {
  let { nodes, edges } = graph;
  switch (change.kind) {
    case "insert":
      nodes = putIn(nodes, change.nodes);
      edges = putIn(edges, change.edges);
      break;
    case "remove":
      nodes = takeOut(nodes, change.nodes);
      edges = takeOut(edges, change.edges);
      break;
    case "replace":
      nodes = swap(nodes, change.nodes);
      edges = swap(edges, change.edges);
      break;
    case "move": {
      const rects = new Map(change.moves.map((move) => [move.id, move.rect]));
      let changed = false;
      const next = nodes.map((node) => {
        const rect = rects.get(node.id);
        if (rect === undefined || rectsEqual(rect, node.rect)) return node;
        changed = true;
        return { ...node, rect };
      });
      if (changed) nodes = next;
      break;
    }
  }
  return nodes === graph.nodes && edges === graph.edges ? graph : { ...graph, nodes, edges };
}

export function applyGraphChanges<N extends GraphNode, E extends GraphEdge>(
  graph: GraphData<N, E>,
  changes: ReadonlyArray<GraphChange<N, E>>,
): GraphData<N, E> {
  let next = graph;
  for (const change of changes) next = applyGraphChange(next, change);
  return next;
}

/** The change that puts back what a change did. */
export function invertGraphChange<N extends GraphNode, E extends GraphEdge>(
  change: GraphChange<N, E>,
): GraphChange<N, E> {
  switch (change.kind) {
    case "insert":
      return { ...change, kind: "remove" };
    case "remove":
      return { ...change, kind: "insert" };
    case "move":
      return {
        kind: "move",
        moves: change.moves.map(({ id, rect, previous }) => ({ id, rect: previous, previous: rect })),
      };
    case "replace": {
      const turn = <T>({ item, previous }: Replaced<T>): Replaced<T> => ({ item: previous, previous: item });
      return { kind: "replace", nodes: change.nodes.map(turn), edges: change.edges.map(turn) };
    }
  }
}

/** The changes that undo several, in the order to apply them: all that undo needs. */
export function invertGraphChanges<N extends GraphNode, E extends GraphEdge>(
  changes: ReadonlyArray<GraphChange<N, E>>,
): Array<GraphChange<N, E>> {
  return changes.map(invertGraphChange).toReversed();
}

/** The change that adds nodes and edges, after those there are. */
export function insertion<N extends GraphNode, E extends GraphEdge>(
  graph: GraphData<N, E>,
  nodes: readonly N[],
  edges: readonly E[] = [],
): GraphChange<N, E> {
  return {
    kind: "insert",
    nodes: nodes.map((item, index) => ({ at: graph.nodes.length + index, item })),
    edges: edges.map((item, index) => ({ at: graph.edges.length + index, item })),
  };
}

/**
 * The change that takes out the nodes and edges with the given ids — and, with
 * each node, every edge at it. `null` when none of the ids is in the graph.
 */
export function removal<N extends GraphNode, E extends GraphEdge>(
  graph: GraphData<N, E>,
  ids: Iterable<string>,
): GraphChange<N, E> | null {
  const going = new Set(ids);
  const nodes = graph.nodes.flatMap((item, at) => (going.has(item.id) ? [{ at, item }] : []));
  const gone = new Set(nodes.map((each) => each.item.id));
  const edges = graph.edges.flatMap((item, at) =>
    going.has(item.id) || gone.has(item.source.node) || gone.has(item.target.node) ? [{ at, item }] : [],
  );
  return nodes.length === 0 && edges.length === 0 ? null : { kind: "remove", nodes, edges };
}

/**
 * The change that joins two ports, as the edge `make` gives for its two ends —
 * or the reason it is refused.
 */
export function connection<N extends GraphNode, E extends GraphEdge>(
  graph: GraphData<N, E>,
  from: PortRef,
  to: PortRef,
  make: (source: PortRef, target: PortRef) => E,
  rules: ConnectRules = {},
): GraphChange<N, E> | Refusal {
  const refused = refusal(graph, from, to, rules);
  if (refused !== null) return refused;
  const way = orient(from, findPort(graph, from)!.port, to, findPort(graph, to)!.port)!;
  return insertion(graph, [], [make(way.source, way.target)]);
}

/**
 * The change that moves one end of an edge to another port — or the reason it
 * is refused. `null` when the edge is not there, or already ends there.
 */
export function reconnection<N extends GraphNode, E extends GraphEdge>(
  graph: GraphData<N, E>,
  edgeId: string,
  end: "source" | "target",
  to: PortRef,
  rules: ConnectRules = {},
): GraphChange<N, E> | Refusal | null {
  const previous = graph.edges.find((edge) => edge.id === edgeId);
  if (previous === undefined || samePort(previous[end], to)) return null;
  const kept = end === "source" ? previous.target : previous.source;
  const refused = refusal(graph, kept, to, { ...rules, replacing: edgeId });
  if (refused !== null) return refused;
  const way = orient(kept, findPort(graph, kept)!.port, to, findPort(graph, to)!.port)!;
  return { kind: "replace", nodes: [], edges: [{ item: { ...previous, ...way }, previous }] };
}

/**
 * The changes that put a node into an edge: the edge taken out, and in its place
 * one from the edge's source to a port of the node that takes it, and one from a
 * port of the node that gives to the edge's target — the first of each, in the
 * order of the node's ports. `null` when the node has no such pair, or is at
 * either end of the edge already.
 */
export function splice<N extends GraphNode, E extends GraphEdge>(
  graph: GraphData<N, E>,
  edgeId: string,
  nodeId: string,
  make: (source: PortRef, target: PortRef) => E,
  rules: ConnectRules = {},
): Array<GraphChange<N, E>> | null {
  const at = graph.edges.findIndex((edge) => edge.id === edgeId);
  const edge = graph.edges[at];
  const node = graph.nodes.find((each) => each.id === nodeId);
  if (edge === undefined || node === undefined) return null;
  if (edge.source.node === nodeId || edge.target.node === nodeId) return null;
  const taken: GraphChange<N, E> = { kind: "remove", nodes: [], edges: [{ at, item: edge }] };
  const without = applyGraphChange(graph, taken);
  for (const into of node.ports) {
    const inward = { node: nodeId, port: into.id };
    // Into the node, the way the edge ran: the node's port must take what the source gives.
    if (into.direction === "out" || refusal(without, edge.source, inward, rules) !== null) continue;
    for (const out of node.ports) {
      const outward = { node: nodeId, port: out.id };
      if (out === into || out.direction === "in" || refusal(without, outward, edge.target, rules) !== null) {
        continue;
      }
      return [taken, insertion(without, [], [make(edge.source, inward), make(outward, edge.target)])];
    }
  }
  return null;
}

/** The change that pins nodes where they are, or lets them go. `null` when it would change nothing. */
export function pinning<N extends GraphNode, E extends GraphEdge>(
  graph: GraphData<N, E>,
  ids: Iterable<string>,
  pinned: boolean,
): GraphChange<N, E> | null {
  const which = new Set(ids);
  const nodes = graph.nodes.flatMap((previous) =>
    which.has(previous.id) && (previous.pinned === true) !== pinned
      ? [{ item: { ...previous, pinned }, previous }]
      : [],
  );
  return nodes.length === 0 ? null : { kind: "replace", nodes, edges: [] };
}

export type LayoutOptions = LayeredOptions;

/** Whether a layout leaves a node where it is. */
export const isHeld = (node: GraphNode): boolean => node.pinned === true || node.locked === true;

const SLACK = 1e-6;

/**
 * The moves that lay a graph out in layers (`algorithms/layered-layout.ts`),
 * edges reading one way.
 *
 * - A node that is pinned or locked is not moved.
 * - With none held, the layout's top-left corner is the top-left corner of
 *   where the nodes were: the whole does not jump. With some held, the layout
 *   is placed so that the first of them is exactly where the layout wants it.
 * - A node that is moved is put clear of every held node: where one stands in
 *   its layer's way, it and those after it in the layer are pushed along past
 *   it. So no two nodes overlap, unless both are held.
 * - Laying out what has just been laid out moves nothing.
 */
export function autoLayout(graph: GraphData, options: LayoutOptions = {}): GraphMove[] {
  const { nodes } = graph;
  const count = nodes.length;
  if (count === 0) return [];
  const { layerGap = 64, nodeGap = 24, direction = "right" } = options;
  const index = new Map(nodes.map((node, at) => [node.id, at]));
  const pairs: number[] = [];
  for (const edge of graph.edges) {
    const source = index.get(edge.source.node);
    const target = index.get(edge.target.node);
    if (source !== undefined && target !== undefined) pairs.push(source, target);
  }
  const sizes = new Float64Array(count * 2);
  for (let at = 0; at < count; at += 1) {
    sizes[at * 2] = nodes[at]!.rect.width;
    sizes[at * 2 + 1] = nodes[at]!.rect.height;
  }
  const layout = layeredLayout(graphFrom(count, pairs), sizes, { ...options, layerGap, nodeGap, direction });

  const anchor = nodes.findIndex(isHeld);
  let shiftX = Infinity;
  let shiftY = Infinity;
  if (anchor === -1) {
    for (const node of nodes) {
      shiftX = Math.min(shiftX, node.rect.x);
      shiftY = Math.min(shiftY, node.rect.y);
    }
  } else {
    shiftX = nodes[anchor]!.rect.x - layout.x[anchor]!;
    shiftY = nodes[anchor]!.rect.y - layout.y[anchor]!;
  }

  const down = direction === "down";
  // Along the layers' direction, and across it.
  const alongOf = (rect: Rect) => (down ? rect.y : rect.x);
  const acrossOf = (rect: Rect) => (down ? rect.x : rect.y);
  const lengthOf = (rect: Rect) => (down ? rect.height : rect.width);
  const breadthOf = (rect: Rect) => (down ? rect.width : rect.height);
  const along = down ? layout.y : layout.x;
  const across = down ? layout.x : layout.y;
  const shiftAlong = down ? shiftY : shiftX;
  const shiftAcross = down ? shiftX : shiftY;

  const held: number[] = [];
  const free: number[] = [];
  for (let at = 0; at < count; at += 1) (isHeld(nodes[at]!) ? held : free).push(at);
  // Layer by layer, and within each in the order the layout gave.
  // In place: the array was made here.
  // oxlint-disable-next-line unicorn/no-array-sort
  free.sort((a, b) => layout.layer[a]! - layout.layer[b]! || across[a]! - across[b]! || a - b);

  const moves: GraphMove[] = [];
  let layer = -1;
  let next = -Infinity;
  for (const at of free) {
    const { rect } = nodes[at]!;
    if (layout.layer[at] !== layer) {
      layer = layout.layer[at]!;
      next = -Infinity;
    }
    const from = along[at]! + shiftAlong;
    const length = lengthOf(rect);
    const breadth = breadthOf(rect);
    let place = Math.max(across[at]! + shiftAcross, next);
    // Past every held node in the way, one after another until none is.
    for (let moved = true; moved;) {
      moved = false;
      for (const other of held) {
        const fixed = nodes[other]!.rect;
        if (
          alongOf(fixed) < from + length + layerGap - SLACK &&
          alongOf(fixed) + lengthOf(fixed) > from - layerGap + SLACK &&
          acrossOf(fixed) - nodeGap < place + breadth - SLACK &&
          acrossOf(fixed) + breadthOf(fixed) + nodeGap > place + SLACK
        ) {
          place = acrossOf(fixed) + breadthOf(fixed) + nodeGap;
          moved = true;
        }
      }
    }
    next = place + breadth + nodeGap;
    const placed: Rect = down
      ? { x: place, y: from, width: rect.width, height: rect.height }
      : { x: from, y: place, width: rect.width, height: rect.height };
    if (!rectsEqual(placed, rect)) moves.push({ id: nodes[at]!.id, rect: placed, previous: rect });
  }
  return moves;
}

/**
 * Changes, with the layout kept live after them: what the changes moved by
 * hand is pinned where it was put, and everything not held is laid out again.
 * The result is the changes to make — and to record — as one.
 */
export function keepLaidOut<N extends GraphNode, E extends GraphEdge>(
  graph: GraphData<N, E>,
  changes: ReadonlyArray<GraphChange<N, E>>,
  options: LayoutOptions = {},
): Array<GraphChange<N, E>> {
  const all = [...changes];
  let next = applyGraphChanges(graph, changes);
  const moved = changes.flatMap((change) =>
    change.kind === "move" ? change.moves.map((move) => move.id) : [],
  );
  const pin = pinning(next, moved, true);
  if (pin !== null) {
    all.push(pin);
    next = applyGraphChange(next, pin);
  }
  const moves = autoLayout(next, options);
  if (moves.length > 0) all.push({ kind: "move", moves });
  return all;
}