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, 2013 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, 2013 at 21:36
  • $\begingroup$ @whuber Right, that repeated vertex problem is where I'm stuck. $\endgroup$
    – Peter
    Apr 22, 2013 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, 2013 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, 2013 at 14:30

1 Answer 1

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$.

  • $\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, 2015 at 11:42
  • $\begingroup$ this actually gives the command $\endgroup$ Oct 23, 2015 at 11:58
  • $\begingroup$ And ? We do have the link to the whole documentation page just half a screen above $\endgroup$
    – Sektor
    Oct 23, 2015 at 11:59
  • $\begingroup$ Some people want fast $\endgroup$ Oct 23, 2015 at 12:07
  • 4
    $\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, 2015 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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