2.5. Answers

Solution to Exercise 2.1

def length_3_walk_nodes(adj, i):
    node_list = []
    for j in adj[i]:
        for k in adj[j]:
            for q in adj[k]:
                if not q in node_list:
                    node_list.append(q)
    return node_list

c_elegans_graph = [[1, 2, 3], [0, 3], [3, 4, 6], [], [3], [3, 6], [2, 3, 5]]

length_3_walk_nodes(c_elegans_graph, 0)

[1, 2, 3, 5]

Solution to Exercise 2.2

The function length_2_walk_nodes has two nested for loops. The function length_3_walk_nodes has three nested loops. A function length_n_walk_nodes(adj, i, n) would have to have n nested loops for arbitrary n. Such a structure doesn’t exist in Python (or other programming languages, as far as I am aware…)

Solution to Exercise 2.3

Nodes 0 and 1 are never visited because there exists no path from node 2 to node 0 or node 1 .

def bfs(adj, i):
    visited = [i]
    frontier = [i]

    while len(frontier) > 0:
        next = frontier
        frontier = []
        for j in next:
            neighbours = adj[j]
            for k in neighbours:
                if not k in visited:
                    frontier.append(k)
                    visited.append(k)
    return visited

bfs(c_elegans_graph, 2)

[2, 3, 4, 6, 5]

Solution to Exercise 2.4

def bfs(adj, i):
    visited = [i]
    frontier = [i]

    while len(frontier) > 0:
        print(frontier) # print nodes in the current frontier   
        next = frontier
        frontier = []
        for j in next:
            neighbours = adj[j]
            for k in neighbours:
                if not k in visited:
                    frontier.append(k)
                    visited.append(k)
    return visited

bfs(c_elegans_graph, 2)

[2]
[3, 4, 6]
[5]

[2, 3, 4, 6, 5]

[2] is level 0: just the starting node 2.
[3, 4, 6] is level 1: nodes connected directly from node 2.
[5] is level 2: nodes connected directly to nodes in level 1.

Solution to Exercise 2.5

The path distance to a node is just the number of the level that it appears in.

import numpy as np

def path_distances(adj, i):
    visited = [i]
    frontier = [i]

    # create an array of the correct length
    distances = np.zeros(len(adj))
    # set all nodes to a distance of -1
    distances[:] = -1
    # node i is at a distance 0
    distances[i] = 0
    # d will count the layers
    d = 0
    while len(frontier) > 0:
        d += 1 # increase d by 1 at each iteration
        next = frontier
        frontier = []
        for j in next:
            neighbours = adj[j]
            for k in neighbours:
                if not k in visited:
                    frontier.append(k)
                    visited.append(k)
                    distances[k] = d
    return distances

path_distances(c_elegans_graph, 2)

array([-1., -1.,  0.,  1.,  1.,  2.,  1.])