russell@unturf.com
db29a08762
B&W print-friendly diagrams + tinkerpop-0001 + wave-3 proof sections. Squash of 94 local commits onto remote master.
84 lines
4.3 KiB
Text
84 lines
4.3 KiB
Text
// Diagram 2: Tarjan DFS Execution — Defect Highlighted
|
|
// Shows the algorithm walking a path graph N0→N1→N2→N3→N4→N0 (back edge).
|
|
// At each step, the stack grows. When the back edge N4→N0 is reached,
|
|
// stack.contains(N0) scans ALL 5 stack entries instead of reading N0.active.
|
|
//
|
|
// Render: dot -Tsvg 0001-tarjan-defect.dot -o 0001-tarjan-defect.svg
|
|
|
|
digraph tarjan_defect {
|
|
graph [
|
|
label="Tarjan SCC: Execution Trace on Path Graph N0→N1→N2→N3→N4→N0\nDefect: stack.contains(N0) at back-edge fires O(n) scan (GraphUtils.java:186)"
|
|
labelloc=t
|
|
fontsize=13
|
|
fontname="monospace"
|
|
bgcolor="#f8f8f8"
|
|
rankdir=LR
|
|
pad=0.5
|
|
]
|
|
node [fontname="monospace" fontsize=10]
|
|
edge [fontname="monospace" fontsize=9]
|
|
|
|
// ── Input graph ─────────────────────────────────────────────────────────
|
|
subgraph cluster_input {
|
|
label="Input graph"
|
|
style=solid color="#333333"
|
|
rankdir=LR
|
|
|
|
N0 [label="N0\nindex=0" shape=circle style=filled fillcolor="#cce5ff"]
|
|
N1 [label="N1\nindex=1" shape=circle style=filled fillcolor="#cce5ff"]
|
|
N2 [label="N2\nindex=2" shape=circle style=filled fillcolor="#cce5ff"]
|
|
N3 [label="N3\nindex=3" shape=circle style=filled fillcolor="#cce5ff"]
|
|
N4 [label="N4\nindex=4" shape=circle style=filled fillcolor="#cce5ff"]
|
|
|
|
N0 -> N1 [label="forward"]
|
|
N1 -> N2 [label="forward"]
|
|
N2 -> N3 [label="forward"]
|
|
N3 -> N4 [label="forward"]
|
|
N4 -> N0 [label="BACK EDGE" color="#cc0000" penwidth=2 style=dashed]
|
|
}
|
|
|
|
// ── Stack at moment of back-edge check ──────────────────────────────────
|
|
subgraph cluster_stack {
|
|
label="Stack at step 5 (visiting N4, checking neighbour N0)"
|
|
style=solid color="#cc0000" fontcolor="#cc0000"
|
|
rankdir=TB
|
|
|
|
s_top [label="N4 ← top" shape=record style=filled fillcolor="#ffcccc"]
|
|
s_3 [label="N3" shape=record style=filled fillcolor="#ffe0cc"]
|
|
s_2 [label="N2" shape=record style=filled fillcolor="#ffe0cc"]
|
|
s_1 [label="N1" shape=record style=filled fillcolor="#ffe0cc"]
|
|
s_bot [label="N0 ← bottom / TARGET" shape=record style=filled fillcolor="#ffeeaa" penwidth=2]
|
|
|
|
s_top -> s_3 [style=invis]
|
|
s_3 -> s_2 [style=invis]
|
|
s_2 -> s_1 [style=invis]
|
|
s_1 -> s_bot [style=invis]
|
|
}
|
|
|
|
// ── The defective scan ──────────────────────────────────────────────────
|
|
subgraph cluster_scan {
|
|
label="stack.contains(N0) — LINEAR SCAN (GraphUtils.java:186)"
|
|
style=filled fillcolor="#fff0f0" color="#cc0000" fontcolor="#cc0000"
|
|
|
|
cmp1 [label="N4 == N0 ? NO" shape=diamond style=filled fillcolor="#ffcccc"]
|
|
cmp2 [label="N3 == N0 ? NO" shape=diamond style=filled fillcolor="#ffcccc"]
|
|
cmp3 [label="N2 == N0 ? NO" shape=diamond style=filled fillcolor="#ffcccc"]
|
|
cmp4 [label="N1 == N0 ? NO" shape=diamond style=filled fillcolor="#ffcccc"]
|
|
cmp5 [label="N0 == N0 ? YES" shape=diamond style=filled fillcolor="#aaff88" penwidth=2]
|
|
|
|
cmp1 -> cmp2 -> cmp3 -> cmp4 -> cmp5
|
|
}
|
|
|
|
// ── The fix ─────────────────────────────────────────────────────────────
|
|
subgraph cluster_fix {
|
|
label="n.active — O(1) CHECK (fix)"
|
|
style=filled fillcolor="#f0fff0" color="#006600" fontcolor="#006600"
|
|
|
|
fix [label="N0.active == true ? YES\n→ done, 1 operation" shape=diamond style=filled fillcolor="#aaff88" penwidth=2]
|
|
}
|
|
|
|
// ── Connections ─────────────────────────────────────────────────────────
|
|
N4 -> cmp1 [label="back edge triggers\nstack.contains(N0)" color="#cc0000" penwidth=2]
|
|
N4 -> fix [label="fix: n.active" color="#006600" penwidth=2 style=dashed]
|
|
s_top -> cmp1 [label="scan starts\nat top" color="#cc0000" style=dotted]
|
|
}
|