from typing import List
from typing import Set


def send_probe(wfg: List[List[int]], visited: Set[int], initiator: int, source: int, destination: int) -> bool:
    """Run through the complete graph to check for cycles

    Args:
        wfg (List[List[int]]): The wait for graph in form of a 2D mtrix of ints
        visited (set): Set to denote which sites have been probed
        initiator (int): The original initiator for the probe 
        source (int): The current probe's source site
        destination (int): The current probe's destination site


    Returns:
        bool: Is there a cycle between initiator and destination
    """

    tmp = False

    print(f"Probe: ({initiator+1}, {source+1}, {destination+1})")
    
    
    ## Check all sites wrt to the dest
    for site, is_wait in enumerate(wfg[destination]):
        ## If the dest is waiting for a site
        if site not in visited and site != destination and is_wait == 1:
            visited.add(site)        
            ## If we find a probe with initiator same as destination,
            ## Return True
            if initiator == destination:
                print("Deadlock detected")
                return True
            
            ## Otherwise, send a new probe to the new site
            ## from destination to the site its waiting for

            tmp = send_probe(wfg, visited, initiator, destination, site) 
            if tmp:
                return True

    ## If all sites are exhausted,
    ## Return False
    return tmp