[algogeeks] Re: graph problem : i need help
Not sure about what's wrong with your code is but the answer to the problem is Warshall's algorithm for graph closure. Just to brief, say we are given the adjacency matrix A[1] where A[1][i] [j] = 1 if there's an edge from i to j. Let A[k][i][j] be the the number of paths from i to j passing through only vertices numbered from 1..k. Then note that A[k][i][j] = A[k-1][i][j] + A[k-1][i][k] * A[k-1][k] [j]. i.e., the number of paths from i to j passing through only vertices numbered 1...k is equal to number of paths from i to k passing through vertices numbered 1...k-1 PLUS number of paths from i to k (with vertices 1...k-1) and k to j (with vertices 1..k-1). What we want is the A[n] matrix which has the number of paths between every pair of vertices. But by any chance A[n][i][i] 0 for any 'i' that means there's a loop and i is a part of that loop. So this means there are infinite ways to reach i from i and hence infinite ways to reach from i to j if there's a way to reach from i to j. Hope that helps. I will paste the code once I am done with it. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: graph problem : i need help
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 algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
