在digraph_utils:is_acyclic/1之后找到循环或循环返回false [英] Finding a cycle or loop after digraph_utils:is_acyclic/1 returns false

问题描述

在 digraph_utils:is_acyclic/1 返回false之后，如何(有效地)在Erlang有向图中找到一个循环或循环?

How can I (efficiently) find a cycle or a loop in an Erlang digraph after digraph_utils:is_acyclic/1 returns false?

is_acyclic 是推荐答案

您可以使用 digraph_utils:cyclic_strong_components/1 .

You can use digraph_utils:cyclic_strong_components/1.

cyclic_strong_components(图)->[StrongComponent].

返回强连接的组件的列表.每个强烈组件由其顶点表示.顶点顺序组件的顺序是任意的.仅顶点是返回包含在Digraph中的某个循环中，否则返回列表等于 strong_components/1 返回的列表a>.

Returns a list of strongly connected components. Each strongly component is represented by its vertices. The order of the vertices and the order of the components are arbitrary. Only vertices that are included in some cycle in Digraph are returned, otherwise the returned list is equal to that returned by strong_components/1.

测试:

get_cycles() ->
    G = digraph:new(),
    Vertices = [a, c, b, d, e, f, g],
    lists:foreach(fun(V) -> digraph:add_vertex(G, V) end, Vertices),
    Edges = [{a,b},{b,c},{c,a},{b,d},{d,e},{e,b},{a,f},{f,g},{g,f}],
    lists:foreach(fun({V1,V2}) -> digraph:add_edge(G, V1, V2) end, Edges),
    digraph_utils:cyclic_strong_components(G).

输出:

3> test:get_cycles().
[[c,a,b,d,e],[f,g]]

注意:
由于每个组件中的顶点顺序是任意的，因此，如果要查找确切的路径，可以使用 digraph:get_cycle/2 .例如，在上述 digraph:get_cycle(G，c)的情况下，您会得到 [c，d，a，b，c] .

Note:
Since the order of the vertices in each component is arbitrary, if you want to find the exact path you can just use digraph:get_cycle/2. For example, in the case above digraph:get_cycle(G, c) will give you [c,d,a,b,c].

编辑-另一个重要说明:
尽管每个 cycle 都是一个循环强连接的组件，但事实并非完全相反.这意味着您在一个这样的组件中可能没有几个循环.
因此，在这种情况下，如果要获得每个周期，则可以扔掉每个组件并将其拆分为简单的周期.

Edit - Another Important Note:
Although every cycle is a cyclic strongly connected component, the opposite is not exactly true. Meaning that you might have few cycles in one such component.
So in this case, if you want to get every cycle, you can go threw every component and split it to it's simple cycles.

因此，上述的扩展"版本为:

So the 'extended' version of above will be:

get_cycles() ->
    G = digraph:new(),
    Vertices = [a, c, b, d, e, f, g],
    lists:foreach(fun(V) -> digraph:add_vertex(G, V) end, Vertices),
    Edges = [{a,b},{b,c},{c,a},{b,d},{d,e},{e,b},{a,f},{f,g},{g,f}],
    lists:foreach(fun({V1,V2}) -> digraph:add_edge(G, V1, V2) end, Edges),
    Components = digraph_utils:cyclic_strong_components(G),
    lists:foldl(fun(Comp, Acc) -> get_more_cycles(G,Comp,[]) ++ Acc end, [], Components).

get_more_cycles(_G, [], Acc) ->
    Acc;
get_more_cycles(G, [H|T], Acc) ->
    Cycle = digraph:get_cycle(G,H),
    get_more_cycles(G, T -- Cycle, [Cycle|Acc]).

输出:

3> test:get_cycles().
[[f,g,f],[d,e,b,d],[c,a,b,c]]

这篇关于在digraph_utils:is_acyclic/1之后找到循环或循环返回false的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！