Further algorithms that are suitable for NoGraphs?

[HeWeMel]

NoGraphs is focused on graph algorithms that make sense for its domain: „Graphs that can not or should not be fully computed, stored or adapted.“. And it only provides algorithms that are „often“ helpful, because library bloat should be prevented. But there might be more algorithms that fulfill these selection criteria.

Any suggestions? And why is the suggested algorithm suited for NoGraphs?

[HeWeMel]

Suggestion: DFS with iterative deepening

Pro:

• Often used for graphs with unknown depth
  Contra:
• Its typical advantage over BFS, the lower memory usage, is not so strong with implicit graphs. A set ‚visited’ for avoiding to visit vertices twice within a single deepening run is needed anyways (other libraries hide this in a flag in the vertex nodes, but NoGraphs does not need them), and the additional space for the horizon list is not so much larger in comparison.
• Higher runtime than BFS, because visited vertices are visited in subsequent deepening steps again

[leshabirukov]

Being totally agreed about library bloat, I don't see a problem about having support materials in form such as app, layer II or just examples as I create, and concrete algorithms is only one target for such a material. Those status can upgrade later, if proven useful and demanded.

[HeWeMel]

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.

[leshabirukov]

How you think an interface?

[HeWeMel]

Results could be reported as: a) Iterator of tuples (vertex, component_id) or b) Iterator of components, each as list of vertices

[leshabirukov]

Can it produce DAG of components? Can it be incrementally applyed to infinite graph?

[leshabirukov]

Let's do implementation examples (no integration), I will make one soon, hereby challenge you to compete.