Suggestion: Computing strongly connected components (of the sub-graph reachable from a set of vertices), e.g., with algorithms like described here. These are linear-time algorithms that can be applied to directed graphs.
Originally posted by @HeWeMel in #12 (comment)
Hello again!
New issue, and now it's real deal, I think. Consider Tarjan algorithm: With DFS, we need to do some work on_leaving node, but how? The only visitor is 'next_something( vert )', and we already leaved it!
So, we in need of 'on_leave(v)'. What we can do (in user code part) now, is everytime leaving vertex, check it's predecessors, possibly all way to root. Not the dream.
Possible solutions:
- Add algorithms like Tarjans to the nog core. That's what you actuallu proposed, but I think it must be user level.
- Saying "we don't". Painfuly restrictive.
- Point to solution, using interaction with different graph lib. Hardly could be done with good performance.
- Provide traversal object with 'on_leave' (on_finish, post_process) event, user can hook.
- Provide some other template for algoritms like Tarjan's.
Originally posted by @HeWeMel in #12 (comment)
Hello again!
New issue, and now it's real deal, I think. Consider Tarjan algorithm: With DFS, we need to do some work on_leaving node, but how? The only visitor is 'next_something( vert )', and we already leaved it!
So, we in need of 'on_leave(v)'. What we can do (in user code part) now, is everytime leaving vertex, check it's predecessors, possibly all way to root. Not the dream.
Possible solutions: