Search code examples
algorithmtopological-sort

Topological sort by arcs

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.

Solution

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