Graphs: Maps, Routes and Networks

A graph is a set of things and the connections between them. Each thing is a node (also called a vertex), and each connection between two nodes is an edge. That is all a graph is: dots and lines.

The word “graph” here doesn’t mean a chart of numbers, like a bar graph. It is a second meaning of the same word, and in computing it almost always means dots and lines.

Two nodes joined by an edge are neighbors. In Figure 2.1, Bhaktapur’s neighbors are Thimi, Nagarkot and Banepa. The number of edges at a node is its degree: Bhaktapur’s degree is 3, Thimi’s is 1 (in this small graph).

One way or both ways

A road can be driven both ways, and if Asha is Bimal’s friend, Bimal is Asha’s. Edges like these go both ways, and the graph is undirected: its edges are drawn as plain lines.

Some connections go only one way. The school’s home page may link to the News page without News linking back. On a social media app, you can follow a famous cricketer without the cricketer following you. A one-way street in Thamel can be driven in only one direction. A graph whose edges go one way is directed, and its edges are drawn as arrows. If two pages link to each other, that is two edges, one each way (Home and News in Figure 2.1).

What a graph leaves out

Look at the towns in Figure 2.1 again. The graph doesn’t show how long each road is, whether it is paved, or how the hills lie. It shows only one thing: which towns are joined to which. Leaving out everything except what the problem needs is called abstraction, and a graph is one of the most useful abstractions in computing. Once a problem is a graph, it doesn’t matter whether the nodes were towns or people: the same program works on both.

Where a node is drawn doesn’t matter either. You could move Nagarkot to the bottom of the page and it would be the same graph, as long as the same nodes are joined. A map of bus routes is often drawn like this, as straight lines between stops, because a passenger needs to know the order of the stops and where to change buses, not the exact shape of each road.

A drawing is good for people. A program needs the graph as data. The question to ask, as in Grade 9’s Unit 3, is: what will the program do with the data most often? For a graph, the answer is almost always: “given a node, find its neighbors.” A search stands at a town and asks which towns it can reach next, again and again.

A dictionary of neighbors

So the best structure is a dictionary of neighbors: each node is a key, and its value is the list of its neighbors. Finding a town’s neighbors is then a single lookup, which a dictionary does at once, however big it is (Grade 9). This way of storing a graph is called an adjacency list (“adjacent” means next to).

Here are some of the main roads in and around the Kathmandu Valley, simplified, as a dictionary. Every road appears twice, once in each town’s list, because a road goes both ways.

