Skip to content

AI-native design editor. Open-source Figma alternative.

17.0 KB
Raw Blame
import type { ElkExtendedEdge, ElkNode, ElkPort } from 'elkjs/lib/elk-api'
import { groupBy } from 'es-toolkit'

import type { ConnectorSide } from '@open-pencil/scene-graph/connectors'
import type { Rect, Size, Vector } from '@open-pencil/scene-graph/primitives'

import { layoutWithElk } from './elk'

/**
 * How boxes are arranged, by the ELK algorithm behind each:
 * - `spread` pushes overlapping boxes apart, keeping them near where they were (SPOrE overlap
 *   removal);
 * - `compact` spreads them and then closes the gaps, keeping their relative places (SPOrE
 *   compaction);
 * - `pack` packs them into rows in their order (rectangle packing);
 * - `flow` ranks them along their edges with right-angled routes (layered);
 * - `tree` lays a tree out from its roots (Mr. Tree);
 * - `radial` lays a tree out in rings around its root (radial);
 * - `network` places joined boxes near each other, with no direction (stress).
 */
export type BoxLayout = 'spread' | 'compact' | 'pack' | 'flow' | 'tree' | 'radial' | 'network'

/** The way a flow or a tree runs: top to bottom, bottom to top, left to right, or right to left. */
export type ArrangeDirection = 'TB' | 'BT' | 'LR' | 'RL'

/** A box or group, at the top or inside the group it names. */
export interface ArrangeMember {
  id: string
  group?: string
  /** Where it is now, in the arrangement's axes, which `spread` and `compact` start from. */
  position?: Vector
}

export interface ArrangeBox extends ArrangeMember, Size {}

/** A box around boxes and other groups, sized to hold them. */
export type ArrangeGroup = ArrangeMember

/** An edge between two boxes or groups; its label, by size, gets room along it in a flow. */
export interface ArrangeEdge {
  id: string
  from: string
  to: string
  label?: Size
}

export interface ArrangeInput {
  layout: BoxLayout
  /** For `flow` and `tree`; top to bottom unless given. */
  direction?: ArrangeDirection
  /** Room between boxes; ranks of a flow get half as much again. */
  spacing?: number
  boxes: ArrangeBox[]
  groups: ArrangeGroup[]
  edges: ArrangeEdge[]
}

/** The way a flow's edge runs: the sides it leaves and enters by, and its corners between them. */
export interface ArrangedRoute {
  startSide: ConnectorSide
  endSide: ConnectorSide
  /**
   * From its start, on the middle of `startSide`, to its end, on the middle of `endSide`; empty
   * when only the sides are given.
   */
  points: Vector[]
}

/**
 * Where everything went, in the arrangement's axes. A flow routes its edges, a tree gives only the
 * sides its own edges leave and enter by, and other layouts leave edges to the connectors.
 */
export interface Arrangement {
  boxes: Map<string, Rect>
  groups: Map<string, Rect>
  edges: Map<string, ArrangedRoute>
}

const SPACING = 40
/** Room inside a group around what it holds, and above it for the group's title. */
const GROUP_PADDING = 24
const GROUP_TITLE = 48

const ALGORITHMS: Record<BoxLayout, string> = {
  spread: 'sporeOverlap',
  compact: 'sporeCompaction',
  pack: 'rectpacking',
  flow: 'layered',
  tree: 'mrtree',
  radial: 'radial',
  network: 'stress'
}

const ELK_DIRECTION: Record<ArrangeDirection, string> = {
  TB: 'DOWN',
  BT: 'UP',
  LR: 'RIGHT',
  RL: 'LEFT'
}

/** The side a flow's edges leave a box by, and the side they enter one by. */
const FLOW_SIDES: Record<ArrangeDirection, [ConnectorSide, ConnectorSide]> = {
  TB: ['BOTTOM', 'TOP'],
  BT: ['TOP', 'BOTTOM'],
  LR: ['RIGHT', 'LEFT'],
  RL: ['LEFT', 'RIGHT']
}

const ELK_SIDE: Record<ConnectorSide, string> = {
  TOP: 'NORTH',
  RIGHT: 'EAST',
  BOTTOM: 'SOUTH',
  LEFT: 'WEST'
}

function portId(boxId: string, side: ConnectorSide): string {
  return `${boxId}\u0000${side}`
}

/**
 * A port on the middle of each side a box's edges use, fixed there: connectors attach to side
 * midpoints, so ELK routes every edge to where its connector will meet the box.
 */
