Efficient algorithm for retrieving the transitive closure of a directed acyclic graph
The fact that our graph is acyclic makes this problem much simpler.

Topological sort can give us an ordering of the vertices $v_1,v_2,\dots,v_n$ such that, if $i &lt; j$, then there is no edge from $v_j$ back to $v_i$. We've listed the vertices such that all edges in go "forward" in our list.

(edited to fix analysis and give slightly faster algorithm)

Now we just go backwards through this list, starting at the last vertex $v_n$. $v_n$'s transitive closure is just itself. Also add $v_n$ to the transitive closure of every vertex with an edge to $v_n$.

For each other vertex $v_i$, going from the end backwards, first add $v_i$ to its own transitive closure, then add everything in the transitive closure of $v_i$ to the transitive closure of all the vertices with an edge to $v_i$.

The running time is $O(n+m+nm) = O(n^3)$ in the worst case, with $n$ the number of vertices and $m \in O(n^2)$ the number of edges. Topological sort takes time $O(n+m)$. Then we do another $O(mn)$ work in the backward pass: As we go backwards through the list, for each edge, we have to add up to $n$ vertices to somebody's transitive closure.

Note that you can get a nice constant-factor speedup by representing everyone's transitive closure by bit-arrays. Say you only had $n=64$; then you would use a single 64-bit int where bit $i$ is 1 if $i$ is in my transitive closure and 0 otherwise. Then the part where we add everything in $i$'s transitive closure to $j$'s is really fast: We just take $c_j$ |= $c_i$. (Binary OR operation.)

For $n &gt; 64$, you'd have to keep them in arrays and do some arithmetic, but it would be much faster than an Object set.

Also, I know the big-$O$ in the very worst case is still $O(n^3)$, but to beat this in practice you'd have to have something much more complex. This algorithm also does very well on sparse graphs.