Transitivity

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

Transitive closure means the augmentation of a graph’s edge set such that an existing path between any two nodes, which are not direct neighbors to each other, leads to an additional edge connecting these nodes.

In effect, this means that any two nodes that are reachable by a path of arbitrary length before the augmentation, are instantly reachable thereafter, i.e., they are direct neighbors.

In Transitive closure of a graph a simple graph together with its transitive closure is depicted. The additionally inserted edges are dotted. For example, the dotted edge between Start and e has been inserted to reflect even multiple possible paths from Start to e: [a, b, e], [a, d, e], or [c, d, e] are all existing paths.

Note that class TransitiveClosure computes only the transitive, but not the reflexive, transitive closure. However, the latter one can easily be achieved by adding self-loops to each node.

Calculating the Transitive Closure shows the code used to calculate the edges that need to be added to get the transitive closure of a graph. edgesToAdd contains instances of class TransitiveEdge which only holds references to the source and target nodes between which an edge has to be created.

// 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 means the removal of all directly connecting edges from a graph as long as there remains another path of at least two edges length between the two considered nodes.

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

Calculating the Transitive Reduction shows the code used to calculate the edges that need to be removed 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 are not related to the two above approaches. It can be applied if some nodes should be removed/hidden from the graph, and the transitive relations between the remaining visible nodes should be maintained. Note that 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. More precisely, when node b should be 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 gets lost.