jernejfrank commented on code in PR #1483:
URL: https://github.com/apache/hamilton/pull/1483#discussion_r2886624650
##########
hamilton/graph.py:
##########
@@ -1091,13 +1090,19 @@ def directional_dfs_traverse(
nodes = set()
user_nodes = set()
Review Comment:
FYI, this dfs transversal order should in principle be different from the
`iterative` one.
Since we are doing DAGs I think this should be fine.
##########
hamilton/graph.py:
##########
@@ -1091,13 +1090,19 @@ def directional_dfs_traverse(
nodes = set()
user_nodes = set()
- def dfs_traverse(node: node.Node):
- nodes.add(node)
- for n in next_nodes_fn(node):
- if n not in nodes:
- dfs_traverse(n)
- if node.user_defined:
- user_nodes.add(node)
+ def dfs_traverse_iterative(start_node: node.Node):
+ """Iterative DFS to avoid recursion depth limits with large
DAGs."""
+ stack = [start_node]
+ while stack:
+ n = stack.pop()
+ if n in nodes:
+ continue
+ nodes.add(n)
+ if n.user_defined:
+ user_nodes.add(n)
+ for next_n in next_nodes_fn(n):
+ if next_n not in nodes:
+ stack.append(next_n)
Review Comment:
This can lead to duplicate nodes being on stack I think because you don't
mark the nodes as seen until you pop from the stack instead of marking them
when you push onto the stack.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
