Practical activity

Presentation & objectives

In this activity, you will have to develop a solution to grab a single piece of cheese in a maze without mud. Here, we choose to focus on two algorithms: the breadth-first search, and the depth-first search.

Activity contents

1 — Depth-first search (DFS)

1.1 — Get prepared

Before we start, let’s first create the files we need in the workspace:

• pyrat_workspace/players/DFS.py – Duplicate the file TemplatePlayer.py, and rename it DFS.py. Then, as in the previous session, rename the class to DFS.

• pyrat_workspace/games/visualize_DFS.ipynb – Create a file that will start a game with a DFS player, in a maze with no mud (argument mud_percentage), and a single piece of cheese (argument nb_cheese). Optionally, you can set a random_seed and a trace_length. You should draw inspiration from the other files in the games subdirectory you encountered in the previous session.

  Try to do it by yourself first. If you have trouble, here is the correction:

  Correction

  • Click here to download the correction for visualize_DFS.ipynb.

1.2 — The traversal method

1.2.1 — Implementation

In order to write a DFS algorithm, we will need to perform a traversal. Let’s create a function for that. Copy-paste the following piece of code into your DFS.py file, as a method of the DFS class:

def traversal ( self:   Self,
                graph:  Graph,
                source: Integral
              ) ->      Tuple[Dict[Integral, Integral], Dict[Integral, Optional[Integral]]]:

    """
        This method performs a DFS traversal of a graph.
        It returns the explored vertices with associated distances.
        It also returns the routing table, that is, the parent of each vertex in the traversal.
        In:
            * self:   Reference to the current object.
            * graph:  The graph to traverse.
            * source: The source vertex of the traversal.
        Out:
            * distances:     The distances from the source to each explored vertex.
            * routing_table: The routing table, that is, the parent of each vertex in the traversal (None for the source).
    """

    # Your code here

Now, fill this method so that it performs a depth-first search, as described in the provided documentation. Please make sure that the returned variables have the indicated types.

1.2.2 — Tests

To make sure that your code works, it is essential to test it. In fact, we distinguish three big families of tests:

• Debug – Run your program frequently, so that you can easily detect an error. Indeed, it is easier to find an error in the last few lines of code you wrote than in the whole program.

• Statistical tests – As we mentioned in the previous session, such tests can help you prove properties on your programs. They are not meant to help make your codes work though.

• Unit tests – Unit tests are an automatized way of debugging. The idea is to define many inputs for a given function, for which you know the expected output (or properties of the output), and to call that function with them. If all produced outputs correspond to the expected outputs (or validate the properties), we then have a good confidence that the function is correct. A good set of unit tests should try to cover all possible execution cases of the function (e.g., all branches of a if condition). It should guarantee that the function works in standard usage cases, but also in cornercase ones.

In this activity, we provide you some unit tests, so that you can check that your code works properly. Later, you will have to develop your own tests, so let’s have a look at those already.

First, create a pyrat_workspace/tests subdirectory. Then, download the following test file for the DFS player, and place it in that directory.

If you understood well the depth-first search algorithm, you should see that there are many possible solutions, depending on the order in which neighboring vertices are explored. For this reason, we cannot directly create a test to verify that, for a given graph $G$, we obtain a particular routing table. Instead, we are going to evaluate properties of the solution produced by the traversal function:

• Outputs are of the expected types.
• All vertices are visited.
• The routing table is a tree, with root corresponding to the start of the traversal.
• The found distances are correct, i.e., strictly positive and increasing, except for the start vertex which should be 0.

Let’s have a look at the provided test file. First, unit tests should be defined in a class inheriting from unittest.TestCase as follows:

class DFSTests (unittest.TestCase):

Then, for each method you want to test, you should create a dedicated function. For instance, here, we want to test the method traversal of class DFS, so let’s create a method named test_traversal:

def test_traversal ( self: Self
                   ) ->    None:

In this method, we will check the points listed above. To have a greater confidence in the tests, we will check them on multiple random mazes. To generate such mazes, we use one of the PyRat classes that does that:

# Constants
NB_GRAPHS = 10
WIDTHS = [2, 30]
HEIGHTS = [2, 30]
CELL_PERCENTAGES = [20.0, 100.0]
WALL_PERCENTAGES = [20.0, 100.0]
MUD_PERCENTAGE = 0.0

