graph_searches.py

from collections import deque
from typing import Dict, Hashable, MutableSet, MutableSequence, Set, TypeVar, Union, Generic, List, Generator

Node = Hashable
Adjacent = Union[MutableSequence[Hashable], MutableSet[Hashable]]


def depth_first_connected_nodes_iterative(graph: Dict[Node, Adjacent],
                                          start: Node) -> Set[Node]:
    to_visit = [start]
    visited = set()
    while to_visit:
        node = to_visit.pop()
        visited.add(node)
        new = graph[node] - visited
        to_visit.extend(new)
    return visited


def depth_first_find_goal_iterative(graph: Dict[Node, Adjacent],
                                    start: Node,
                                    goal: Node) -> bool:
    to_visit = [start]
    visited = set()
    while to_visit:
        node = to_visit.pop()
        if node == goal:
            return True
        visited.add(node)
        new = graph[node] - visited
        to_visit.extend(new)
    return False


def depth_first_find_paths_iterative(graph: Dict[Node, Adjacent],
                                     start: Node,
                                     goal: Node) -> List[Node]:
    complete_paths = []
    partial_paths = [[start]]
    while partial_paths:
        path = partial_paths.pop()
        node = path[-1]
        for next_node in graph[node] - set(path):
            new_path = path + [next_node]
            if next_node == goal:
                complete_paths.append(new_path)
            else:
                partial_paths.append(new_path)
    return complete_paths


def depth_first_find_paths_iterative_generator(graph: Dict[Node, Adjacent],
                                               start: Node,
                                               goal: Node) -> List[Node]:
    partial_paths = [[start]]
    while partial_paths:
        path = partial_paths.pop()
        node = path[-1]
        for next_node in graph[node] - set(path):
            new_path = path + [next_node]
            if next_node == goal:
                yield new_path
            else:
                partial_paths.append(new_path)


def depth_first_connected_nodes_recursive(graph: Dict[Node, Adjacent],
                                          start: Node,
                                          visited: Set[Node] = None) -> Set[Node]:
    if visited is None:
        visited = set()
    visited.add(start)
    for next_node in graph[start] - visited:
        depth_first_connected_nodes_recursive(graph, next_node, visited)
    return visited


def depth_first_find_goal_recursive(graph: Dict[Node, Adjacent],
                                    start: Node,
                                    goal: Node,
                                    visited: Set[Node] = None) -> bool:
    if visited is None:
        visited = set()
    visited.add(start)
    for next_node in graph[start] - visited:
        if next_node == goal or depth_first_connected_nodes_recursive(graph, next_node, visited):
            return True
    return False


def depth_first_find_paths_recursive(graph: Dict[Node, Adjacent],
                                     start: Node,
                                     goal: Node,
                                     partial_path: List[Node] = None,
                                     completed_paths: List[List[Node]] = None) -> List[List[Node]]:
    if partial_path is None:
        partial_path = [start]
    if completed_paths is None:
        completed_paths = []
    for next_node in graph[start] - set(partial_path):
        new_path = partial_path + [next_node]
        if next_node == goal:
            completed_paths.append(new_path)
        else:
            depth_first_find_paths_recursive(graph, next_node, goal, new_path, completed_paths)
    return completed_paths


def depth_first_find_paths_recursive_generator(graph: Dict[Node, Adjacent],
                                               start: Node,
                                               goal: Node,
                                               partial_path: List[Node] = None) -> List[Node]:
    if partial_path is None:
        partial_path = [start]
    for next_node in graph[start] - set(partial_path):
        new_path = partial_path + [next_node]
        if next_node == goal:
            yield new_path
        else:
            depth_first_find_paths_recursive_generator(graph, next_node, goal, partial_path)


def breadth_first_connected_nodes(graph: Dict[Node, Adjacent],
                                  start: Node) -> Set[Node]:
    to_visit = deque([start])
    visited = set()
    while to_visit:
        node = to_visit.popleft()
        visited.add(node)
        new = graph[node] - visited
        to_visit.extend(new)
    return visited


def breadth_first_find_goal(graph: Dict[Node, Adjacent],
                            start: Node,
                            goal: Node) -> bool:
    to_visit = deque([start])
    visited = set()
    while to_visit:
        node = to_visit.popleft()
        if node == goal:
            return True
        visited.add(node)
        new = graph[node] - visited
        to_visit.extend(new)
    return False


def breadth_first_find_paths(graph: Dict[Node, Adjacent],
                             start: Node,
                             goal: Node) -> List[Node]:
    complete_paths = []
    partial_paths = deque([[start]])
    while partial_paths:
        path = partial_paths.popleft()
        node = path[-1]
        for next_node in graph[node] - set(path):
            new_path = path + [next_node]
            if next_node == goal:
                complete_paths.append(new_path)
            else:
                partial_paths.append(new_path)
    return complete_paths


def breadth_first_find_paths_generator(graph: Dict[Node, Adjacent],
                                       start: Node,
                                       goal: Node) -> List[Node]:
    partial_paths = deque([[start]])
    while partial_paths:
        path = partial_paths.popleft()
        node = path[-1]
        for next_node in graph[node] - set(path):
            new_path = path + [next_node]
            if next_node == goal:
                yield new_path
            else:
                partial_paths.append(new_path)