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)]
15 '''Python implementation of Varol and Rotem (1979)
16 generate all linear extensions of a poset based on an initial valid linear extension
19 Yaakov L. Varol and Doron Rotem, An Algorithm to Generate All Topological Sorting Arrangements.
20 Computer J., 24 (1981) pp. 83-84.
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')
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
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
37 # The algorithm was written with list indicies starting at 1,
38 # so this implementation does the same. http://xkcd.com/163/
48 p[i:k+1] = [p[k]]+p[i:k] # roll-right a[i:k+1]
52 p[k],p[kk] = p[kk],p[k]
58 if __name__ == "__main__":
60 poset = [(1,2), (2,3), (1,5)]
61 grid = partial_order_to_grid(poset,n)
62 for le in vr_topsort(n,grid):