An answer to this question on Stack Overflow.

Question

I am writing a C program to find transitivity. In a 2D array, if adj[0][1] = 1 and adj[1][2] = 1, I want to mark adj[0][2] also as 1. This should hold for any transitive relation in the matrix.

Please help me with some code for this.

adj_matrix[j1][j2]=1;
	for(i=0;i<26;i++)
	{
		if (adj_matrix[i][j1])
		adj_matrix[i][j2]=1;
		
	}
	for(i=0;i<26;i++)
	{
		if(adj_matrix[j2][i])
		{
		adj_matrix[j1][i]=1;
		}
	}

Answer

What you want is a "transitive closure algorithm"

The Floyd-Warshall Algorithm is a good example of one of these, though there are many (many) others such as Johnson's Algorithm. A quick search on Google Scholar will point you towards some of the other sources and more technical descriptions.

The code for the Floyd-Warshall algorithm in its original form (which finds the shortest paths between every connected point) is:

int dist[N][N];  // For some N
int i, j, k;
// Input data into dist, where dist[i][j] is the distance from i to j.
// If the nodes are unconnected, dist[i][j] should be infinity
for ( k = 0; k < N; k++ )
for ( i = 0; i < N; i++ )
for ( j = 0; j < N; j++ )
   dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] );

Modifying this code for your use scenario gives:

int dist[N][N];  // For some N
int i, j, k;
// Input data into dist, where dist[i][j] is the distance from i to j.
// If the nodes are unconnected, dist[i][j] should be infinity
for ( k = 0; k < N; k++ )
for ( i = 0; i < N; i++ )
for ( j = 0; j < N; j++ )
   if(dist[i][k] && dist[k][j])
      dist[i][j] = 1;

Notice that the order of the subscripts here. Having the subscripts in this order fulfills a criterion of dynamic programming which ensures that the path is improved incrementally and is at all times optimal.

The time complexity is O(N^3).