knst's blog

Number of topological sort
By knst, 11 years ago, translation, In English

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

Answer: 
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)
  • Vote: I like it
  • +9
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    ohh :( It's not simple as I thought. Thx.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So, is 2^1000 hours acceptable?

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +30 Vote: I do not like it

        I'm waiting my trivial O(N!) solution already :-)

        → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I bet it requires at least 21000 bytes of memory. Only problem I can see is 1024-bit addressation.

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it +14 Vote: I do not like it

          I take it that 7 people don't have a sense of humor.

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it -16 Vote: I do not like it

            Hi if you take out printing the sequences . is possible to count the number of topological sorts?

            → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

Here is the code implementation using mask. certainly it will not help you but it works fine for smaller values.

→ Reply