Skip to main content

Lesson 6-5 · Three Planners, One Harness

Module 6 · Dijkstra's Algorithm (Optional)

Lesson 6-5 · Three Planners, One Harness

45 minOptional extensionClasses track onlySlides (PowerPoint)
👩‍🏫

Teacher mode is on. Toggle it off (bottom-right) to preview the student view.

This lesson is for students who built the Manhattan and BFS classes in Lessons 4-3 and 5-5. It adds the third one, Dijkstra, and runs all three as objects through the Module 5 class harness. The harness never finds out which one it is holding. That property has a name — polymorphism — and this is the cleanest place in the course to see it. If you did Lesson 6-3 as a function, this lesson replaces that function with the class; if you skipped ahead from 6-3, this is where you write it.

Learning Objectives

By the end of this lesson you will be able to:

  • Write the Dijkstra class by copying BFS and making the same two changes as Lesson 6-3
  • Give it add_slow_edge(), clear_slow_edges() and weight() as methods, with the slow list inside the object
  • Run Manhattan(), BFS() and Dijkstra() through one harness and read the results
  • Explain why the harness can treat three different classes the same way

This lesson's skeleton​

This is the class-track skeleton for the DIJKSTRA PLANNER section. Paste it in place of the section's banner and compute_dijkstra_path() — closest() sits under the new banner, and dijkstra_distances(), compare(), the Lesson 6-4 part and your tests stay where they are — and move your Lesson 6-3 body into compute_path(). The WEIGHTED GRAPH section stays as it is too: from today it is the harness's record of the slow edges, the way HARNESS_BLOCKED is its record of the blocks.

# ===== DIJKSTRA PLANNER (class version) =====
# One Dijkstra object holds the grid size, ITS OWN blocked
# list and ITS OWN slow list, and plans by cost around both:
# the BFS class with the slow-list methods added and the two
# Lesson 6-3 changes inside compute_path(). Same names as the
# function version, with planner. in front; the 5-6 class
# harness tests all three planners without naming one.
class Dijkstra:
def __init__(self, rows=4, cols=4):
self.rows = rows
self.cols = cols
self.blocked = []
self.slow_edges = [] # NEW: lives inside the planner

def add_blocked(self, intersection):
# as in BFS
pass

def clear_blocked(self):
pass

def add_slow_edge(self, a, b, cost):
# your function, with self.slow_edges for SLOW_EDGES
pass

def clear_slow_edges(self):
pass

def weight(self, a, b):
# your function, reading self.slow_edges
pass

def compute_path(self, start, destination):
# your compute_dijkstra_path(), with
# build_graph(self.rows, self.cols, self.blocked)
# and self.weight(); closest() stays a function
pass

planner = Dijkstra()

The third class​

BFS from Lesson 5-5 holds its blocked list in self.blocked and exposes add_blocked(), clear_blocked() and compute_path(start, destination). Dijkstra is a copy of it with one more list and the two changes. Same shape as the other two: compute_path(start, destination), told the start every call, returning a path that excludes the start. The slow list is the planner's own data, as the blocked list already was, so nothing outside the object reaches in to change it.

The name under the class is the Lesson 5-5 rule again: one object called planner, and it is your newest planner. Delete planner = BFS(), and everything in Module 5 that said planner. now plans by cost — on a grid with no slow edges, it gives the same answers as before, which you can prove by running any Module 5 test.

Knowledge Check

Where does the slow-edge list live in the class version, and why?

One harness, three objects​

The Lesson 5-6 class harness is handed an object and calls its methods:

run_all_tests("Manhattan", Manhattan())
run_all_tests("BFS", BFS())
run_all_tests("Dijkstra", Dijkstra())

Inside, every line is planner.compute_path(start, destination), block(planner, ...) or clear(planner). Nothing in the harness names a class. The seventh case needs one more helper of the block() kind — slow(planner, a, b, cost) tells the planner about a slow edge and records it in SLOW_EDGES, so that path_cost() adds up the true weights whichever planner is being tested — and clear() has to forget the slow edges as well as the blocks, on both sides. Paste these under clear() in the 5-6 part of the file, and make the three edits:

