5 added 6 characters in body
source | link

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
4 added 8 characters in body
source | link

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
source | link

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
source | link
1
source | link