Assignment 4 - cycle detection

Deadline: Dec 2, 2024 14:00 CET

This assignment includes a set of exercises with cycle detection in undirected graphs.

Exercises

You are given a class to represent an undirected graph. There is a couple of instance variables:

• self.nodes: a set of all nodes
• self.nodes2idx : a dictionary mapping the nodes to the indices
• self.idx2nodes : a dictionary mapping the indices to the nodes
• self.matrix : a numpy adjacency matrix representing the structure of the graph. Self-loops are not possible, therefore the diagonal always remains filled with False. You can think of an undirected graph as a directed graph will all edges being bidirectional. Therefore, the matrix is always symmetrical to the diagonal: if there is an edge from a to b, there must be an edge from b to a. This can be seen from how the matrix is initialized.

You are allowed to create helper methods and add default parameters as long as the tests can be run without changes.

5.1 Add a node to the matrix with its incident edges.

Implement the method add_node(), which should add a node to the matrix with the associated neighbor nodes. This is a void method. You may make use of the add_edges() method.

5.2 DFS and cycles

Detect a cycle by using a depth-first traversal of the graph from start node. When it is possible to visit more than one node, visit them in alphabetical order. You may assume all nodes have string names.

The method should return a tuple where the first element is a boolean (was a cycle found in this traversal) and the second one is the “visited” dictionary.

5.3 Implement method to determine if the matrix contains a cycle

Implement contains_cycle which returns True iff the graph contains a cycle.

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