Assignment 6

Deadline: Dec. 16, 2022, 14:00 CET

You will be working with matrices much like last week. This time, the nodes are their indices in the matrix. Node 0 is a special node that we will call “the root”. Node 0 can have no incoming edges.

Exercises

6.1 Find a cycle in a graph

Return the first cycle found by a depth-first traversal of the graph. When it is possible to visit more than one node, visit them in order.

The return value is a sorted list of the nodes that participate in the first cycle found.

6.2 Break one cycle

Void function. Calls the function find_cycle and breaks the cycle found by deleting the edge going from the lowest node in the cycle (n) to its lowest child also in the cycle (m) so that matrix[n][m] = False.

Additionally, m should be attached to the root (node 0), so that matrix[0][m] = True.

For example, if the cycle is [1, 3, 4, 5] and the children of 1 are [2, 3, 4], matrix[1][3] will be set to False and matrix[0][m] will be set to True.

6.3 Get a spanning tree

Get rid of all the cycles in the graph and return a spanning tree in the form of an adjacency matrix. That is, no node can have more than one parent.

When a node has two or more parents, delete all incoming edges except the one coming from the parent with the lowest value.

For example, the following are all the incoming edges of node 2: [3, 2], [6, 2], [4, 2]. The tree should only contain the edge [3, 2]. As a result, matrix[3][2] = True but matrix[6][2] = matrix[4][2] = False.

Wrapping up

Do not forget to

• indicate your name(s) in the file header
• add the honor code (I/We pledge that this code represents my/our own work)
• commit all your changes
• push it to your GitHub repository