Assignment 5

Deadline: Dec 9, 2022 14:00 CET

Exercises

You are given a class to represent a directed graph. We keep the adjacency matrix as an instance variable as well as a list of nodes in the order that they are represented in the matrix and two dictionaries, one to map nodes to their indices and the other one to map the indices to the nodes.

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 incoming and outgoing adjacent nodes. This is a void 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.

It 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 teh matrix contains a cycle

Implement contains_cycle which returns True iff the matrix of self 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