The function makes few assumptions about the representation of the graph; instead of a graph object, it takes in two function arguments that are called to describe the graph:
- def NODES(): an iterable returning all nodes
- def EDGES(node): an iterable returning all nodes reached via node's outgoing edges
- def READY(node): called when we know node is not part of any cycles
def find_cycle(NODES, EDGES, READY):Discussion: The EDGES() function may be called multiple times for the same node, and the for loop does some duplicate work in that case. A straightforward fix for this inefficiency is to maintain a parallel stack of iterators that is pushed and popped at the same times at the main stack, and at all times contains iter(node). I'll leave that version as an excercise.
todo = set(NODES())
node = todo.pop()
stack = [node]
top = stack[-1]
for node in EDGES(top):
if node in stack:
if node in todo:
node = stack.pop()
Update: Fixed a typo in the algorithm (EDGES(top)) and renamed all to todo.