-
Notifications
You must be signed in to change notification settings - Fork 16
Expand file tree
/
Copy pathTransitive_Closure.java
More file actions
89 lines (77 loc) · 2.85 KB
/
Transitive_Closure.java
File metadata and controls
89 lines (77 loc) · 2.85 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
package graphs;
// Problem Title => Program for transitive closure using Floyd Warshall Algorithm
import java.lang.*;
class GraphClosure {
//Number of vertices in a graph
final static int V = 4;
// 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 short est 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 an 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 an 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);
}
/* A utility function to print solution */
void printSolution(int[][] reach) {
System.out.println("Following matrix is transitive closure"+ " of the given graph");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if ( i == j)
System.out.print("1 ");
else
System.out.print(reach[i][j]+" ");
}
System.out.println();
}
}
// Driver Code
public static void main (String[] args) {
/* Let us create the following weighted graph
10
(0)------->(3)
| /|\
5 | |
| | 1
\|/ |
(1)------->(2)
3 */
/* Let us create the following weighted graph
10
(0)------->(3)
| /|\
5 | |
| | 1
\|/ |
(1)------->(2)
3 */
int[][] graph = new int[][]{ {1, 1, 0, 1},
{0, 1, 1, 0},
{0, 0, 1, 1},
{0, 0, 0, 1}
};
// Print the solution
GraphClosure g = new GraphClosure();
g.transitiveClosure(graph);
}
}