Skip to content

Instantly share code, notes, and snippets.

@tuck1s
Last active November 30, 2023 10:54
Show Gist options
  • Save tuck1s/01f3b4a05749f9319056e894ef5b795b to your computer and use it in GitHub Desktop.
Save tuck1s/01f3b4a05749f9319056e894ef5b795b to your computer and use it in GitHub Desktop.
from copy import deepcopy
from collections import deque
# Expand a tree to the "leaves"
def leaves_of(item, dependencies):
# return the leaf nodes
def dfs2(item, level, visited):
result = []
if item in dependencies:
visited.add(item) # mark that we've seen this branch
#print(f"{'.'*level}br: {item}")
for i2 in dependencies[item]:
if i2 in visited:
raise ValueError(f"Circular dependency detected, on item={item}, loops back to {i2}, visited branches={visited}")
result += dfs2(i2, level+1, deepcopy(visited))
else:
#print(f"{'.'*level}leaf:{item}")
result.append(item) # a leaf node
return result
return dfs2(item, 0, set())
#----- NON recursive version
def leaves_of2(item, dependencies):
stack = deque([(item, set())])
result = []
while stack:
current_item, visited = stack.pop()
if current_item in dependencies:
visited.add(current_item)
for next_item in dependencies[current_item]:
if next_item in visited:
raise ValueError(f"Circular dependency detected, on item={current_item}, loops back to {next_item}, visited branches={visited}")
stack.append((next_item, visited.copy()))
else:
result.append(current_item)
return result
# Example usage:
items = ['A', 'B', 'C']
dependency_graph = {
'A': ['B', 'C'],
'B': ['C'],
'C': ['D'], # Acceptable
# 'C': ['D', 'A'], # This intentionally shows detection a fatal loop!
}
for item in items:
try:
print("Recursion RESULT: ", end='')
print(item, leaves_of(item, dependency_graph))
except ValueError as e:
print(e)
try:
print("Deque RESULT: ", end='')
print(item, leaves_of2(item, dependency_graph))
except ValueError as e:
print(e)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment