This question tests the following learning outcomes:

Apply general-purpose data structures and algorithmic techniques to efficiently solve computational problems.
Explain in a clear and succinct way how an algorithm or data structure works, and its assumptions, in order to communicate with peers.
Analyse the complexity of algorithms to support design choices.
Write readable, tested and documented Python functions and classes to implement algorithms and abstract data types.
The files m269_digraph.py, m269_ungraph.py and Q4_warehouse.py should be in the folder with this TMA notebook.

A warehouse, similar to Ocado's algorithm-controlled warehouse that you met in The Secret Rules of Modern Living: Algorithms Part 3, has a despatch area and a vast storage area divided into zones. Requested items are brought to despatch from the storage area by an automatic picking system. An automated crate travels along tracks from despatch to the appropriate storage area zones, and back to despatch. Tracks are in pairs that allow the crate to travel in either direction.

The crate may need to pass through other zones to get to and from the zones where the requested items are.

The warehouse can be represented by a weighted digraph. Nodes represent the despatch and storage zones. Weighted edges represent tracks between the despatch and storage zones, and between zones. A weight represents the time (in seconds) that it takes to travel between the two zones joined by the edge.

 

Run the code below to draw an instance of a weighted digraph that represents an example warehouse.

 

OUTPUT:

 

 

 

m269_digrap.py

 

import networkx
from typing import Hashable
class DiGraph:
   """A directed graph with hashable node objects.
   Edges are between different nodes.
   There's at most one edge from one node to another.
   """
   def __init__(self):
       self.out = dict()   # a map of nodes to their out-neighbours
   def has_node(self, node: Hashable) -> bool:
       """Return True if and only if the graph has the node."""
       return node in self.out
   def has_edge(self, start: Hashable, end: Hashable) -> bool:
       """Return True if and only if edge start -> end exists.
       Preconditions: self.has_node(start) and self.has_node(end)
       """
       return end in self.out[start]
   def add_node(self, node: Hashable) -> None:
       """Add the node to the graph.
       Preconditions: not self.has_node(node)
       """
       self.out[node] = set()
   def add_edge(self, start: Hashable, end: Hashable) -> None:
       """Add edge start -> end to the graph.
       If the edge already exists, do nothing.
       Preconditions:
       self.has_node(start) and self.has_node(end) and start != end
       """
       self.out[start].add(end)
   def remove_node(self, node: Hashable) -> None:
       """Remove the node and all its attached edges.
       Preconditions: self.has_node(node)
       """
       self.out.pop(node)
       for start in self.out:
           self.remove_edge(start, node)
   def remove_edge(self, start: Hashable, end: Hashable) -> None:
       """Remove edge start -> end from the graph.
       If the edge doesn't exist, do nothing.
       Preconditions: self.has_node(start) and self.has_node(end)
       """
       self.out[start].discard(end)
   def nodes(self) -> set:
       """Return the graph's nodes."""
       all_nodes = set()
       for node in self.out:
           all_nodes.add(node)
       return all_nodes
   def edges(self) -> set:
       """Return the graph's edges as a set of pairs (start, end)."""
       all_edges = set()
       for start in self.out:
           for end in self.out[start]:
               all_edges.add( (start, end) )
       return all_edges
   def out_neighbours(self, node: Hashable) -> set:
       """Return the out-neighbours of the node.
       Preconditions: self.has_node(node)
       """
       return set(self.out[node])  # return a copy
   def out_degree(self, node: Hashable) -> int:
       """Return the number of out-neighbours of the node.
       Preconditions: self.has_node(node)
       """
       return len(self.out[node])
   def in_neighbours(self, node: Hashable) -> set:
       """Return the in-neighbours of the node.
       Preconditions: self.has_node(node)
       """
       start_nodes = set()
       for start in self.out:
           if self.has_edge(start, node):
               start_nodes.add(start)
       return start_nodes
   def in_degree(self, node: Hashable) -> int:
       """Return the number of in-neighbours of the node.
       Preconditions: self.has_node(node)
       """
       return len(self.in_neighbours(node))
   def neighbours(self, node: Hashable) -> set:
       """Return the in- and out-neighbours of the node.
       Preconditions: self.has_node(node)
       """
       return self.out_neighbours(node).union(self.in_neighbours(node))
   def degree(self, node: Hashable) -> int:
       """Return the number of in- and out-going edges of the node.
       Preconditions: self.has_node(node)
       """
       return self.in_degree(node) + self.out_degree(node)
   def draw(self) -> None:
       """Draw the graph."""
       if type(self) == DiGraph:
           graph = networkx.DiGraph()
       else:
           graph = networkx.Graph()
       graph.add_nodes_from(self.nodes())
       graph.add_edges_from(self.edges())
       networkx.draw(graph, with_labels=True,
           node_size=1000, node_color='lightblue',
           font_size=12, font_weight='bold')
from collections import deque
def bfs(graph: DiGraph, start: Hashable) -> DiGraph:
   """Return the subgraph traversed by a breadth-first search.
   Preconditions: graph.has_node(start)
   """
   # changes from traversed function noted in comments
   visited = DiGraph()
   visited.add_node(start)
   unprocessed = deque()                           # set -> deque
   for neighbour in graph.out_neighbours(start):
       unprocessed.append( (start, neighbour) )    # add -> append
   while len(unprocessed) > 0:
       edge = unprocessed.popleft()                # pop -> popleft
       previous = edge[0]
       current = edge[1]
       if not visited.has_node(current):
           visited.add_node(current)
           visited.add_edge(previous, current)
           for neighbour in graph.out_neighbours(current):
               unprocessed.append( (current, neighbour) )  # add -> append
   return visited
def dfs(graph: DiGraph, start: Hashable) -> DiGraph:
   """Return the subgraph traversed by a depth-first search.
   Preconditions: graph.has_node(start)
   """
   visited = DiGraph()
   visited.add_node(start)
   unprocessed = []                            # deque -> list
   for neighbour in graph.out_neighbours(start):
       unprocessed.append( (start, neighbour) )
   while len(unprocessed) > 0:
       edge = unprocessed.pop()                # popleft -> pop
       previous = edge[0]
       current = edge[1]
       if not visited.has_node(current):
           visited.add_node(current)
           visited.add_edge(previous, current)
           for neighbour in graph.out_neighbours(current):
               unprocessed.append( (current, neighbour) )
   return visited
import math
class WeightedDiGraph(DiGraph):
   """A weighted directed graph with hashable node objects.
   Edges are between different nodes.
   There's at most one edge from one node to another.
   Edges have weights, which can be floats or integers.
   """
   def add_node(self, node: Hashable) -> None:
       """Add the node to the graph.
       Preconditions: not self.has_node(node)
       """
       self.out[node] = dict() # a map of out-neighbours to weights
   def add_edge(self, start: Hashable, end: Hashable, weight: float) -> None:
       """Add edge start -> end, with the given weight, to the graph.
       If the edge already exists, set its weight.
       Preconditions:
       self.has_node(start) and self.has_node(end) and start != end
       """
       self.out[start][end] = weight
   def weight(self, start: Hashable, end: Hashable) -> float:
       """Return the weight of edge start -> end or infinity if it doesn't exist.
       Preconditions: self.has_node(start) and self.has_node(end)
       """
       if self.has_edge(start, end):
           return self.out[start][end]
       else:
           return math.inf
   def remove_edge(self, start: Hashable, end: Hashable) -> None:
       """Remove edge start -> end from the graph.
       If the edge doesn't exist, do nothing.
       Preconditions: self.has_node(start) and self.has_node(end)
       """
       if self.has_edge(start, end):
           self.out[start].pop(end)
   def edges(self) -> set:
       """Return the graph's edges as a set of triples (start, end, weight)."""
       all_edges = set()
       for start in self.out:
           for (end, weight) in self.out[start].items():
               all_edges.add( (start, end, weight) )
       return all_edges
   def out_neighbours(self, node: Hashable) -> set:
       """Return the out-neighbours of the node.
       Preconditions: self.has_node(node)
       """
       return set(self.out[node].keys())
   def draw(self) -> None:
       """Draw the graph."""
       if type(self) == WeightedDiGraph:
           graph = networkx.DiGraph()
       else:
           graph = networkx.Graph()
       graph.add_nodes_from(self.nodes())
       for (node1, node2, weight) in self.edges():
           graph.add_edge(node1, node2, w=weight)
       pos = networkx.spring_layout(graph)
       networkx.draw(graph, pos, with_labels=True,
           node_size=1000, node_color='lightblue',
           font_size=12, font_weight='bold')
       networkx.draw_networkx_edge_labels(graph, pos,
           edge_labels=networkx.get_edge_attributes(graph, 'w'))
