DFS processing finished nodes

[zemanpeter]

Describe the bug If a node appears several times on the stack, then it will be processed several times in the else branch. https://github.com/cheran-senthil/PyRival/blob/master/pyrival/graphs/dfs.py

Expected behaviour I would expect the implementation to process each node only once after its subtree is finished. I think it would be suitable to add something like this after line 18: if finished[start]: continue

[bjorn-martinsson]

I kind of agree that this is a bug. If the graph is a tree than the code is correct, but on general graphs it is wrong. The fact that the code is using child makes me think it was coded to be used for trees.

I think a good fix would be to rename child to neighbour and change the else: on line 17 to be elif not finished[start]:

[zemanpeter]

Hmm, maybe I am missing something, but if you modified the code according to your suggestion, would then a vertex pop from the stack? I mean if a vertex appears 2 times on stack, then when processing it, first time we pop it, but second time it is finished so it will not get popped and the while cycle gets stuck. Or am I wrong?

[bjorn-martinsson]

Ah yes, you are correct.

Hmm I wonder what would be the best fix.

Btw, one modification that might be worth doing is to change

for child in graph[start]:
    if not visited[child]:
        stack.append(child)

to

stack += graph[start]

[zemanpeter]

I personally do not have such deep knowledge of python, but if "+=" is better than "append", then it should be good.

Concerning the stack issue, I think a clean solution would be what I suggested. The reason is that this DFS is supposed to mimic the recursive DFS (since we cannot use recursion with Python in CP) at the cost of larger stack. This version of DFS traverses the neighbours in the reverse order as they appear on the adjacency list. So the relevant occurrence of a vertex on the stack is the last one. All the previous occurrences should be treated as if they did not exists an therefore skipped. In my opinion the cleanest way to achieve this is to just add the statement

if finished[start]: continue

after popping from the stack.