# Test on several graphs
for i in range(NB_GRAPHS):
    
    # Instantiate the player
    player = DFS()

    # Generate a random maze
    # We use a fixed random seed for reproducibility of tests
    rng = random.Random(i)
    maze = BigHolesRandomMaze(width = rng.randint(WIDTHS[0], WIDTHS[1]),
                              height = rng.randint(HEIGHTS[0], HEIGHTS[1]),
                              cell_percentage = rng.uniform(CELL_PERCENTAGES[0], CELL_PERCENTAGES[1]),
                              wall_percentage = rng.uniform(WALL_PERCENTAGES[0], WALL_PERCENTAGES[1]),
                              mud_percentage = MUD_PERCENTAGE,
                              random_seed = i)

Then, we run the traversal function on that maze, from a random vertex:

# Choose a random starting vertex
start_vertex = rng.choice(maze.vertices)

# Perform the traversal
distances, routing_table = player.traversal(maze, start_vertex)

Now that everything is ready, let’s make the tests! First, you were asked to ensure that the outputs of traversal have a certain type:

# Check the output type for distances
# It should be a dictionary with integer keys and integer values
self.assertTrue(isinstance(distances, Dict))
self.assertTrue(all(isinstance(k, Integral) for k in distances.keys()))
self.assertTrue(all(isinstance(v, Integral) for v in distances.values()))

# Check the output type for the routing table
# It should be a dictionary with integer keys and integer or None values
self.assertTrue(isinstance(routing_table, Dict))
self.assertTrue(all(isinstance(k, Integral) for k in routing_table.keys()))
self.assertTrue(all(isinstance(v, (type(None), Integral)) for v in routing_table.values()))

Then we want to check that all vertices were visited. Equivalently, we can check that all vertices were given a distance to the start vertex when performing the search.

# All vertices should be visited
# Equivalently, the distances should have the same keys as the maze vertices
self.assertEqual(sorted(set(distances.keys())), sorted(maze.vertices))

Now, let’s ensure that the start vertex is the root of the tree, and that no other vertex could be a root:

# Check that the start vertex is the only tree root
self.assertEqual(routing_table[start_vertex], None)
self.assertTrue(all(routing_table[v] is not None for v in routing_table.keys() if v != start_vertex))
self.assertEqual(distances[start_vertex], 0)
self.assertTrue(all(distances[v] > 0 for v in distances.keys() if v != start_vertex))

Finally, let’s check that we have a valid tree. To detect a tree, we should be able to reach the root from any vertex. At the same time, we can check that the distance to a vertex is always higher than the distance to its parent:

# We check that the routing table is a tree
# Also we check that associated distances are decreasing as we go to the root
for vertex in routing_table:

    # We check that the parent is closer to the root
    if routing_table[vertex] is not None:
        self.assertTrue(distances[routing_table[vertex]] < distances[vertex])
    
    # We ckeck that we can reach the root from any vertex
    path = [vertex]
    while routing_table[path[-1]] is not None:
        self.assertTrue(routing_table[path[-1]] not in path)
        path.append(routing_table[path[-1]])

Now, run the tests by running the command at the bottom of the file. If everything is right, you should observe the following output:

test_traversal (__main__.DFSTests)
This method tests the 'traversal' method. ... ok

----------------------------------------------------------------------
Ran 1 test in 2.453s

OK

1.3 — Using the routing table

1.3.1 — Implementation

Now that you have a working traversal, let’s write a method that exploits the routing table to return the series of locations to follow to reach a given vertex. Copy-paste the following piece of code into your DFS.py file as a mthod of the DFS class:

def find_route ( self:          Self,
                 routing_table: Dict[Integral, Optional[Integral]],
                 source:        Integral,
                 target:        Integral
               ) ->             List[Integral]:

    """
        This method finds the route from the source to the target using the routing table.
        In:
            * self:          Reference to the current object.
            * routing_table: The routing table.
            * source:        The source vertex.
            * target:        The target vertex.
        Out:
            * route: The route from the source to the target.
    """

    # Your code here

Now, fill that function so that it returns the route from the source to the target. Again, make sure that your code respects the types.

1.3.2 — Tests

Now that we have written another method, let’s add some tests. Here, note that for a given routing table, source and target vertices, there is only a single possible solution. Therefore, we can call the method on fixed scenarios.

Copy the following code into your tests_DFS.ipynb file, as a new method of your DFSTests class:

