从Erlang定向循环图中的一个顶点找到所有可能的路径 [英] Find all possible paths from one vertex in a directed cyclic graph in Erlang

问题描述

我想实现一个函数，它在有向循环图G中从源顶点V中找到所有可能的顶点的所有可能路径。

现在，我只是想了解这个算法。我已经阅读了深度优先搜索算法的定义，但是我没有完全理解该做什么。

我没有任何完成的代码提供在这里，因为我不知道如何：

• 存储结果（与A-> B-> C->我们还应该存储A-> B和A-> B-> C）;


• 代表图形（有向图？元组列表？）;


• 要使用多少递归（与每个相邻顶点一起工作？）

如何找到所有可能的路径一个给定的源顶点在Erlang的有向循环图中？

UPD：根据迄今为止的答案，我必须重新定义图定义：它是一个非非循环图。我知道如果我的递归函数打到一个循环，这是一个无限循环。为了避免这一点，我可以检查当前的顶点是否在结果路径的列表中 - 如果是，我停止遍历并返回路径。

---

UPD2：感谢您的发人深省的评论！是的，我需要找到没有从一个源顶点到其他所有其他循环的所有简单路径。

在这样的图形中：

与源顶点A算法应该找到以下路径：

• A，B

A，B，C

• A，B，C，D


• A，D


• 
  
• A，D，C，B

做这个工作，但它不可用的图形有更多的20个顶点（我猜这是递归错误 - 占用太多的内存，永远不会结束）：

  dfs（Graph，Source） - > 
？DBG（开始遍历图〜n，[]），
 Neighbors = digraph：out_neighbours（Graph，Source），
？DBG（Entering recursion for source vertex〜w 〜n，[Source]），
 dfs（邻居，[Source]，[]，Graph，Source），
 ok。 
 
 
 dfs（[]，路径，结果，_Graph，源） - > 
？DBG（没有更多的邻居留下顶点〜w〜n，[Source]），
结果; 
 
 dfs（[Neighbor | Other_neighbours]，路径，结果，图形，源） - > 
？DBG（///要检查的邻居为〜w，其他邻居为：〜w〜n，[Neighbor，Other_neighbours]），
？DBG（***当前结果： 〜w〜n，[结果]），
 New_result = relax_neighbours（Neighbor，Paths，Result，Graph，Source），
 
 dfs（Other_neighbours，Paths，New_result，Graph，Source） 。 
 
 
 relax_neighbours（邻居，路径，结果，图形，来源） - > 
案例列表：
的成员（邻居，路径）false  - > 
？DBG（找到一个未访问的邻居〜，路径是：〜w〜n，[邻居，路径]），
邻居=有向图：out_neighbours（图，邻居），
 ？DBG（未访问的顶点的邻居〜w是〜w，路径是：
〜w〜n，[邻居，邻居，[邻居|路径]]），
 dfs（邻居， [邻居|路径]，结果，图形，源）; 
 true  - > 
 [路径|结果] 
 
结束。 
  

---

UPD3： / p>

问题是常规的深度优先搜索算法将首先到达路径之一：（A，B，C，D）或（A，D，C ，B），并且永远不会走第二条路径。

在任一情况下，它将是唯一的路径 - 例如，当常规DFS从（A，B， C，D）它返回到A并检查是否访问D（A的第二个邻居）。而且由于常规DFS为每个顶点保持全局状态，所以D将具有访问状态。

因此，我们必须引入递归依赖状态 - 如果从（A，B，C，D）到A的回溯，我们应该在结果列表中有（A，B，C，D），我们应该在算法的开头有D标记为未访问。

我已经尝试优化解决方案的尾递归算法，但仍然是算法的运行时间是不可行的 - 大概需要4秒的时间来遍历一个每顶点有3个边的16个顶点：

  dfs（Graph，Source） - > 
？DBG（开始遍历图〜n，[]），
 Neighbors = digraph：out_neighbours（Graph，Source），
？DBG（Entering recursion for source vertex〜w 〜n，[Source]），
结果= ets：new（generated_pa​​ths，[bag]），
 Root = Source，
 dfs（Neighbors，[Source]源，[]，根）。 
 
 
 dfs（[]，路径，结果，_Graph，源，_，_） - > 
？DBG（没有更多的邻居为顶点〜w，路径为〜w，结果为〜w〜n，[源，路径，结果]），
结果; 
 
 dfs（[Neighbor | Other_neighbours]，路径，结果，图形，源，Recursion_list，根） - > 
？DBG（〜w *当前源为〜w〜n，[Recursion_list，Source]），
？DBG（〜w检查邻居__ w_ _ _ w_，其他邻居：〜w〜n，[Recursion_list，Neighbor，Source，Other_neighbours]），
 
 
 
？ DBG（〜w准备检查访问：〜w〜n，[Recursion_list，Neighbor]），
 
案例列表：
的成员（邻居，路径）false  - > 
？DBG（〜w找到一个未访问的邻居〜w，路径是：〜w〜n，[Recursion_list，Neighbor，Paths]），
 New_paths = [Neighbor | Paths]，
？DBG（〜w添加路径的邻居：〜w〜n，[Recursion_list，New_paths]），
 ets：insert（Result，{Root，Paths}），
 
邻居=图：out_neighbours（Graph，Neighbor），
？DBG（〜w未访问的顶点的邻居〜w为〜w，路径为：〜w，递归：〜n，[Recursion_list，Neighbor，邻居，[邻居|路径]]），
 dfs（Neighbors，New_paths，Result，Graph，Neighbor，[[[]] | Recursion_list]，Root） 
 true  - > 
