Bug in DFS advance: premature unwinding element from DFS stack

[TrungDinhT]

First of all, I would like to thank you all for the great library, and attempt for making graph into standard library :clap:.

Currently, I'm using this at work and I'm having a small issue when using DFS views, as it doesn't traverse all the nodes in reachable edges, in some specific circumstances, especially a vertex (and branches connected to it) will be ignored from traversal, if it is the target of an edge whose source also connects to another vertex at the leaf of the graph (no more outgoing edges).

After debugging, I was able to trace back the issue to this line below in the advance() method of dfs_base class https://github.com/stdgraph/graph-v2/blob/fedd598e585847b304fb58f9649f73caa0585beb/include/graph/views/depth_first_search.hpp#L163

I think that popping the stack at this stage is too early, and is the cause of the problem mentioned above. As elements on stack consist of a pair of source and edge (from that source), and if we are in the case where we reach this line, the edge is reaching a "black" target, so we want to pop it out. However, it is possible that the source of that edge has other outgoing edges to other vertices that are not visited yet. Therefore, popping out the element in this case is too early in my opinion. Anyway, the block of code just after that line also checks and pops elements on stack in case of unvisited edges. Thus, I think that the S_.pop() mentioned above is not necessary and can cause problems.

I've just worked with graph-v2 recently so I'm not sure to have full understanding of the library. Hence, my analysis could be wrong. However, the issue that I'm facing is real, so I would like to mention it here and ask for help.

Thanks

[kdeweese]

Hi Trung,

Thank you for your feedback. I will try to reproduce what you are describing but it would be helpful if you could provide a small example graph with a starting vertex that demonstrates the problem.

Thanks

[TrungDinhT]

Above is the graph that I was working on and having such problem. It is a DAG. For our business logic, we need to traverse in DFS from the top level children, so either C, D or E. I've encountered the problem when for our configuration, the DFS traversal starts from C, reaches F, then H, and stops there, instead of reaching B (and all other unvisited nodes).

[mcmillan03]

FYI, that model is not a DAG. I see two cycles {BCF} and {BDF}

On Mon, Sep 25, 2023 at 12:54 AM TrungDinhT @.***> wrote:

[image: problematic_graph] https://user-images.githubusercontent.com/24397712/270268062-942a1edc-be0d-40d9-a49e-74e22a2d9d80.jpeg

Above is the graph that I was working on and having such problem. It is a DAG. For our business logic, we need to traverse in DFS from the top level children, so either C, D or E. I've encountered the problem when for our configuration, the DFS traversal starts from C, reaches F, then H, and stops there, instead of reaching B (and all other unvisited nodes).

— Reply to this email directly, view it on GitHub https://github.com/stdgraph/graph-v2/issues/71#issuecomment-1733113012, or unsubscribe https://github.com/notifications/unsubscribe-auth/AANXEP7GLDYLPXV246XAPGTX4E2D7ANCNFSM6AAAAAA4IWMS2A . You are receiving this because you are subscribed to this thread.Message ID: @.***>

[TrungDinhT]

Thank you for the info. And yes, I'm aware of that.

Actually, in our real configuration, the F->B edge is "marked" as back edge. Moreover, we want to verify that F->B is really a back edge, so that's why above I said that we traverse from C, D or E (not really top level children, but more precisely they are neighbours of a vertex that are the destination of a back edge), but it is our internal business logic so it does not impact the fact that DFS view does not reach B via F->B edge in case H is reached first.