digraph_utils：is_acyclic/1の後にサイクルまたはループを見つけると、

Question

digraph_utils:is_acyclic/1がfalseを返した後、Erlangの有向グラフでサイクルまたはループをどのように見つけることができますか？

EDIT：is_acyclicあなたはdigraph_utils:cyclic_strong_components/1を使用することができますdefined asloop_vertices(G) =:= [] andalso topsort(G) =/= false.

Answer 1

です。

cyclic_strong_components(Digraph) -> [StrongComponent].

strongly connected componentsのリストを返します。それぞれのコンポーネントはその頂点によって表されます。 頂点の順番は であり、コンポーネントの順序は任意です。一部のサイクルでは、 の頂点のみが返されます。そうでない場合、返される のリストは、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]]