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

Question

How can I (efficiently) find a cycle or a loop in an Erlang digraph after digraph_utils:is_acyclic/1 returns false?

EDIT: is_acyclic is defined as loop_vertices(G) =:= [] andalso topsort(G) =/= false.

Answer 1

You can use 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.

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

Output:

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

Note:
Since the order of the vertices in each component is arbitrary, if you want to find the exact path you can just use digraph:get_cycle/2. For example, in the case above digraph:get_cycle(G, c) will give you [c,d,a,b,c].

Edit - Another Important Note:
Although every cycle is a cyclic strongly connected component, the opposite is not exactly true. Meaning that you might have few cycles in one such component.
So in this case, if you want to get every cycle, you can go threw every component and split it to it's simple cycles.

So the 'extended' version of above will be:

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

Output:

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