在 digraph_utils:is_acyclic/1 returns 之后查找循环或循环 false

Question

在 digraph_utils:is_acyclic/1 returns false 之后，如何（有效地）在 Erlang 有向图中找到循环或循环？

编辑：is_acyclic 是 defined as loop_vertices(G) =:= [] andalso topsort(G) =/= false.

Answer 1

您可以使用 digraph_utils:cyclic_strong_components/1.

cyclic_strong_components(Digraph) -> [StrongComponent].

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

编辑 - 另一个重要说明：
虽然每个 cycle 都是一个 cyclic strongly connected component，但反之则不完全正确。这意味着您在一个这样的组件中可能只有几个周期。
所以在这种情况下，如果你想获得每个循环，你可以扔掉每个组件并将其拆分为简单的循环。

所以上面的 'extended' 版本将是：

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 returns 之后查找循环或循环 false

Finding a cycle or loop after digraph_utils:is_acyclic/1 returns false

erlang

digraphs