4.1. Homework Answers and Mark Scheme#

Results/objectives Maximum score: 5 (see mark breakdown below)
These marks are awarded for submissions that produce the correct outputs. The code should run without errors and should fulfil the criteria set by the question. You must ensure that you include a written explanation of the output produced by your code.

Implementation/technique Maximum score: 5
Marks are awarded here for demonstration of good coding practice. The code should be easy to follow. It should use methods/techniques demonstrated in the notes appropriately and correctly. Markers will also be looking out for code that is reasonably efficient, as this is important in the field of numerical methods. You must be able to explain/justify your method to the marker.

The specimen answers below are just one example of how to solve the problems. My answers are not necessarily more ‘correct’ than yours!

4.1.1. Question 1#

x = [[3], [11, 6, 5], [4, 11, 5], [0], [2, 6, 6], [12, 19, 2, 1],
        [4, 17, 1, 4, 8],[14, 11], [6], [], [15, 11], [10, 2, 1, 16, 15, 7],
        [5], [], [7], [10, 11], [11], [6, 19], [], [5, 17]]

# The following code loops over every edge in the graph.
# For each edge i -> j it then checks if there exists an
# edge j -> i.

n = len(x)
T = True
for i in range(n):
    for j in x[i]:
        if not i in x[j]:
            T = False
            
print("x is the adjacency list of a directed graph:", T)

x is the adjacency list of a directed graph: True

1 mark for a solution which works for any adjacency list.

4.1.2. Question 2#

Note that the question asks for two nodes not connected by a path.

# First We use the breadth first search to determine all nodes connected
# to node 0


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

comp1 = bfs(x, 0)

# Because the graph is not connected, comp1  only contains a subset
# of the nodes. Any node not in comp1 is not connected to node 0
# by a path.

# The following loop terminates once it finds a node not in comp1:

i = 0
while i in comp1:
    i += 1
print("Node 0 is not connected to node", i) # [0, 3]

Node 0 is not connected to node 1

1 mark for a solution which finds any pair of disconnected nodes (or a solution which finds all pairs of disconnected nodes).

NB the function bfs(adj, i) is defined in the notes.

4.1.3. Question 3#

See the Exercise 2.5 to understand how to calculate path distances by making a simple change to the bfs function.

import numpy as np

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

    distances = np.zeros(len(adj))
    distances[:] = -1
    distances[i] = 0
    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

# First create an n by n array
# whose elements are the path distances
# between node pairs
n = len(x)
distances = np.zeros((n, n))
for i in range(n):
    distances[i] = path_distances(x, i)

# The maximum path distance is the maximum
# of the array
max_dis = np.max(distances)

print("Maximum distance:", max_dis)

# Now loop over the array and determine all node
# pairs with the maximum distance
node_pairs = []
for i in range(n):
    for j in range(i-1):
        if distances[i, j] == max_dis:
            node_pairs.append([i, j])

print("Node pairs with maximum path distance:", node_pairs)

Maximum distance: 5.0
Node pairs with maximum path distance: [[14, 8], [14, 12], [17, 14], [19, 14]]

1.5 marks for a solution which finds all four pairs of nodes with path distance 5 (it is not necessary to state the distance). 1 mark if only one node-pair is identified.

4.1.4. Question 4#

# Loop over every node in the graph, performing BFS
# on each to determine its connected component.
# Maintain a list of visited nodes and only perform
# the BFS if the node hasn't already been visited.

visited = []
components = []
for i in range(len(x)):
    if not i in visited:
        comp = bfs(x, i)
        components.append(comp)
        # these two lines could be replaced by
        # visited.extend(comp)
        for j in comp:
            visited.append(j)

print("Graph components:", components)

Graph components: [[0, 3], [1, 11, 6, 5, 10, 2, 16, 15, 7, 4, 17, 8, 12, 19, 14], [9], [13], [18]]

1.5 marks for a solution which identifies the nodes in each of the 5 connected components. Subtract 0.5 marks if any components are repeated. Subtract 0.5 marks if the method is not entirely automated.