Topological sorting

In computer science, a topological sort (sometimes abbreviated topsort or toposort) or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge u--v from vertex u to vertex v, u comes before v in the ordering.

Note 1 : A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG).

Note 2 : Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time.

Ques: Can you give me an example ?

Ans:Yes :)

Example : The graph is given below.

It has many valid topological orders :

7, 5, 3, 11, 8, 2, 9, 10 (visual left-to-right, top-to-bottom)

3, 5, 7, 8, 11, 2, 9, 10 (smallest-numbered available vertex first)

5, 7, 3, 8, 11, 10, 9, 2 (fewest edges first)

7, 5, 11, 3, 10, 8, 9, 2 (largest-numbered available vertex first)

7, 5, 11, 2, 3, 8, 9, 10 (attempting top-to-bottom, left-to-right)

3, 7, 8, 5, 11, 10, 2, 9 (arbitrary)

Ques : Can we find all possible topological sort in a Garph ?

Ans : Computing all possible topological sort outcomes can't be done efficiently simply because number of possible outcomes might be huge and outputting them itself will take a lot of time. 

For example, in a graph on  vertices with no edges, number of valid topological sort outcomes is . 

Algorithm :

First, find a list of "start nodes" which have no incoming edges and insert them into a set S; at least one such node must exist in an acyclic graph. 

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)

If the graph is a DAG, a solution will be contained in the list L (the solution is not necessarily unique). Otherwise, the graph must have at least one cycle and therefore a topological sorting is impossible.

SAMPLE CODE :

Time Complexity:

The usual algorithms for topological sorting have running time linear in the number of nodes plus the number of edges, asymptotically, .

Visualizations of Topological Sort (DFS) 

Ques: Can You give me some questions for practice ?
Ans :Yes, Links are below 
Problem-1:  http://www.codechef.com/problems/TSUBSTR/
Problem-2:   http://www.spoj.com/problems/TOPOSORT/

Application :

1- .Build systems

Consider a source code structure where you are building several libraries (DLLs) and they have dependencies on each other. For example, to build dll A, you must have built DLLs B, C an D (Maybe you have a reference of B,C and D in the project that builds A).

Let's mark a dependency edge from each of B, C and D to A implying that A  depends on the other three and can only be built once each of the three are built. Technically speaking, (u,v) => An edge from u to v implies v.dll can be built only when u.dll is already built.

After constructing a graph of these dlls and dependency edges, you can conclude that a successful build is possible iff the resulting graph is acyclic (Ignoring advanced ways of resolving cyclic dependencies like asmmeta [1] files). How does the build system decide in which order to build these dlls? It sorts them topologically.

Therefore, in an order like X->Z->T->B->D->C->A, it can start building X (which may only depend on external assemblies already built), then follow the topologically sorted list of assemblies.

Note: This is a "contrived real-world application". This may not be how assemblies are built by msbuild or other compilers. 

2: apt-get uses topological sorting to obtain the best possible sequence in which a set of debian packages can be installed/removed.

3: Resolving Dependencies.

4:Graph Drawing Algorithms.

5:Workflow management-Project management.

• Alert !!! if you find anything usefull please do share :)

References:

1.http://en.wikipedia.org/wiki/Topological_sorting

2.http://www.quora.com/What-are-some-real-world-applications-of-topological-sort

3.http://stackoverflow.com/questions/1316518/how-did-microsoft-create-assemblies-that-have-circular-references

4.https://www.cs.usfca.edu/~galles/visualization/TopoSortDFS.html