Total number of topological sorts

Question

For a given DAG (directed acyclic graph), each of its topological sorts is a permutation of all vertices, where for every edges (u,v) in the DAG, u appears before v in the permutation.

Your task is to calculate the total number of topological sorts of a given DAG.

Rules

• You can use any format to represent the graph, like adjacency matrix, adjacency list or edge list, as long as you don't do useful computations in your encoding. You can also have things like vertex count or vertex list in the input, if those are useful.
• You can assume the graph in the input is always a DAG (doesn't have any cycles).
• Your program should work in theory for any input. But it can fail if it overflows the basic integer type in your language.
• The names of vertices can be any consecutive values in any type. For example: numbers starting at 0 or 1. (And only if you are not storing code in this number, of course.)
• This is code-golf. Shortest code wins.

Example

This is the same input in different formats. Your program don't have to accept all of them. Vertices are always integers starting at 0.

Adjacency list:
[ [1 2 3 5] [2 4] [] [2] [] [3] ]
Adjacency matrix:
[ [0 1 1 1 0 1] [0 0 1 0 1 0] [0 0 0 0 0 0] [0 0 1 0 0 0] [0 0 0 0 0 0] [0 0 0 1 0 0] ]
Edge list:
6 [ [0 1] [0 2] [0 3] [0 5] [1 2] [1 4] [3 2] [5 3] ]

It's the graph shown in this image:

The output should be:

9

The topological sorts are:

[0 1 4 5 3 2]
[0 1 5 4 3 2]
[0 1 5 3 4 2]
[0 1 5 3 2 4]
[0 5 1 4 3 2]
[0 5 1 3 4 2]
[0 5 1 3 2 4]
[0 5 3 1 4 2]
[0 5 3 1 2 4]

Answer 1

CJam - 25

q~{_f{1$-_j@j@&!*}_!+:+}j

With great help from user23013 :)

Try it online

Explanation:

The general algorithm is the same as in xnor's Python solution.
The key here is the j operator, which does memoized recursion. It takes a parameter, a value or array for the initial value(s) (as in f(0), f(1), etc) and a block to define the recursion. The j operator is used again inside the block for doing recursive (and memoized) calls to the same block. It can also be used with multiple parameters, but it's not the case here.
user23013's great innovation is to use j with different data types, making use of the adjacency list as the array of initial values.

q~             read and evaluate the input (vertex list followed by adjacency list)
{…}j           run the block on the vertex list, doing memoized recursion
                and using the adjacency list for initial values
    _          copy the vertex list
    f{…}       for each vertex and the vertex list
        1$-    copy the vertex and remove it from the list
                Python: "V-{v}"
        _j     copy the reduced list and call the j block recursively
                this solves the problem for the reduced vertex list
                Python: "f(G,V-{v})"
        @j     bring the vertex to the top of the stack and call the j block recursively
                in this case, it's called with a vertex rather than a list
                and the memoized value is instantly found in the list of initial values
                effectively, this gets the list of vertices adjacent to the current vertex
                Python: "G[v]"
        @&     bring the reduced list to the top of the stack and intersect
        !*     multiply the number of topological sorts of the reduced vertex list
                with 1 if the intersection was empty and 0 if not
                Python: equivalent to "*(V-G[v]==V)"
               after this loop we get an array of sub-results for the reduced vertex lists
    _!+        add 1 or 0 to the array if the array was empty or not
                because we want to get 1 for the empty array
                Python: equivalent to "V<{0}or"
    :+         add the numbers in the array
                Python: "sum(…)"

Answer 2

Python, 58

f=lambda G,V:V<{0}or sum(f(G,V-{v})*(V-G[v]==V)for v in V)

The input consists of an adjacency dictionary G and a vertex set V.

G = {0:{1,2,3,5}, 1:{2,4}, 2:set(), 3:{2}, 4:set(), 5:{3}, 6:set()}
V = {0,1,2,3,4,5}

The code is recursive. The set V stores all nodes that still need visiting. For each potential next node, we check its suitability by seeing if no remaining vertices point to it, with V-G[v]==V checking that V and G[v] are disjoint. For all suitable such vertices, we add the number of topological sorts with it removed. As a base case, the empty set gives 1.

Answer 3

Mathematica, 80 57 51 bytes

Count[Permutations@#,l_/;l~Subsets~{2}~SubsetQ~#2]&

Very straight-forward implementation of the definition. I'm just generating all permutations and count how many of them are valid. To check if a permutation is valid, I get all pairs of vertices in the permutation. Conveniently, Subsets[l,{2}] not only gives me all pairs, it also maintains the order they are found in in l - just what I need.

The above is a function that expects the vertex list and edge list, like

f[{1, 2, 3, 4, 5, 6}, {{1, 2}, {1, 3}, {1, 4}, {1, 6}, {2, 3}, {2, 5}, {4, 3}, {6, 4}}]

if you call the function f.

I'll try to golf this, or maybe use another approach later.

Answer 4

Haskell, 102 107 100 89 85 bytes

import Data.List
(%)=elemIndex
n#l=sum[1|p<-permutations[0..n],and[u%p<v%p|[u,v]<-l]]

The input is the highest vertex number (starting with 0) and an edge list, where an edge is a two element list. Usage example: 5 # [[0,1], [0,2], [0,3], [0,5], [1,2], [1,4], [3,2], [5,3]]

How it works: count all permutations p of the vertices for which all edges [u,v] satisfy: position of u in p is less than position of v in p. That's a direct implementation of the definition.

Edit: my first version returned the topological sorts themselves and not how many there are. Fixed it.

Edit II: didn't work for graphs with not connected vertices. Fixed it.

Answer 5

Pyth, 27 bytes

Mlf!sm}_dHfq2lYyTfqSZUZ^UGG

Defines a 2 input function, g. First input is the number of vertices, second is the list of directed edges.

To test:

Code:
Mlf!sm}_dHfq2lYyTfqSZUZ^UGGghQeQ

Input:
6, [ [0, 1], [0, 2], [0, 3], [0, 5], [1, 2], [1, 4], [3, 2], [5, 3] ]

Try it here.