The incidence-list graph notebook contains an implementation of a graph data structure based on incidence lists as discussed in the lecture. There, the class for the graph itself is IncidenceListGraph, the class for nodes (vertices) in such a graph is IncidenceListGraphNode, and the class for edges in such a graph is IncidenceListGraphEdge.
In the notebook, an example graph is constructed from data for an instance of the cashier problem; note that this is just used here as an arbitrary example for data to be stored a graph. Make sure that you understand how the incidence-list data structure for graphs works, and how it is implemented and used here.
Use the incidence-list based graph data structure to store the graph with labelled nodes and edges given below:
In breadth-first search, nodes are visited in order of the number of edges that need to be followed in order to reach them, starting from the initial node. As discussed in the lecture, the BFS spanning tree (also breadth-first tree) consists of the edges through which nodes are reached during breadth-first search. The initial node of the search operation becomes the root node of the spanning tree, and the distance of a node in the graph from the initial node becomes its depth in the spanning tree:
The notebook contains the skeleton of a function bfs_depth(graph, initial_label, search_label, debug_output) that uses graph traversal by BFS to compute the distance between two nodes in an unweighted graph. These nodes are identified by their labels, initial_label and search_label. Complete the function implementation such that it returns the depth of the node labelled search_label in a BFS search tree that has a node labelled initial_label as its root. This is the same as the number of edges that need to be followed to get from initial_label to search_label.
If problem part a) is solved correctly, assuming that the graph is called graph_a, the function call bfs_depth(graph_a, 5, 1, False) should return 3, since the shortest path from the node labelled 5 to the node labelled 1 consists of three edges.
Submission deadline: 15th January 2022; discussion planned for 3rd February 2022. Group work by up to four people is welcome.