transitive Closure Algorithm

The transitive closure algorithm is a graph theory technique used to determine the reachability of nodes within a directed graph. It is a computational method that finds all possible paths between any pair of nodes in the graph, considering the transitive property. In other words, if a path exists from node A to node B, and from node B to node C, then the transitive closure of the graph will include a path from node A to node C. This process is repeated for all pairs of nodes in the graph, ultimately providing a comprehensive representation of the relationships between the nodes. There are several algorithms used to compute the transitive closure of a graph, with the most well-known being the Floyd-Warshall algorithm and the Warshall algorithm. These algorithms make use of dynamic programming and matrix manipulations to efficiently compute the transitive closure. The Floyd-Warshall algorithm, in particular, has a time complexity of O(n^3) for a graph with n nodes, making it suitable for graphs with a moderate number of nodes. The transitive closure algorithm has various applications in computer science, including solving problems in databases, artificial intelligence, and network analysis.
#include <stdio.h>
#include <stdbool.h>

#define NODES 4

int digraph[NODES][NODES]={ {0,1,1,1}, {1,0,1,0}, {0,1,0,0}, {0,0,0,0} };
int tc[NODES][NODES];

void warshall() {
   int i, s, t;
   for (s = 0; s < NODES; s++)
      for (t = 0; t < NODES; t++)
	 tc[s][t] = digraph[s][t];

   for (i = 0; i < NODES; i++)
      for (s = 0; s < NODES; s++)
	 for (t = 0; t < NODES; t++)
	    if (tc[s][i] && tc[i][t])
	       tc[s][t] = 1;
}

int main(void) {
   warshall();
   int i, j;
   for (i = 0; i < NODES; i++) {
      for (j = 0; j < NODES; j++) {
	 printf("%d ", tc[i][j]);
      }
      putchar('\n');
   }
   return 0;
}

// By 
//  .----------------.  .----------------.  .----------------.  .-----------------.  .----------------.  .----------------. 
// | .--------------. || .--------------. || .--------------. || .--------------. | | .--------------. || .--------------. |
// | |  _________   | || | _____  _____ | || |      __      | || | ____  _____  | | | |  ____  ____  | || |     ____     | |
// | | |  _   _  |  | || ||_   _||_   _|| || |     /  \     | || ||_   \|_   _| | | | | |_   ||   _| | || |   .'    `.   | |
// | | |_/ | | \_|  | || |  | |    | |  | || |    / /\ \    | || |  |   \ | |   | | | |   | |__| |   | || |  /  .--.  \  | |
// | |     | |      | || |  | '    ' |  | || |   / ____ \   | || |  | |\ \| |   | | | |   |  __  |   | || |  | |    | |  | |
// | |    _| |_     | || |   \ `--' /   | || | _/ /    \ \_ | || | _| |_\   |_  | | | |  _| |  | |_  | || |  \  `--'  /  | |
// | |   |_____|    | || |    `.__.'    | || ||____|  |____|| || ||_____|\____| | | | | |____||____| | || |   `.____.'   | |
// | |              | || |              | || |              | || |              | | | |              | || |              | |
// | '--------------' || '--------------' || '--------------' || '--------------' | | '--------------' || '--------------' |
//  '----------------'  '----------------'  '----------------'  '----------------'   '----------------'  '----------------' 
 
//  Email :    z5261243@unsw.edu.au
//             hhoanhtuann@gmail.com

LANGUAGE:

DARK MODE: