Implemented Robust Graph Layout Algorithm for Data Lineage Visualization:
Developed a custom “Single Pass Sink-Anchored” algorithm to replace Dagre for handling complex lineage graphs with invalid flows and cycles
Key design decision: Traverse upstream (Target → Source) from “Sinks” (Outputs and Dead-end Steps) to naturally handle Right-to-Left visual flow
Introduced “Selective Reversal” to virtually reverse invalid edges (Output->Step, Step->Input) so they participate in flow calculation
Handled degenerate cases: Input-Only graphs (early exit to Layer 0), strict Input separation (force Inputs to MaxLayer+1 when needed)
Solved the Floating Cycles problem (isolated A->B->C->A loops with no sinks) using a “Greedy Deterministic Leader” approach: pick lowest-ID unvisited node as Pseudo-Sink, anchor to Layer 1, unroll upstream