For a directed graph, we have the following module:
digraph_utils:cyclic_strong_components(G)
Is there anything like this available for undirected graphs in Erlang? I want to find all the cycles in an undirected graph.
Is there a method by which I can use the digraph utilities for an undirected graph instead? It would be much handy and easier to use the modules directly.
I tried the following way:
I tried the same digraph module, added bi-directed edges, hence the graph is undirected now. Then I added a case, where length of cycles is greater than 3, then print such a cycle. For the graphs I used the code, it worked fine. The code is as follows: (added my code to the code from this answer : Finding a cycle or loop after digraph_utils:is_acyclic/1 returns false )
-module(test1).
-export([get_cycles/0,pri/2,get_more_cycles/3]).
pri(L,0) ->
io:fwrite("~n");
pri(L,V) ->
List = lists:nth(V,L),
case (length(List) > 3) of
true -> io:fwrite("Cycle is ~w ~n",[List]);
false -> io:fwrite("~n")
end,
pri(L,V-1).
get_cycles() ->
G = digraph:new(),
Vertices = [1,2,3,4,5,6,7,8,9,10,11,12,13],
lists:foreach(fun(V) -> digraph:add_vertex(G, V) end, Vertices),
Edges = [{12,13},{13,12},{11,12},{12,11},{11,13},{13,11},{10,11},{11,10},{9,5},{5,9},{10,6},{6,10},{8,7},{7,8},{4,7},{7,4},{1,2},{2,1},{2,3},{3,2},{3,4},{4,3},{4,6},{6,4},{6,5},{5,6},{3,5},{5,3}],
lists:foreach(fun({V1,V2}) -> digraph:add_edge(G, V1, V2) end, Edges),
Components = digraph_utils:cyclic_strong_components(G),
List = lists:foldl(fun(Comp, Acc) -> get_more_cycles(G,Comp,[]) ++ Acc end, [], Components),
pri(List,length(List)).
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]).
Is this correct approach, or is there any graph for which it will not work? I mean, is there a loophole graphs?