Here's the code.
void Closure(int **a, int v) //a is the given adjacency matrix and v
is the number of vertices
{
int **t1 = new int*[v];
int **t2 = new int*[v];
for(int i = 0; i < v; ++i)
{
t1[i] = new int[v];
t2[i] = new int[v];
for(int j = 0; j < v; ++j)
t1[i][j] = a[i][j];
}
int **p1 = t1, **p2 = t2, **t;
for(int k = 0; k < v; ++k)
{
for(int i = 0; i < v; ++i)
for(int j = 0; j < v; ++j)
p2[i][j] = p1[i][j] + (p1[i][k] * p1[k][j]);
//to count the number
of paths
//swap p1, p2
t = p1; p1 = p2; p2 = t;
}
//if p1[i][i] != 0, then there is a path from i to i itself which is
a loop so there are infinite paths from i to j if there's one path
from i to j
for(int i = 0; i < v; ++i)
{
if (p1[i][i] != 0)
{
p1[i][i] = -1; //-1 means loop and hence infinite paths
for(int j = 0; j < v; ++j)
p1[i][j] = p1[i][j] ? -1 : p1[i][j];
}
}
for(int i = 0; i < v; ++i)
for(int j = 0; j < v; ++j)
a[i][j] = p1[i][j];
//array a now has the number of paths
}
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
