MathLab/task-board/frontend/js/layout-engine.js

const DEFAULT_LAYOUT = {
  nodeWidth: 270,
  nodeHeight: 108,
  horizontalGap: 340,
  verticalGap: 138,
  marginX: 180,
  marginY: 120,
};

function safeTime(node) {
  const created = node?.timestamps?.created || node?.createdAt || "";
  return Date.parse(created) || 0;
}

function cmpByTime(a, b) {
  const dt = safeTime(a) - safeTime(b);
  if (dt !== 0) return dt;
  return String(a.id).localeCompare(String(b.id));
}

function createAdjacency(nodes, edges) {
  const byId = new Map(nodes.map((node) => [node.id, node]));
  const outgoing = new Map();
  const incoming = new Map();
  const indegree = new Map();

  for (const node of nodes) {
    outgoing.set(node.id, []);
    incoming.set(node.id, []);
    indegree.set(node.id, 0);
  }

  for (const edge of edges) {
    if (!byId.has(edge.from) || !byId.has(edge.to)) continue;
    outgoing.get(edge.from).push(edge);
    incoming.get(edge.to).push(edge);
    indegree.set(edge.to, (indegree.get(edge.to) || 0) + 1);
  }

  return { byId, outgoing, incoming, indegree };
}

function topologicalOrder(nodes, graph) {
  const queue = nodes
    .filter((node) => (graph.indegree.get(node.id) || 0) === 0)
    .slice()
    .sort(cmpByTime);
  const indegree = new Map(graph.indegree);
  const order = [];

  while (queue.length) {
    const node = queue.shift();
    order.push(node);
    const outgoing = graph.outgoing.get(node.id) || [];
    for (const edge of outgoing) {
      const nextCount = (indegree.get(edge.to) || 0) - 1;
      indegree.set(edge.to, nextCount);
      if (nextCount === 0) {
        queue.push(graph.byId.get(edge.to));
      }
    }
    queue.sort(cmpByTime);
  }

  if (order.length < nodes.length) {
    const seen = new Set(order.map((node) => node.id));
    const fallback = nodes.filter((node) => !seen.has(node.id)).sort(cmpByTime);
    order.push(...fallback);
  }

  return order;
}

function computeLayers(order, graph) {
  const layerById = new Map();
  for (const node of order) {
    const incoming = graph.incoming.get(node.id) || [];
    let layer = 0;
    for (const edge of incoming) {
      const parentLayer = layerById.get(edge.from) || 0;
      layer = Math.max(layer, parentLayer + 1);
    }
    layerById.set(node.id, layer);
  }
  return layerById;
}

function layerBarycenter(node, graph, positions) {
  const incoming = graph.incoming.get(node.id) || [];
  if (!incoming.length) return Number.POSITIVE_INFINITY;
  let sum = 0;
  let count = 0;
  for (const edge of incoming) {
    const pos = positions.get(edge.from);
    if (!pos) continue;
    sum += pos.y;
    count += 1;
  }
  return count ? sum / count : Number.POSITIVE_INFINITY;
}

function computeBounds(positions, layout) {
  if (!positions.size) {
    return { minX: 0, minY: 0, maxX: 0, maxY: 0, width: 0, height: 0 };
  }
  const xs = [];
  const ys = [];
  positions.forEach((pos) => {
    xs.push(pos.x);
    ys.push(pos.y);
  });
  const minX = Math.min(...xs) - layout.nodeWidth / 2 - 60;
  const maxX = Math.max(...xs) + layout.nodeWidth / 2 + 60;
  const minY = Math.min(...ys) - layout.nodeHeight / 2 - 60;
  const maxY = Math.max(...ys) + layout.nodeHeight / 2 + 60;
  return {
    minX,
    minY,
    maxX,
    maxY,
    width: maxX - minX,
    height: maxY - minY,
  };
}

export function computeThoughtChainLayout(graphData, options = {}) {
  const layout = { ...DEFAULT_LAYOUT, ...options };
  const nodes = Array.isArray(graphData?.nodes) ? graphData.nodes.slice() : [];
  const edges = Array.isArray(graphData?.edges) ? graphData.edges.slice() : [];
  if (!nodes.length) {
    return {
      positions: new Map(),
      links: [],
      bounds: { minX: 0, minY: 0, maxX: 0, maxY: 0, width: 0, height: 0 },
      layout,
    };
  }

  const graph = createAdjacency(nodes, edges);
  const order = topologicalOrder(nodes, graph);
  const layerById = computeLayers(order, graph);
  const layers = new Map();

  for (const node of order) {
    const layer = layerById.get(node.id) || 0;
    if (!layers.has(layer)) layers.set(layer, []);
    layers.get(layer).push(node);
  }

  const positions = new Map();
  const layerKeys = Array.from(layers.keys()).sort((a, b) => a - b);
  for (const layer of layerKeys) {
    const layerNodes = layers.get(layer).slice().sort((a, b) => {
      const ba = layerBarycenter(a, graph, positions);
      const bb = layerBarycenter(b, graph, positions);
      if (Number.isFinite(ba) && Number.isFinite(bb) && ba !== bb) return ba - bb;
      if (Number.isFinite(ba) && !Number.isFinite(bb)) return -1;
      if (!Number.isFinite(ba) && Number.isFinite(bb)) return 1;
      return cmpByTime(a, b);
    });

    for (let i = 0; i < layerNodes.length; i += 1) {
      const node = layerNodes[i];
      positions.set(node.id, {
        x: layout.marginX + layer * layout.horizontalGap,
        y: layout.marginY + i * layout.verticalGap,
      });
    }
  }

  const links = edges
    .map((edge) => {
      const from = positions.get(edge.from);
      const to = positions.get(edge.to);
      if (!from || !to) return null;
      const targetNode = graph.byId.get(edge.to);
      return {
        ...edge,
        from,
        to,
        status: targetNode ? targetNode.status : "pending",
      };
    })
    .filter(Boolean);

  return {
    positions,
    links,
    bounds: computeBounds(positions, layout),
    layout,
  };
}