Python Programming

This lab exercise is designed to try to get you to apply what you have learnt to a practical problem.

Many thanks to the following people for contributing to these exercises: Luca Grillotti

Description of the Problem

In this problem, you will try to implement a several functions that perform operations on graphs.

A graph is made of:

• nodes
• edges that link some pairs on nodes together

We will consider 2 types of graph:

• Directed Graphs, in which the edges have a one-way direction
• Undirected Graphs, in which every edge is bidirectional

Thus, an undirected graph can be seen as a special kind of directed graph in which: if there is an edge from a to b, then there is also an edge from b to a.

A remark on function signature

In the skeleton code, most of the function definition have the following form:

def depth_first_search(self,
                       node_start: str,
                       nodes_already_visited: List[str]=None,
                       ) -> List[str]:

Those indications are purely indicative for the user and the IDEs. Python does not take them into account when it interprets the code. For example, the above function would be interpreted this way:

def depth_first_search(self,
                       node_start,
                       nodes_already_visited=None,
                       ):

But the signature given above provides a significant amount of information regarding the function argument and return type:

• node_start should be of type str
• nodes_already_visited should be a list of str
• the function depth_first_search(...) should return a list of str

As explained above, List[X] refers to a list of type X. It comes from the typing module. Here are some examples of other annotations you may find later in this course:

• Tupe[str, float, int] refers to a tuple (str, float, int) such as ("Hello World", 3.14, 42).
• Dict[int, str] refers to a dictionary whose:
  • keys are integers
  • values are strings
    {1: “Hello”, 2: “World”} is an example of such a directory.
• Union[int, str] refers to an element which is either of type int or of type str.

Problem

You may find the skeleton of the code to complete here

Most of the functions should be implemented following their order of appearance in the document. All functions that should be implemented have a # TODO comment after their docstring.

All the necessary documentation is provided in the docstrings of the functions to implement.

For each method to implement, do not hesitate to use the methods you will have implemented so far.