Topological sort by arcs

Question

Really need just some guidance : Topological sort by arcs definition (from my question) - is a way of ordering all the arcs in directional graph so all arcs that insert to vertex must apear before the one that come out from this vertex.

Answer 1

No need to to change anything in topological sort, you can just use it, and post-process.

high level pseudo code:

1. run topological sort, let the resulting array be arr
2. create empty edges list, let it be l
3. for each vertex v in arr [ordered iteration]:
   3.1. for each (v,u) in E:
   3.1.1. append (v,u) to l
4. return l

The advantage of this method is you can use topological sort as black box, without modifying it and just post-process to get the desired result.

Correctness [sketch of proof]:
Since for each edge (v,u) - u appears after v in topological sort, when you print it, it is done via v, and thus (v,u) is printed before you print any vertex attached to u.

Complexity:
O(|V|+|E|) topological sort, O(|V|+|E|) for post processing [iterating all vertices and all edges].

Answer 2

"Traditional" topological sort is sorting vertices, while this one is sorting arcs. Otherwise the principle is the same...