0
$\begingroup$

I want to detect whether a subset of a directional graph reachable from a given root has a cycle, and print some useful debug information about the cycle. It's not a problem if there's a cycle not reachable from a given root. The useful debug information does not need to be exact (i.e. it is not a problem if the program prints few nodes not belonging to the cycle, as long as the nodes belonging to the cycle are among the output).

I created the following algorithm

function cycle_detect(node current_node, set<node> &parents)
    if (current_node in parents)
        print("cycle found")
        for (parent in parents)
            print(parent)
        exit(1)
    end if
    parents.add(current_node)
    for (child_node in current_node.children)
        cycle_detect(child_node, parents)
    end for
    parents.remove(current_node)
end function

Here the set<node> & is a reference to a set that is initially empty. The algorithm is called as follows:

set<node> parents = empty_set();
cycle_detect(root_node, parents)

This algorithm should print the nodes belonging to the cycle, and the nodes from the parent node to the cycle.

My question is: is my algorithm correct? I assume it is not optimal (has less than optimal running time), but that's not what I'm looking for currently. I'm looking for an algorithm that is (a) simple to implement; (b) prints useful debug information.

If the algorithm is correct, what is its running time? My intuition is it's O(exp(N)) in the worst case. However, I don't believe the worst case running time would occur all that often. (I'm creating a tool the input to which cannot be constructed by malicious actors.)

Is there any simple way to improve the performance of this algorithm to let's say O(N^2)?

I'm thinking perhaps this algorithm should work:

function cycle_detect2(node current_node, set<node> &parents, set<node> &no_cycles)
    if (current_node in no_cycles)
        return
    end if
    if (current_node in parents)
        print("cycle found")
        for (parent in parents)
            print(parent)
        exit(1)
    end if
    parents.add(current_node)
    for (child_node in current_node.children)
        cycle_detect2(child_node, parents, no_cycles)
    end for
    parents.remove(current_node)
    no_cycles.add(current_node)
end function

The algorithm is called as follows:

set<node> parents = empty_set();
set<node> no_cycles = empty_set();
cycle_detect2(root_node, parents, no_cycles)

Is this second algorithm correct? Am I right in that it's O(N^2) if the set is a hash set? If it's a tree set, it's O(N^2 log(N)), right? Here N refers to the node count, not to the arc count.

$\endgroup$
  • 1
    $\begingroup$ There are standard polynomial-time algorithms for cycle detection in graphs. Just use them, especially if you have any reason at all to suspect that your own algorithm is exponential! $\endgroup$ – David Richerby May 4 at 11:06
  • $\begingroup$ Now that I searched for cycle detection algorithms for graphs, I found this which seems very similar to my second algorithm: geeksforgeeks.org/detect-cycle-in-a-graph $\endgroup$ – juhist May 4 at 11:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.