How can I find all 'long' simple acyclic paths in a graph?

Question

Let's say we have a fully connected directed graph G. The vertices are [a,b,c]. There are edges in both directions between each vertex.

Given a starting vertex a, I would like to traverse the graph in all directions and save the path only when I hit a vertex which is already in the path.

So, the function full_paths(a,G) should return:

- [{a,b}, {b,c}, {c,d}]
- [{a,b}, {b,d}, {d,c}]
- [{a,c}, {c,b}, {b,d}]
- [{a,c}, {c,d}, {d,b}]
- [{a,d}, {d,c}, {c,b}]
- [{a,d}, {d,b}, {b,c}]

I do not need 'incomplete' results like [{a,b}] or [{a,b}, {b,c}], because it is contained in the first result already.

Is there any other way to do it except of generating a powerset of G and filtering out results of certain size?

How can I calculate this?

Edit: As Ethan pointed out, this could be solved with depth-first search method, but unfortunately I do not understand how to modify it, making it store a path before it backtracks (I use Ruby Gratr to implement my algorithm)

Answer 1

Have you looked into depth first search or some variation? A depth first search traverses as far as possible and then backtracks. You can record the path each time you need to backtrack.

Answer 2

If you know your graph G is fully connected there is N! paths of length N when N is number of vertices in graph G. You can easily compute it in this way. You have N possibilities of choice starting point, then for each starting point you can choose N-1 vertices as second vertex on a path and so on when you can chose only last not visited vertex on each path. So you have N*(N-1)*...*2*1 = N! possible paths. When you can't chose starting point i.e. it is given it is same as finding paths in graph G' with N-1 vertices. All possible paths are permutation of set of all vertices i.e. in your case all vertices except starting point. When you have permutation you can generate path by:

perm_to_path([A|[B|_]=T]) -> [{A,B}|perm_to_path(T)];
perm_to_path(_) -> [].

simplest way how to generate permutations is

permutations([]) -> [];
permutations(L) ->
  [[H|T] || H <- L, T <- permutations(L--[H])].

So in your case:

paths(A, GV) -> [perm_to_path([A|P]) || P <- permutations(GV--[A])].

where GV is list of vertices of graph G.

If you would like more efficient version it would need little bit more trickery.