Transitivity

The algorithms TransitiveClosure and TransitiveReduction offer sophisticated computational services related to reachability questions in directed acyclic graphs.

Transitive closure augments a graph’s edge set. If there is an existing path between two nodes that are not directly connected, an edge is added to connect them.

In effect, this means that any two nodes reachable by a path of arbitrary length before the augmentation become directly connected.

Transitive closure of a graph shows a simple graph and its transitive closure. The added edges are dotted. For example, the dotted edge between Start and e represents the multiple paths from Start to e: [a, b, e], [a, d, e], or [c, d, e].

Note that class TransitiveClosure computes only the transitive closure, not the reflexive transitive closure. However, you can easily achieve the reflexive transitive closure by adding self-loops to each node.

Calculating the Transitive Closure shows the code that calculates the edges to add to get the transitive closure of a graph. edgesToAdd contains instances of TransitiveEdge, which holds references to the source and target nodes that an edge must be created between.

// run the transitive closure algorithm
const transitiveClosureResult = new TransitiveClosure().run(graph)
// create an IEdge for each returned Edge
transitiveClosureResult.edgesToAdd.forEach((edge) => {
  graph.createEdge(edge.source, edge.target)
})

Transitive reduction is the reverse operation to transitive closure. It removes directly connecting edges from a graph if there is another path of at least two edges between the two nodes.

Transitive reduction of a graph shows a simple graph and its transitive reduction.

Calculating the Transitive Reduction shows the code that calculates the edges to remove to get the transitive reduction of a graph.

// run the transitive reduction algorithm
const transitiveReductionResult = new TransitiveReduction().run(graph)
// remove all surplus edges
transitiveReductionResult.edgesToRemove.forEach((edge) => {
  graph.remove(edge)
})

Transitive edges is not related to the two above approaches. It can be applied if some nodes should be removed or hidden from the graph and the transitive relations between the remaining visible nodes should be maintained. A transitive edge between two nodes is only created if there is not already an edge between them.

Transitive edges of a graph shows a simple graph and its transitive edges. If node b is removed from the input graph, the algorithm creates the two dashed edges to show the transitive connection of node a to nodes c and d. Without applying the algorithm before removing node b, this information is lost.