Transitive Closure

The transitive closure of a graph G = (V, E) is the graph G’ = (V, E’) such that E’ contains an edge (u, v) if and only if there is a path from u to v in G. Intuitively, it captures all reachability relationships between nodes in the original graph.

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
boolean[][] transitiveClosure(int[][] graph) {
  int V = graph.length;
  boolean[][] tc = new boolean[V][V];  

  for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++) {
      if (graph[i][j] == 1) {
        tc[i][j] = true; 
      }
    }
  }

  for (int k = 0; k < V; k++) {
    for (int i = 0; i < V; i++) {
      for (int j = 0; j < V; j++) {
        tc[i][j] |= tc[i][k] && tc[k][j];  
      }
    }
  }

  return tc;
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<vector<bool>> transitiveClosure(vector<vector<int>> graph) {
  int V = graph.size();
  vector<vector<bool>> tc(V, vector<bool>(V, false));

  for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++) {
      if (graph[i][j] == 1) {
        tc[i][j] = true;
      } 
    }
  }

  for (int k = 0; k < V; k++) {
    for (int i = 0; i < V; i++) {
      for (int j = 0; j < V; j++) {
        tc[i][j] |= tc[i][k] && tc[k][j];
      }
    }
  }

  return tc;
}

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def transitive_closure(graph):
  V = len(graph)
  tc = [[False] * V for _ in range(V)]

  for i in range(V):
    for j in range(V):
      if graph[i][j]:
        tc[i][j] = True
  
  for k in range(V):
    for i in range(V):
      for j in range(V):
        tc[i][j] |= tc[i][k] and tc[k][j]
  
  return tc

The key steps are:

Initialize reachability matrix
Populate direct reachability from graph
Use Floyd-Warshall to populate transitive closure

Finding the transitive closure allows determining all ancestry relationships in a graph through path composition. It can be done in O(V^3) time.

Reachability Relationship

Transitive closure is a graph algorithm concept, but the notion of computing reachability relationships transitively can be applied to other data structures as well:

Trees: The ancestry relationship forms a transitive closure on tree nodes. We can compute the transitive closure of a tree by finding all ancestors of each node.

Collections: In a hierarchical collection of items, we can compute the transitive closure of the “contains” relationship. This will find all containers reachable from each item.

State machines: The transition function of a finite state machine induces a directed graph over states. We can find the transitive closure to determine all states reachable from a given state.

Relations: Any binary relation R induces a directed graph where vertices are related by R. The transitive closure of R contains all ordered pairs (x,y) such that x is related to y directly or through a sequence of relations.

Networks: Just like with graphs, we can compute the transitive closure of connectivity and routing relationships in a network. This finds all nodes reachable from each node.

The core ideas extend naturally to computing the full reachability relation induced by various hierarchical and networked data structures and systems. The algorithms carry over with only minor adjustments to handle semantics.

Concept of Transitive Closure

Transitive Closure of a graph is a concept that extends the notion of transitive relationships to graphs. Given a graph (G), the transitive closure (T) is a new graph where an edge ( (A, C) ) exists if there is a path from vertex ( A ) to vertex ( C ) in (G). This ensures that if you can get from ( A ) to ( C ) via any number of intermediate vertices in (G), there should be a direct edge from ( A ) to ( C ) in ( T ).

This concept is useful in various applications, including network reachability, ontology reasoning, and social network analysis. The most common algorithm to find the transitive closure is the Floyd-Warshall algorithm.

Example Code

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class TransitiveClosure {
  public static void floydWarshall(int[][] graph) {
    int V = graph.length;
    int[][] closure = new int[V][V];

    // Initialize closure matrix
    for (int i = 0; i < V; i++) {
      for (int j = 0; j < V; j++) {
        closure[i][j] = graph[i][j];
      }
    }

    // Update closure matrix
    for (int k = 0; k < V; k++) {
      for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
          closure[i][j] = closure[i][j] | (closure[i][k] & closure[k][j]);
        }
      }
    }
  }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>

void floydWarshall(std::vector<std::vector<int>> graph) {
  int V = graph.size();
  std::vector<std::vector<int>> closure(V, std::vector<int>(V));

  // Initialize closure matrix
  for (int i = 0; i < V; ++i) {
    for (int j = 0; j < V; ++j) {
      closure[i][j] = graph[i][j];
    }
  }

  // Update closure matrix
  for (int k = 0; k < V; ++k) {
    for (int i = 0; i < V; ++i) {
      for (int j = 0; j < V; ++j) {
        closure[i][j] = closure[i][j] | (closure[i][k] & closure[k][j]);
      }
    }
  }
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def floyd_warshall(graph):
  V = len(graph)
  closure = [[0 for _ in range(V)] for _ in range(V)]

  # Initialize closure matrix
  for i in range(V):
    for j in range(V):
      closure[i][j] = graph[i][j]

  # Update closure matrix
  for k in range(V):
    for i in range(V):
      for j in range(V):
        closure[i][j] = closure[i][j] or (closure[i][k] and closure[k][j])

Key Takeaways

Algorithm Choice: The Floyd-Warshall algorithm is commonly used for calculating the transitive closure of a graph. It iterates through all pairs of vertices to update their reachability.
Bitwise Operations: The example uses bitwise OR and AND to update the closure matrix efficiently.
Initial Matrix: The initial matrix is a copy of the adjacency matrix of the graph. It gets updated to represent transitive closure.
Graph Representation: The graph is represented as an adjacency matrix, which makes the algorithm more straightforward to implement.

Understanding the transitive closure of a graph can provide you with insights into the properties and structure of networks, making it a valuable concept in fields like computer science, mathematics, and data analysis.