russell@unturf.com
db29a08762
B&W print-friendly diagrams + tinkerpop-0001 + wave-3 proof sections. Squash of 94 local commits onto remote master.
74 lines
3.9 KiB
Text
74 lines
3.9 KiB
Text
// Diagram 3: Complexity Comparison — stack.contains(n) vs n.active
|
|
// Shows operation count growth as graph size V increases.
|
|
// Defective: V*(V+1)/2 comparisons for a path graph with back edge.
|
|
// Fixed: 1 comparison per edge regardless of stack depth.
|
|
//
|
|
// Render: dot -Tsvg 0001-stack-scan.dot -o 0001-stack-scan.svg
|
|
|
|
digraph complexity_comparison {
|
|
graph [
|
|
label="Stack Membership Check: O(V²) Defect vs O(1) Fix\nComparisons required when back edge is reached on a path graph of V nodes"
|
|
labelloc=t
|
|
fontsize=13
|
|
fontname="monospace"
|
|
bgcolor="#f8f8f8"
|
|
pad=0.6
|
|
]
|
|
node [fontname="monospace" fontsize=10]
|
|
edge [fontname="monospace" fontsize=9]
|
|
|
|
// ── Defective: stack.contains(n) ────────────────────────────────────────
|
|
subgraph cluster_defect {
|
|
label="DEFECTIVE: stack.contains(n) — GraphUtils.java:186"
|
|
style=filled fillcolor="#fff0f0" color="#cc0000" penwidth=2
|
|
fontcolor="#cc0000"
|
|
|
|
d_v5 [label="V=5\n15 comparisons" shape=rect style=filled fillcolor="#ff9999" height=0.6 width=1.4]
|
|
d_v10 [label="V=10\n55 comparisons" shape=rect style=filled fillcolor="#ff6666" height=1.0 width=1.4]
|
|
d_v50 [label="V=50\n1275 comparisons" shape=rect style=filled fillcolor="#ff3333" height=2.0 width=1.4]
|
|
d_v100[label="V=100\n5050 comparisons" shape=rect style=filled fillcolor="#cc0000" fontcolor=white height=3.0 width=1.4]
|
|
|
|
d_v5 -> d_v10 -> d_v50 -> d_v100 [style=invis]
|
|
|
|
d_label [label="O(V²)\ngrowth" shape=none fontcolor="#cc0000" fontsize=12]
|
|
}
|
|
|
|
// ── Fixed: n.active ─────────────────────────────────────────────────────
|
|
subgraph cluster_fix {
|
|
label="FIXED: n.active — O(1) boolean read"
|
|
style=filled fillcolor="#f0fff0" color="#006600" penwidth=2
|
|
fontcolor="#006600"
|
|
|
|
f_v5 [label="V=5\n1 comparison" shape=rect style=filled fillcolor="#99ff99" height=0.25 width=1.4]
|
|
f_v10 [label="V=10\n1 comparison" shape=rect style=filled fillcolor="#99ff99" height=0.25 width=1.4]
|
|
f_v50 [label="V=50\n1 comparison" shape=rect style=filled fillcolor="#99ff99" height=0.25 width=1.4]
|
|
f_v100[label="V=100\n1 comparison" shape=rect style=filled fillcolor="#99ff99" height=0.25 width=1.4]
|
|
|
|
f_v5 -> f_v10 -> f_v50 -> f_v100 [style=invis]
|
|
|
|
f_label [label="O(1)\nper edge" shape=none fontcolor="#006600" fontsize=12]
|
|
}
|
|
|
|
// ── Source location ──────────────────────────────────────────────────────
|
|
src_defect [
|
|
label="GraphUtils.java:186\n} else if (stack.contains(n)) {\n // ListBuffer linear scan"
|
|
shape=box style="filled,rounded" fillcolor="#ffeeee"
|
|
fontcolor="#cc0000" penwidth=2
|
|
]
|
|
src_fix [
|
|
label="GraphUtils.java:186 (patched)\n} else if (n.active) {\n // TarjanNode.active field — O(1)"
|
|
shape=box style="filled,rounded" fillcolor="#eeffee"
|
|
fontcolor="#006600" penwidth=2
|
|
]
|
|
|
|
src_defect -> d_v5 [label="drives" color="#cc0000" style=dashed]
|
|
src_fix -> f_v5 [label="drives" color="#006600" style=dashed]
|
|
|
|
// ── Where Tarjan fires ───────────────────────────────────────────────────
|
|
callers [
|
|
label="Call sites:\nInfer.java:1908 (type inference — every call site with unresolved vars)\nDeferredAttr.java:675 (stuck expression resolution — every lambda/method-ref)"
|
|
shape=box style=filled fillcolor="#e8e8ff"
|
|
]
|
|
callers -> src_defect [style=dotted]
|
|
callers -> src_fix [style=dotted]
|
|
}
|