roads = {    "Kathmandu": ["Lalitpur", "Kirtipur", "Budhanilkantha", "Thimi", "Sankhu"],    "Lalitpur": ["Kathmandu", "Kirtipur", "Godawari", "Thimi"],    "Kirtipur": ["Kathmandu", "Lalitpur", "Pharping"],    "Budhanilkantha": ["Kathmandu"],    "Thimi": ["Kathmandu", "Lalitpur", "Bhaktapur"],    "Sankhu": ["Kathmandu"],    "Godawari": ["Lalitpur"],    "Pharping": ["Kirtipur"],    "Bhaktapur": ["Thimi", "Nagarkot", "Banepa"],    "Nagarkot": ["Bhaktapur", "Dhulikhel"],    "Banepa": ["Bhaktapur", "Dhulikhel"],    "Dhulikhel": ["Nagarkot", "Banepa"],} print(roads["Bhaktapur"])print(len(roads["Kathmandu"]), "roads meet at Kathmandu")print("Banepa" in roads["Thimi"]) ends = 0for town in roads:    ends = ends + len(roads[town])print(ends // 2, "roads in all")

['Thimi', 'Nagarkot', 'Banepa']5 roads meet at KathmanduFalse14 roads in all

Line 16 finds Bhaktapur’s neighbors in one lookup. Line 17 gives Kathmandu’s degree: the length of its list. Line 18 asks whether two towns are joined by a road: is Banepa in Thimi’s list? Lines 20–23 add up all the lists. Each road is counted twice, once from each end, so the number of roads is half the total. (This is true of every undirected graph: the degrees add up to twice the number of edges.)

Building the graph from data

Writing a big dictionary by hand is slow, and it is easy to forget one end of a road. It is safer to keep the data as a plain list of roads, one road per line, and let a program build the dictionary. A function that adds one road at both ends can never forget one.

Kathmandu,LalitpurKathmandu,KirtipurKathmandu,BudhanilkanthaKathmandu,ThimiKathmandu,SankhuLalitpur,KirtipurLalitpur,GodawariLalitpur,ThimiKirtipur,PharpingThimi,BhaktapurBhaktapur,NagarkotBhaktapur,BanepaNagarkot,DhulikhelBanepa,Dhulikhel

def add_road(graph, a, b):    if a not in graph:        graph[a] = []    if b not in graph:        graph[b] = []    graph[a].append(b)    graph[b].append(a) roads = {}with open("roads.txt", encoding="utf-8") as f:    for line in f:        a, b = line.strip().split(",")        add_road(roads, a, b) for town in roads:    print(town, "->", ", ".join(roads[town]))

Kathmandu -> Lalitpur, Kirtipur, Budhanilkantha, Thimi, SankhuLalitpur -> Kathmandu, Kirtipur, Godawari, ThimiKirtipur -> Kathmandu, Lalitpur, PharpingBudhanilkantha -> KathmanduThimi -> Kathmandu, Lalitpur, BhaktapurSankhu -> KathmanduGodawari -> LalitpurPharping -> KirtipurBhaktapur -> Thimi, Nagarkot, BanepaNagarkot -> Bhaktapur, DhulikhelBanepa -> Bhaktapur, DhulikhelDhulikhel -> Nagarkot, Banepa

add_road first makes sure both towns are keys (a town seen for the first time gets an empty list), then puts each town in the other’s list. The dictionary it builds is exactly the one written by hand above, in the same order, because the lines of the file are in that order.

Other ways to store a graph

The dictionary of neighbors is not the only way. Two others are common:

• A list of edges, like roads.txt: [("Kathmandu", "Lalitpur"), ("Kathmandu", "Kirtipur"), …]. It is simple to write and to save, but to find Bhaktapur’s neighbors you must look through every edge.
• A table (an adjacency matrix): a row and a column for every node, with a 1 where two nodes are joined and 0 where they aren’t. Checking whether two particular nodes are joined is one look. But a graph of 10,000 towns needs a table of 10,000 × 10,000 = 100 million cells, almost all of them 0, since each town has only a few roads.

Road maps, friendships and the web all have many nodes but only a few edges at each. For them, and for the searches in this unit, the dictionary of neighbors wins. Choosing a data structure by the operations a program needs is exactly what Grade 9 taught; graphs are one more place to do it.

Now the graph is in Python. Here is the first question to ask of it: starting from Kathmandu, which towns can you reach, and how many roads away is each?

Think of news spreading in a village. One person hears it first. By the next morning, everyone they talk to knows it. By the morning after, everyone those people talked to knows it. The news spreads out in rings: first the people one step away, then two steps, then three. A search that spreads the same way is called breadth-first search (BFS): it explores the whole breadth of one ring before going deeper.

By hand: a list of places still to visit

To search by hand, keep two things on paper:

• the list of places still to visit, in order. New places go on the back of the list, and the next place to visit is always taken from the front. A list used like this is a queue: first in, first out, like the queue at a bank counter or for tickets at a cinema.
• for each place you have seen, its number of steps from the start. Seen means it has been put on the list at some time, so it is never put on again.

The algorithm:

1. Write the start with 0 steps, and put it on the list.
2. While the list is not empty:
   1. Take the place at the front of the list. This is the place you visit.
   2. For each of its neighbors that you have not seen yet: write its steps (the visited place’s steps + 1) and put it on the back of the list.
3. When the list is empty, every place you can reach has been visited, and each has its number of steps.

Breadth-first search in Python

Each part of the hand method becomes a data structure:

• the list still to visit is a Python list, to_visit: append() puts a place on the back and pop(0) takes the one at the front (Grade 9’s queue);
• the places seen and their steps are a dictionary, steps. A place is seen if it is a key: nxt not in steps checks that in one lookup.

roads = {    "Kathmandu": ["Lalitpur", "Kirtipur", "Budhanilkantha", "Thimi", "Sankhu"],    "Lalitpur": ["Kathmandu", "Kirtipur", "Godawari", "Thimi"],    "Kirtipur": ["Kathmandu", "Lalitpur", "Pharping"],    "Budhanilkantha": ["Kathmandu"],    "Thimi": ["Kathmandu", "Lalitpur", "Bhaktapur"],    "Sankhu": ["Kathmandu"],    "Godawari": ["Lalitpur"],    "Pharping": ["Kirtipur"],    "Bhaktapur": ["Thimi", "Nagarkot", "Banepa"],    "Nagarkot": ["Bhaktapur", "Dhulikhel"],    "Banepa": ["Bhaktapur", "Dhulikhel"],    "Dhulikhel": ["Nagarkot", "Banepa"],} def breadth_first(graph, start):    steps = {start: 0}    to_visit = [start]    while len(to_visit) > 0:        place = to_visit.pop(0)        print(steps[place], place)        for nxt in graph[place]:            if nxt not in steps:                steps[nxt] = steps[place] + 1                to_visit.append(nxt)    return steps steps = breadth_first(roads, "Kathmandu")print("Steps to Dhulikhel:", steps["Dhulikhel"])

0 Kathmandu1 Lalitpur1 Kirtipur1 Budhanilkantha1 Thimi1 Sankhu2 Godawari2 Pharping2 Bhaktapur3 Nagarkot3 Banepa4 DhulikhelSteps to Dhulikhel: 4

Compare the printed order with the hand search: it is the same, because the program does exactly what you did. Lines 17–18 set up the start; line 20 takes the front of the queue; lines 22–25 look at each neighbor and add the new ones. The function returns the steps dictionary, so the rest of the program can use it (line 29).

Painting a picture, ring by ring

A drawing app’s paint bucket uses the same search. Tap a square, and every square of its color that can be reached from it, up to the outlines, is painted: flood fill. Each square is a node, and an edge joins it to each neighbor above, below, left and right of the same color. Breadth-first search from the tapped square paints the area outward in rings.

In Python, on the same picture, # for the outlines and . for empty:

from pixels import show_frames picture = [    "....................",    ".........##.........",    "........####........",    "......########......",    ".......#....#.......",    "......########......",    "....############....",    "......#......#......",    "......#......#......",    "....############....",    "..################..",    "....#..........#....",    "....#..........#....",    "..################..",    "..#..............#..",    "####################",] def flood_fill(picture, start):    old = picture[start[0]][start[1]]    steps = {start: 0}    to_visit = [start]    while len(to_visit) > 0:        r, c = to_visit.pop(0)        for nr, nc in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:            if 0 <= nr < len(picture) and 0 <= nc < len(picture[0]):                if picture[nr][nc] == old and (nr, nc) not in steps:                    steps[(nr, nc)] = steps[(r, c)] + 1                    to_visit.append((nr, nc))    return steps steps = flood_fill(picture, (1, 1))print(len(steps), "squares; the farthest is", max(steps.values()), "steps away")frames = []for ring in range(max(steps.values()) + 1):    frame = []    for r in range(len(picture)):        row = ""        for c in range(len(picture[0])):            if (r, c) in steps and steps[(r, c)] <= ring:                row = row + "o"            else:                row = row + picture[r][c]        frame.append(row)    frames.append(frame)show_frames(frames, {"#": "black", ".": "white", "o": "steelblue"})

160 squares; the farthest is 33 steps away

Picture

flood_fill() is breadth_first() with one change: a square’s neighbors are worked out (line 28), not looked up, so the graph is never written down. A square is a tuple (r, c). The last loops draw a picture per ring, painted squares as "o".

How much work is a search?

Count the work as Grade 9 did. Each reachable town is visited once, since it is added to the list only once. At each visit, the search reads that town’s list of neighbors once. So the work grows with the number of towns plus the number of roads: double the map, and the search does about twice the work. That is why a computer can search a graph of millions of nodes in a moment.

(There is one catch in our Python: pop(0) moves every other item in the list one place forward, which gets slow for a list of a million. Python has a structure made for queues, deque from the collections library, whose popleft() takes the front at once. Grade 11 explains why.)

Breadth-first search reaches the towns in rings: all those 1 road away, then all those 2 roads away, and so on. So the first time it reaches a town is by the fewest possible roads. Could there be a shorter way that the search missed? No: a shorter way would have reached the town in an earlier ring, and the search finishes every earlier ring before it starts the next.

That is why the steps it writes beside each town are the fewest steps from the start. Map apps, games and networks all use this.

Remembering the way

Knowing that Dhulikhel is 4 roads away is useful, but a traveler needs the route: which towns to pass through. One more dictionary does it. Each time the search reaches a new town, it writes down which town it came from. Following these notes backwards, from the goal to the town it came from, then to the town that came from, leads back to the start: the route, in reverse. Turn it round, and you have it. (These notes are the blue arrows in the widget above.)

The search can also stop as soon as it visits the goal: by then, the route to it is known.

roads = {    "Kathmandu": ["Lalitpur", "Kirtipur", "Budhanilkantha", "Thimi", "Sankhu"],    "Lalitpur": ["Kathmandu", "Kirtipur", "Godawari", "Thimi"],    "Kirtipur": ["Kathmandu", "Lalitpur", "Pharping"],    "Budhanilkantha": ["Kathmandu"],    "Thimi": ["Kathmandu", "Lalitpur", "Bhaktapur"],    "Sankhu": ["Kathmandu"],    "Godawari": ["Lalitpur"],    "Pharping": ["Kirtipur"],    "Bhaktapur": ["Thimi", "Nagarkot", "Banepa"],    "Nagarkot": ["Bhaktapur", "Dhulikhel"],    "Banepa": ["Bhaktapur", "Dhulikhel"],    "Dhulikhel": ["Nagarkot", "Banepa"],} def fewest_steps(graph, start, goal):    came_from = {start: None}    to_visit = [start]    while len(to_visit) > 0:        place = to_visit.pop(0)        if place == goal:            route = []            while place is not None:                route.append(place)                place = came_from[place]            route.reverse()            return route        for nxt in graph[place]:            if nxt not in came_from:                came_from[nxt] = place                to_visit.append(nxt)    return None print(fewest_steps(roads, "Kathmandu", "Dhulikhel"))print(fewest_steps(roads, "Pharping", "Nagarkot"))print(fewest_steps(roads, "Sankhu", "Sankhu"))

['Kathmandu', 'Thimi', 'Bhaktapur', 'Nagarkot', 'Dhulikhel']['Pharping', 'Kirtipur', 'Kathmandu', 'Thimi', 'Bhaktapur', 'Nagarkot']['Sankhu']

came_from does two jobs at once. Its keys are the places seen (the start is seen, and came from nowhere: None, Python’s value for “nothing”). Its values are the notes for the route. Lines 22–27 walk back along the notes until they reach the start, whose note is None, then reverse the list. If the list still to visit runs out before the goal is visited, there is no way there, and line 32 returns None.

Friends of friends

“People you may know” on a social media app starts from this idea: the people 2 steps away in the friendship graph. They aren’t your friends yet, but they are friends of your friends. Breadth-first search from you finds them: they are the people it gives 2 steps.

When a road is closed

Every monsoon, landslides close roads in Nepal. Which towns are then cut off? This is a graph question: take the edge out, then search from the start and see which nodes are no longer reached.

roads = {    "Kathmandu": ["Lalitpur", "Kirtipur", "Budhanilkantha", "Thimi", "Sankhu"],    "Lalitpur": ["Kathmandu", "Kirtipur", "Godawari", "Thimi"],    "Kirtipur": ["Kathmandu", "Lalitpur", "Pharping"],    "Budhanilkantha": ["Kathmandu"],    "Thimi": ["Kathmandu", "Lalitpur", "Bhaktapur"],    "Sankhu": ["Kathmandu"],    "Godawari": ["Lalitpur"],    "Pharping": ["Kirtipur"],    "Bhaktapur": ["Thimi", "Nagarkot", "Banepa"],    "Nagarkot": ["Bhaktapur", "Dhulikhel"],    "Banepa": ["Bhaktapur", "Dhulikhel"],    "Dhulikhel": ["Nagarkot", "Banepa"],} def steps_from(graph, start):    steps = {start: 0}    to_visit = [start]    while len(to_visit) > 0:        place = to_visit.pop(0)        for nxt in graph[place]:            if nxt not in steps:                steps[nxt] = steps[place] + 1                to_visit.append(nxt)    return steps def remove_road(graph, a, b):    graph[a].remove(b)    graph[b].remove(a) def cut_off(graph, start):    reached = steps_from(graph, start)    return [town for town in graph if town not in reached] remove_road(roads, "Bhaktapur", "Banepa")print("Bhaktapur–Banepa closed. Cut off:", cut_off(roads, "Kathmandu"))print("Dhulikhel is now", steps_from(roads, "Kathmandu")["Dhulikhel"], "roads away")remove_road(roads, "Thimi", "Bhaktapur")print("Thimi–Bhaktapur closed too. Cut off:", cut_off(roads, "Kathmandu"))

Bhaktapur–Banepa closed. Cut off: []Dhulikhel is now 4 roads awayThimi–Bhaktapur closed too. Cut off: ['Bhaktapur', 'Nagarkot', 'Banepa', 'Dhulikhel']

With the Banepa road closed, nothing is cut off: Dhulikhel can still be reached through Nagarkot, by the same number of roads. A second way round is what keeps a graph connected when one edge fails, in roads, in the internet’s cables (Grade 9) and in power grids. But with Thimi–Bhaktapur closed as well, four towns are cut off from Kathmandu in this simplified map. A road whose loss cuts a graph in two is called a bridge (Euler’s bridges again, by another meaning); planners look for them, because they are where a single landslide or a single broken cable does the most harm.

([town for town in graph if town not in reached] is a list comprehension: Python’s short way to write “a list of each town in the graph that wasn’t reached”. It does the same as a loop that appends each such town to an empty list.)

One-way links

In a directed graph, breadth-first search follows the arrows only forwards: a page’s list holds the pages it links to. Search engines find pages much like this: a program called a crawler starts from pages it knows, follows every link to new pages, then follows their links, and so on, keeping a list of pages still to visit.

Breadth-first search finds the fewest roads. But a traveler doesn’t count roads; they care about distance or time. A single long road can take longer than three short ones.

A graph with a number on each edge, a length, a time or a cost, is a weighted graph, and the number is the edge’s weight. For a weighted graph, breadth-first search gives the wrong answer: it would send you from Home through the Chowk, because 2 roads is fewer than 4.

Nearest first

The idea that fixes it is a small change to breadth-first search. Breadth-first search visits places in order of how many roads away they are. A map app visits them in order of how far away they are: at each step it visits the nearest place it hasn’t visited yet, where “nearest” is the shortest distance found so far.

Picture water poured at the start, running out along every road at the same speed. It reaches nearby places first and far places later, and the first moment it arrives anywhere is along the shortest way there. In Figure 2.3, the water reaches the School after 0.8 km, the Temple after 1.8, the Market after 2.7, and the Hospital along the bottom roads after 3.8 km, long before the water on the Chowk road gets there (after 6.5 km). So the shortest way is the one through the School, Temple and Market.

To do this, the app keeps, for each place, the shortest distance found to it so far and the place it came from (like came_from). When it visits a place, it checks each road out of it: is going this way shorter than the best way known? If so, it writes down the new distance and the new note. When it visits the goal, its distance is final, and the notes lead back along the shortest route.

This method was invented by the Dutch computer scientist Edsger Dijkstra in 1956, and is called Dijkstra’s algorithm. You will write it in Grade 12, with a better way to keep the list (a priority queue, which always gives back the nearest place first).

What a real map app does

A real map app works on the same idea, at a huge size and with a few more tricks:

• The graph is enormous. Every junction is a node and every stretch of road between junctions is an edge, so a country has millions of nodes. Each edge is weighted by the time it takes, worked out from its length, its speed limit and its type of road.
• The weights change. Phones with location turned on report how fast traffic is moving, so a road in a jam at 5 pm gets a bigger weight than the same road at 5 am. That is why the app’s answer changes through the day.
• It aims at the goal. Instead of spreading out equally in all directions, the search prefers places that are closer, in a straight line, to where you are going. This idea, called A* (said “A star”), from 1968, saves a great deal of work (Grade 12).
• It works out a lot beforehand. Before anyone asks, the company’s computers find the important long-distance roads and store shortcuts, so a route from Ilam to Mahendranagar doesn’t have to try every lane in every town on the way.
• The map must be right. A route can only use roads the graph knows. A new bridge missing from the data, or a closed road still in it, gives a wrong answer however clever the algorithm.

Routers on the internet do something similar for messages: many of them keep a graph of the network, with a cost on each link, and work out the best next hop with Dijkstra’s algorithm (Grade 9 met routers).

Some graphs have a special shape: they never go round in a loop. Your phone’s folders are like this. The main folder holds other folders, each of those holds more, and so on, but no folder ever leads back to one above it.

A tree is a graph that is joined up (every node can be reached from every other) and has no loops: there is no way to go out from a node along edges and come back to it without using some edge twice. A loop (also called a cycle) is exactly that kind of round trip. Because a tree has no loops, there is exactly one route between any two of its nodes.

Words for trees

Trees are usually drawn upside down, with the root at the top:

• The root is the node everything hangs from: the main folder.
• A node’s children are the nodes just below it, joined to it; it is their parent. Every node except the root has exactly one parent. In Figure 2.4, Grade 10 is the parent of Science and Computing.
• A node with no children is a leaf: the files in Figure 2.4, and the empty Science folder.

A tree with n nodes always has exactly n − 1 edges: every node except the root has one edge up to its parent, and that is every edge. The folder tree in Figure 2.4 has 8 nodes and 7 edges. Add one more edge anywhere and you make a loop.

You have met trees already: the folders on a computer (Grade 6 and Grade 8), the names of the internet, where .np holds edu.np, which holds a school’s name (Grade 9), and the families in a vamshavali (वंशावली), a family’s record of descent, which shows one ancestor and all the descendants below. A knockout cricket tournament is a tree too, with the final at the root.

Visiting every folder

Here is a folder tree as a dictionary, each folder with the list of its children. A name that isn’t a key is a file. To list everything in it, use breadth-first search from the root: the list still to visit holds each item’s path, and a folder’s children are put on the back with the path made longer.

folders = {    "School": ["Grade 10", "Photos"],    "Grade 10": ["Science", "Computing"],    "Photos": ["sports-day.jpg"],    "Science": [],    "Computing": ["graphs.py", "notes.txt"],} def list_everything(tree, root):    to_visit = [root]    files = 0    while len(to_visit) > 0:        path = to_visit.pop(0)        print(path)        name = path.split("/")[-1]        if name in tree:            for child in tree[name]:                to_visit.append(path + "/" + child)        else:            files = files + 1    return files count = list_everything(folders, "School")print(count, "files")

SchoolSchool/Grade 10School/PhotosSchool/Grade 10/ScienceSchool/Grade 10/ComputingSchool/Photos/sports-day.jpgSchool/Grade 10/Computing/graphs.pySchool/Grade 10/Computing/notes.txt3 files

Something is missing compared with the road search: there is no dictionary of places seen. In a tree, nothing can be reached twice, because there is only one route to each node, so the search doesn’t need to check. In a graph with loops, a search without that check would go round a loop forever.

The folder tree here is listed ring by ring: first the root, then what is in it, then what is in those. A program could also list it in the other order, depth-first, showing everything inside Grade 10 before going on to Photos, as the folder tree beside a computer’s file manager does when every folder is opened; both orders visit every node once.

You now have a toolkit: a dictionary of neighbors to store a graph, a queue to search it one ring at a time, a dictionary of steps or of notes to remember what the search found. Most graph problems are solved by choosing what the nodes and edges are, then using these tools. When you meet a new problem, ask:

1. What are the nodes? (towns, people, pages, bus stops)
2. What are the edges? Do they go one way or both? Do they have weights?
3. What is the question? Can I reach it? How many steps? Which route? Who is 2 steps away? What is cut off?
4. Which search answers it, and what must it remember? Steps, notes for the route, a count.
5. Test it on a small graph you can check by hand, including the edges: the start equal to the goal, a goal that can’t be reached, a node with no edges.