|
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:
- graphops-tarjan-fix-with-test.diff [download] added by anonymous on 2026-08-08 16:23:01. [details]
