Tcl Library Source Code

View Ticket
Login
2026-11-15
14:01 • Ticket [0f65bfa2d3] ::struct::graph::op::tarjan infinite loop status still Open with 3 other changes artifact: b09f337e15 user: serhiy.storchaka
13:23
Fix [0f65bfa2d3]: struct::graph::op::tarjan hung and isCutVertex? gave wrong answers for node names containing spaces. 'struct::set subtract' treats such a name as a set of words; use 'struct::set exclude' to remove the single node. The fix for Bug 2815302 (746fd7f965) had been undone by the GSoC merge (42c21b6c75). leaf check-in: 1ad56464d4 user: serhiy.storchaka tags: graph-tarjan-node-spaces
2026-08-08
16:23 • Ticket [0f65bfa2d3] ::struct::graph::op::tarjan infinite loop status still Open with 4 other changes artifact: 4ec499c94d user: anonymous
16:23 • Add attachment graphops-tarjan-fix-with-test.diff to ticket [0f65bfa2d3] artifact: b6a2260f16 user: anonymous
16:20 • New ticket [0f65bfa2d3] ::struct::graph::op::tarjan infinite loop. artifact: ef8fa41ef0 user: anonymous

Ticket UUID: 0f65bfa2d3cefba806c82a4647a87cdd50ce609c
Title: ::struct::graph::op::tarjan infinite loop
Type: Bug Version: 1.21
Submitter: anonymous Created on: 2026-08-08 16:20:23
Subsystem: struct :: graph Assigned To:
Priority: 5 Medium Severity: Minor
Status: Open Last Modified: 2026-11-15 14:01:42
Resolution: None Closed By: nobody
    Closed on:
Description:
I was using struct::graph::op::tarjan to create input to a dag queue implementation I've written.  It hung, so I added some debug statements, and I think I discovered a bug.

$g node insert {beamsect_C C}

calling Tarjan on this seems to split this into beamsect_C and C and then never remove it.

The node name was a mistake in my code, but nonetheless... I think it should have worked with Tarjan and failed later.

I think this is a regression that was previously fixed... I have a fix based on that, and a test case that reproduces it.


Ref info based on language model research of the issue attached, I tested the failing test case and fix.  Seems to work.
User Comments: serhiy.storchaka added on 2026-11-15 14:01:42:

Proposed fix in branch graph-tarjan-node-spaces: the change in the attached diff (struct::set exclude instead of subtract in TarjanSub), plus the same fix in isCutVertex?, which still uses subtract on trunk. This is a regression of Bug 2815302: the fix [746fd7f965] was undone by the GSoC merge [42c21b6c75]. Tests tarjan-3.9 and isCutVertex?-3.4.


Attachments: