» Post-Order Iterative DFS Traversal using Stack

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.

    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...

Software Engineering: Java Tuples

This post is related to Java Tuples. Every time I'm switching from Scala or Python back to Java what I'm missing are tuples. Simple but effective idea of tuples minimizes the amount of code needed to express my ideas in code.

Sure thing you don't want to publish an API with Tuples as a return type of your methods. But if the tuples are used between your methods - they can significantly reduce the amount of work and a number of classes needed. So I've implemented my own library to add Tuples to Java. Feel free to try it. Sources on GitHub

<dependency>
    <groupId>com.othelle.jtuples</groupId>
    <artifactId>jtuples</artifactId>
    <version>{always.try.to.pick.the.latest.version}</version>
</dependency>