function ports(boxId: string, size: Size, sides: ConnectorSide[]): ElkPort[] {
  const at: Record<ConnectorSide, Vector> = {
    TOP: { x: size.width / 2, y: 0 },
    RIGHT: { x: size.width, y: size.height / 2 },
    BOTTOM: { x: size.width / 2, y: size.height },
    LEFT: { x: 0, y: size.height / 2 }
  }
  return sides.map((side) => ({
    id: portId(boxId, side),
    ...at[side],
    width: 0,
    height: 0,
    layoutOptions: { 'elk.port.side': ELK_SIDE[side] }
  }))
}

/** Each box's place in the input: a box's own, a group's that of its first member. */
function inputOrder(input: ArrangeInput): Map<string, number> {
  const order = new Map<string, number>()
  const groupOf = new Map(input.groups.map((group) => [group.id, group.group]))
  for (const [index, box] of input.boxes.entries()) {
    order.set(box.id, index)
    for (let group = box.group; group !== undefined; group = groupOf.get(group)) {
      if (!order.has(group)) order.set(group, index)
    }
  }
  return order
}

/**
 * The edges of a spanning forest of the boxes and groups, taken breadth first from those no edge
 * enters, in the input's order, then from the first still unreached: the tree a tree or radial layout
 * lays out. ELK's radial layout recurses without end on a loop, and a tree reads from its start;
 * the edges left out, such as one looping back, still join their boxes. Only edges within one
 * group count, as these layouts arrange each group on its own.
 */
function treeEdges(input: ArrangeInput): Set<string> {
  // A group laid out around its members is a node of its parent's layout, as a box is.
  const order = inputOrder(input)
  const members = [...input.groups, ...input.boxes].sort(
    (a, b) => (order.get(a.id) ?? 0) - (order.get(b.id) ?? 0)
  )
  const groupOf = new Map(members.map((member) => [member.id, member.group]))
  const edges = input.edges.filter(
    (edge) =>
      edge.from !== edge.to &&
      groupOf.has(edge.from) &&
      groupOf.has(edge.to) &&
      groupOf.get(edge.from) === groupOf.get(edge.to)
  )
  const outgoing = groupBy(edges, (edge) => edge.from)
  const entered = new Set(edges.map((edge) => edge.to))
  const starts = [
    ...members.filter((member) => !entered.has(member.id)),
    ...members.filter((member) => entered.has(member.id))
  ]
  const reached = new Set<string>()
  const tree = new Set<string>()
  for (const start of starts) {
    if (reached.has(start.id)) continue
    reached.add(start.id)
    const queue = [start.id]
    for (let at = queue.shift(); at !== undefined; at = queue.shift()) {
      // An id such as `constructor` must not read a property every object has.
      for (const edge of Object.hasOwn(outgoing, at) ? outgoing[at] : []) {
        if (reached.has(edge.to)) continue
        reached.add(edge.to)
        tree.add(edge.id)
        queue.push(edge.to)
      }
    }
  }
  return tree
}

/** The edges ELK lays out: a tree or radial layout's tree, every edge for the others. */
function laidOutEdges(input: ArrangeInput): ArrangeInput['edges'] {
  if (input.layout !== 'tree' && input.layout !== 'radial') return input.edges
  const tree = treeEdges(input)
  return input.edges.filter((edge) => tree.has(edge.id))
}

/** The layout options of the root and of each group, for the input's layout. */
function layoutOptions(input: ArrangeInput): Record<string, string> {
  const spacing = input.spacing ?? SPACING
  const direction = ELK_DIRECTION[input.direction ?? 'TB']
  const common = {
    'elk.algorithm': ALGORITHMS[input.layout],
    'elk.spacing.nodeNode': String(spacing),
    'elk.spacing.componentComponent': String(spacing),
    'elk.padding': `[top=${GROUP_TITLE},left=${GROUP_PADDING},bottom=${GROUP_PADDING},right=${GROUP_PADDING}]`
  }
  switch (input.layout) {
    case 'flow':
      return {
        ...common,
        'elk.direction': direction,
        'elk.hierarchyHandling': 'INCLUDE_CHILDREN',
        'elk.edgeRouting': 'ORTHOGONAL',
        'elk.layered.spacing.nodeNodeBetweenLayers': String(spacing * 1.5),
        'elk.spacing.edgeNode': '20',
        'elk.spacing.edgeEdge': '12',
        'elk.layered.spacing.edgeNodeBetweenLayers': '20',
        // Flowcharts read from their first node: break cycles along the order they were written
        // in, rather than where ELK's greedy pass would, which can put the start mid-drawing.
        'elk.layered.cycleBreaking.strategy': 'DEPTH_FIRST',
        'elk.layered.considerModelOrder.strategy': 'NODES_AND_EDGES',
        'elk.edgeLabels.placement': 'CENTER'
      }
    case 'tree':
      return {
        ...common,
        'elk.direction': direction,
        'elk.mrtree.spacing.nodeNode': String(spacing)
      }
    case 'network':
      return { ...common, 'elk.stress.desiredEdgeLength': String(spacing * 4) }
    default:
      return common
  }
}

