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.
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…
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 {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.
