Skip to content

Instantly share code, notes, and snippets.

@Tadaboody
Last active January 9, 2019 14:29
Show Gist options
  • Save Tadaboody/6b436efdb2ac706438f273302d695677 to your computer and use it in GitHub Desktop.
Save Tadaboody/6b436efdb2ac706438f273302d695677 to your computer and use it in GitHub Desktop.
Generic and pythonic implementation of the Depth First Search traversal algorithm
"""Generic and pythonic implementation of the Depth First Search traversal algorithm"""
from typing import Callable, List, Iterable,TypeVar,Hashable, MutableSequence
from pathlib import Path
from collections import deque
T = TypeVar('T', bound=Hashable)
S = TypeVar('S')
def iter_top(stack: MutableSequence[S]) -> Iterator[S]:
"""Iterate a stack as long as it is full, yielding the top every time"""
while stack:
yield stack.pop()
def dfs(root: T, neighbors_func: Callable[[T], Iterable[T]) -> Iterator[T]:
"""Iterate starting from root, going depth first
`neighbors_func`: a function that returns an iterable of the nodes neighbors
"""
stack = deque([root])
visited_nodes = set()
for item in (item for item in iter_top(stack)
if item not in visited_nodes):
visited_nodes.add(item)
stack.extend(neighbors_func(item))
yield item
# Example usage:
def safe_iterdir(path: Path):
return path.iterdir() if path.is_dir() else tuple()
def main():
root = Path(Path.home()/'Desktop')
path: Path
print('\n'.join(str(path.resolve()) for path in dfs(root, safe_iterdir) if path.is_dir()))
if __name__ == '__main__':
main()
@Tadaboody
Copy link
Author

The typing isn't completely correct, if someone here has more mypy experience than me feel free to comment!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment