Counting paths of a certain length between a source and sink vertex - Mathematica Stack Exchange most recent 30 from mathematica.stackexchange.com 2019-09-21T18:33:56Z https://mathematica.stackexchange.com/feeds/question/23799 https://creativecommons.org/licenses/by-sa/4.0/rdf https://mathematica.stackexchange.com/q/23799 7 Counting paths of a certain length between a source and sink vertex Peter https://mathematica.stackexchange.com/users/7038 2013-04-22T20:42:24Z 2017-10-01T01:10:50Z <p>I have a graph $G$, which may be directed or not, and I was wondering if there was an efficient way of using, say, <code>BreadthFirstScan[]</code> and <code>FindShortestPath[]</code> to count the number of paths between some source vertex, $v(a)$, some sink vertex, $v(b)$, of a certain length $D$? </p> <p>As of right now, I'm simply sequentially running through all of the vertices in my graph, applying <code>FindShortestPath[]</code> 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.</p> <p>Assuming I have plenty of memory to spare, is there a better / faster solution?</p> <hr> <p>Let me better specify what I'm looking for - </p> <p>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).</p> <p>Please note, however, that I would be open to elegant/nice solutions that allow repeat vertex visits but forbid repeat edge traversals.</p> https://mathematica.stackexchange.com/questions/23799/-/97683#97683 3 Answer by Alexander Giles for Counting paths of a certain length between a source and sink vertex Alexander Giles https://mathematica.stackexchange.com/users/18994 2015-10-23T11:21:17Z 2015-10-23T11:21:17Z <pre><code>FindPath[G, 1, 2, {L}, All] </code></pre> <p>where $G$ is some graph. This finds all paths of length exactly $L$ edges which run between nodes $1$ and $2$.</p>