在 digraph_utils:is_acirclic/1 返回 false 后查找循环或循环

我怎样才能（有效地）在Erlang有向图中找到循环或循环digraph_utils:is_acyclic/1返回假？

EDIT: is_acyclic is 定义为 https://github.com/erlang/otp/blob/maint/lib/stdlib/src/digraph_utils.erl#L113 loop_vertices(G) =:= [] andalso topsort(G) =/= false.

您可以使用digraph_utils:cyclic_strong_components/1 http://erlang.org/doc/man/digraph_utils.html#cyclic_strong_components-1.

cyclic_strong_components(Digraph) -> [StrongComponent].

返回一个列表强连通分量 http://erlang.org/doc/man/digraph_utils.html#strong_components。每一个都强烈 组件由其顶点表示。顶点的顺序 并且组件的顺序是任意的。仅那些顶点 返回包含在有向图中某个循环中的内容，否则返回 列表等于返回的列表strong_components/1 http://erlang.org/doc/man/digraph_utils.html#strong_components-1.

Test:

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]]

Note:
由于每个组件中顶点的顺序是任意的，如果你想找到确切的路径，你可以使用digraph:get_cycle/2 http://erlang.org/doc/man/digraph.html#get_cycle-2。例如，在上面的例子中digraph:get_cycle(G, c)会给你[c,d,a,b,c].

编辑 - 另一个重要说明：
虽然每cycle is a 循环强连通分量，事实恰恰相反。这意味着您在此类组件中可能只有几个周期。
因此，在这种情况下，如果您想获得每个周期，您可以扔掉每个组件并将其拆分为简单的周期。

所以上面的“扩展”版本将是：

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]).

Output:

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