def slow(planner, a, b, cost):
"""Tell planner about the slow edge AND note it in
SLOW_EDGES, so path_cost() can see it."""
pass
  1. clear(planner) also calls planner.clear_slow_edges() and clear_slow_edges().
  2. In run_all_tests(), the seventh case: slow(planner, (0, 1), (0, 2), 5) where it said add_slow_edge(...), planner.compute_path(...) for the plan, and clear(planner) for both clears.
  3. compare() makes a fresh BFS() and a fresh Dijkstra(), and a fresh object knows nothing — so before it plans, each one is told every entry in SLOW_EDGES with p.add_slow_edge(a, b, cost). Two lines, and BFS ignores them.

That slow() call, and clear()'s, mean Manhattan and BFS need an add_slow_edge() and a clear_slow_edges() too, even though they ignore them, exactly as Manhattan.add_blocked() did nothing in Module 5:

class BFS:
# ...
def add_slow_edge(self, a, b, cost):
pass # BFS does not plan by cost; it accepts the call and ignores it

def clear_slow_edges(self):
pass
Functions (6-3)
run_all_tests("Dijkstra", compute_dijkstra_path)

path = planner(position, destination)
add_slow_edge((0, 1), (0, 2), 5)
Objects (6-5)
run_all_tests("Dijkstra", Dijkstra())

path = planner.compute_path(start, destination)
slow(planner, (0, 1), (0, 2), 5)

Three classes, one set of method names, one harness that works on any of them. That is polymorphism: code written against a shape — the names a planner answers to — rather than against one particular class. You have been using it since Lesson 5-6, where the harness was handed a function. Objects make the shape explicit: it is the list of methods.

The harness at the top calls planner.compute_path and never names a class. Manhattan, BFS and Dijkstra objects each have the same five methods; the ones a planner cannot use are pass. Results: 4, 6 and 7 of 7.
One shape, three classes. The methods a planner cannot use are still there, doing nothing, so the harness can call them on any of the three.
Knowledge Check

Why must BFS have an add_slow_edge() method that does nothing?

Activity · Build it, test it, read the results​

  1. Fill in the Dijkstra methods: the two blocked methods as in BFS, the three slow ones from your WEIGHTED GRAPH functions with self.slow_edges in place of SLOW_EDGES, and compute_path() from your Lesson 6-3 body with the two self. changes in its comment. Delete planner = BFS().
  2. Give Manhattan and BFS the two methods that do nothing.
  3. Write slow() and make the three harness edits. Then the tests, the usual way: test_three_planners() hands in Manhattan(), BFS() and Dijkstra(); test_cost_grid() says slow(planner, ...) and draws planner.blocked; dijkstra_distances() reads planner.blocked and planner.weight(). Set the run line to test_three_planners().

Expected, on the slow grid:

=== Manhattan === blocked cases FAIL, cost FAIL 4 of 7
=== BFS === blocked cases PASS, cost FAIL 6 of 7
=== Dijkstra === everything PASS 7 of 7

Each planner fails exactly the tests that describe what it cannot do, and the harness that showed you that is the one you wrote in Lesson 5-6, with one case added.

  1. Last, the swap on the floor. In test_drive_slow_grid(), PLANNER_NAME now chooses an object — planner = Dijkstra() or planner = BFS() — which is told the slow segment with slow(planner, ...) and asked for the path with planner.compute_path(). With the Navigator class, the drive is navigator.drive_path(path). Run both planners as in Lesson 6-4: same test program, and the only line that changes is the class name.

Wrap-up​

  • What does Dijkstra add to BFS? (A slow list with three methods, and the two changes.)
  • Why can one harness test three classes? (They answer to the same method names.)
  • What is that called? (Polymorphism.)

Resources​