# Breadth-first search for finding shortest paths in Digraph.
#
# Jesper Larsson, Malmö University, 2018–2020

import collections
from clo_decorators import clo_method

class BFS:
    def __init__(self, G, s):
        edge_to = [-1] * G.V
        dist_to = [-1] * G.V

        q = collections.deque()
        q.append(s)
        dist_to[s] = 0
        while q:                        # while q not empty
            v = q.popleft()
            for w in G.adj(v):
                if dist_to[w] < 0:         # if w not visited
                    q.append(w)
                    edge_to[w] = v
                    dist_to[w] = dist_to[v] + 1

        @clo_method(self)
        def has_path_to(v):
            return dist_to[v] >= 0

        @clo_method(self, 'dist_to')
        def _(v):
            return dist_to[v]

        @clo_method(self)
        def path_to(v):
            if dist_to[v] < 0:
                return None
            p = [v]
            while v != s:
                v = edge_to[v]
                p.append(v)
            p.reverse()
            return p