Given the adjacency matrix of a digraph G, and a pair of starting node s and destination node d, determine if the destination d is reachable from s. Implement the following function is_reachable(adj_matrix, s, d), where adj_matrix is the adjacency matrix with 1 denoting an arc exists, and 0 otherwise. The function return True if d is reachable from s, and False otherwise. Note: You can use any Python built-in package to implement stack/queue/priority queue if needed. For example: Test Result adj_matrix = [[0,1,1,0],[0,0,1,0],[1,0,0,0],[0,1,0,0]] print(is_reachable(adj_matrix, 0, 3)) print(is_reachable(adj_matrix, 3, 0)) False True

Here's one possible implementation of the is_reachable function using breadth-first search:

from collections import deque

def is_reachable(adj_matrix, s, d):
    n = len(adj_matrix)
    visited = [False] * n
    queue = deque([s])
    visited[s] = True
    
    while queue:
        node = queue.popleft()
        if node == d:
            return True
        for neighbor, arc in enumerate(adj_matrix[node]):
            if arc == 1 and not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)
    
    return False

The function starts by initializing a list of visited nodes with False, and a queue with the starting node s. It then enters a loop where it repeatedly dequeues a node from the queue, and checks if it is equal to the destination node d. If it is, the function returns True, indicating that d is reachable from s. Otherwise, the function enqueues all unvisited neighbors of the dequeued node, and marks them as visited.

If the loop completes without finding the destination node, the function returns False, indicating that d is not reachable from s.

The time complexity of this implementation is O(n^2), where n is the number of nodes in the graph, since we may visit all nodes and arcs in the worst case. However, the actual time complexity may be lower depending on the structure of the graph and the position of s and d.