Tcl Library Source Code

View Ticket
Login
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: