Course 3.1Lesson 5 of 5

Project: finding the way

In this project we build a route finder on a small map of towns. The roads are a dictionary of neighbours, and breadth-first search with a queue finds the shortest route as a list of towns, or None when there is no way. From it we get the number of stops, and a second search gives every town that can be reached. An unknown town is refused with a ValueError. We plan the expected routes by hand, build the functions, test the same town, a town that cannot be reached and an unknown town, and extend the finder with road lengths and a path that avoids a closed town.

about 25 min1 simulation2 practice questions

Lesson 5 of 5Show all lessons

Try the code and the simulations beside the lesson.

What you will be able to do

After this lesson you can

turn a map into a graph, and use a search to answer questions about it,
return a route, and handle the cases where there is none,
test a search on the edge cases, and
extend a graph program with new rules.

The goal

A traveller has a small map of towns in the west of India. The roads join some of the towns. The traveller wants to ask:

What is the shortest route (fewest towns on the way) from one town to another?
How many stops is that?
Which towns can be reached at all from a given town?

And the program must be safe: a town that is not on the map is refused, and a town that cannot be reached gives None, not a crash.

Step 1: the map and the expected answers

The roads (each road goes both ways):

Pune joins Mumbai, Nashik and Satara.
Mumbai joins Pune, Nashik and Thane.
Nashik joins Pune and Mumbai.
Satara joins Pune and Kolhapur.
Goa has no roads on this map.

Work out the answers by hand.

Question	Answer
route Thane to Kolhapur	Thane, Mumbai, Pune, Satara, Kolhapur: 4 stops
stops from Pune to Pune	0
stops from Pune to Goa	cannot be reached
towns reached from Nashik	Nashik, Pune, Mumbai, Satara, Thane, Kolhapur
route to a town not on the map	refused

Check the first. From Thane the only road is to Mumbai. From Mumbai to Pune. From Pune, Satara is the way to Kolhapur. That is 4 roads: Thane to Mumbai, Mumbai to Pune, Pune to Satara, Satara to Kolhapur.

Step 2: the program

Run it, and compare with your answers.

Look at the design.

- roads is the graph: a dictionary of neighbours. Goa is on the map with an empty list, so roads["Goa"] does not raise a KeyError.

- route is breadth-first search, as in the lesson. It first checks that both towns are on the map, and raises a ValueError if not: a map that does not have the town is a different problem from a town that cannot be reached. Then it searches. It returns the path as a list, or None.

- stops reuses route: the number of stops is the number of towns minus one. It gives None when there is no route. A small function built on a bigger one.

- reachable is a second search. It does not need the path, so it keeps only a set of the seen towns. It returns the set.

- The main program asks the questions, and catches the ValueError for the unknown town.

Step 3: test the edges

Test	Expected
start equals goal	the route is just the start, and 0 stops
a town with no roads (Goa)	`route` to it gives `None`
from the town with no roads	`reachable` gives only that town
an unknown town	`ValueError`
two routes of the same length	either is correct, but the answer must be one of them
a graph with a loop (Pune, Mumbai, Nashik)	the search must end

The third row is easy to miss: reachable(roads, "Goa") is {"Goa"}, the start itself. The last row tests the memory: Pune, Mumbai and Nashik are joined in a triangle, and a search that forgets where it has been would never end.

Goa is reached only through Satara and Kolhapur. Remove the road from Satara to Kolhapur, and shortest_path would give None.

Step 4: extend it

Pick one or two, and do them without looking at a solution. Write the expected answers first.

Closed towns. route(graph, start, goal, closed) avoids the towns in a set closed.
Road lengths. Store the length of each road, and give the length of the route. (The shortest route in stops is not always the shortest in kilometres.)
All the shortest routes. Give every route of the minimum length.
Distance from a start. A dictionary of every reachable town and its number of steps.
Is the map connected? Can you get from every town to every other?

Common mistakes

Forgetting to record the places seen and going round a loop for ever.
A town that is missing from the dictionary, giving a KeyError.
Returning the path backwards. Reverse it after walking back from the goal.
Mixing up "unknown town" and "cannot be reached". They are different answers.
Using DFS and expecting the shortest route.

Practice

Start with two quick questions. Each New numbers gives you a fresh one, so you can practise as long as you like.

Then the labs and the problems:

Warm-up. Open the lab Project: finding the way. The checker uses a map that is different from the lesson, with a loop and a town that cannot be reached.
Build. Do Step 4 for one extension.
Stretch. Open the lab Reachable places and compare its search with reachable here.

Remember these

A map is a graph: a dictionary of neighbours. Every town needs an entry.
BFS with a queue gives the route with the fewest stops. A dictionary of "came from" rebuilds it.
Distinguish a town that is not on the map (an error) from a town that cannot be reached (None).
Test the same town, the town with no roads, and a loop in the graph.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

Why does roads have an entry for Goa with an empty list?

How is the number of stops found from the route?

Why must the search record the towns that it has seen?

Enroll free in Data Structures

Every lesson is open to read. Enrolling also lets you:

Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.

No payment. You can leave at any time.

Python Labs (1)

Project: finding the wayPython Lab · by StemPy Lab

That was the last lessonBack to the course: take the test

← Data Structures

← Graphs: connections and searchingNext →

Discussion (0)

Loading…