## Friday, March 18, 2016

### Transitive closure of a graph - GeeksforGeeks

Transitive closure of a graph - GeeksforGeeks
Given a directed graph, find out if a vertex j is reachable from another vertex i for all vertex pairs (i, j) in the given graph. Here reachable mean that there is a path from vertex i to j. The reach-ability matrix is called transitive closure of a graph.

```
Transitive closure of above graphs is
1 1 1 1
1 1 1 1
1 1 1 1
0 0 0 1 ```
Floyd Warshall Algorithm can be used, we can calculate the distance matrix dist[V][V] using Floyd Warshall, if dist[i][j] is infinite, then j is not reachable from i, otherwise j is reachable and value of dist[i][j] will be less than V.
Instead of directly using Floyd Warshall, we can optimize it in terms of space and time, for this particular problem. Following are the optimizations:
1) Instead of integer resultant matrix (dist[V][V] in floyd warshall), we can create a boolean reach-ability matrix reach[V][V] (we save space). The value reach[i][j] will be 1 if j is reachable from i, otherwise 0.
2) Instead of using arithmetic operations, we can use logical operations. For arithmetic operation ‘+’, logical and ‘&&’ is used, and for min, logical or ‘||’ is used. (We save time by a constant factor. Time complexity is same though)

`    ``final` `static` `int` `V = ``4``; ``//Number of vertices in a graph`

`    ``// Prints transitive closure of graph[][] using Floyd`
`    ``// Warshall algorithm`
`    ``void` `transitiveClosure(``int` `graph[][])`
`    ``{`
`        ``/* reach[][] will be the output matrix that will finally`
`           ``have the shortest  distances between every pair of`
`           ``vertices */`
`        ``int` `reach[][] = ``new` `int``[V][V];`
`        ``int`  `i, j, k;`

`        ``/* Initialize the solution matrix same as input graph`
`           ``matrix. Or  we can say the initial values of shortest`
`           ``distances are based  on shortest paths considering`
`           ``no intermediate vertex. */`
`        ``for` `(i = ``0``; i < V; i++)`
`            ``for` `(j = ``0``; j < V; j++)`
`                ``reach[i][j] = graph[i][j];`

`        ``/* Add all vertices one by one to the set of intermediate`
`           ``vertices.`
`          ``---> Before start of a iteration, we have reachability`
`               ``values for all  pairs of vertices such that the`
`               ``reachability values consider only the vertices in`
`               ``set {0, 1, 2, .. k-1} as intermediate vertices.`
`          ``----> After the end of a iteration, vertex no. k is`
`                ``added to the set of intermediate vertices and the`
`                ``set becomes {0, 1, 2, .. k} */`
`        ``for` `(k = ``0``; k < V; k++)`
`        ``{`
`            ``// Pick all vertices as source one by one`
`            ``for` `(i = ``0``; i < V; i++)`
`            ``{`
`                ``// Pick all vertices as destination for the`
`                ``// above picked source`
`                ``for` `(j = ``0``; j < V; j++)`
`                ``{`
`                    ``// If vertex k is on a path from i to j,`
`                    ``// then make sure that the value of reach[i][j] is 1`
`                    ``reach[i][j] = (reach[i][j]!=``0``) ||`
`                             ``((reach[i][k]!=``0``) && (reach[k][j]!=``0``))?``1``:``0``;`
`                ``}`
`            ``}`
`        ``}`

`        ``// Print the shortest distance matrix`
`        ``printSolution(reach);`
`    ``}`