Recherche d'un cycle ou d'une boucle après digraph_utils: is_acyclic/1 retourne false

Question

Comment trouver (efficacement) un cycle ou une boucle dans un digramme d'Erlang après que digraph_utils:is_acyclic/1 est retourné faux?

EDIT: is_acyclic est defined asloop_vertices(G) =:= [] andalso topsort(G) =/= false.

Answer 1

Vous pouvez utiliser digraph_utils:cyclic_strong_components/1.

cyclic_strong_components(Digraph) -> [StrongComponent].

Renvoie une liste des strongly connected components. Chaque composant fortement est représenté par ses sommets. L'ordre des sommets et l'ordre des composants sont arbitraires. Seuls les vertices inclus dans un cycle dans Digraf sont renvoyés, sinon la liste retournée est égale à celle renvoyée par 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). 

Sortie:

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

Note:
Depuis l'ordre des sommets dans chaque composant est arbitraire, si vous voulez trouver le chemin exact vous pouvez simplement utiliser digraph:get_cycle/2. Par exemple, dans le cas ci-dessus digraph:get_cycle(G, c) vous donnera [c,d,a,b,c].

Edition - Une autre remarque importante:
Bien que chaque cycle est un composant cyclique fortement connecté, le contraire est pas tout à fait vrai. Cela signifie que vous pourriez avoir quelques cycles dans un de ces composants.
Donc, dans ce cas, si vous voulez obtenir chaque cycle, vous pouvez lancer chaque composant et le diviser en cycles simples.

Ainsi, le 'étendu' version ci-dessus seront:

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

Sortie:

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