Non-recursive DFS visits siblings in reversed order. Typical, but could be surprising. Should be documented.

[leshabirukov]

While doing depth first search(DFS), siblings (children of one parent) are visited in order, reversed, comparing to order next_thing reported them.

import nographs as nog  
dict_1= {0:{111,2,4}, 111:{3,5}, 2:{3,6,0}, 3:{37,0}, 37:{7}, 4:{5,6}, 5:{57}, 57:{7},  6:{67}, 67:{7}, 7:{6} }  

def forward( vert, _):  
    print( f"\n visiting {vert}", end=' - ' )  
    for child in dict_1[ vert ]:  
        print( f"found {child}", end=' - ' )  
        yield child  

trav_forward = nog.TraversalDepthFirst( forward, )  
trav_forward.start_from( 0, )  
list(trav_forward)  

visiting 0 - found 2 - found 4 - found 111 -   
 visiting 111 - found 3 - found 5 -   
 visiting 5 - found 57 -   
 visiting 57 - found 7 -   
 visiting 7 - found 6 -   
 visiting 6 - found 67 -   
 visiting 67 - found 7 -   
 visiting 3 - found 0 - found 37 -   
 visiting 37 - found 7 -   
 visiting 4 - found 5 - found 6 -   
 visiting 2 - found 0 - found 3 - found 6 -  

Being aware of nog internals, I doubt this can be fixed painlessly, but this must be documented explicitly and loud, avoiding surprising user that way.

Sometime, may be, we to introduce a compatibility mode, for ones who needs canonical traversal, I suggest doing it only if someone else hit this issue.

[HeWeMel]

Thanks for your remarks.

The order of the visit of siblings does not belong to the guarantees of a DFS algorithms. Not according to the documentation of NoGraphs. And not according to the specification of a DFS as such, e.g., in Wikepedia.

In fact, the recursive DFS shown in Wikipedia visits them "in order", and the non-recursive version visits them in "reversed order" (like the non-recursive implementation in NoGraphs). This is even described in Wikepedia: "These two variations of DFS visit the neighbors of each vertex in the opposite order from each other: the first neighbor of v visited by the recursive variation is the first one in the list of adjacent edges, while in the iterative variation the first visited neighbor is the last one in the list of adjacent edges."

And in fact, many other non-recursive implementations of the DFS behave like this.

In this situation, changing the implementation would not "fix" something, but would make its behavior strange and unexpected. Thus, I would also not confirm the word "compatibility" - because a change would make the behavior incompatible to typical implementations.

But I am with you that the documentation should be improved: It should state that the order of the sibling visits is not specified, and might even change in the future. Like this, surprises for users could be prevented.

[leshabirukov]

Oh, thank you for explanation, I didn't know this. Thing I still disagree, even with Wikipedia, is they call it 'implementation', if it changes the order, it is rather 'variation'.

[leshabirukov]

Also, though mathematically neighbours order in graph is not determined, practically it frequently is.

[HeWeMel]

Comment added: https://nographs.readthedocs.io/en/latest/traversals.html#:~:text=Note%20that%20these,without%20prior%20notice.