Improved support for writing new algorithms in application code

[leshabirukov]

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.

[HeWeMel]

Approaches 4 & 5 are possible (maybe in addition to 1).

[HeWeMel]

(A Tarjan implemented as part of the library can offer full typing flexibility and good performance, better than what can be done in application code)

[leshabirukov]

...as part of the library can offer...

Of course it is, the question is lib structure complexity cost. In my opinion, general solution with acceptable performance is better then specialized with the best performance, at least for begining.

[HeWeMel]

Most libraries do both. Thus, I evaluate both.

[HeWeMel]

Some libraries provide a DFS that several visitors can be given to. Additional chance: Their return values can control how the DFS continues. Disadvantage: In Python, function calls are quite slow. But since the application can decide whether to use this functionality or not, this might not be a problem.

[HeWeMel]

Side note: It could be, that all the necessary functionality is already given in the implementation of the topological search, as it has some job to do when a vertex is left.

[HeWeMel]

A second approach could be to report vertices not just when they have a single, fixed state (e.g., visited), but in several states, together with the state. In order to keep the interface and typing constant, the state could be given as attribute of the traversal. This requires an attribute write (in the lib) and an attribute read (in the application) instead of a function call.

[HeWeMel]

Both approaches could either be done by adding further parameters to existing functions (callback function or flags demanding additional functionality) or by offering an additional traversal algorithm with the additional features.

I do not know so far, which approach in which form is the best for the users...

[leshabirukov]

additional traversal algorithm

There is already a few of DFS traversals in the nog, and, I suppose any of them could benefit from SCC, aaand I sence a ghost of the combinatorial growth.

[leshabirukov]

which form is the best for the users...

“Put the oxygen mask on yourself first and then on the baby.”
User will not benefit if you sank with the support.

[HeWeMel]

The algorithms of NoGraphs are non-recursive. In this variant, there is no notion of "leaving" a vertex, if not implemented manually. See, e.g., simple version of non-recursive DFS in wikipia

So, implementing the feature costs code, runtime, and memory. Either in form of a new traversal class, or in form of a new algorithm within a class, or a conditionally activated additional functionality (which means more complexity within an algorithm).

[HeWeMel]

Example: networx pushes tuples of (vertex, iterator_of_children) on the stack, instead of just the vertex. Tuples are large, iterators also. And the lib gets each such tuple several times from the stack in order to process more children. This is quite ineffective. But by doing so, a good bases is there to derive all kinds of special functions.