[Java] Topological sorting

Topological sorting of an acyclic graph is a representation of the graph where each node appears before every other node that links to it. This is useful for example for dependency checking to determine which items should be processed before others.

There are many ways of solving this problem, some easier to derive than others.
If the graph contains a cycle no solution can be obviously found.

The runtime of the proposed solution is O(V+E) where V is the number of vertexes and E the number or edges. The input could have included the list of vertexes as well, but it can also be derived from the list of edges itself, therefore I did not include it, although this means that vertexes with NO incoming edges at all, would not be included in the solution.

The idea is to preprocess the given list of edges (O(E)) and generate two auxiliary structures to track, for each vertex, the list of nodes it depends on (dependencies) and the list of nodes depending on it (require).

Then, the dependencies list can be scanned (O(V)) to identify nodes that have none and can therefore be processed immediately. These items are put in a queue.

For each item in the queue (O(V)), we add it to the solution set and retrieve all the nodes that are waiting on it (require) (O(E)) and remove the item from their dependencies list (also O(E)). If by doing so the dependencies list becomes empty, it means we freed a new item and add it to the queue, otherwise we simply update its dependency list.

Gotcha: remember to remove the current free item from the dependencies structure, since it has none anymore, and also check for NULLs when retrieving the list or items depending on it (require).

When the queue is empty, we are sure we processed all items that no longer have a dependency and need to check if the dependencies structure still contains something. If so, the graph contains at least one cycle.

This implementation uses extra O(V+E) space for the auxiliary structures

You can check my implementation of getTopologicalSorting on my Gist as well as some test cases in TopologicalSortingJTests. Since there might be multiple possible ways of sorting the same graph, the test results have to be checked manually :(