from heapq import heappush, heappop
def dijkstra(graph: WeightedDiGraph, start: Hashable) -> WeightedDiGraph:
   """Return a shortest path from start to each reachable node.
   Preconditions:
   - graph.has_node(start)
   - node objects are comparable
   - no weight is negative
   """
   visited = WeightedDiGraph()
   visited.add_node(start)
   # create min-priority queue of tuples (cost, (A, B, weight))
   # cost is total weight from start to B via shortest path to A
   unprocessed = []    # min-priority queue
   for neighbour in graph.out_neighbours(start):
       weight = graph.weight(start, neighbour)
       heappush(unprocessed, (weight, (start, neighbour, weight)) )
   while len(unprocessed) > 0:
       info = heappop(unprocessed)
       cost = info[0]
       edge = info[1]
       previous = edge[0]
       current = edge[1]
       weight = edge[2]
       if not visited.has_node(current):
           visited.add_node(current)
           visited.add_edge(previous, current, weight)
           for neighbour in graph.out_neighbours(current):
               weight = graph.weight(current, neighbour)
               edge = (current, neighbour, weight)
               heappush(unprocessed, (cost + weight, edge) )
   return visited

m269_ungraph.py

 

from typing import Hashable
class UndirectedGraph(DiGraph):
   """An undirected graph with hashable node objects.
   There's at most one edge between two different nodes.
   There are no edges between a node and itself.
   """
   def add_edge(self, node1: Hashable, node2: Hashable) -> None:
       """Add an undirected edge node1-node2 to the graph.
       If the edge already exists, do nothing.
       Preconditions: self.has_node(node1) and self.has_node(node2)
       """
       super().add_edge(node1, node2)
       super().add_edge(node2, node1)
   def remove_edge(self, node1: Hashable, node2: Hashable) -> None:
       """Remove edge node1-node2 from the graph.
       If the edge doesn't exist, do nothing.
       Preconditions: self.has_node(node1) and self.has_node(node2)
       """
       super().remove_edge(node1, node2)
       super().remove_edge(node2, node1)
   def edges(self) -> set:
       """Return the graph's edges as a set of pairs.
       Postconditions: for every edge A-B,
       the output has either (A, B) or (B, A) but not both
       """
       all_edges = set()
       for node1 in self.out:
           for node2 in self.out[node1]:
               if (node2, node1) not in all_edges:
                   all_edges.add( (node1, node2) )
       return all_edges
   def in_neighbours(self, node: Hashable) -> set:
       """Return all nodes that are adjacent to the node.
       Preconditions: self.has_node(node)
       """
       return self.out_neighbours(node)
   def neighbours(self, node: Hashable) -> set:
       """Return all nodes that are adjacent to the node.
       Preconditions: self.has_node(node)
       """
       return self.out_neighbours(node)
   def in_degree(self, node: Hashable) -> int:
       """Return the number of edges attached to the node.
       Preconditions: self.has_node(node)
       """
       return self.out_degree(node)
   def degree(self, node: Hashable) -> int:
       """Return the number of edges attached to the node.
       Preconditions: self.has_node(node)
       """
       return self.out_degree(node)
