Get all cycles in an undirected graph

Given an array of nodes (graph) I want to be able to return a nested array containing all nodes that form a cycle.

This is an unsorted graph, so the recursion could start from any node.

Screenshot_20221212_121438

Example in the screenshot above:
{A,B,C,D,E,F} are the graph.

{A,E,B,F} are one cycle, and {E,B,F,D} is another, but {A,B,D,E,F} should not be counted as a cycle because B “splits” it into the previously named two cycles, but let’s say B wasn’t present, then {A,D,E,F} would be a cycle.

I’ve attempted this with a DFS algorithm, but I kept getting {A,D,E,F} as a cycle.

I’ve been stuck on this problem for literally 4 days, and I’m attempting on just dropping this project…

1 Like

Damn not a single reply…? Well I guess that’s that, I’m going to bed then.

1 Like

It is a cycle. Check out chordless cycle and induced paths (same thing AFAICT).

This paper (found in the wikipedia bibliography for Induced Paths) seems promising. I don’t have time to check it out properly though, at least not right now.

function find_cycle(nodes)
  local visited = {}

  for i = 1, #nodes do
    -- If we've already visited this node, skip it
    if visited[i] then
      goto continue
    end

    -- Mark this node as visited
    visited[i] = true

    -- Keep track of the path that we're traversing
    local path = {i}

    -- Start at the current node and traverse its neighbors
    local j = nodes[i]
    while true do
      -- If we've reached a visited node, then we've found a cycle
      if visited[j] then
        -- Return the cycle as a nested array
        return path
      end

      -- Mark the current node as visited
      visited[j] = true

      -- Add the current node to the path
      path[#path + 1] = j

      -- Move to the next node
      j = nodes[j]
    end

    ::continue::
  end

  -- If we didn't find any cycles, return an empty array
  return {}
end

Here’s an example of how you could use this function:

local nodes = {1, 2, 3, 4, 5, 6, 7, 8}

-- This graph has a cycle formed by nodes 2, 3, and 4
nodes[2] = 3
nodes[3] = 4
nodes[4] = 2

-- This graph has a cycle formed by nodes 5, 6, and 7
nodes[5] = 6
nodes[6] = 7
nodes[7] = 5

-- This graph has no cycles
nodes[8] = nil

print(find_cycle(nodes)) --> {2, 3, 4}

I know that works because there’s only 3 parts and it’s not a complex graph, so this doesn’t solve my problem sadly.

I know {A,D,E,F} is a cycle, but I don’t want that to be returned if there are cycles in that one, only if there are no other cycles I’d want to return {A,D,E,F}.

I’ve looked at cycles in graph theory, while they do seem promising, they are complex nonetheless!

I’ll take another look into graph theory and I’ll also check out induced paths.

Would you happen to have your code for your DFS cycle? Its likely you are only checking for cycles when you backtrack from a node, but not when you first visit a node.

No I deleted the code to start from scratch, but I assure you it wasn’t the case.
The issue is I have no current way of picking which node gets selected next; since it’s undirected.

Though I read a paper earlier and it mentioned getting all cycles and checking for “smaller” cycles in other cycles.

Paper in question:

Though I believe it stated this method is costly, and I think at one point it was traversing 200+ cycles.

“Use allcycles to compute all of the cycles in the new graph. For this graph there are over 200 cycles, which is too many to plot.”

I’m going to refer this post to a friend, maybe he will like the challenge or at least know the answer.

Bump because I am just like that…?