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.
It's easy to provide a method for counting the topological sortings of a graph $G$:
- If $G$ has 0 vertices, it has exactly 1 topological sorting. Otherwise...
- 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$.
- 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$.
- 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