Outputting all Cycles in an undirected graph using DFS

Specific Domains Graphs
,
1

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

3

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"
4

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

5

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.

6

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

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.