dls.py

from backtrack import backtrack_path


def dls_recurs(graph, start_node, end_node, limit=1, visited=set(), level=0):
    order = []
    if level > limit:
        return []
    if start_node not in visited:
        order.append(start_node)
        visited.add(start_node)
        for node in graph[start_node]:
            if node not in visited:
                if (level + 1 == limit) and node not in order:
                    order.append(node)
                else:
                    new_order = dls_recurs(
                        graph, node, end_node, limit, visited, level + 1
                    )
                    for sub_node in new_order:
                        if sub_node not in order:
                            order.append(sub_node)
            if end_node in order:
                break
    return order


def dls(graph, start_node, end_node, limit=1, visited=set(), level=0):
    order = dls_recurs(graph, start_node, end_node, limit, visited, level)
    return order, backtrack_path(start_node, end_node, order, graph)