Re^2: find all paths of length n in a graph

Sorry for restarting a closed thread. Can this be updated to find acyclic paths. i.e. I don't get these :- 1,0,1,0 1,0,1,4 1,0,2,1 Yes I can eliminate them after I've found them but that would mean a lot of work. Thank You, Himanshu

Comment on Re^2: find all paths of length n in a graph

Replies are listed 'Best First'.
Re^3: find all paths of length n in a graph by Anonymous Monk on Sep 12, 2013 at 04:59 UTC
Depending on what you mean by acyclic paths, you might be able to. I would assume that if you can reach a point with a path of length 2, you don't want to count it again if you can reach it with a path of length 4. This situation might occur if these two points were a part of a path, and they could connect the short way--via two edges, or the long way--using 4 edges. In this case, just define an element wise subtraction operation and subtract all the shorter paths. Aka, calculate A^4 - A^3 - A^2 - A. You might be able to make this faster by leaving markers in your matrix. For example, if two points have been connected using a shorter path, place a -1 into the matrix and force your multiplication algorithm to copy it when the matrix is multiplied. I.e., -1 always maps to -1.	[reply]

Replies are listed 'Best First'.

Re^3: find all paths of length n in a graph
by Anonymous Monk on Sep 12, 2013 at 04:59 UTC

Depending on what you mean by acyclic paths, you might be able to. I would assume that if you can reach a point with a path of length 2, you don't want to count it again if you can reach it with a path of length 4. This situation might occur if these two points were a part of a path, and they could connect the short way--via two edges, or the long way--using 4 edges. In this case, just define an element wise subtraction operation and subtract all the shorter paths. Aka, calculate A^4 - A^3 - A^2 - A. You might be able to make this faster by leaving markers in your matrix. For example, if two points have been connected using a shorter path, place a -1 into the matrix and force your multiplication algorithm to copy it when the matrix is multiplied. I.e., -1 always maps to -1.

[reply]