Is it possible to calculate how many Topological sortings exist for any given Graph?

Question

Is it possible to calculate for any given graph, how many topological sortings exist? In this previous question, it is explained for a certain graph but I'm wondering if there is a more general way for much more complicated graphs.

Answer 1

It's easy to provide a method for counting the topological sortings of a graph $G$:

0. If $G$ has 0 vertices, it has exactly 1 topological sorting. Otherwise...
1. Find the source vertices of $G$. (These are just the vertices with indegree 0.) If there are none, there are no topological sortings of $G$.
2. For each source vertex $s$ of $G$, let $t_s$ be the number of topological sortings of the simpler graph $G_s$ obtained by deleting $s$ from $G$.
3. The number you want is just the sum of the $t_s$ values.

Whether this is practical depends on how large $G$ was to begin with. But it's easy to implement for a computer. Here's an implementation of the principal algorithm:

# Python 3
def number_of_topological_sortings(graph):
    if len(graph.V) == 0: return 1
    else:
        return sum([ graph.without_vertex(source).number_of_topological_sortings()
                     for source in graph.sources() ])

With minor changes we can have it calculate a list of all possible sortings instead of a count:

# Python
def topological_sortings(graph):
    if len(graph.V) == 0:         # no vertices
        yield []
        return

    # otherwise there might be some source vertices
    for source_vertex in graph.source_vertices():
        g = graph.without_vertex(source_vertex)
        for ts in g.topological_sortings():
            yield [source_vertex] + ts
    return

I've put the complete program online.