Graphs
debt(d7/e5/b5/t5)
Closest to 'only careful code review or runtime testing' (d7). The detection_hints note automated detection is 'no', and the code_pattern describes recognizing a V×V adjacency matrix for a sparse graph or missing graph representation entirely — neither of which any standard linter or SAST tool flags automatically. Only a careful reviewer or profiler catching memory bloat would catch these misuses.
Closest to 'touches multiple files / significant refactor in one component' (e5). The quick_fix suggests switching to adjacency lists, but the common_mistakes include several distinct issues (cycle detection, directed vs undirected semantics, visited sets for BFS/DFS). Correcting all misuses typically requires restructuring the graph representation and adjusting traversal logic across multiple algorithms or components, going beyond a single-line patch.
Closest to 'persistent productivity tax' (b5). The term applies to web and CLI contexts broadly, and choosing the wrong representation (adjacency matrix for sparse graphs) or missing cycle detection imposes ongoing costs — every algorithm built on top of a wrong representation must work around it. However, it doesn't dominate the entire codebase architecture, keeping it below b7.
Closest to 'notable trap (a documented gotcha most devs eventually learn)' (t5). The misconception field explicitly states that developers conflate trees and graphs, treating them as separate concepts when trees are a special case of graphs. Additionally, common mistakes like treating directed edges as undirected and forgetting visited sets in cyclic graphs are well-documented but frequently encountered surprises for developers new to graph algorithms.
Also Known As
TL;DR
Explanation
A graph G = (V, E) has vertices V and edges E. Directed graphs have one-way edges; undirected have two-way. Weighted graphs assign costs to edges. Representations: adjacency matrix (O(V²) space, O(1) edge lookup), adjacency list (O(V+E) space, better for sparse graphs). Cycles: DAGs (Directed Acyclic Graphs) have no cycles — used for dependency resolution (Composer), build systems, and topological sorting. Trees are DAGs with one path between any two nodes.
Common Misconception
Why It Matters
Common Mistakes
- Adjacency matrix for sparse graphs — wastes O(V²) memory when most edges don't exist.
- Not detecting cycles before topological sort — Kahn's algorithm or DFS detects cycles.
- Treating directed edges as undirected — in a dependency graph, A depends on B is not the same as B depends on A.
- Infinite loops without a visited set in BFS/DFS on cyclic graphs.
Code Examples
// Adjacency matrix for sparse social graph — 1M users = 1TB memory:
$matrix = array_fill(0, 1000000, array_fill(0, 1000000, 0));
// 10^12 entries for a graph with ~1 billion edges// Adjacency list — O(V+E) space:
$graph = [
'A' => ['B', 'C'],
'B' => ['D'],
'C' => ['D', 'E'],
'D' => [],
'E' => [],
];
// Only stores actual edges — efficient for sparse graphs
// 5 vertices, 5 edges — exactly 10 entries total