# Outputting all Cycles in an undirected graph using DFS

**URL:** <https://discourse.julialang.org/t/outputting-all-cycles-in-an-undirected-graph-using-dfs/84222>\
**Category:** Graphs\
**Tags:** question, graphs\
**Created:** [July 14, 2022, 3:05pm UTC](https://discourse.julialang.org/t/outputting-all-cycles-in-an-undirected-graph-using-dfs/84222 "2022-07-14T15:05:04Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![Temi-Tory](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/temi-tory/32/29716_2.png) [@Temi-Tory](https://discourse.julialang.org/u/Temi-Tory)\
**Post date:** [July 14, 2022, 3:05pm UTC](https://discourse.julialang.org/t/outputting-all-cycles-in-an-undirected-graph-using-dfs/84222/1 "2022-07-14T15:05:04Z")

</div>

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](https://www.geeksforgeeks.org/print-all-the-cycles-in-an-undirected-graph/)  
For a graph that looks like this:  
 ![image](https://global.discourse-cdn.com/julialang/original/3X/5/1/51ffb9fed1c64b2585e64726e46961d9c639f363.png)

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:

```julia

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)

```

---

<div class="post-metadata">

**Author:** ![Rudi79](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rudi79/32/3884_2.png) [@Rudi79](https://discourse.julialang.org/u/Rudi79)\
**Post date:** [July 14, 2022, 3:38pm UTC](https://discourse.julialang.org/t/outputting-all-cycles-in-an-undirected-graph-using-dfs/84222/2 "2022-07-14T15:38:47Z")

</div>

```julia
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](https://juliagraphs.org/Graphs.jl/dev/algorithms/cycles/#Graphs.cycle_basis)

---

<div class="post-metadata">

**Author:** ![contradict](https://avatars.discourse-cdn.com/v4/letter/c/ac91a4/32.png) [@contradict](https://discourse.julialang.org/u/contradict)\
**Post date:** [July 14, 2022, 3:46pm UTC](https://discourse.julialang.org/t/outputting-all-cycles-in-an-undirected-graph-using-dfs/84222/3 "2022-07-14T15:46:52Z")

</div>

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

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

```

And your last line is

```julia
    colour = "BLACK"

```

I think you meant

```julia
    colour[u] = "BLACK"

```

---

<div class="post-metadata">

**Author:** ![Temi-Tory](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/temi-tory/32/29716_2.png) [@Temi-Tory](https://discourse.julialang.org/u/Temi-Tory)\
**Post date:** [July 14, 2022, 4:12pm UTC](https://discourse.julialang.org/t/outputting-all-cycles-in-an-undirected-graph-using-dfs/84222/4 "2022-07-14T16:12:02Z")

</div>

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 =

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

---

<div class="post-metadata">

**Author:** ![Temi-Tory](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/temi-tory/32/29716_2.png) [@Temi-Tory](https://discourse.julialang.org/u/Temi-Tory)\
**Post date:** [July 14, 2022, 4:13pm UTC](https://discourse.julialang.org/t/outputting-all-cycles-in-an-undirected-graph-using-dfs/84222/5 "2022-07-14T16:13:12Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![etienne\_dg](https://avatars.discourse-cdn.com/v4/letter/e/fbc32d/32.png) [@etienne\_dg](https://discourse.julialang.org/u/etienne_dg)\
**Post date:** [July 15, 2022, 10:01am UTC](https://discourse.julialang.org/t/outputting-all-cycles-in-an-undirected-graph-using-dfs/84222/6 "2022-07-15T10:01:41Z")

</div>

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

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

```

---

<div class="post-metadata">

**Author:** ![Temi-Tory](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/temi-tory/32/29716_2.png) [@Temi-Tory](https://discourse.julialang.org/u/Temi-Tory)\
**Post date:** [July 15, 2022, 11:04am UTC](https://discourse.julialang.org/t/outputting-all-cycles-in-an-undirected-graph-using-dfs/84222/7 "2022-07-15T11:04:38Z")

</div>

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.