In a recent algorithms course we had to form a condensation graph and compute its reflexive-transitive closure to get a partial order. But it was never really explained why we would want to do that in a graph. I understand the gist of a condensation graph in that it highlights the strongly connected components, but what does the partial order give us that the original graph did not?
The algorithm implemented went like this:
Find strongly connected components (I used Tarjan)
Create condensation graph for the SCCs
Form reflexive-transitive closure of adjacency matrix (I used Warshall)
Doing that forms the partial order, but.... what advantage does finding the partial order give us?