Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 68 ยท Sets, Relations and Functions

Closures of Relations and Warshall's Algorithm

Build the reflexive, symmetric and transitive closure of a relation, understand reachability and compute transitive closure with Warshall's algorithm in Python.

A relation may almost have a property. A road network might connect most cities in both directions but miss one return road. A friendship list might be nearly transitive. The closure of a relation answers: what is the smallest set of extra pairs we must add so that the relation gains the property?

Closures are everywhere in computing. The transitive closure is reachability: "can data flow from A to Z?", "does module X depend, directly or not, on module Y?", "is this person in my extended network?" In this lesson you will build each closure by hand, then learn Warshall's algorithm, a compact method that computes the transitive closure in three nested loops.

What a closure is

Let R be a relation on a set A and let P be a property (reflexive, symmetric or transitive). The P-closure of R is the relation S such that:

  1. S contains R,
  2. S has property P,
  3. S is contained in every other relation that contains R and has property P.

Condition 3 says "smallest". Not every property has a closure: there is no "antisymmetric closure", because adding pairs can only destroy antisymmetry. The three properties from Relations all do.

Reflexive and symmetric closure

These two are easy, because each missing pair can be read off directly.

  • Reflexive closure: add (a, a) for every a in A. In symbols, R โˆช ฮ” where ฮ” = {(a, a) : a โˆˆ A} is the diagonal.
  • Symmetric closure: add (b, a) for every (a, b) in R. In symbols, R โˆช Rโปยน, where the inverse flips every pair.
Python Reflexive and symmetric closure

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that (3, 3) was already present, so only three diagonal pairs are new, and the symmetric closure adds three mirror pairs but skips (3, 3), whose mirror is itself.

Transitive closure is harder

Adding the missing shortcuts for transitivity can create new chains that need new shortcuts. For R = {(1,2), (2,3), (3,4)} the first round adds (1,3) and (2,4), but now (1,3) and (3,4) demand (1,4). The closure is complete only when a full pass adds nothing.

Think of R as a directed graph (see Graph Basics). Then (a, b) is in the transitive closure Rโบ exactly when there is a path of length at least 1 from a to b. This gives a second formula using composition:

Rโบ = R โˆช Rยฒ โˆช Rยณ โˆช ... โˆช Rโฟ, where n = |A|

Paths longer than n revisit a vertex, so you never need more than n steps.

Three closures, three recipes

Reflexive Add every pair (a, a).
Symmetric Add the mirror of every pair.
Transitive Add a shortcut for every path.

Each closure is the smallest relation that has the property and contains R.

1 / 2
Python Transitive closure by repeated composition

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Squaring the relation in each round doubles the path length covered, so even long chains settle in few rounds.

Warshall's algorithm

Warshall's algorithm uses a cleverer idea: allow the intermediate stops one vertex at a time. Number the vertices 1..n. Let W_k[i][j] be true if a path from i to j exists whose intermediate vertices all come from {1, ..., k}. Then:

W_k[i][j] = W_{k-1}[i][j] OR (W_{k-1}[i][k] AND W_{k-1}[k][j])

In words: after allowing vertex k as a stop, i reaches j if it already did, or if it reaches k and k reaches j. Start with W_0 equal to the adjacency matrix and finish with W_n, the transitive closure. Updating one matrix in place is enough, giving three nested loops and O(nยณ) time.

Python Warshall's algorithm on a matrix

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the output, a reaches b, c and d but nothing reaches a, and each of b, c, d reaches all three (including itself, because of the cycle). Notice that the diagonal entry for a stays empty: the transitive closure does not make a relation reflexive. If you want both, take the reflexive transitive closure by adding the diagonal afterwards; this is the relation "reachable in zero or more steps".

Combining closures

Order matters when you combine them. The equivalence closure of a relation (the smallest equivalence relation containing it, as in Equivalence Relations and Partial Orders) is computed by taking the reflexive closure, then the symmetric closure, then the transitive closure. Doing transitive before symmetric can miss pairs, since adding mirror pairs creates new chains.

Python Equivalence closure groups connected items

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The classes {1, 2, 3}, {4, 5} and appear: the equivalence closure merges everything linked by any chain.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the symmetric closure of R = {(1, 2), (2, 2)} on {1, 2}?

    Add the mirror (2, 1). The pair (2, 2) is its own mirror, and no diagonal pair (1, 1) is needed for symmetry.
  2. 2. In graph terms, what does (a, b) in the transitive closure mean?

    Transitive closure is reachability by paths of at least one edge.
  3. 3. What is the running time of Warshall's algorithm on n vertices?

    Three nested loops over n vertices each give n cubed steps.
  4. 4. Why is there no antisymmetric closure?

    A relation containing both (a, b) and (b, a) with a different from b cannot be fixed by adding more pairs.

Summary

  • The P-closure of R is the smallest relation containing R that has property P.
  • Reflexive closure: add the diagonal. Symmetric closure: add every mirror pair. Transitive closure: add shortcuts until stable.
  • The transitive closure is reachability: R plus all paths of length two or more.
  • Warshall's algorithm adds one allowed intermediate vertex at a time and runs in O(nยณ).
  • Reflexive, then symmetric, then transitive closure gives the smallest equivalence relation containing R.

Continue with Partial Orders, Hasse Diagrams and Lattices.