Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
2  
Read the answer off the $(a,b)$ entry in the $D$th power of the graph's adjacency matrix (using MatrixPower). –  whuber Apr 22 '13 at 21:10
3  
@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. –  Szabolcs Apr 22 '13 at 21:36
    
@whuber Right, that repeated vertex problem is where I'm stuck. –  Peter Apr 22 '13 at 23:08
1  
@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. –  Szabolcs Apr 22 '13 at 23:20
1  
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. –  whuber Apr 23 '13 at 14:30
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.