class WeightedUndirectedGraph(WeightedDiGraph):
   """A weighted undirected graph with hashable node objects.
   There's at most one edge between two different nodes.
   There are no edges between a node and itself.
   Edges have weights, which may be integers or floats.
   """
   def add_edge(self, node1: Hashable, node2: Hashable, weight: float) -> None:
       """Add an edge node1-node2 with the given weight to the graph.
       If the edge already exists, do nothing.
       Preconditions: self.has_node(node1) and self.has_node(node2)
       """
       super().add_edge(node1, node2, weight)
       super().add_edge(node2, node1, weight)
   def remove_edge(self, node1: Hashable, node2: Hashable) -> None:
       """Remove edge node1-node2 from the graph.
       If the edge doesn't exist, do nothing.
       Preconditions: self.has_node(node1) and self.has_node(node2)
       """
       super().remove_edge(node1, node2)
       super().remove_edge(node2, node1)
   def edges(self) -> set:
       """Return the graph's edges as a set of triples (node1, node2, weight).
       Postconditions: for every edge A-B,
       the output has either (A, B, w) or (B, A, w) but not both
       """
       all_edges = set()
       for start in self.out:
           for (end, weight) in self.out[start].items():
               if (end, start, weight) not in all_edges:
                   all_edges.add( (start, end, weight) )
       return all_edges
   def in_neighbours(self, node: Hashable) -> set:
       """Return all nodes that are adjacent to the node.
       Preconditions: self.has_node(node)
       """
       return self.out_neighbours(node)
   def neighbours(self, node: Hashable) -> set:
       """Return all nodes that are adjacent to the node.
       Preconditions: self.has_node(node)
       """
       return self.out_neighbours(node)
   def in_degree(self, node: Hashable) -> int:
       """Return the number of edges attached to the node.
       Preconditions: self.has_node(node)
       """
       return self.out_degree(node)
   def degree(self, node: Hashable) -> int:
       """Return the number of edges attached to the node.
       Preconditions: self.has_node(node)
       """
       return self.out_degree(node)
from heapq import heappush, heappop
def prim(graph: WeightedUndirectedGraph, start: Hashable) -> WeightedUndirectedGraph:
   """Return a minimum spanning tree of graph, beginning at start.
   Preconditions:
   - graph.has_node(start)
   - graph is connected
   - node objects are comparable
   """
   visited = WeightedUndirectedGraph()
   visited.add_node(start)
   unprocessed = []
   for neighbour in graph.neighbours(start):
       weight = graph.weight(start, neighbour)
       heappush(unprocessed, (weight, start, neighbour) )
   while len(unprocessed) > 0:
       edge = heappop(unprocessed)
       weight = edge[0]
       previous = edge[1]
       current = edge[2]
       if not visited.has_node(current):
           visited.add_node(current)
           visited.add_edge(previous, current, weight)
           for neighbour in graph.neighbours(current):
               weight = graph.weight(current, neighbour)
               heappush(unprocessed, (weight, current, neighbour) )
   return visited
 

Q4_warehouse.py

 

warehouse = WeightedDiGraph()
warehouse.add_node('despatch')
warehouse.add_node('A')
warehouse.add_node('D')
warehouse.add_node('P')
warehouse.add_node('S')
warehouse.add_node('U')
warehouse.add_node('Y')
warehouse.add_node('Z')
warehouse.add_edge('despatch','U',30)
warehouse.add_edge('U','despatch',30)
warehouse.add_edge('despatch','A',10)
warehouse.add_edge('A','despatch',10)
warehouse.add_edge('despatch','D',5)
warehouse.add_edge('D','despatch',5)
warehouse.add_edge('despatch','Z',16)
warehouse.add_edge('Z','despatch',16)
warehouse.add_edge('A','U',15)
warehouse.add_edge('U','A',15)
warehouse.add_edge('A','P',10)
warehouse.add_edge('P','A',10)
warehouse.add_edge('P','S',12)
warehouse.add_edge('S','P',12)
warehouse.add_edge('D','Z',8)
warehouse.add_edge('Z','D',8)
warehouse.add_edge('P','D',15)
warehouse.add_edge('D','P',15)
warehouse.add_edge('P','Y',8)
warehouse.add_edge('Y','P',8)
warehouse.add_edge('Y','S',12)
warehouse.add_edge('S','Y',12)
warehouse.add_edge('Y','Z',15)
warehouse.add_edge('Z','Y',15)
warehouse.draw()

 

Use Dijsktra's algorithm to compute a shortest path from despatch to each zone. Draw the resulting tree.

The contents of Q4_warehouse.py are reproduced below for your reference.

 

#Code Here

 

#Take note of the first image as the relevant .py have been called and matplotlib.pyplot