TarjanTest.test_4 failed

[edogawashinichi]

TarjanTest.test_4 failed

[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.