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

Synopsis

• Usage:

  M = transitiveClosure(I,R)

• Inputs:

  • I, a list, ground set
  • R, a list, of pairs of elements in the ground set I.
• Outputs:

  • M, a matrix, whose (i,j) entry is 1 if (i,j) is a relation and 0 otherwise.

Description

i1 : I = {a,b,c,d,e}; -- the ground set

i2 : R = {(a,b),(b,c),(a,c),(a,d),(d,e)}; -- relations

i3 : transitiveClosure(I,R)

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

                5          5
o3 : Matrix RR    <--- RR
              53         53

Caveat

See also

• Poset -- a class for partially ordered sets (posets)
• poset -- creating a poset
• Relations -- a set of relations in the poset that generates all other relations
• RelationMatrix -- the matrix expressing all of the relations between elements in a Poset
• allPairsShortestPath -- computes lengths of shortest paths between all pairs in a directed graph