TarjanTest.test_4 failed

[edogawashinichi]

Describe the bug
Unit Test 1 FAILED TEST
[ RUN ] TarjanTest.test_4
/mnt/CXXGraph/test/TarjanTest.cpp:185: Failure
Expected equality of these values:
res.verticeBiconnectedComps.size()
Which is: 6
expectRes.size()
Which is: 7

[ FAILED ] TarjanTest.test_4 (0 ms)

To Reproduce
in my environment(CentOS in Docker on macOS), I modified
zlib version from 1.2.13 to 1.2.12 for cmake
in order to pass cmake&&make.
I tried TarjanTest.test_4 on master commit 994e9b9, v3.1.0, v3.0.0,
which all have the same problem.

Expected behavior
expectRes.size()
Which is: 7
Screenshots

Desktop (please complete the following information):

• OS: macOS Sonoma 14.4, Docker 25.0.3, CentOS 7.9.2009
• cmake: 3.23.0
• gcc: 7.3.1

Additional context
I'm not sure whether it's a bug or just something to do with my environment.
The following is my debug information:

[ RUN ] TarjanTest.test_4
[debug]start tarjan
[debug]notDirected
[debug]start dfs_helper
[debug]curnode=1 timestamp=0
[debug]find vbcc: stack emplace curnode
[debug]for neinode: 2 (curnode: 1)
[debug]if neinode notdisc dfs_helper start: 2
[debug]start dfs_helper
[debug]curnode=2 timestamp=1
[debug]find vbcc: stack emplace curnode
[debug]for neinode: 5 (curnode: 2)
[debug]if neinode notdisc dfs_helper start: 5
[debug]start dfs_helper
[debug]curnode=5 timestamp=2
[debug]find vbcc: stack emplace curnode
[debug]for neinode: 2 (curnode: 5)
[debug]else skip
[debug]for neinode: 6 (curnode: 5)
[debug]if neinode notdisc dfs_helper start: 6
[debug]start dfs_helper
[debug]curnode=6 timestamp=3
[debug]find vbcc: stack emplace curnode
[debug]for neinode: 5 (curnode: 6)
[debug]else skip
[debug]for neinode: 7 (curnode: 6)
[debug]if neinode notdisc dfs_helper start: 7
[debug]start dfs_helper
[debug]curnode=7 timestamp=4
[debug]find vbcc: stack emplace curnode
[debug]for neinode: 11 (curnode: 7)
[debug]if neinode notdisc dfs_helper start: 11
[debug]start dfs_helper
[debug]curnode=11 timestamp=5
[debug]find vbcc: stack emplace curnode
[debug]for neinode: 7 (curnode: 11)
[debug]else skip
[debug]for neinode: 10 (curnode: 11)
[debug]if neinode notdisc dfs_helper start: 10
[debug]start dfs_helper
[debug]curnode=10 timestamp=6
[debug]find vbcc: stack emplace curnode
[debug]for neinode: 9 (curnode: 10)
[debug]if neinode notdisc dfs_helper start: 9
[debug]start dfs_helper
[debug]curnode=9 timestamp=7
[debug]find vbcc: stack emplace curnode
[debug]for neinode: 10 (curnode: 9)
[debug]else skip
[debug]for neinode: 8 (curnode: 9)
[debug]if neinode notdisc dfs_helper start: 8
[debug]start dfs_helper
[debug]curnode=8 timestamp=8
[debug]find vbcc: stack emplace curnode
[debug]for neinode: 14 (curnode: 8)
[debug]if neinode notdisc dfs_helper start: 14
[debug]start dfs_helper
[debug]curnode=14 timestamp=9
[debug]find vbcc: stack emplace curnode
[debug]for neinode: 13 (curnode: 14)
[debug]if neinode notdisc dfs_helper start: 13
[debug]start dfs_helper
[debug]curnode=13 timestamp=10
[debug]find vbcc: stack emplace curnode
[debug]for neinode: 15 (curnode: 13)
[debug]if neinode notdisc dfs_helper start: 15
[debug]start dfs_helper
[debug]curnode=15 timestamp=11
[debug]find vbcc: stack emplace curnode
[debug]for neinode: 13 (curnode: 15)
[debug]else skip
[debug]for neinode: 8 (curnode: 15)
[debug]else if: neinode disc and (undir or neinode instack)
[debug]curlow: 15/11
[debug]neilow: 8/8
[debug]curlow=min: 15/8
[debug]finish dfs_helper: 15
[debug]if neinode notdisc dfs_helper finish: 15/8
[debug]for tmpcurlow: 13/11
[debug]for curlow=min: 13/8
[debug]if find vbcc
[debug]curdisc: 13/10
[debug]neilow: 15/8
[debug]else curnode not cutv and rootnode: 13
[debug]for neinode: 14 (curnode: 13)
[debug]else skip
[debug]for neinode: 12 (curnode: 13)
[debug]if neinode notdisc dfs_helper start: 12
[debug]start dfs_helper
[debug]curnode=12 timestamp=12
[debug]find vbcc: stack emplace curnode
[debug]for neinode: 13 (curnode: 12)
[debug]else skip
[debug]for neinode: 8 (curnode: 12)
[debug]else if: neinode disc and (undir or neinode instack)
[debug]curlow: 12/12
[debug]neilow: 8/8
[debug]curlow=min: 12/8
[debug]finish dfs_helper: 12
[debug]if neinode notdisc dfs_helper finish: 12/8
[debug]for tmpcurlow: 13/11
[debug]for curlow=min: 13/8
[debug]if find vbcc
[debug]curdisc: 13/10
[debug]neilow: 12/8
[debug]else curnode not cutv and rootnode: 13
[debug]finish dfs_helper: 13
[debug]if neinode notdisc dfs_helper finish: 13/8
[debug]for tmpcurlow: 14/10
[debug]for curlow=min: 14/8
[debug]if find vbcc
[debug]curdisc: 14/9
[debug]neilow: 13/8
[debug]else curnode not cutv and rootnode: 14
[debug]for neinode: 8 (curnode: 14)
[debug]else skip
[debug]finish dfs_helper: 14
[debug]if neinode notdisc dfs_helper finish: 14/8
[debug]for tmpcurlow: 8/9
[debug]for curlow=min: 8/8
[debug]if find vbcc
[debug]curdisc: 8/8
[debug]neilow: 14/8
[debug]if curdisc<=neilow (curnode cutv or rootnode)
[debug]while pop topnode to vbcc: 12
[debug]while pop topnode to vbcc: 15
[debug]while pop topnode to vbcc: 13
[debug]while pop topnode to vbcc: 14
[debug]while break: topnode=neinode=14
[debug]vbcc append curnode: 8
[debug]result emplace vbcc
[debug]for neinode: 15 (curnode: 8)
[debug]else if: neinode disc and (undir or neinode instack)
[debug]curlow: 8/8
[debug]neilow: 15/8
[debug]curlow=min: 8/8
[debug]for neinode: 9 (curnode: 8)
[debug]else skip
[debug]for neinode: 7 (curnode: 8)
[debug]else if: neinode disc and (undir or neinode instack)
[debug]curlow: 8/8
[debug]neilow: 7/4
[debug]curlow=min: 8/4
[debug]for neinode: 11 (curnode: 8)
[debug]else if: neinode disc and (undir or neinode instack)
[debug]curlow: 8/4
[debug]neilow: 11/5
[debug]curlow=min: 8/4
[debug]for neinode: 12 (curnode: 8)
[debug]else if: neinode disc and (undir or neinode instack)
[debug]curlow: 8/4
[debug]neilow: 12/8
[debug]curlow=min: 8/4
[debug]finish dfs_helper: 8
[debug]if neinode notdisc dfs_helper finish: 8/4
[debug]for tmpcurlow: 9/8
[debug]for curlow=min: 9/4
[debug]if find vbcc
[debug]curdisc: 9/7
[debug]neilow: 8/4
[debug]else curnode not cutv and rootnode: 9
[debug]for neinode: 11 (curnode: 9)
[debug]else if: neinode disc and (undir or neinode instack)
[debug]curlow: 9/4
[debug]neilow: 11/5
[debug]curlow=min: 9/4
[debug]finish dfs_helper: 9
[debug]if neinode notdisc dfs_helper finish: 9/4
[debug]for tmpcurlow: 10/7
[debug]for curlow=min: 10/4
[debug]if find vbcc
[debug]curdisc: 10/6
[debug]neilow: 9/4
[debug]else curnode not cutv and rootnode: 10
[debug]for neinode: 18 (curnode: 10)
[debug]if neinode notdisc dfs_helper start: 18
[debug]start dfs_helper
[debug]curnode=18 timestamp=13
[debug]find vbcc: stack emplace curnode
[debug]for neinode: 17 (curnode: 18)
[debug]if neinode notdisc dfs_helper start: 17
[debug]start dfs_helper
[debug]curnode=17 timestamp=14
[debug]find vbcc: stack emplace curnode
[debug]for neinode: 18 (curnode: 17)
[debug]else skip
[debug]for neinode: 10 (curnode: 17)
[debug]else if: neinode disc and (undir or neinode instack)
[debug]curlow: 17/14
[debug]neilow: 10/4
[debug]curlow=min: 17/4
[debug]finish dfs_helper: 17
[debug]if neinode notdisc dfs_helper finish: 17/4
[debug]for tmpcurlow: 18/14
[debug]for curlow=min: 18/4
[debug]if find vbcc
[debug]curdisc: 18/13
[debug]neilow: 17/4
[debug]else curnode not cutv and rootnode: 18
[debug]for neinode: 10 (curnode: 18)
[debug]else skip
[debug]finish dfs_helper: 18
[debug]if neinode notdisc dfs_helper finish: 18/4
[debug]for tmpcurlow: 10/7
[debug]for curlow=min: 10/4
[debug]if find vbcc
[debug]curdisc: 10/6
[debug]neilow: 18/4
[debug]else curnode not cutv and rootnode: 10
[debug]for neinode: 17 (curnode: 10)
[debug]else if: neinode disc and (undir or neinode instack)
[debug]curlow: 10/4
[debug]neilow: 17/4
[debug]curlow=min: 10/4
[debug]for neinode: 11 (curnode: 10)
[debug]else skip
[debug]for neinode: 16 (curnode: 10)
[debug]if neinode notdisc dfs_helper start: 16
[debug]start dfs_helper
[debug]curnode=16 timestamp=15
[debug]find vbcc: stack emplace curnode
[debug]for neinode: 10 (curnode: 16)
[debug]else skip
[debug]finish dfs_helper: 16
[debug]if neinode notdisc dfs_helper finish: 16/15
[debug]for tmpcurlow: 10/7
[debug]for curlow=min: 10/4
[debug]if find vbcc
[debug]curdisc: 10/6
[debug]neilow: 16/15
[debug]if curdisc<=neilow (curnode cutv or rootnode)
[debug]while pop topnode to vbcc: 16
[debug]while break: topnode=neinode=16
[debug]vbcc append curnode: 10
[debug]result emplace vbcc
[debug]finish dfs_helper: 10
[debug]if neinode notdisc dfs_helper finish: 10/4
[debug]for tmpcurlow: 11/6
[debug]for curlow=min: 11/4
[debug]if find vbcc
[debug]curdisc: 11/5
[debug]neilow: 10/4
[debug]else curnode not cutv and rootnode: 11
[debug]for neinode: 8 (curnode: 11)
[debug]else if: neinode disc and (undir or neinode instack)
[debug]curlow: 11/4
[debug]neilow: 8/4
[debug]curlow=min: 11/4
[debug]for neinode: 9 (curnode: 11)
[debug]else if: neinode disc and (undir or neinode instack)
[debug]curlow: 11/4
[debug]neilow: 9/4
[debug]curlow=min: 11/4
[debug]finish dfs_helper: 11
[debug]if neinode notdisc dfs_helper finish: 11/4
[debug]for tmpcurlow: 7/5
[debug]for curlow=min: 7/4
[debug]if find vbcc
[debug]curdisc: 7/4
[debug]neilow: 11/4
[debug]if curdisc<=neilow (curnode cutv or rootnode)
[debug]while pop topnode to vbcc: 17
[debug]while pop topnode to vbcc: 18
[debug]while pop topnode to vbcc: 8
[debug]while pop topnode to vbcc: 9
[debug]while pop topnode to vbcc: 10
[debug]while pop topnode to vbcc: 11
[debug]while break: topnode=neinode=11
[debug]vbcc append curnode: 7
[debug]result emplace vbcc
[debug]for neinode: 6 (curnode: 7)
[debug]else skip
[debug]for neinode: 5 (curnode: 7)
[debug]else if: neinode disc and (undir or neinode instack)
[debug]curlow: 7/4
[debug]neilow: 5/2
[debug]curlow=min: 7/2
[debug]for neinode: 8 (curnode: 7)
[debug]else if: neinode disc and (undir or neinode instack)
[debug]curlow: 7/2
[debug]neilow: 8/4
[debug]curlow=min: 7/2
[debug]finish dfs_helper: 7
[debug]if neinode notdisc dfs_helper finish: 7/2
[debug]for tmpcurlow: 6/4
[debug]for curlow=min: 6/2
[debug]if find vbcc
[debug]curdisc: 6/3
[debug]neilow: 7/2
[debug]else curnode not cutv and rootnode: 6
[debug]for neinode: 2 (curnode: 6)
[debug]else if: neinode disc and (undir or neinode instack)
[debug]curlow: 6/2
[debug]neilow: 2/1
[debug]curlow=min: 6/1
[debug]finish dfs_helper: 6
[debug]if neinode notdisc dfs_helper finish: 6/1
[debug]for tmpcurlow: 5/3
[debug]for curlow=min: 5/1
[debug]if find vbcc
[debug]curdisc: 5/2
[debug]neilow: 6/1
[debug]else curnode not cutv and rootnode: 5
[debug]for neinode: 7 (curnode: 5)
[debug]else if: neinode disc and (undir or neinode instack)
[debug]curlow: 5/1
[debug]neilow: 7/2
[debug]curlow=min: 5/1
[debug]finish dfs_helper: 5
[debug]if neinode notdisc dfs_helper finish: 5/1
[debug]for tmpcurlow: 2/2
[debug]for curlow=min: 2/1
[debug]if find vbcc
[debug]curdisc: 2/1
[debug]neilow: 5/1
[debug]if curdisc<=neilow (curnode cutv or rootnode)
[debug]while pop topnode to vbcc: 7
[debug]while pop topnode to vbcc: 6
[debug]while pop topnode to vbcc: 5
[debug]while break: topnode=neinode=5
[debug]vbcc append curnode: 2
[debug]result emplace vbcc
[debug]for neinode: 3 (curnode: 2)
[debug]if neinode notdisc dfs_helper start: 3
[debug]start dfs_helper
[debug]curnode=3 timestamp=16
[debug]find vbcc: stack emplace curnode
[debug]for neinode: 2 (curnode: 3)
[debug]else skip
[debug]for neinode: 4 (curnode: 3)
[debug]if neinode notdisc dfs_helper start: 4
[debug]start dfs_helper
[debug]curnode=4 timestamp=17
[debug]find vbcc: stack emplace curnode
[debug]for neinode: 3 (curnode: 4)
[debug]else skip
[debug]for neinode: 2 (curnode: 4)
[debug]else if: neinode disc and (undir or neinode instack)
[debug]curlow: 4/17
[debug]neilow: 2/1
[debug]curlow=min: 4/1
[debug]finish dfs_helper: 4
[debug]if neinode notdisc dfs_helper finish: 4/1
[debug]for tmpcurlow: 3/17
[debug]for curlow=min: 3/1
[debug]if find vbcc
[debug]curdisc: 3/16
[debug]neilow: 4/1
[debug]else curnode not cutv and rootnode: 3
[debug]finish dfs_helper: 3
[debug]if neinode notdisc dfs_helper finish: 3/1
[debug]for tmpcurlow: 2/2
[debug]for curlow=min: 2/1
[debug]if find vbcc
[debug]curdisc: 2/1
[debug]neilow: 3/1
[debug]if curdisc<=neilow (curnode cutv or rootnode)
[debug]while pop topnode to vbcc: 4
[debug]while pop topnode to vbcc: 3
[debug]while break: topnode=neinode=3
[debug]vbcc append curnode: 2
[debug]result emplace vbcc
[debug]for neinode: 6 (curnode: 2)
[debug]else if: neinode disc and (undir or neinode instack)
[debug]curlow: 2/1
[debug]neilow: 6/1
[debug]curlow=min: 2/1
[debug]for neinode: 4 (curnode: 2)
[debug]else if: neinode disc and (undir or neinode instack)
[debug]curlow: 2/1
[debug]neilow: 4/1
[debug]curlow=min: 2/1
[debug]for neinode: 1 (curnode: 2)
[debug]else skip
[debug]finish dfs_helper: 2
[debug]if neinode notdisc dfs_helper finish: 2/1
[debug]for tmpcurlow: 1/1
[debug]for curlow=min: 1/0
[debug]if find vbcc
[debug]curdisc: 1/0
[debug]neilow: 2/1
[debug]if curdisc<=neilow (curnode cutv or rootnode)
[debug]while pop topnode to vbcc: 2
[debug]while break: topnode=neinode=2
[debug]vbcc append curnode: 1
[debug]result emplace vbcc
[debug]finish dfs_helper: 1
/mnt/CXXGraph-3.0.0/debug/TarjanTest.cpp:188: Failure
Expected equality of these values:
res.verticeBiconnectedComps.size()
Which is: 6
expectRes.size()
Which is: 7
[ FAILED ] TarjanTest.test_4 (1 ms)