/**
 * SPOrE's importer moves a box whose centre another box already has with an unseeded
 * `Math.random()`, and SPOrE ignores `elk.randomSeed`, so a pile would spread differently on every
 * run (ElkGraphImporter.java, eclipse-elk/elk b715fb1, lines 166-172). Doing that move here,
 * deterministically, means ELK never reaches it. Remove once elkjs seeds it
 * (https://github.com/eclipse-elk/elk/issues/1211). `NUDGE` is the first
 * move's length in pixels.
 */
const NUDGE = 0.5
/** Each further move turns by the golden angle, so the moved centres do not fall on one line. */
const GOLDEN_ANGLE = Math.PI * (3 - Math.sqrt(5))

/** Gives every box in each container, at every level, a centre of its own. */
function separateCentres(container: ElkNode): void {
  const repeats = new Map<string, number>()
  for (const node of container.children ?? []) {
    separateCentres(node)
    const x = (node.x ?? 0) + (node.width ?? 0) / 2
    const y = (node.y ?? 0) + (node.height ?? 0) / 2
    const key = `${x},${y}`
    const repeat = repeats.get(key) ?? 0
    repeats.set(key, repeat + 1)
    if (repeat === 0) continue
    const distance = NUDGE * Math.sqrt(repeat)
    node.x = (node.x ?? 0) + distance * Math.cos(repeat * GOLDEN_ANGLE)
    node.y = (node.y ?? 0) + distance * Math.sin(repeat * GOLDEN_ANGLE)
  }
}

/** The graph ELK lays `input` out from. */
function elkGraph(input: ArrangeInput): ElkNode {
  const root = elkHierarchy(input)
  if (input.layout === 'spread' || input.layout === 'compact') separateCentres(root)
  return root
}

function elkHierarchy(input: ArrangeInput): ElkNode {
  const flow = input.layout === 'flow'
  const [outSide, inSide] = FLOW_SIDES[input.direction ?? 'TB']
  const options = layoutOptions(input)
  const elk = new Map<string, ElkNode>()
  for (const group of input.groups) {
    elk.set(group.id, {
      id: group.id,
      ...group.position,
      children: [],
      edges: [],
      layoutOptions: flow ? { ...options, 'elk.portConstraints': 'FIXED_SIDE' } : options,
      ports: flow
        ? [
            {
              id: portId(group.id, outSide),
              layoutOptions: { 'elk.port.side': ELK_SIDE[outSide] }
            },
            { id: portId(group.id, inSide), layoutOptions: { 'elk.port.side': ELK_SIDE[inSide] } }
          ]
        : []
    })
  }
  for (const box of input.boxes) {
    elk.set(box.id, {
      id: box.id,
      ...box.position,
      width: box.width,
      height: box.height,
      layoutOptions: flow ? { 'elk.portConstraints': 'FIXED_POS' } : {},
      ports: flow ? ports(box.id, box, [outSide, inSide]) : []
    })
  }
  const root: ElkNode = {
    id: '\u0000root',
    layoutOptions: { ...options, 'elk.json.shapeCoords': 'ROOT', 'elk.json.edgeCoords': 'ROOT' },
    children: [],
    edges: []
  }
  const groupOf = new Map(
    [...input.groups, ...input.boxes].map((member) => [member.id, member.group])
  )
  const container = (group: string | undefined) => (group ? elk.get(group) : undefined) ?? root
  // ELK keeps the order it is given, so boxes go in the input's order: a box where it appears, a
  // group where its first member does.
  const order = inputOrder(input)
  const members = [...input.groups, ...input.boxes].sort(
    (a, b) => (order.get(a.id) ?? 0) - (order.get(b.id) ?? 0)
  )
  for (const member of members) {
    const node = elk.get(member.id)
    if (node) container(member.group).children?.push(node)
  }
  for (const edge of laidOutEdges(input)) {
    if (!elk.has(edge.from) || !elk.has(edge.to)) continue
    if (flow) {
      root.edges?.push({
        id: edge.id,
        sources: [portId(edge.from, outSide)],
        targets: [portId(edge.to, inSide)],
        // ELK skips a label without text; only its size matters here.
        labels: edge.label ? [{ text: edge.id, ...edge.label }] : []
      })
      continue
    }
    // Other layouts arrange each group on its own, so an edge counts only between boxes that
    // share one.
    const group = groupOf.get(edge.from)
    if (group !== groupOf.get(edge.to)) continue
    container(group).edges?.push({ id: edge.id, sources: [edge.from], targets: [edge.to] })
  }
  return root
}

