I have a graph $G$, which may be directed or not, and I was wondering if there was an efficient way of using, say, BreadthFirstScan[] and FindShortestPath[] to count the number of paths between some source vertex, $v(a)$, some sink vertex, $v(b)$, of a certain length $D$?

As of right now, I'm simply sequentially running through all of the vertices in my graph, applying FindShortestPath[] to determine the distance of the vertex to my source and sink vertices, and then seeing if the total distance is $D$. If the total path distance is in fact $D$, I then put the path in a list which is later pruned for redundant paths or paths that revisit vertices.

Assuming I have plenty of memory to spare, is there a better / faster solution?

Let me better specify what I'm looking for -

Provided an undirected or directed graph $G$, I want to count the number of possible ordered sets, $(q_1,...,q_N)$, of all-unique vertices, $(v_{source}, ..., v_{sink}) \in q_i$, that one must visit to move from a source vertex, $v(source)$ to a sink vertex, $v(sink)$ s.t. $||q_i|| = D$ for all $q_i$, i.e. s.t. the total number of vertices along any path $q_i$ (including the source and sink) is $D$. Two paths, $(q_a, q_b)$, may have common vertices, but individual $q_i$ cannot have redundant vertices (i.e. they are not multisets).

Please note, however, that I would be open to elegant/nice solutions that allow repeat vertex visits but forbid repeat edge traversals.

  • 3
    $\begingroup$ Read the answer off the $(a,b)$ entry in the $D$th power of the graph's adjacency matrix (using MatrixPower). $\endgroup$ – whuber Apr 22 '13 at 21:10
  • 3
    $\begingroup$ @whuber The usual "problem" with that is that it also counts paths with repeated vertices, e.g. 1->2->1->2 is a lengh 4 path between 1 and 2. It's up to the OP to decide is this is a problem for his application. Just something good to be aware of. $\endgroup$ – Szabolcs Apr 22 '13 at 21:36
  • $\begingroup$ @whuber Right, that repeated vertex problem is where I'm stuck. $\endgroup$ – Peter Apr 22 '13 at 23:08
  • 1
    $\begingroup$ @Peter It'd be good if you could update the problem with a precise formulation (explaining what you mean by path, and whether repeated vertices or repeated edges are allowed---two different things!) The current solution you are currently using does neither and won't correctly count the number of paths. To sum up: a precise formulation is needed. $\endgroup$ – Szabolcs Apr 22 '13 at 23:20
  • 1
    $\begingroup$ Peter, are you really sure you meant to say you want to count sets of vertices and not the actual paths? The former, of course, ignores the sequence in which the vertices are visited. There is a contradiction between what you say and the notation you use. $\endgroup$ – whuber Apr 23 '13 at 14:30
FindPath[G, 1, 2, {L}, All]

where $G$ is some graph. This finds all paths of length exactly $L$ edges which run between nodes $1$ and $2$.

| improve this answer | |
  • $\begingroup$ Well, that's just mrm's comment -- No test cases, no corner cases. Try to expand on it otherwise it's just the same thing. $\endgroup$ – Sektor Oct 23 '15 at 11:42
  • $\begingroup$ this actually gives the command $\endgroup$ – Alexander Giles Oct 23 '15 at 11:58
  • $\begingroup$ And ? We do have the link to the whole documentation page just half a screen above $\endgroup$ – Sektor Oct 23 '15 at 11:59
  • $\begingroup$ Some people want fast $\endgroup$ – Alexander Giles Oct 23 '15 at 12:07
  • 3
    $\begingroup$ Since this is an answer to the question, I think it should be written as an answer and not just a comment. The comment was too easy to miss. Generally, the existence of a comment that also answers the question shouldn't prevent anyone else from posting it as an actual answer. $\endgroup$ – Szabolcs Oct 23 '15 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.