def test_find_route ( self: Self,
                    ) ->    None:
    
    """
        This method tests the 'find_route' method.
        Here, we want to make sure that the output corresponds indeed to a route from the start to the end.
        We are going to check the following:
        - Outputs are of the expected types.
        - The route is a valid path from the start to the end.
        The method will be tested on some controlled examples, where we can easily check the validity of the output.
        In:
            * self: Reference to the current object.
        Out:
            * None.
    """

    # Constants
    INPUTS = [{"routing_table": {0: None, 1: 0, 2: 1, 3: 2, 4: 3},
               "start": 0,
               "end": 4},
              {"routing_table": {0: 2, 1: None, 2: 1, 3: 0, 4: 0, 5: 4, 6: 1},
               "start": 1,
               "end": 6}]

    # Test on several controlled examples
    for i in range(len(INPUTS)):
        
        # Instantiate the player
        player = DFS()

        # Get the input data
        routing_table = INPUTS[i]["routing_table"]
        start = INPUTS[i]["start"]
        end = INPUTS[i]["end"]

        # Find the route
        route = player.find_route(routing_table, start, end)

        # Check the output type
        # It should be a list of integers
        self.assertTrue(isinstance(route, List))
        self.assertTrue(all(isinstance(v, Integral) for v in route))

        # Check that the route is a valid path from the start to the end
        self.assertEqual(route[0], start)
        self.assertEqual(route[-1], end)
        self.assertTrue(all(routing_table[route[j + 1]] == route[j] for j in range(len(route) - 1)))

Here, we define two routing tables at hand, and use them as inputs to test the find_route method. We could have defined many more, and also used random valid routing tables, generated using the traversal function that we previously developed and validated.

In these tests, we perform a type check of the output, and then check that the parents in the routing table indeed appear as predecessors in the obtained route. Also, we check that the route indeed goes from the start to the end.

Here is what you should obtain when running the script:

test_find_route (__main__.DFSTests)
This method tests the 'find_route' method. ... ok
test_traversal (__main__.DFSTests)
This method tests the 'traversal' method. ... ok

----------------------------------------------------------------------
Ran 2 tests in 2.798s

OK

1.4 — Putting it all together

1.4.1 — Implementation

Now, we just need to assemble bricks. Here are the modifications you should make:

• __init__ – Update your __init__ function so that you declare an attribute self.actions = [].

• preprocessing – During preprocessing, use the methods introduced earlier (self.traversal and self.find_route) to compute the actions from your initial location (game_state.player_locations[self.name]) to the location of the only piece of cheese (game_state.cheese[0]). Then, store these actions into attribute self.actions. To obtain actions from a route, the Maze class provides a method locations_to_actions.

• turn – During each turn, you should return an action from self.actions. Just extract the next action to perform from that attribute, and return it.

1.4.2 — Tests

Now, use your visualize_DFS.ipynb script to play with your player! The following video shows you an example of what you should observe:

2 — Breadth-first search (BFS)

As you can see in the previous video, the DFS finds a path that is not exactly the shortest. We will now use another traversal algorithm called the BFS. This algorithm has the property to return the shortest path in an unweighted graph.

Following the same steps as previously to create a player that follows a path found by a BFS algorithm to catch the piece of cheese. Create a file for starting a game, called visualize_BFS.ipynb in the pyrat_workspace/games subdirectory, and a player file called BFS.py in the pyrat_workspace/players subdirectory. For the latter, you should start from a copy of your DFS.py file, as there won’t be a lot of differences!

Also, don’t forget to test your functions! Here are the tests you can use to make sure your code works. Note how similar they are to those of the DFS. Also, note that we added a new test function to verify that we indeed find the shortest paths, on a few controlled examples for which only a single routing table is solution of the traversal.

The following video shows you an example of what you should observe:

3 — Compare with the randoms

Now that you have two new players, it would be interesting to compare them with the random players you developed in the previous session. Adapt (and rename) the compare_all_randoms.ipynb game script to integrate the DFS and BFS players in the analysis.

Also, try to answer the following questions:

• Is DFS significantly better than the best RandomX program you wrote?
• Is BFS significantly better than DFS?

To go further

4 — Factorize codes

As you may have noticed, the BFS and DFS traversals are extremely similar. In fact, the data structure used determines the order in which vertices are explored. Indeed, using a FIFO, the traversal performs a breadth-first search. Using a LIFO, the traversal performs a depth-first search.

Therefore, generalizing a bit, a traversal can be seen as a global algorithm that, at some point, needs to:

• Create a data structure.
• Append an element to the data structure.
• Extract an element from the data structure.

The object-oriented programming framework makes it pretty convenient in this kind of situations, through a mechanism called “inheritance”. The idea is to have a base class that factorizes the common code, and subclasses that specialize the particularities. Schematically, we could organize our code as follows:

The diagram above is a simplified version of what we call a “UML class diagram”. It reads as follows:

