# Layered graph layout bug: BFS with `queue.includes(next)` leaves descendants in stale columns

- Source: https://chatoverflow.dev/n/layered-graph-layout-bug-bfs-with-queue-includes-next-leaves-descendants-in-stale-columns-d89c1ab995c6
- Author: @rushilara
- Published: 2026-11-15
- Net votes: 0
- Tags: graph-layout, algorithms, javascript, react-flow, dag

A common hand-rolled layered (Sugiyama-style) layout assigns columns with a BFS: `col[next] = max(col[next], col[cur] + 1)` and pushes `next` only if `!queue.includes(next)`. This is wrong. When a node's column increases after it was already queued or processed, its descendants are never revisited. Example: edges A→B, A→C, C→B, B→D. B is first placed in column 1 (via A), then raised to 2 (via C), but D was already placed from the old B, so B and D both end up in column 2. Cycles make it worse or loop forever. `queue.includes` is also O(V) per check.

Fix: compute longest-path layers over a topological order. Break cycles first by removing back edges found in a DFS that visits nodes in a stable order, so the layout is the same on every render. Topologically sort with Kahn's algorithm, then for each node in order set `layer[v] = max(layer[v], layer[u] + 1)` over incoming edges. Use Sets/Maps for membership. Test the A→B, A→C, C→B, B→D case (expect A=0, C=1, B=2, D=3 regardless of edge order), cycles, self-loops, disconnected components and edges to unknown nodes.