？DBG（〜w邻居〜w是：已访问，路径：〜w，回溯到其他邻居：〜n，[Recursion_list，Neighbor，Paths]），
 ets：insert结果，{Root，Paths}）
 
 end，
 
 dfs（Other_neighbours，Paths，Result，Graph，Source，Recursion_list，Root）。 
  

任何想法可以在可接受的时间内运行？

解决方案

编辑：
好​​的我现在明白了，你想找到所有简单的路径从有向图中的顶点。因此，如您所了解的，具有回溯的深度优先搜索将是合适的。一般的想法是去一个邻居，然后去另一个（不是你访问的一个），并继续前进，直到你陷入死胡同。然后回溯到你所在的最后一个顶点，并选择一个不同的邻居等。
你需要得到正确的位，但不应该太难。例如。在每一步，您需要根据您之前是否已经访问过的标签来标记探索或未开发的顶点。性能不应该是一个问题，正确实现的算法应该是O（n ^ 2）时间。所以我不知道你在做错什么，也许你正在访问太多的邻居？例如。也许你正在重新访问你已经访问过的邻居，并循环回到一起。

我没有真正阅读你的程序，但是在深度上的Wiki页面-first搜索有一个简单，简单的伪代码程序，您可以尝试以您的语言复制。将图形存储为邻接列表，使其更容易。

编辑：
是的，对不起，你是对的，标准的DFS搜索将无法正常工作，您需要稍微调整，以便重新访问之前访问过的顶点。因此，您可以访问除已经存储在当前路径中的任何顶点之外的任何顶点。
这当然意味着我的运行时间是完全错误的，你的算法的复杂性将通过屋顶。如果您的图形的平均复杂度为d + 1，那么将有大约d * d * d * ... * d = d ^ n个可能的路径。
所以即使每个顶点只有3个邻居，当你得到20个顶点以上时，仍然有很多路径。
真的没有办法，因为如果你想要你的程序输出所有可能的路径，那么确实你必须输出所有的d ^ n。

我有兴趣知道你是否需要这个特定的任务，或者只是试图对这个兴趣进行编程。如果是后者，那么你只需要对小型，稀疏连接的图形感到满意。

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

The performance doesn't matter now, I just would like to understand the algorithm. I have read the definition of the Depth-first search algorithm, but I don't have full comprehension of what to do.

I don't have any completed piece of code to provide here, because I am not sure how to:

• store the results (along with A->B->C-> we should also store A->B and A->B->C);
• represent the graph (digraph? list of tuples?);
• how many recursions to use (work with each adjacent vertex?).

How can I find all possible paths form one given source vertex in a directed cyclic graph in Erlang?

UPD: Based on the answers so far I have to redefine the graph definition: it is a non-acyclic graph. I know that if my recursive function hits a cycle it is an indefinite loop. To avoid that, I can just check if a current vertex is in the list of the resulting path - if yes, I stop traversing and return the path.

---

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

In a graph like this:

with the source 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 unusable with graphs that have more that 20 vertices (I guess it is something wrong with recursion - takes too much memory, 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 regular depth-first search algorithm will go one of the to paths first: (A,B,C,D) or (A,D,C,B) and will never go the second path.

In either case it will be the only path - for example, when the regular DFS backtracks from (A,B,C,D) it goes back up to A and checks if D (the second neighbour of A) is visited. And since the regular DFS maintains a global state for each vertex, D would have 'visited' state.

So, we have to introduce a recursion-dependent state - if we backtrack from (A,B,C,D) up to A, we should have (A,B,C,D) in the list of the results and we should have D marked as unvisited as at the very beginning of the algorithm.

I have tried to optimize the solution to tail-recursive one, but still the running time of the algorithm is unfeasible - it takes about 4 seconds to traverse a tiny graph of 16 vertices with 3 edges per 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 in acceptable time?

解决方案

Edit: Okay I understand now, you want to find all simple paths from a vertex in a directed graph. So a depth-first search with backtracking would be suitable, as you have realised. The general idea is to go to a neighbour, then go to another one (not one which you've visited), and keep going until you hit a dead end. Then backtrack to the last vertex you were at and pick a different neighbour, etc. You need to get the fiddly bits right, but it shouldn't be too hard. E.g. at every step you need to label the vertices 'explored' or 'unexplored' depending on whether you've already visited them before. The performance shouldn't be an issue, a properly implemented algorithm should take maybe O(n^2) time. So I don't know what you are doing wrong, perhaps you are visiting too many neighbours? E.g. maybe you are revisiting neighbours that you've already visited, and going round in loops or something.

I haven't really read your program, but the Wiki page on Depth-first Search has a short, simple pseudocode program which you can try to copy in your language. Store the graphs as Adjacency Lists to make it easier.

Edit: Yes, sorry, you are right, the standard DFS search won't work as it stands, you need to adjust it slightly so that does revisit vertices it has visited before. So you are allowed to visit any vertices except the ones you have already stored in your current path. This of course means my running time was completely wrong, the complexity of your algorithm will be through the roof. If the average complexity of your graph is d+1, then there will be approximately d*d*d*...*d = d^n possible paths. So even if every vertex has only 3 neighbours, there's still quite a few paths when you get above 20 vertices. There's no way around that really, because if you want your program to output all possible paths then indeed you will have to output all d^n of them.

I'm interested to know whether you need this for a specific task, or are just trying to program this out of interest. If the latter, you will just have to be happy with small, sparsely connected graphs.

这篇关于从Erlang定向循环图中的一个顶点找到所有可能的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！