# 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:

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:

``````
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";
if v==parent[u]
continue
end
end
colour = "BLACK"
end

if marker[i] != 0
append!(cycles_list[marker[i]], i)
end
end
end

else
end
end
end
end

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

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;
``````

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

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

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.