CO2412 Tutorial 3.5: Week 16

Computational Thinking (CO2412) Tutorial 3.5: Week 16

3.5.1 Adjacency matrix data structure for labelled graphs

The adjacency-matrix & TSP graph notebook contains an implementation of a graph data structure based on an adjacency matrix.

This code implements a labelled graph (with edge labels), specifically, a weighted undirected graph: The edge labels are numbers, which are all zero or positive and understood to represent the distances between nodes; e.g., self._adj_matrix[2][4] is the distance between node 2 and node 4.

Since the graph is undirected, this distance applies both ways, and the adjacency matrix is therefore symmetric: self._adj_matrix[i][j] has the same value as self._adj_matrix[j][i].
The values on the diagonal of the matrix are all set to zero, self._adj_matrix[i][i] = 0, because they represent the distance of a node from itself.
If all the entries of the adjacency matrix are finite, this means that the graph is complete (i.e., there are edges between all pairs of nodes).

Graphs where some of the edges are absent might be represented by setting the distance to infinity, self._adj_matrix[i][j] = math.inf, for the appropriate values of i and j.

Make sure that you understand how this data structure is meant to work. Raise any issues so that they can be discussed.
Implement the missing method, get_length_of_path(self, path), which should be a three-liner that computes the length of a path, say, the cycle 3 → 5 → 0 → 3 if the list [3, 5, 0, 3] is passed as the method argument path.
What modifications would be necessary if you wanted to apply such a data structure to the sort of graphs considered in the assessment problem?

3.5.2 Travelling salesman problem

The code contains a brute-force solver for the travelling salesman problem (TSP). This solver evaluates all the Hamilton cycles in the graph (i.e., all the cycles that visit each node of the graph exactly once) and returns the solution of the TSP, namely, the shortest Hamilton cycle.

In case of n = 12 nodes, the brute-force TSP solver finds 39,916,800 cycles. Why is it this number, and what would it be for n = 15?
This approach becomes forbiddingly expensive for graphs as they grow in size. An approximation to the TSP solution (shortest of all cycles) can be obtained by computing the length of m random cycles and selecting the shortest one out of this random set, rather than out of all possible cycles. Try this out for some moderate values of m such as m = 2, 4, 8, …, 65536. Discuss: If you are satisfied with a close, but inexact solution, would you regard this as a viable method?

Remark: Random Hamilton cycles can be created using random.shuffle() as follows:

random_cycle = list(range(n))
random.shuffle(random_cycle)
random_cycle.append(random_cycle[0])

Submission deadline: 5^th February 2022; discussion planned for 24^th February 2022. Group work by up to four people is welcome.