Several days ago I had to traverse a huge graph in depth (depth-first-search) visiting edges in post-order. I was working on Kasaraju's algorithm to find strongly connected components of a graph.

Of course the default (natural) implementation of post-order DFS is very easy to be read and understand. In my implementation of I'm using callback in order to change the behaviour when node is visited - for example I can just print the nodes or add the into a collection without changing the algorithm.

The thing is, there were about a million of nodes in the graph. So it's possible to reach a stack depth of 1 million of nested calls while doing recursive DFS. The Java stack by default is not configured to work with such a huge amount of recursive calls...

Of course the default (natural) implementation of post-order DFS is very easy to be read and understand. In my implementation of I'm using callback in order to change the behaviour when node is visited - for example I can just print the nodes or add the into a collection without changing the algorithm.

public void dfsPostOrderRecursive(AdjGraph graph, AdjGraph.Node vertex,

Callback callback) { if (vertex.isVisited()) return; vertex.markVisited(); List<AdjGraph.Node> edges = graph.edges(vertex); for (AdjGraph.Node node : edges) { if (!node.isVisited()) dfsPostOrderRecursive(graph, node, callback); } callback.nodeVisited(graph, vertex); //post order call to callback }

The thing is, there were about a million of nodes in the graph. So it's possible to reach a stack depth of 1 million of nested calls while doing recursive DFS. The Java stack by default is not configured to work with such a huge amount of recursive calls...