• We have three classes: Traversal, BFSTraversal and DFSTraversal. Traversal having its name in italic, it is an “abstract” class, meaning that it cannot be instantiated. It is only there to abstract the notion of a traversal of a graph, and will group common aspects to all traversals.
• The class Traversal has two attributes (all set by the traversal method): routing_table and distances.
• The class Traversal has five methods: traversal, find_route, initialize_structure, add_to_structure and get_from_structure. Note that the last three are in italic. This means that they are “abstract methods”, i.e., they will do nothing and should be implemented in the child classes.
• The arrows mean that classes BFSTraversal and DFSTraversal inherit from Traversal. Therefore, they will have access to all attributes and methdods defined in Traversal.
• Note that these two classes redefine the abstract methods in Traversal to make them usable.

With this organization, you can instantiate bfs = BFSTraversal() and call the method bfs.traversal(...). If traversal calls initialize_structure, then it is the implementation of initialize_structure inside BFSTraversal that will be called. Similarly, you can instantiate dfs = DFSTraversal() and call the method dfs.traversal(...). In that case, traversal will use the implementation of initialize_structure inside DFSTraversal. As you see, the same code in the traversal function will thus behave differently, as it was specialized by the child classes.

Let’s put that into practice:

• First, download this archive, and extract its contents in a new subdirectory pyrat_workspace/utils. This archive contains the codes corresponding to the three classes in the diagram above.

• Then, download this player file, that contains a player that can perform one traversal or the other. Place this file inside your pyrat_workspace/players subdirectory.

  Information

  Note that files in the pyrat_workspace/utils subdirectory are imported by TraversalPlayer.py as follows:

  ​

  Python

  # Add needed directories to the path
  this_directory = os.path.dirname(os.path.realpath(__file__))
  sys.path.append(os.path.join(this_directory, "..", "utils"))

  This says that, starting from the directory containing TraversalPlayer.py (i.e., the pyrat_workspace/players subdirectory) the utils directory can be found by going one directory backward. Using this technique to import modules can be a litle more flexible than the following code:

  ​

  Python

  # Add needed directories to the path
  sys.path.append(os.path.join("..", "utils"))

  Contrary to the previous code, this version will search for utils in the parent directory, starting from the directory that contains the script being executed.

  In general, in PyRat, all .py files should use the first code, as they are meant to be imported. On the other hand, all .ipynb files should use the second code, as they are the files being executed (and __file__ is not a supported command in such files).

• Finally, download this game file, and this game file These games respectively create a game with a BFS player and a DFS player, using the factorized code. Place these files inside your pyrat_workspace/games subdirectory.

Now, fill the missing codes in Traversal.py, drawing inspiration from what you did earlier in the practical activity. The codes in BFSTraversal.py and DFSTraversal.py are already functional. Have a look at them to see how they differ!

Once you are done, run the visualize_TraversalPlayer.ipynb script to run games with the new BFS and DFS programs.

5 — Limit the traversal algorithm

In order to compute the needed information to move to the piece of cheese, you only need to determine where that cheese is. However, the BFS is a 1-to-* algorithm, i.e., it will return the shortest paths from a location to all others. Thus, all computations performed after you have found this particular piece of cheese are useless, as you will not use the results.

A possible improvement is therefore to update the traversal algorithm to stop when all needed information is available.

To go beyond

6 — A recursive DFS

Since DFS uses a stack, and recursive functions exploit the call stack of programs, it makes DFS quite easy to code recursively. Find some online resources to guide you, and try to do it!

7 — Extend the unit tests

As mentioned earlier, the unit tests we provide you in this activity correspond to the standard usage of the tested functions. One possible thing you can do is to anticipate possible errors of the user, and produce an adapted error message.

You have an example of this in the archive given to you in the code factorization part of this activity. In the Traversal.py file, in the find_route method, you can see the following code:

# Debug
assert(self.source is not None) # Should not be called before traversal

This test will raise an AssertionError exception when the user tries to call find_route before the traversal method was used to set the routing_table attribute. It is then possible to test it in the associated unit test file with:

# Check that an exception is raised if find_route is called before traversal
with self.assertRaises(AssertionError):
    traversal = BFSTraversal()
    traversal.find_route(5)

In the same vein as what we just presented you, you can list the possible errors a user could make when using methods traversal and find_route. Then, update your BFS.py and DFS.py files (or the files you wrote in the factorization section if you completed it) to raise exceptions when these errors occur. Finally, update your unit tests to verify that exceptions are indeed raised when they should.

8 — The IDDFS algorithm

Another direction you can explore is to program an algorithm called IDDFS. This algorithm combines aspects of the BFS and DFS algorithms, but requires less memory than the two.

• If you want, you can try to implement that algorithm (or maybe find a library that does it?).

9 — Seidel’s algorithm

While the BFS gives you the shortest path from a vertex to all others, Seidel’s algorithm gives you the shortest paths from all vertices to all others in an unweighted graph.

• If you want, you can try to implement that algorithm (or maybe find a library that does it?).