Classify the arcs of a digraph while running the depth-first search algorithm. Implement the depth-first search function dfs(adj_matrix), which takes the adjacency matrix of the digraph as input and returns four lists - the lists of tree arcs, forward arcs, back arcs and cross arcs. Each arc (i, j) is denoted by a Python tuple (i, j). Note: The arcs in each list returned should be ranked in the ascending order of the starting node, then the destination node. For example, if the tree arcs are (1, 2), (1, 3), (0, 1), you should return the tree arcs list as [(0, 1), (1, 2), (1, 3)]. For example: Test Result adj_matrix = [[0,1,1,1],[0,0,0,1],[0,0,0,1],[0,0,0,0]] tree, forward, back, cross = dfs(adj_matrix) print('Tree arcs: {}'.format(tree)) print('Forward arcs: {}'.format(forward)) print('Back arcs: {}'.format(back)) print('Cross arcs: {}'.format(cross)) Tree arcs: [(0, 1), (0, 2), (1, 3)] Forward arcs: [(0, 3)] Back arcs: [] Cross arcs: [(2, 3)]

Here's the implementation of the depth-first search function `dfs`:

def dfs(adj_matrix):
    n = len(adj_matrix)
    visited = [False] * n
    tree, forward, back, cross = [], [], [], []
    
    def dfs_visit(u):
        nonlocal visited, tree, forward, back, cross
        visited[u] = True
        for v in range(n):
            if adj_matrix[u][v] == 1:  # (u, v) is an arc
                if not visited[v]:
                    # (u, v) is a tree arc
                    tree.append((u, v))
                    dfs_visit(v)
                elif visited[v] and v not in [w for (_, w) in tree]:
                    # (u, v) is a back arc
                    back.append((u, v))
                elif visited[v] and u not in [w for (_, w) in tree]:
                    # (u, v) is a forward arc
                    forward.append((u, v))
                else:
                    # (u, v) is a cross arc
                    cross.append((u, v))
    
    for u in range(n):
        if not visited[u]:
            dfs_visit(u)
    
    tree.sort()
    forward.sort()
    back.sort()
    cross.sort()
    
    return tree, forward, back, cross

The function takes an adjacency matrix of a digraph as input and returns four lists - the lists of tree arcs, forward arcs, back arcs, and cross arcs.

The function first initializes the `visited` list to keep track of the visited nodes and initializes the four arc lists to be empty. It then defines a helper function `dfs_visit` that performs the actual DFS traversal from a given node `u`.

The `dfs_visit` function first marks node `u` as visited and then iterates over all nodes `v` that are adjacent to `u`. If `(u, v)` is an arc and `v` has not been visited yet, then `(u, v)` is a tree arc and we add it to the `tree` list and recursively call `dfs_visit` on `v`. If `v` has already been visited and is not a descendant of `u` in the DFS tree, then `(u, v)` is either a forward arc (if `u` is a descendant of `v`) or a cross arc (if `u` is neither a descendant nor an ancestor of `v`). We add `(u, v)` to the corresponding list based on this condition. Finally, if `v` has already been visited and is a descendant of `u` in the DFS tree, then `(u, v)` is a back arc and we add it to the `back` list.

The main `dfs` function then iterates over all nodes in the graph that have not been visited yet and calls `dfs_visit` on each of them. After the traversal is complete, the function sorts each of the four arc lists in ascending order of the starting node, then the destination node, and returns them.

For the given example of `adj_matrix`, the function returns the expected output:

Tree arcs: [(0, 1), (0, 2), (1, 3)]
Forward arcs: [(0, 3)]
Back arcs: []
Cross arcs: [(2, 3)]