[algogeeks] Re: Graph problem
On 11/30/07, John [EMAIL PROTECTED] wrote:
Given a DAG and two vertices s and t , give a linear time number of
paths between s and t in G.
How does topological sort help in finding the same ?
Hi Joh,
you can do a dynamic programming algorithm Your state is S[x] = number
of path going from s to x, s is the initial vertex. It's easy to see
that equation holds :
S[x] = sum { S[v], for all v neighbor of x }
Think about base cases and make a memorized function to get the answer.
Hope this help,
Caio
--~--~-~--~~~---~--~~
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
Just to clarify, you are looking for a linear time algorithm that counts all s-t paths (not necessarily disjoint) in a DAG? On Nov 29, 10:35 pm, John [EMAIL PROTECTED] wrote: Given a DAG and two vertices s and t , give a linear time number of paths between s and t in G. How does topological sort help in finding the same ? --~--~-~--~~~---~--~~ 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
Just use BFS, its running time is O(V+E). In our case, there's no cycle in DAG so, E=V-1 always. John wrote: Given a DAG and two vertices s and t , give a linear time number of paths between s and t in G. How does topological sort help in finding the same ? --~--~-~--~~~---~--~~ 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
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
-~--~~~~--~~--~--~---
[algogeeks] Re: Graph Problem
Can it be a solution? At first let us think all the edges are undirected. That is if a adjacent to b then both a-b and b-a are present. then we discard a-b if a is the current vertex with maximum outdegree and b is its adjacent with minimum outdegree and b-a is present we continue it again and again untill all the extra edges are removed. will it work? --~--~-~--~~~---~--~~ 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
Ohh, sorry to have missed that information. Consider minimizing the maximum out-degree. On May 16, 5:04 pm, Rajiv Mathews [EMAIL PROTECTED] wrote: Could you please explain the question. Typically in a directed graph we talk of in-degree and out-degree for a vertex. So is the question then to minimize the maximum of these in all vertices of the graph? If so what operations are permitted? On 5/16/07, pramod [EMAIL PROTECTED] wrote: Here's a graph problem. We are given a directed graph. We are allowed to change the directions of the edges. Our aim is to minimize the maximum degree in the graph. How do we achieve this? One way is to take the vertex with maximum degree, and take another vertex with least degree reachable from this max-degree vertex and then reverse all the edges' direction along the path. Now the questions with this approach are (1) how do we prove that this will lead to the optimal-graph in the sense, can we get a graph such that it's maximum degree is the best possible? (2) What's the time complexity, is it bound tightly? (3) Is there any better way? Thanks -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ 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
Could you please explain the question. Typically in a directed graph we talk of in-degree and out-degree for a vertex. So is the question then to minimize the maximum of these in all vertices of the graph? If so what operations are permitted? On 5/16/07, pramod [EMAIL PROTECTED] wrote: Here's a graph problem. We are given a directed graph. We are allowed to change the directions of the edges. Our aim is to minimize the maximum degree in the graph. How do we achieve this? One way is to take the vertex with maximum degree, and take another vertex with least degree reachable from this max-degree vertex and then reverse all the edges' direction along the path. Now the questions with this approach are (1) how do we prove that this will lead to the optimal-graph in the sense, can we get a graph such that it's maximum degree is the best possible? (2) What's the time complexity, is it bound tightly? (3) Is there any better way? Thanks -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
