How can I implement the Algorithm I have explained below?

Question

Hi, How ca I Implement the algorithm for calculating the transitive closure given a set of functional dependencies? I have sent the detail of this algorithm in a ZIP file.

Farhan Shariff · Answer

/* 1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) 2 for each vertex v 3 dist[ v ][ v ] ← 0 4 for each edge ( u , v ) 5 dist[ u ][ v ] ← w( u , v ) // the weight of the edge ( u , v ) 6 for k from 1 to |V| 7 for i from 1 to |V| 8 for j from 1 to |V| 9 if dist[ i ][ j ] > dist[ i ][ k ] + dist[ k ][ j ] 10 dist[ i ][ j ] ← dist[ i ][ k ] + dist[ k ][ j ] 11 end if */ #include // Number of vertices in the graph #define V 4 // A function to print the solution matrix void printSolution(int reach[][V]); void transitiveClosure(int graph[][V]) { /* reach[][] will be the output matrix that will finally have the shortest distances between every pair of vertices */ int reach[V][V], 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 for (j = 0; 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, .. k} */ for (k = 0; k { // Pick all vertices as source one by one for (i = 0; i { // Pick all vertices as destination for the // above picked source for (j = 0; 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] || (reach[i][k] && reach[k][j]); } } } // Print the shortest distance matrix printSolution(reach); } /* A utility function to print solution */ void printSolution(int reach[][V]) { printf ("Following matrix is transitive closure of the given graph
"); for (int i = 0; i { for (int j = 0; j printf ("%d ", reach[i][j]); printf("
"); } } int main() { int graph[V][V] = { {1, 1, 0, 1}, {0, 1, 1, 0}, {0, 0, 1, 1}, {0, 0, 0, 1} }; // Print the solution transitiveClosure(graph); return 0; }

Ranjan Dailata · Answer

We generally don't do home work. Let us know what effort you have put. Take a look into the available solutions - http://www.sanfoundry.com/cpp-program-find-transitive-closure-graph/