Outputting all Cycles in an undirected graph using DFS

Hi Guys,
I’m hoping someone can help me figure out why my function is not working as expected.
Any help is appreciated.
I was going through this geek-for-geek post on how to detect and print cycles in an undircetd graph at: Print all the cycles in an undirected graph - GeeksforGeeks
For a graph that looks like this:
image

The output I expect is: [ [3 5 4 6 ] [11 12 13] ].
But for whatever reason whenever I run it, julia is suck on evaluating. Running the debugger didn’t seem to help.

Here are my functions:


function DFS_Out_cycle(u,p,colour,marker,parent,cycle_number,adj_list)
    if colour[u]=="BLACK"
        return
    end

    if colour[u]=="GRAY"
        cycle_number += 1;
        cur = p
        marker[u] = cycle_number
        while cur != u
            cur = parent[cur]
            marker[cur] = cycle_number
        end
        return
    end
    parent[u]=p;
    colour[u] = "GRAY";
    for v in adj_list[u]
        if v==parent[u]
            continue
        end
        DFS_Out_cycle(v,u,colour,marker,parent,cycle_number,adj_list)
    end
    colour = "BLACK"
end

function print_dfs_cycles(adj_list,marker)
    for i in 1:length(adj_list)+1 
        if marker[i] != 0
            append!(cycles_list[marker[i]], i)
        end
    end
end

function adjacency_list(G)
    adj_mat=adjacency_matrix(G);
    adj_list= Dict{Int64,Vector{Int64}}();
    
    for i ∈ axes(adj_mat,1), j ∈ axes(adj_mat,2)
        if iszero(adj_mat[i,:] )
            adj_list[i]=Vector{Int64}()
        elseif adj_mat[i,j]==1
            if  haskey(adj_list,i)
                push!(adj_list[i],j)
            else
                adj_list[i]=Vector{Int64}()
                push!(adj_list[i],j)
            end
        end
    end
    return adj_list
end

g = Graph(13); add_edge!(g,1,2); add_edge!(g,2,3); add_edge!(g,3,4); add_edge!(g,3,5); add_edge!(g,5,6); add_edge!(g,4,6); add_edge!(g,4,7);  
add_edge!(g,7,8); add_edge!(g,6,10); add_edge!(g,5,9);  add_edge!(g,10,11); add_edge!(g,11,12); add_edge!(g,11,13);  add_edge!(g,12,13); 

g_l = adjacency_list(g);
cycles_list = [[]];
cycle_number = 0;
marker = Dict(i=>0 for i in 0:length(g_l));
parent = Dict(i=>0 for i in 0:length(g_l));
colour = ["WHITE" for key ∈ keys(g_l)]



DFS_Out_cycle(1,0,colour,marker,parent,cycle_number,g_l);
print_dfs_cycles(g_l,marker)
using Graphs
g = Graph(13); add_edge!(g,1,2); add_edge!(g,2,3); add_edge!(g,3,4); add_edge!(g,3,5); add_edge!(g,5,6); add_edge!(g,4,6); add_edge!(g,4,7);  
add_edge!(g,7,8); add_edge!(g,6,10); add_edge!(g,5,9);  add_edge!(g,10,11); add_edge!(g,11,12); add_edge!(g,11,13);  add_edge!(g,12,13); 

cycle_basis(g)

I don’t know what you want to archieve. And I don’t know too much about the methods, but it gives the outcome you expected.
See Cycles · Graphs.jl

I didn’t test this, but in the blog post the last line of dfs_out_cycle is

    // completely visited.
    color[u] = 2;

And your last line is

    colour = "BLACK"

I think you meant

    colour[u] = "BLACK"

Thank you for catching that. Okay, i decided to test out what the output of the DFS_Out_cycle was. and I noticed that marker =

  7  => 0
  12 => 1
  8  => 0
  1  => 0
  0  => 0
  4  => 1
  6  => 1
  13 => 0
  2  => 0
  10 => 0
  11 => 1
  9  => 0
  3  => 1

This is almost what I was expecting except that:
I expected 13 and 5 to also be marked. And the two cycles should be marked with different cycle numbers.
I’m not sure where in the function is misbehaving

Hi, thank you
the cycle_basis method does give the output I’m expecting.
But it doesn’t seem to use a DFS algorithm to achieve it which is the main part for me.

marker[u] = cycle_number should be marker[cur] = cycle_number, otherwise, it is missing a vertex in each cycle. cycle_number must be a global variable. You can avoid the global by returning the number of cycles created in the recursive call.
Note that if two cycles share a vertex, this vertex will only be print in one cycle, you should store the cycles as you find these. And you will not get all cycles, only a basis (but you will spot every vertex belonging to a cycle).
Here is the code I get:

function DFS_Out_cycle!(u, p, colour, marker, parent, cycle_number, adj_list)
    # global cycle_number
    if colour[u] == "BLACK"
        return cycle_number
    end
    if colour[u] == "GRAY"
        cycle_number += 1
        cur = p
        marker[cur] = cycle_number
        while cur != u
            cur = parent[cur]
            marker[cur] = cycle_number
        end
        return cycle_number
    end
    parent[u] = p
    colour[u] = "GRAY"
    for v in adj_list[u]
        if v == parent[u]
            continue
        end
        cycle_number = DFS_Out_cycle!(v, u, colour, marker, parent, cycle_number, adj_list)
    end
    colour[u] = "BLACK"
    return cycle_number
end

function print_dfs_cycles!(adj_list, marker, cycles_list)
    for i in 0:length(adj_list)
        if marker[i] != 0
            push!(cycles_list[marker[i]], i)
        end
    end
    for (i, l) in enumerate(cycles_list)
        println("Cycle $i : $l")
    end
end

g = Graph(13); add_edge!(g,1,2); add_edge!(g,2,3); add_edge!(g,3,4); add_edge!(g,3,5); add_edge!(g,5,6); add_edge!(g,4,6); add_edge!(g,4,7);
add_edge!(g,7,8); add_edge!(g,6,10); add_edge!(g,5,9);  add_edge!(g,10,11); add_edge!(g,11,12); add_edge!(g,11,13);  add_edge!(g,12,13);

g_l = g.fadjlist
# g_l = adjacency_list(g);
cycle_number = 0;
marker = Dict(i=>0 for i in 0:length(g_l));
parent = Dict(i=>0 for i in 0:length(g_l));
colour = ["WHITE" for key ∈ keys(g_l)]

cycle_number = DFS_Out_cycle!(1, 0, colour, marker, parent, cycle_number, g_l);
cycles_list = [Int[] for i in  1:cycle_number];

print_dfs_cycles!(g_l, marker, cycles_list)

Thank you, for your solution and explanation.

This was not only the solution but also helped me notice something important for my application. I do want to be able to find all nodes that make up a cycles even if if two cycles share a vertex.
I will first try to resolve this by myself first.
thanks again @etienne_dg

Edit: To get all vertex in each cycle even if some cyccles share vertices, I set marker as marker = Dict(i=>[] for i in 0:length(g_l)) so that each node can belong to more than one cycle.