# Counting paths of a certain length between a source and sink vertex

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.

• Read the answer off the $(a,b)$ entry in the $D$th power of the graph's adjacency matrix (using MatrixPower). Apr 22, 2013 at 21:10
• @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. Apr 22, 2013 at 21:36
• @whuber Right, that repeated vertex problem is where I'm stuck. Apr 22, 2013 at 23:08
• @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. Apr 22, 2013 at 23:20
• 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. Apr 23, 2013 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$.