Author |
Topic: Number of paths in a DAG (Read 1698 times) |
|
howard roark
Full Member
Posts: 241
|
 |
Number of paths in a DAG
« on: Dec 27th, 2008, 1:11pm » |
 Quote  Modify
|
Design an algo to find out the number of paths between two vertices in a DAG
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Number of paths in a DAG
« Reply #1 on: Dec 27th, 2008, 1:52pm » |
Quote Modify
|
I could do it very easily and inefficient in prolog:
path(V1,V2, V1-V2):- edge(V1,V2).
path(V1,V2, P1+P2) :- path(V1, V3, P1), path(V3, V2, P2).
num_paths(V1, V2, N) :- findall(P, path(V1,V2,P), All_P), size(All_P, N).
You could do it more efficiently in another programming language using dynamic programming, by finding the paths through all nodes in between. The number of paths from A to B is the sum of paths from A to each node that leads to B in one single step. (So, say you can get from C,D and E to B in one step, then sum the paths from A to C, A to D and A to E). You can work backwards.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
howard roark
Full Member
Posts: 241
|
|
Re: Number of paths in a DAG
« Reply #2 on: Dec 27th, 2008, 3:28pm » |
Quote Modify
|
Suppose there are n vertices between A and B.
Doesnt the algorithm to find number of paths between A and B take O(n**3) time?
Finding all single length paths and then paths of length=2,......n. We do it for every pair of vertices in that n.
So O(n**3)
Can this be improved asymptotically?
|
| « Last Edit: Dec 27th, 2008, 3:35pm by howard roark » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Number of paths in a DAG
« Reply #3 on: Dec 28th, 2008, 2:10am » |
Quote Modify
|
on Dec 27th, 2008, 3:28pm, howard roark wrote:Suppose there are n vertices between A and B.
Doesnt the algorithm to find number of paths between A and B take O(n**3) time? |
|
Not if you do it properly. You can reuse information. At most it should be O(n2), and that's as many paths as there can be. Since it's a dag the nodes are partially ordered. There is always a next node which will not be encountered again, because there are no cycles. You can find the paths through those one at a time.
I suppose you could explicitly sort them, then for each node note the previous nodes that connect to it (adding all paths); and when you reach your destination node you should be done, I think. O(n2).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Number of paths in a DAG
« Reply #4 on: Dec 28th, 2008, 4:24pm » |
Quote Modify
|
Isn't it just F(end)=1, and F(x) =  x->y F(y)? It's O(m) if you memoize.
Or if you want to use a BFS instead: T(start)=1, and for each edge x->y, T(y) += T(x).
|
| « Last Edit: Dec 28th, 2008, 4:34pm by Eigenray » |
IP Logged |
|
|
|
howard roark
Full Member
Posts: 241
|
|
Re: Number of paths in a DAG
« Reply #5 on: Dec 28th, 2008, 4:59pm » |
Quote Modify
|
Quote:Isn't it just F(end)=1, and F(x) = x->y F(y)? It's O(m) if you memoize.
Or if you want to use a BFS instead: T(start)=1, and for each edge x->y, T(y) += T(x). |
|
O(n**2) , here n is number of vertices between source and destination.
I assume m is number of paths, which is O(n**2)
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Number of paths in a DAG
« Reply #6 on: Dec 28th, 2008, 5:45pm » |
Quote Modify
|
m is the number of edges, sorry.
The number of paths can be exponentially large, e.g., 3n -> 3n+1 -> 3n+3, 3n -> 3n+2 -> 3n+3.
|
|
IP Logged |
|
|
|
howard roark
Full Member
Posts: 241
|
|
Re: Number of paths in a DAG
« Reply #7 on: Dec 28th, 2008, 10:55pm » |
Quote Modify
|
Exponentially large??
I think it is possible only if two neighboring vertices have more than one edge connecting them.
Otherwise number of paths is O(n**2)
How do you guys write math expressions. Is there any plug-in for that?
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Number of paths in a DAG
« Reply #8 on: Dec 28th, 2008, 11:09pm » |
Quote Modify
|
on Dec 28th, 2008, 10:55pm, howard roark wrote:Exponentially large??
I think it is possible only if two neighboring vertices have more than one edge connecting them.
Otherwise number of paths is O(n**2) |
|
Take a graph with 3n+1 vertices {0,...,3n}, and edges (3i, 3i+1), (3i, 3i+2), (3i+1, 3i+3), (3i+2, 3i+3), for 0  i < n. There are 2 independent ways to get from 3i to 3(i+1) for each i, so there are 2n paths from 0 to 3n.
Quote:| How do you guys write math expressions. Is there any plug-in for that? |
|
SMQ wrote a script here that should work on all major browsers if you install the appropriate extension.
|
|
IP Logged |
|
|
|
howard roark
Full Member
Posts: 241
|
|
Re: Number of paths in a DAG
« Reply #9 on: Dec 28th, 2008, 11:24pm » |
Quote Modify
|
Sorry, I was thinking of number of edges. But I wrote about number of paths.
|
|
IP Logged |
|
|
|
howard roark
Full Member
Posts: 241
|
|
Re: Number of paths in a DAG
« Reply #10 on: Dec 28th, 2008, 11:28pm » |
Quote Modify
|
I think with n vertices in between A and B(exclusive) there can be atmost 2^n paths.
|
| « Last Edit: Dec 28th, 2008, 11:29pm by howard roark » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Number of paths in a DAG
« Reply #11 on: Dec 29th, 2008, 2:20am » |
Quote Modify
|
on Dec 28th, 2008, 11:28pm, howard roark wrote:| I think with n vertices in between A and B(exclusive) there can be atmost 2^n paths. |
|
I get 2n-2, if you have the maximum number of edges.
on Dec 28th, 2008, 4:24pm, Eigenray wrote:| Isn't it just F(end)=1, and F(x) = \sumx->y F(y)? It's O(m) if you memoize. |
|
I suppose it is...
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
howard roark
Full Member
Posts: 241
|
|
Re: Number of paths in a DAG
« Reply #12 on: Dec 29th, 2008, 2:50am » |
Quote Modify
|
Quote:I get 2n-2, if you have the maximum number of edges.
|
|
N is the number of vertices between A and B. It does not include either of them. So I think both of us got the same number
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Number of paths in a DAG
« Reply #13 on: Dec 29th, 2008, 3:19am » |
Quote Modify
|
on Dec 29th, 2008, 2:50am, howard roark wrote:| N is the number of vertices between A and B. It does not include either of them. So I think both of us got the same number |
|
Ah, yes.
I should read more closely..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print