2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sure it is possible: Make a list of every order of the vertices. Check each one to see if it is properly sorted, and cross it off the list if not. Count the ones that remain. $\endgroup$ – MJD May 10 '19 at 10:36
  • $\begingroup$ Or, perhaps more efficiently, do depth-first searching on the graph, starting from the source nodes, counting each complete topological order as you find it. $\endgroup$ – MJD May 10 '19 at 10:38
  • $\begingroup$ math.stackexchange.com/questions/2933640 $\endgroup$ – Misha Lavrov May 10 '19 at 21:19
3
$\begingroup$

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

  1. If $G$ has 0 vertices, it has exactly 1 topological sorting. Otherwise...
  2. 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$.
  3. 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$.
  4. 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.