2

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

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

4

1 回答 1

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

输出： 

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

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

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

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]]
于 2016-06-29T05:46:37.337 回答