Show HN: Xkcd #2347 lived in my head, so I built the dependency tower for real
7 days ago
- #algorithm-design
- #graph-visualization
- #dependency-management
- The author was inspired by an XKCD comic to visualize software dependencies as a tower of blocks, where each block represents a dependency.
- Traditional dependency graphs (like UML or node-link diagrams) are technically correct but lack intuitive visualization.
- The challenge was to render a dependency graph as a stacked tower, ensuring no edge crossings (where dependencies overlap).
- The problem was identified as NP-hard, meaning no known efficient solution exists for all cases.
- The author explored multiple approaches: brute force, PQ-trees (to represent valid permutations), barycenter heuristic (for greedy ordering), and a hybrid heuristic-guided search.
- Key optimizations included transitive reduction (removing redundant edges), edge shortening (breaking long dependencies into steps), and planarity repair (resolving unavoidable tangles).
- The final algorithm combined PQ-trees for constraint-based ordering, barycenter heuristic for initial guesses, and branch-and-bound for efficient search.
- The project was implemented in Go for performance, with parsers for PyPI, crates.io, and npm to fetch real dependency data.
- A 'Nebraska Guy Ranking' was added to highlight critical maintainers deep in the dependency stack.
- The visualization separates layout logic from rendering, allowing for multiple styles (clean and hand-drawn).