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

Fil*_*und 2 erlang digraphs

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

编辑:is_acyclic定义为 loop_vertices(G) =:= [] andalso topsort(G) =/= false.

A. *_*rid 5

您可以使用digraph_utils:cyclic_strong_components/1.

cyclic_strong_components(Digraph) -> [StrongComponent].

返回强连接组件的列表。每个强分量由其顶点表示。顶点的顺序和组件的顺序是任意的。只返回包含在 Digraph 中某个循环中的顶点,否则返回的列表等于 返回的列表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).
Run Code Online (Sandbox Code Playgroud)

输出:

3> test:get_cycles().
[[c,a,b,d,e],[f,g]]
Run Code Online (Sandbox Code Playgroud)

注意:
由于每个组件中顶点的顺序是任意的,如果你想找到确切的路径,你可以使用digraph:get_cycle/2. 例如,在上面的情况下digraph:get_cycle(G, c)会给你[c,d,a,b,c]

编辑 - 另一个重要说明:
虽然每个循环都是一个循环强连通分量,但事实并非如此。这意味着您在一个这样的组件中可能只有几个周期。
所以在这种情况下,如果你想得到每个循环,你可以扔掉每个组件并将其拆分为简单的循环。

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

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]).
Run Code Online (Sandbox Code Playgroud)

输出:

3> test:get_cycles().
[[f,g,f],[d,e,b,d],[c,a,b,c]]
Run Code Online (Sandbox Code Playgroud)