### knst's blog

By knst, 7 years ago, translation,

How to calculate number of topological sort?

Brute force not acceptable: number of vertex N is 10^3; number of edges M: 3 * 10^5. Time limit of calculation isn't critical: 1 hour is acceptable. Can you help me with this problem? I can't find solution.

Trivial example:
N = 6; M = 7
V: 1 2 3 4 5
E:
1 2
1 3
1 4
1 5
2 4
2 5
3 5

5
(1 2 3 4 5)
(1 3 2 4 5)
(1 2 4 3 5)
(1 2 3 5 4)
(1 3 2 5 4)


• +9

 » 7 years ago, # |   +9 It seems that counting the number of topological orderings of the graph is #P-complete. (article). So I think that without any additional information about graph structure there is no chance to calculate an answer until the end of this era. All known algorithms are exponential, so they won't work fast on the dense graph of such great size (thousand of vertices!).Anyway, in the article above there is a mention of algorithms that can possibly estimate the answer.
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 ohh :( It's not simple as I thought. Thx.
•  » » » 7 years ago, # ^ |   0 So, is 2^1000 hours acceptable?
•  » » » » 7 years ago, # ^ |   +30 I'm waiting my trivial O(N!) solution already :-)
•  » » » » 7 years ago, # ^ |   +3 I bet it requires at least 21000 bytes of memory. Only problem I can see is 1024-bit addressation.
•  » » » » » 7 years ago, # ^ |   +14 I take it that 7 people don't have a sense of humor.
•  » » » » » » 2 years ago, # ^ |   -16 Hi if you take out printing the sequences . is possible to count the number of topological sorts?
•  » » 6 weeks ago, # ^ |   -79 What if the graph is a tree whose edges are directed in such a way that every other node can visit node U?
 » 9 months ago, # | ← Rev. 3 →   -8 Here is the code implementation using mask. certainly it will not help you but it works fine for smaller values.