I was following Tushar Roy's video on detecting cycles in directed graphs. I understand the use of the white, gray and black sets to detect the cycle but the main thing that I don't understand is how as we check for the length of the white set, next(iter(white)) would know where to go next since the set size has changed. The documentation says that iter gives you an iterator object and next would retrieve the next item. Is the main point that the iterator is evaluated differently each time?
You can find the code here or here.
def has_cycle(graph):
white = set()
gray = set()
black = set()
for vertex in graph.all_vertex.values():
white.add(vertex)
while len(white) > 0:
current = next(iter(white))
if dfs(current, white, gray, black) == True:
return True
return False
def dfs(current, white, gray, black):
move_vertex(current, white, gray)
for neighbor in current.adjacent_vertices:
if neighbor in black:
continue
if neighbor in gray:
return True
if dfs(neighbor, white, gray, black) == True:
return True
move_vertex(current, gray, black)
return False
def move_vertex(vertex, source_set, destination_set):
source_set.remove(vertex)
destination_set.add(vertex)
next(iter(white)) just returns an element of the set white. A set is not ordered so there is no guarantee as to which element is picked. You are right to think the iterator is evaluated for each iteration of the loop.
The fact that the set changes as the loop progresses forbids the use of a for loop.