Sorry to keep hammering on this but there are still tab characters ;-)

A question: Is there a point to using a lazy adjlist instead of an adjlist? Won't it usually traverse the whole graph anyway, meaning that a lazy adjlist is more likely to be a performance hit than a performance gain? I don't know. It won't traverse the whole graph if the graph is not connected. Perhaps that is not such an uncommon situation with real-world directed graphs.

Anyway, it's just a thought. I wouldn't necessarily spend time changing this—it might turn out to make next to no difference. However, if you are going for the ultimate performance (part of the reason for this function is to have better performance than igraph_dfs, right?) then you might want to investigate this.

Thanks, I finally fixed my editor to avoid tabs, sorry about that. Laziness is a difficult beast.

Honestly I'm happy with either igraph_dfs, having a new igraph_i_dfs, or even using Python. The main push from me is having some kind of Graph.dfs in Python since it's such an essential function, for the rest I'm just molding on existing infra.

I think it's useful to have igraph_i_dfs() separately in the C core, but maybe we shouldn't mark these functions as "internal". The reason why igraph_i_bfs() exists is that for certain use-cases (running a "quick" BFS) all the arguments in igraph_bfs() are overkill -- to such an extent that the Python interface basically wraps igraph_i_bfs() with the Graph.bfs() method and no one complained about the missing features so far. So maybe calling these igraph_bfs_simple() and igraph_dfs_simple() would be more appropriate.

As for whether igraph_i_bfs() is faster than igraph_bfs() (and whether it would be true for igraph_i_dfs()), I don't know. This would need to be benchmarked, and we need to understand why igraph_i_bfs() is faster if it is indeed faster. Is it faster because it does not have to do as much bookkeeping as igraph_bfs() has to (because of the extra arguments), or is it faster because there are some optimizations in igraph_i_bfs() that were not ported to igraph_bfs()?

Otherwise, @iosonofabio I am totally fine with the proposed simple interface for igraph_i_dfs().

This issue has been automatically marked as stale because it has not had recent activity. It will be closed in 14 days if no further activity occurs. Thank you for your contributions.

Just a heads up; this PR was originally motivated by the fact that we've had an igraph_i_bfs() function that made things a whole lot simpler in the Python interface. igraph_i_bfs() was renamed to igraph_bfs_simple() in the meanwhile to ensure that we don't expose internal functions in the public API. In a similar vein, we could have igraph_dfs_simple() instead of igraph_i_dfs().

@iosonofabio We are about to turn things upside down soon(ish) by transitioning to 64-bit integer types and there will probably be lots of merge conflicts with pending PRs. What's the status of this PR, shall we try and finish this and get this merged before the integer transition or shall we put this aside and deal with it again after the integer transition? (The same question also applies to #1257)

Thanks. The main reason for me was Python, that was solved separately.

I also don't know if the simple function is faster than the full one, for either BFS or DFS. So renaming the other one was good but the key issues are out there.

I could just quickly finish this one for symmetry, then we have bsf and dfs with both simple siblings, or i could just let it fall and come back to it after the 64 bit transition with a fresh PR

We can come back to this after the int64 transition, since it's not urgent.