Find all possible paths from one vertex in a directed cyclic graph in Erlang

Question

I would like to implement a function that finds all possible paths to all possible vertices from the original vertex V in a directed cyclic graph G.

Now performance doesn't matter, I just wanted to understand the algorithm. I read the definition of the depth search algorithm, but I do not have a full understanding of what to do.

I do not have ready-made code to provide here, because I'm not sure how:

• save the results (together with A-> B-> C-> we must also store A-> B and A-> B-> C);
• present a graph (digraph? list of tuples?);
• how many recursions to use (work with each neighboring vertex?).

How to find all possible paths from one given vertex of a source in an oriented cyclic graph in Erlang?

UPD: Based on the answers so far, I need to redefine the definition of the graph: it is a non-acyclic graph. I know that if my recursive function falls into a loop, it is an undefined loop. To avoid this, I can simply check if the current vertex is in the list of the resulting path - if so, I stop moving and returning the path.

---

UPD2: Thanks for the comment causing the comments! Yes, I need to find all the simple paths that do not have cycles from one source vertex to all the others.

In a graph like this:

with the original vertex A, the algorithm should find the following paths:

• A, B
• A, B, C
• A, B, C, D
• A, d
• A, D, C
• A, D, C, B

The following code does the job, but it is unsuitable for graphs with more than 20 vertices (I think this is wrong with recursion - it takes up too much memory, it never ends):

dfs(Graph,Source) -> ?DBG("Started to traverse graph~n", []), Neighbours = digraph:out_neighbours(Graph,Source), ?DBG("Entering recursion for source vertex ~w~n", [Source]), dfs(Neighbours,[Source],[],Graph,Source), ok. dfs([],Paths,Result,_Graph,Source) -> ?DBG("There are no more neighbours left for vertex ~w~n", [Source]), Result; dfs([Neighbour|Other_neighbours],Paths,Result,Graph,Source) -> ?DBG("///The neighbour to check is ~w, other neighbours are: ~w~n",[Neighbour,Other_neighbours]), ?DBG("***Current result: ~w~n",[Result]), New_result = relax_neighbours(Neighbour,Paths,Result,Graph,Source), dfs(Other_neighbours,Paths,New_result,Graph,Source). relax_neighbours(Neighbour,Paths,Result,Graph,Source) -> case lists:member(Neighbour,Paths) of false -> ?DBG("Found an unvisited neighbour ~w, path is: ~w~n",[Neighbour,Paths]), Neighbours = digraph:out_neighbours(Graph,Neighbour), ?DBG("The neighbours of the unvisited vertex ~w are ~w, path is: ~w~n",[Neighbour,Neighbours,[Neighbour|Paths]]), dfs(Neighbours,[Neighbour|Paths],Result,Graph,Source); true -> [Paths|Result] end. 

---

UPD3:

The problem is that the usual depth search algorithm will first go one of the paths: (A, B, C, D) or (A, D, C, B) and never go the second way.

In any case, this will be the only way - for example, when a regular DFS departs from (A, B, C, D), it returns to A and checks if D is visiting (second neighbor A), and since regular DFS maintains a global state for each tops, D will have a “visited” state.

So, we need to introduce a recursion-dependent state - if we step back from (A, B, C, D) to A, we must have (A, B, C, D) in the list of results and we must have D marked as invisible as at the very beginning of the algorithm.

