# Topological Ordering

I have learnt to solve topological ordering using $$in-degree$$ method where we have to take the vertices having in-degree $$0$$ at an instance and arrange them in that order.

For example consider this question asked in Graduate Aptitude Test in Engineering more commonly known as $$GATE$$ the entrance exam for $$IIT$$ $$M.Tech$$ in India. The question goes like this,

Find the number of topological ordering possible for the given graph-->

Here we can see that in-degree of A is 0 so we take $$A$$ as the stating vertex, then we have 2 options either $$B$$ or $$C$$, and so on.... The number of possible topological ordering in this case is $$6$$ as explained below

This method works well for these examples where the number of in-degree 0 vertices is less at a time, but how to solve problems where there are many number of 0 in-degree vertices as the one given below

I think combinatorics will come into picture in such cases, but I am unable to apply it properly. Any help will be highly appreciated.

Unfortunately, there is no "fast" way to count them generally as this problem is #P-Complete. This means that it is basically as hard as every counting version of NP-problems, and is likely not solvable in polynomial time.

For small examples such as this one you can come up with some ad-hoc counting technique however. In this case would try listing all permutations of E,F,G and see how many choices I have for the rest if I insert them in some order. Like this:

• EFG: 1+2+4+6 = 13 (1 choice for A, then 2 for B, 4 for C, 6 for D)
• EGF: 1+2+4+5 = 12 (in A,B,C,D order)
• FEG: 1+2+4+5 = 12 (in B,C,A,D order)
• FGE: 1+2+4+6 = 13 (in B,C,D,A order)
• GEF: 1+2+4+5 = 12 (in D,C,A,B order)
• GFE: 1+2+4+5 = 12 (in D,C,B,A order)

So in total 4*12 + 2*13 = 74 topological orderings (with some non-negligeable probability that I miscounted somewhere).