transitiveClosure -- computes the transitive closure of a set of relations

Synopsis

• Usage:

  M = transitiveClosure(G, R)

• Inputs:
  • G, a list, the ground set
  • R, a list, pairs {$a,b$} which indicate that $a \leq b$
• Outputs:
  • M, a matrix, with entries $(i,j)$ equal to 1 if $G_j \leq G_i$ and 0 otherwise

Description

i1 : G = {1,2,3,4,5};

i2 : R = {{1,2}, {1,3}, {2,4}, {3,4}, {4,5}};

i3 : transitiveClosure(G, R)

o3 = | 1 1 1 1 1 |
     | 0 1 0 1 1 |
     | 0 0 1 1 1 |
     | 0 0 0 1 1 |
     | 0 0 0 0 1 |

              5        5
o3 : Matrix ZZ  <--- ZZ

See also

• poset -- creates a new Poset object