5 added 6 characters in body edited Oct 1 '17 at 1:10 kglr 217k1010 gold badges247247 silver badges498498 bronze badges 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[]BreadthFirstScan[] and FindShortestPath[]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[]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. 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. 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. Tweeted twitter.com/#!/StackMma/status/326833134903627778 occurred Apr 23 '13 at 23:01 4 added 8 characters in body edited Apr 23 '13 at 18:50 Peter 10744 bronze badges 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. 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 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. 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 added 141 characters in body edited Apr 22 '13 at 23:37 Peter 10744 bronze badges 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 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. 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 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). 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 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. 2 added 575 characters in body edited Apr 22 '13 at 23:29 Peter 10744 bronze badges 1 asked Apr 22 '13 at 20:42 Peter 10744 bronze badges