digraphtools/topsort.py

   1 #! /usr/bin/env python
   2
   3 def partial_order_to_grid(poset, n):
   4         '''poset is given in 2tuples of indexes into a list containing a linear extension
   5         as the indicies are into a list containing a valid topological sort,
   6         i must be < j for every (i,j) in the poset'''
   7         grid = [[False for j in xrange(n+1)]+[True] for i in xrange(n+2)]
   8         for i,j in poset:
   9                 assert i<j
  10                 grid[i][j] = True
  11                 grid[j][i] = True
  12         return grid
  13
  14 def vr_topsort(n, m):
  15         '''Python implementation of Varol and Rotem (1979)
  16         generate all linear extensions of a poset based on an initial valid linear extension
  17         as described in
  18
  19          Yaakov L. Varol and Doron Rotem, An Algorithm to Generate All Topological Sorting Arrangements.
  20             Computer J., 24 (1981) pp. 83-84.
  21
  22         the 'seed' topological sort is mapped to integers from [1..n]
  23         e.g. given nodes {a,b,c,d}, with the partial order of {(c,a),(b,a),(a,d)}
  24         one valid topological ordering is c,b,a,d.  We then map 1=c 2=b 3=a 4=d
  25         such that cbad is represented as 1234. The partial order is now
  26         {(1,3),(2,3),(3,4)} (which can be passed to partial_order_to_grid to generate
  27         the incidence matrix 'm')
  28
  29         n is the number of nodes in the set the partial order is across
  30         m is the incidence matrix of the binary relations after mapping to integers
  31         '''
  32         # n is the number of nodes in the DAG
  33         # m is a table (2d array) of bools giving the adjacency matrix
  34         #       (n rows of n+1, indexed from 1).
  35         #       There is also a terminating 'True' at the end of each row
  36
  37         # The algorithm was written with list indicies starting at 1,
  38         # so this implementation does the same. http://xkcd.com/163/
  39         loc = range(n+1)
  40         p = range(n+2)
  41         yield p[1:n+1]
  42         i = 1
  43         k = 1
  44         while i < n:
  45                 k = loc[i]
  46                 kk = k + 1
  47                 if m[i][p[kk]]:
  48                         p[i:k+1] = [p[k]]+p[i:k] # roll-right a[i:k+1]
  49                         loc[i] = i
  50                         i += 1
  51                 else:
  52                         p[k],p[kk] = p[kk],p[k]
  53                         loc[i] = kk
  54                         i = 1
  55                         yield p[1:n+1]
  56
  57
  58 if __name__ == "__main__":
  59         n = 5
  60         poset = [(1,2), (2,3), (1,5)]
  61         grid = partial_order_to_grid(poset,n)
  62         for le in vr_topsort(n,grid):
  63                 print le