function sideOf(point: Vector, box: Rect): ConnectorSide {
  const distances: [ConnectorSide, number][] = [
    ['TOP', Math.abs(point.y - box.y)],
    ['RIGHT', Math.abs(point.x - (box.x + box.width))],
    ['BOTTOM', Math.abs(point.y - (box.y + box.height))],
    ['LEFT', Math.abs(point.x - box.x)]
  ]
  return distances.reduce((best, entry) => (entry[1] < best[1] ? entry : best))[0]
}

function rectOf(node: ElkNode): Rect {
  return { x: node.x ?? 0, y: node.y ?? 0, width: node.width ?? 0, height: node.height ?? 0 }
}

function collect(result: ElkNode, input: ArrangeInput): Arrangement {
  const groupIds = new Set(input.groups.map((group) => group.id))
  const arrangement: Arrangement = { boxes: new Map(), groups: new Map(), edges: new Map() }
  const walk = (node: ElkNode) => {
    for (const child of node.children ?? []) {
      ;(groupIds.has(child.id) ? arrangement.groups : arrangement.boxes).set(
        child.id,
        rectOf(child)
      )
      walk(child)
    }
  }
  walk(result)
  if (input.layout === 'tree') {
    // A tree runs one way, so its own edges leave and enter boxes by the sides a flow would, with
    // the connectors' own elbows between them. An edge outside the tree, such as one looping
    // back up, picks its sides itself rather than running the length of a branch.
    const [startSide, endSide] = FLOW_SIDES[input.direction ?? 'TB']
    const tree = treeEdges(input)
    for (const edge of input.edges) {
      if (tree.has(edge.id) && arrangement.boxes.has(edge.from) && arrangement.boxes.has(edge.to)) {
        arrangement.edges.set(edge.id, { startSide, endSide, points: [] })
      }
    }
    return arrangement
  }
  if (input.layout !== 'flow') return arrangement
  const ends = new Map(input.edges.map((edge) => [edge.id, edge]))
  const placed = new Map([...arrangement.groups, ...arrangement.boxes])
  // ELK may hand an edge back in the group that holds both its ends.
  const edgesOf = (node: ElkNode): ElkExtendedEdge[] => [
    ...(node.edges ?? []),
    ...(node.children ?? []).flatMap(edgesOf)
  ]
  for (const edge of edgesOf(result)) {
    const ended = ends.get(edge.id)
    const from = ended && placed.get(ended.from)
    const to = ended && placed.get(ended.to)
    const points = (edge.sections ?? []).flatMap((section) => [
      section.startPoint,
      ...(section.bendPoints ?? []),
      section.endPoint
    ])
    const first = points.at(0)
    const last = points.at(-1)
    if (!from || !to || !first || !last) continue
    arrangement.edges.set(edge.id, {
      startSide: sideOf(first, from),
      endSide: sideOf(last, to),
      points: points.map(({ x, y }) => ({ x, y }))
    })
  }
  return arrangement
}

/** The input again, each box and group where `result` put it, for a second pass to start from. */
function placedAt(input: ArrangeInput, result: ElkNode): ArrangeInput {
  const positions = new Map<string, Vector>()
  const walk = (node: ElkNode) => {
    for (const child of node.children ?? []) {
      positions.set(child.id, { x: child.x ?? 0, y: child.y ?? 0 })
      walk(child)
    }
  }
  walk(result)
  const at = <Member extends ArrangeMember>(member: Member): Member => ({
    ...member,
    position: positions.get(member.id) ?? member.position
  })
  return { ...input, boxes: input.boxes.map(at), groups: input.groups.map(at) }
}

/**
 * Arranges boxes with ELK in the input's layout: groups around their members, and, in a flow,
 * every edge routed at right angles from the middle of the side it leaves by to the middle of the
 * side it enters by.
 */
export async function arrangeBoxes(input: ArrangeInput): Promise<Arrangement> {
  if (input.layout === 'compact') {
    // Compaction keeps boxes apart only once they are: spread them first.
    const spread = await layoutWithElk(elkGraph({ ...input, layout: 'spread' }))
    const compacted = placedAt(input, spread)
    return collect(await layoutWithElk(elkGraph(compacted)), compacted)
  }
  if (input.layout === 'radial' || input.layout === 'network') {
    // These place boxes by their centres alone, so wide boxes can land on each other: pull them
    // apart afterwards, as a spread does, keeping each near where the layout put it.
    const placed = placedAt(input, await layoutWithElk(elkGraph(input)))
    return collect(await layoutWithElk(elkGraph({ ...placed, layout: 'spread' })), placed)
  }
  return collect(await layoutWithElk(elkGraph(input)), input)
}