I tried to optimize the solution with tail recursive, but still the algorithm is not workable - it takes about 4 seconds to go through a tiny graph of 16 vertices with 3 edges to the vertex:

 dfs(Graph,Source) -> ?DBG("Started to traverse graph~n", []), Neighbours = digraph:out_neighbours(Graph,Source), ?DBG("Entering recursion for source vertex ~w~n", [Source]), Result = ets:new(resulting_paths, [bag]), Root = Source, dfs(Neighbours,[Source],Result,Graph,Source,[],Root). dfs([],Paths,Result,_Graph,Source,_,_) -> ?DBG("There are no more neighbours left for vertex ~w, paths are ~w, result is ~w~n", [Source,Paths,Result]), Result; dfs([Neighbour|Other_neighbours],Paths,Result,Graph,Source,Recursion_list,Root) -> ?DBG("~w *Current source is ~w~n",[Recursion_list,Source]), ?DBG("~w Checking neighbour _~w_ of _~w_, other neighbours are: ~w~n",[Recursion_list,Neighbour,Source,Other_neighbours]), ? DBG("~w Ready to check for visited: ~w~n",[Recursion_list,Neighbour]), case lists:member(Neighbour,Paths) of false -> ?DBG("~w Found an unvisited neighbour ~w, path is: ~w~n",[Recursion_list,Neighbour,Paths]), New_paths = [Neighbour|Paths], ?DBG("~w Added neighbour to paths: ~w~n",[Recursion_list,New_paths]), ets:insert(Result,{Root,Paths}), Neighbours = digraph:out_neighbours(Graph,Neighbour), ?DBG("~w The neighbours of the unvisited vertex ~w are ~w, path is: ~w, recursion:~n",[Recursion_list,Neighbour,Neighbours,[Neighbour|Paths]]), dfs(Neighbours,New_paths,Result,Graph,Neighbour,[[[]]|Recursion_list],Root); true -> ?DBG("~w The neighbour ~w is: already visited, paths: ~w, backtracking to other neighbours:~n",[Recursion_list,Neighbour,Paths]), ets:insert(Result,{Root,Paths}) end, dfs(Other_neighbours,Paths,Result,Graph,Source,Recursion_list,Root). 

Any ideas to run this at an acceptable time?

Answer 1

Edit: Ok, now I understand, you want to find all the simple paths from the top in a directed graph. Thus, a depth search with a countdown would be suitable, as you understand. The general idea is to go to a neighbor, and then go to another (and not to the one you visited), and keep going until you reach a dead end. Then go back to the last peak you were at and choose another neighbor, etc. You need to get the right bits, but it should not be too complicated. For instance. at each step you need to designate "verified" or "unexplored" peaks, depending on whether you have already visited them before. Performance should not be a problem; a correctly implemented algorithm should take, perhaps, O (n ^ 2) time. So I don’t know what you are doing wrong, maybe you are visiting too many neighbors? For instance. perhaps you are revising the neighbors that you have already visited, and going around in a loop or something like that.

I really haven't read your program, but there is a short simple pseudo-code program on the Depth-first Search Wiki page that you can try copying into your language. Keep the charts as Adjacency lists to simplify them.

Edit: Yes, I'm sorry, you're right, the standard DFS search will not work, since it is standing, you need to adjust it a bit to re-look at the vertices that it visited before. Thus, you are allowed to visit any vertices except those that you have already saved in your current path. This, of course, means that the operating time was completely wrong, the complexity of your algorithm will go through the roof. If the average complexity of your graph is d + 1, then there will be possible d * d * d * ... * d = d ^ n possible ways. Therefore, even if each vertex has only 3 neighborhoods, there are still several paths when you get more than 20 vertices. Actually, this is not so, because if you want your program to output all possible paths, you really need to output all d ^ n from them.

I am interested to know if you need this for a specific task or just trying to program it out of interest. If the latter, you just need to be content with small, rarely connected graphs.

Answer 2

I do not understand the question. If I have a graph G = (V, E) = ({A, B}, {(A, B), (B, A)}), then from A to B {[A, B], [A, B, A, B], [A, B, A, B, A, B], ...}. How can I find all possible paths to any vertex in a cyclic graph?

Edit:

Have you even tried to figure out or guess how the possible paths for some graphs are growing? If you have a fully connected schedule, you will receive

• 2 - 1
• 3 to 4
• 4 - 15
• 5 - 64
• 6 - 325
• 7 - 1956
• 8 - 13699
• 9 - 109600
• 10 - 986409
• 11 - 9864100
• 12 - 108505111
• 13 - 1302061344
• 14 - 16926797485
• 15 - 236975164804
• 16 - 3554627472075
• 17 - 56874039553216
• 18 - 966858672404689
• 19 - 17403456103284420
• 20 - 330665665962403999

Are you sure you want to find all paths for all nodes? This means that if you calculate one million paths in one second, it will take 10,750 years to calculate all paths to all nodes in a fully connected graph with 20 nodes. This is the upper bound for your task, so I think you do not want to do this. I think you want something else.

Answer 3

Not an improved algorithmic solution by any means, but you can often improve performance by creating multiple workflows, potentially here one for each first level node, and then aggregating the results. This can often improve naive brute force algorithms relatively easily.

Here you can see an example: Some functions of the Erlang matrix in the maximize_assignment function (comments starting at line 191 to date). Again, the main algorithm has a rather naive and brute force, but parallelization significantly speeds it up for many forms of matrices.

I used a similar approach in the past to find the number of Hamiltonian paths in a graph.