Transitive Closure Calculator: Step-by-Step with Warshall's Algorithm

What is the transitive closure of a relation?

A relation R is transitive if whenever it contains (a, b) and (b, c) it also contains (a, c). The transitive closure of R is the smallest transitive relation that contains R: you keep R's pairs and add only the shortcut pairs that transitivity forces.

Think of R as arrows between elements. The transitive closure has an arrow from a to c exactly when you can get from a to c by following one or more arrows. That is why it answers “can A eventually reach B?” in graphs, ancestry trees and dependency lists.

How to find it: Warshall's algorithm

1. List the pairs of R. These are all kept in the answer.
2. Take the elements one at a time as an intermediate stop k. For every pair (i, k) and (k, j) already present, add (i, j) if it is missing.
3. After every element has been used as a stop, no further pairs can be added. The list is the transitive closure.

Worked example. Let A = {1, 2, 3, 4} and R = {(1,2), (2,3), (3,4), (4,2)}. Using each element as the intermediate stop in turn:

The transitive closure has 12 pairs. The elements 2, 3 and 4 form a loop (2 → 3 → 4 → 2), so each of them reaches all of 2, 3 and 4, including itself, while 1 reaches everything but is reached by nothing. The calculator above is set to this example.

The other closures it computes

• Reflexive closure: adds (a, a) for every element a of the set.
• Symmetric closure: adds the reverse (b, a) of every pair (a, b).
• Reflexive + transitive closure: the transitive closure with every (a, a) added. It means “reachable in zero or more steps”.

The set A matters: it decides which elements exist, and so which (a, a) pairs the reflexive closure must add.

Transitive closure versus a transitive relation

A relation either is transitive or is not; the closure is a new relation built from it. If R is already transitive, its transitive closure is R itself. If not, the closure is R plus the missing shortcut pairs. Taking the closure twice changes nothing.

Where the transitive closure is used

• Reachability in graphs: which vertices can be reached from which, in networks and state machines.
• Databases: recursive queries such as “all managers above this employee” are transitive closures of a manager-of relation.
• Dependency resolution: build systems and package managers need every direct and indirect dependency of an item.
• Permissions and inheritance: a group of a group of a group inherits access, which is a closure over “member of”.

Common mistakes

• Stopping after one pass. New shortcut pairs can create further shortcuts, so repeat until nothing new appears (Warshall's algorithm handles this by its ordering).
• Forgetting loops. In a cycle every element reaches itself, so pairs such as (2,2) belong in the closure.
• Adding pairs that are not forced by a chain. The closure is the smallest transitive relation, nothing more.
• Mixing up transitive and reflexive-transitive closure: only the second adds (a, a) for elements that are not on a cycle.