For the case TarjanTest.test_4

The result I got misses the vbcc [10,17,18].
The problem seems to be caused by the lowestDisc of node 10 modified earlier than the time when it finishes its dfs_helper.

[ZigRazor]

This could be a bug, but we should try to execute it on other platform or with other compiler.
In the meantime if you are able to find some other info, and why this happens, could be a valuable help!
Thank you in advance

[ZigRazor]

Another help could be write tests for some other cases where this bug exist.

[edogawashinichi]

This could be a bug, but we should try to execute it on other platform or with other compiler. In the meantime if you are able to find some other info, and why this happens, could be a valuable help! Thank you in advance

Sure, I shall try to fix this bug, since the reason why this happens is possibly figured out by the debug information.

[edogawashinichi]

Another help could be write tests for some other cases where this bug exist.

Considering different platforms or compilers, the order of cachedAdjMatrix and other data stored and visited may differ, I conjecture, which I have no evidence, due to constraint on machines at hand.

A direct suggestion would be to provide a random implementation on the order of graph data stored or visited, to generate a variety of unit test cases, which are equivalent to the cases already exists, since our algorithms are independent of the order of data.

And of course new tests are still needed.

[edogawashinichi]

The following is to explain in detail why the current master(commit 994e9b9) failed TarjanTest.test_4 on my environment.

For convenience we copy the case here.

According to the debug information, the list of (node, its discoveryTime) is:
[(1,0),(2,1),(5,2),(6,3),(7,4),(11,5),(10,6),(9,7),(8,8),(14,9),(13,10),(15,11),(12,12),(18,13),(17,14),(16,15),(3,16),(4,17)]
or [1,2,5,6,7,11,10,9,8,14,13,15,12,18,17,16,3,4] omitting the discoveryTime,
which is of course a valid DFS order.

When the current node is 10 and the neighbor node is 18,
the lowest discovery time of node 10 is already modified to 4, after dfs_helper of node 9,
since node 9 reaches node 7(whose discoveryTime is 4).
After dfs_helper of node 18, the lowest discovery of node 18 is modified to 4,
since node 18 reaches node 10 through node 17.
By TARJAN_FIND_VBCC condition discoveryTime[curNode]<=lowestDisc[neighborNode],
6<=4 doesn't hold.
Therefore the result misses vbcc=[10,17,18],
which remains in vbccNodeStack until the end of the tarjan function.