Six handshakes

At the end of the last chapter data stopped living alone. Friends know friends of friends, metro stations are joined by tracks and transfers, the chapters of this textbook point to chapters you should read first. The first thing anyone asks about such data is how to get from here to there, and in how many steps. There is an old hypothesis that any two people on Earth are linked by a chain of no more than six handshakes. It sounds like small talk at a party, but it can be checked. We will check it by searching a graph we build ourselves, on two sets of data: the Moscow Metro and this course.

Letters from Nebraska

More than forty years later the experiment was repeated without letters. In 2011 researchers from Facebook and the University of Milan, Lars Backstrom, Paolo Boldi, Marco Rosa, Johan Ugander and Sebastiano Vigna, took the friendship graph of every active user: about 721 million people and 69 billion friendships. The average distance between two people came out at 4.74 steps, which means 3.74 intermediate acquaintances. Their 2012 paper was called “Four Degrees of Separation.”

The two experiments measured different things. In Milgram’s, each participant saw only their own acquaintances and passed the letter on by guesswork, so a chain that arrived could be far from the shortest one. The Facebook researchers saw the whole network at once and counted the shortest chains. That takes a quick way of finding the shortest chain between two points of a network: there were a quarter of a quintillion pairs of people to check.

The instrument: a graph

A network of acquaintances, a metro, a maze, the links between web pages: they are all one structure. There are objects, and there are links between pairs of objects. The objects are called vertices, the links edges, and the whole thing a graph. A graph records only what is connected to what. The positions of stations on the map and the lengths of the tracks between them aren’t in it until we add them ourselves.

Leonhard Euler was the first to see a problem this way, in 1735, when he proved that no walk through Königsberg crosses each of its seven bridges once and only once: the islands and the riverbanks became vertices, the bridges became edges. That story and its mathematics are told in “Mathematics, the Queen of the Sciences,” in the section “Seven bridges”. The theorems can stay there; what we need here are programs that walk around graphs.

Edges come in two kinds. Friendship is mutual, and trains run both ways between two stations, so such an edge goes in both directions. But “read Chapter 17 before Chapter 18” is an arrow, from 17 to 18. A graph with arrows is called directed. The number of edges at a vertex is called its degree: a terminal station has degree 1, a big interchange five or six.

The course sandbox holds a graph of the Moscow Metro, put together from an open directory of stations: 17 lines as the directory lists them, including the Circle line around the center and two larger rings farther out, the Moscow Central Circle (MCC) and the Big Circle line, but not the MCD commuter lines. Every station on every line is a separate vertex. The edges are rides between neighboring stations on one line and transfers between lines: Kievskaya on the Circle line and Kievskaya on the Filyovskaya line are two vertices, with a transfer edge between them. We restored the transfers from the coordinates: stations of different lines less than 450 meters apart count as connected. Nearly always the two are joined by a passage underground, but here and there it means a walk along the street. Here is the raw data, folded into a graph.

The directory comes from Moscow, so the names in the file are Russian, in the Cyrillic alphabet. A function from the course module spells them in Latin letters, much as the English signs in the Moscow Metro do. The number before the colon is the line: 5 is the Circle line, 3 the Arbatsko-Pokrovskaya line, 4 the Filyovskaya line. With its line number in front, a station’s name is unique, which makes it a handy name for a vertex. The graph itself is a dictionary from Chapter 8: the key is a vertex, the value is the list of its neighbors. This way of storing a graph is called adjacency lists. An undirected edge is written down twice, once in each list, so the lengths of all the lists add up to 808, twice the number of edges.

From here on a single line will load the metro graph: graph, names = load_metro() from the course module cs.graphs. It does what the cell above does, and also hands back a dictionary of names without the line number. The order of the stations along each line in the file was restored from their coordinates, and at the fork of the Filyovskaya line, at the far end of the Lyublinsko-Dmitrovskaya line and at Shelepikha it came out wrong; those five rides were corrected in the file by hand.

A table instead of lists

There is another way to store a graph: an $n \times n$ table where the cell in row $a$ and column $b$ holds 1 if there is an edge between $a$ and $b$, and 0 if there isn’t. It is called the adjacency matrix. To check whether an edge exists, you read one cell, $O(1)$, while with adjacency lists you have to go through a list of neighbors. The price is memory: the table has $n^2$ cells however many edges there are.

The metro is no different: a matrix of $312 \times 312 = 97\,344$ cells, of which 808 hold a one, less than one percent. From here on every graph we use is a dictionary of lists.

The wave

Suppose Milgram had allowed the letter to go not to one acquaintance but to all of them at once. On the first day the sender’s acquaintances get it. On the second day their acquaintances do, except those who already have it. On the third, the next circle. The letter spreads in a wave, like ripples on a pond, and the day it first reaches a person is the length of the shortest chain to that person. Anyone who gets the letter a second time throws it away: that won’t make their chain any shorter.

The program has one decision to make: whom to deal with next. The wave itself suggests the answer: whoever got the letter earlier. First come, first served; that is the queue from Chapter 15, a deque with append at the tail and popleft from the head. This is how breadth-first search, BFS for short, works. In Chapter 17 it walked a tree level by level. There is one difference: in a tree a single path leads to each node, in a graph many paths do, so we have to remember who already has the letter. We’ll start the wave from Sokolniki, the station where Moscow’s first metro line began in 1935.

The dictionary dist does two jobs: it holds the answer and it remembers who already has the letter. Each line of the output is a circle of the wave. At distance 1 there are three stations (Krasnoselskaya, Preobrazhenskaya Ploshchad and the transfer to the Big Circle line); at distance 8 there are thirty-one, the widest circle. The last one, the twenty-fourth, is Buninskaya Alleya alone, in the southwest. The wave reached all 312 stations.

Play with the wave. From a station on the Circle line it covers the city faster than from the end of a line: it is closer from the center to any part of the outskirts than from one side of the city to the other. And around the MCC and the Big Circle line you can watch the rings pick up the wave and carry it around.

The path, read backward

The distance is only half the story; we also want the path itself. For that, every vertex remembers who first passed the letter to it. These notes form a tree rooted at the starting vertex, and the path to the goal reads off it backward: from the goal to whoever found it, from that vertex to its parent, and so on back to the start. All that remains is to reverse the list.

Twenty edges: seven stops on the orange line, a transfer to the Circle line, five stops around the ring, a transfer to the red line and six more stops to the southwest. The number of edges on the shortest path is called the distance between the vertices, and the path itself is a shortest path. But why is the path the wave finds the shortest? The search never tries all the paths.

What does the search cost? Each vertex enters the queue once, because the check if u not in dist won’t let it in a second time. Each list of neighbors is scanned once, when its vertex leaves the queue. That makes $O(V + E)$ in all, where $V$ is the number of vertices and $E$ the number of edges: the linear time of Chapter 13. For the metro, a little over a thousand steps. But don’t forget the deque: with an ordinary list and pop(0), every removal shifts the whole queue, as in Chapter 14, and on a big graph the search turns quadratic.

Testing the hypothesis: the metro

The instrument is ready. For the metro, the hypothesis that any two people are six handshakes apart reads like this: from any station to any other there are at most six edges. We will test it head-on, by starting a wave from every station in turn and collecting all the distances. Place your bet first.

Three hundred and twelve waves and over forty-eight thousand pairs take the server a fraction of a second. For the metro the hypothesis fails: there are 11.3 edges between two stations on average, and fewer than a fifth of the pairs are within six edges of each other. The two farthest apart are Fiztekh in the north and Buninskaya Alleya in the southwest, 32 edges. The largest distance in a graph is called its diameter.

Why did Facebook come out under five and the metro over eleven? Recall the reasoning of Karinthy’s hero. If everyone has $k$ acquaintances and the circles don’t overlap, then in $d$ steps you reach about $k^d$ people. To reach all $n$ you need $k^d \approx n$, that is, $d \approx \ln n / \ln k$. For Facebook $n \approx 7.2 \cdot 10^8$ and the average number of friends is $k \approx 190$, so the estimate gives $d \approx 3.9$, not far from the measured 4.74. A metro station has $k \approx 2.6$ neighbors on average, and the estimate promises about six. The measured mean is twice that.

The estimate misses because in a metro the circles overlap. A neighbor’s neighbor on a line is another station on the same line, and along a line the wave grows by addition, one station per step, instead of multiplying. In the cell wave.py the circles grow slowly, 1, 3, 4, 9, 13, 19, and then shrink. A network of acquaintances is much the same: most of your friends live nearby, went to school or work with you and know each other. But somebody has a cousin in Australia, somebody else a college friend in Berlin. Such long-range links are few, and they are what makes the world small.

That is how Duncan Watts and Steven Strogatz explained the “small world” in 1998, in a paper in Nature. They took a ring graph in which everyone is linked only to their nearest neighbors and began rewiring a few edges to random distant vertices. Local clustering barely changed (the friends of your friends were still your friends), but the mean distance collapsed once a few percent of the edges had been rewired. We can try the same on the metro by digging tunnels between random stations.

Twenty tunnels, five percent on top of the metro’s four hundred edges, bring the mean distance down from 11.3 to 8.8. A hundred tunnels halve it, to 5.7: the metro becomes a small world. Three hundred bring it to about four, almost what Facebook has. In a bigger graph the effect is stronger still: the more vertices, the longer the detours each tunnel cuts out.

And this course?

The second graph in our study is the textbook itself. Its 66 chapters are the vertices, and an arrow leads from a chapter to one that builds on it: “recursion → trees” means that recursion is read first. The course module returns these links with a single call, load_course(), as a dictionary “chapter → chapters to read before it.” For the handshakes, forget the direction for now: let a chapter and its prerequisite be acquaintances, neither of them senior.

The course turns out to be a small world: 3.4 steps between two chapters on average, and only nine pairs out of 2,145 are more than six apart, although a chapter has fewer than four links on average. Karinthy’s estimate gives $\ln 66 / \ln 3.7 \approx 3.2$, very close. Unlike the metro, the course isn’t tied to a map. Recursion, dictionaries, trees and complexity are its social butterflies: each of these chapters has eight or nine links reaching all corners of the course, from sorting to game bots. Through them every chapter is a few steps away from every other.

Ariadne’s thread

The wave has an oddity that is easy to miss: vertices it handles one after another may lie at opposite ends of the city, a station in the north, then one in the south, then the north again. The program doesn’t mind, since it sees the whole graph at once. A person in a maze minds very much: you can’t jump from one side of the wave to the other. All you can do is go forward or go back the way you came.

Greek myth already knew how to get out of a labyrinth. Ariadne gave Theseus a ball of thread, and the thread he unwound behind him led him back from the Minotaur. The thread marks the way from the entrance to where you stand. Step forward and the thread grows longer. Hit a dead end and you wind the thread back to the last fork and try another passage. That is depth-first search, DFS. The thread is a stack: the passage walked last is wound back first. And we already have a stack ready to use, the call stack from Chapter 9: a recursive call is a step forward, a return from the call is a step back.

Trémaux’s rules are depth-first search written in chalk on the walls: the marks stand in for the set of visited vertices, and “leave by the passage you first arrived through” is winding the thread back. Here is depth-first search on the metro graph. The list thread is the thread: a station is added to it on the way in and struck off when the search comes back from it empty-handed.

It found a path, but what a path: 199 edges instead of twenty, and on the way the search looked into 245 of the 312 stations. It rode the orange line from end to end, through the center and all the way south, crossed to the Butovskaya line, came back north on the gray line, went almost all the way around the MCC, and visited twelve lines before it stumbled on the goal by chance. Depth-first search finds a path: it pushes stubbornly forward and gives no thought to length. In return, it never has to jump: each next step is a neighbor of the current vertex or a step back. That is why a person can follow it on foot, and nobody can follow the wave.

A maze is a graph too: cells are vertices, and edges join neighboring free cells. There is no need to store lists of neighbors, because they are easy to compute: the neighbors of cell $(r, c)$ are $(r \pm 1, c)$ and $(r, c \pm 1)$, unless there is a wall. The next cell digs a maze and then solves it. Depth-first search does the digging: from a room into a random untouched neighbor, breaking the wall between them, and from a dead end back along the stack. The wave finds the way out.

A maze dug by depth-first search is a tree: the wall into each room was broken once, so there is a single path between any two cells. The wave and the thread then find the same path, and the only difference is how many cells each of them looks at along the way. Start the race and change the maze.

In a tree maze the thread wins about two times out of three: it runs down a single corridor and wastes no steps on the others, while the wave has to spread in every direction at once. But knock a few loops into the walls, and the thread’s path becomes almost twice as long as the shortest one on average, sometimes four times. In an open field its path is a zigzag, on average four times longer than the shortest way to the exit. Speed has little to do with the choice between them: in the worst case both searches examine everything, in $O(V + E)$. If you need the shortest path, take the wave. If you need to visit everything, walk a maze on foot or check whether there is a path at all, the thread will do.

The paint bucket

Every graphics editor has a bucket: touch a pixel and the whole area of the same color around it is repainted, while the paint stops at the outline. That is a graph search too. The vertices are pixels, an edge joins two neighboring pixels of the same color, and the bucket paints everything reachable from the pixel under your finger. As in the maze, the graph isn’t written down anywhere: neighbors are computed from coordinates. A pixel is repainted the moment it is found, so the new color doubles as the mark “been here already,” and no separate set is needed.

Drag the slider. Paint poured into a corner spreads as a diamond, which is what the circles of a wave look like on graph paper. It flows around the shapes and seeps into the square through the gap at the bottom, but the circle is closed, and inside it the white stays white. The line if old == paint is there for a reason: without it a bucket of the same color would run forever, since every repainted pixel would again be of the “old” color.

With a stack instead of a queue the bucket paints the same area in a different order: in long stripes that hit a wall and turn around. The “8 neighbors” switch, though, changes the result: if diagonal pixels count as neighbors too, the paint leaks through a thin slanted line, since two cells touching at the corners are now connected. That is why editors almost always pour paint by four neighbors.

It is tempting to write the fill as a recursion: paint the pixel and call yourself on its four neighbors. That is four lines, and on small pictures they work. But recursion goes deep, and on a picture of one color it crawls through every pixel in a long snake without coming back, so the depth of the calls grows to the area of the picture.

A square 40 by 40, a mere 1,600 pixels, and the recursion already hits the depth limit from Chapter 9. A twelve-megapixel photo is out of its reach altogether. We know the cure from Chapter 15: keep the pile of unfinished business in an ordinary list, which can grow as long as it likes. That is why on big graphs depth-first search is written with a stack of its own, and recursion is kept for graphs that are known to be shallow.

The bucket turns up in many places. The magic wand of a photo editor selects a connected area of similar color. In Minesweeper a click on an empty cell opens the whole empty area around it. In Go a group of stones that touch along their sides is taken off the board when no free points are left around it, and a program finds the group with the same flood fill.

How many pieces

A fill answers the question “what is connected to this pixel?” Pour the bucket again and again, each time into a spot not yet painted, and the picture falls apart into pieces: inside each, everything is connected, and between them nothing is. Such pieces are called connected components. Any search will find them: start it from the first vertex nobody has seen yet, and everything it reaches is one component.

Counting the components is the first thing worth doing with new data about a network. We expect the metro to be connected and, without the transfers, to fall apart into its lines and nothing else. If there turn out to be more pieces, the data has a hole: a missing ride, or a station recorded under two names.

The metro is one piece, and without the transfers it is seventeen, as many as there are lines in the data, each holding the stations of one line. The data passes this check. The largest pieces are the two rings, the MCC and the Big Circle line, with 31 stations each, and the smallest is the Kakhovskaya line with three. That line shows what a count of pieces can’t catch. Since 2023 there has been no Kakhovskaya line: its stations became part of the Big Circle line. The directory, however, still keeps them as a separate line too, so in our data these three stations are recorded twice, and the copies are joined by transfers. The check missed the duplicate, because the piece matched a line the directory names, as it should. The distances hardly change because of it: without the duplicate the mean and the farthest pair stay the same. The same function counts islands on a map, groups of people in a social network with not a single friendship between them, and separate nets in an electrical circuit. Islands are waiting for you in the tasks.

In what order to read

So far we have ignored which way the arrows point. Time to give them their direction back. The arrow “recursion → trees” says: before reading about trees, read about recursion. Distances matter little here. What a reader needs is an order: all the chapters in a row, each one after every chapter it builds on. Such an order is called a topological sort.

There isn’t always one. If chapter A requires chapter B, B requires C, and C requires A, you can’t start with any of them: the arrows have closed into a loop. A path along the arrows that returns to its starting vertex is called a cycle, and a directed graph without cycles is a directed acyclic graph, or DAG. The graph of the course’s chapters has to be one; otherwise we made a mistake somewhere in the plan.

Kahn’s idea: read whatever you already can. Give each chapter a counter of how many of the chapters it needs are still unread. Chapters whose counter is zero are ready, and they wait in a queue. Take a ready chapter, read it, and every chapter that was waiting for it gets its counter decreased by one. A chapter whose counter reaches zero joins the queue of ready ones. If at the end not every chapter has been read, the ones left over are waiting for each other in a loop.

Kahn’s order begins as ours does: 0, 1, 2, 3. And then comes 28: the chapter “Everything is bits,” about binary numbers, builds only on Chapter 2, “Names and values,” and became ready at the same time as Chapter 3. This chapter on graphs is number 39 of 66 in Kahn’s order. The course’s own numbering is a valid order too, one of a great many: when many chapters don’t depend on each other, a graph has an astronomical number of topological sorts. The last line shows what happens if the introduction requires graphs: Chapter 0 waits for Chapter 19, which through a chain waits for Chapter 0, and Kahn gives up: the queue of ready chapters runs dry too early.

Why does Kahn’s algorithm always find an order when there are no cycles? Suppose it stopped while some chapters were still unread. Each of them has a nonzero counter, so each has an unread prerequisite. Stand on any of the remaining chapters and step to its unread prerequisite, from there to the next one, and so on. You can keep walking forever, but there are only so many chapters, so sooner or later you come back to one you have visited, and that is a cycle. So without cycles the algorithm doesn’t stop until everything has been read. Each arrow lowers a counter once along the way, and the time is again $O(V + E)$.

Depth-first search can build the order too: follow the arrows back to the prerequisites and write a chapter down once you are done with all of them, like the post-order traversal from Chapter 17, where a node comes after its branches. And to find out everything you need to read before one particular chapter, a single walk backward along the arrows from it is enough.

To read about public-key encryption in Chapter 60 you don’t have to read 59 chapters in a row: sixteen will do. This chapter needs fifteen, and neither trees nor heaps are among them: graphs stand on lists, dictionaries, recursion and the queue.

Ready-made: graphlib and pip

Since Python 3.9 topological sorting has been part of the standard library, in the module graphlib. It expects a graph in the same form as ours, “vertex → the ones that come before it,” and when there is a cycle, instead of returning None it raises a CycleError with the cycle itself inside.

Read the cycle like this: recursion needs trees, complexity needs recursion, trees need complexity. pip solves the same problem. matplotlib has its dependencies, they have theirs, and since version 6.1 (2015) pip installs them in topological order, dependencies before the packages that depend on them: otherwise a package that needs one of its dependencies while it is being installed might not find it. In the same way make decides what to rebuild first, and a spreadsheet decides which cell to recalculate after an edit: a formula waits for the cells it refers to. A spreadsheet’s complaint about a circular reference is the same dead end that Kahn’s algorithm reached with the unread chapters.

Tasks

Five tasks for the chapter’s five techniques: the wave with the path back, the fill, finding a cycle, an order with a rule for choosing, and the center of a network. In all of them except the islands, a graph is a dictionary of lists, as in the chapter. The tests check the edge cases (empty graphs, unreachable goals, vertices without edges) and big inputs, on which recursion and pop(0) run out of time.

##....#
##...##
...#...
.......
#.#.###

What next

The six-handshake hypothesis nearly held for the course and failed for the metro, and we know why: a small world rests on a few long-range links. The wave, the thread and Kahn’s counters will serve you wherever there are links.

But the instrument has a blind spot. Ask the wave how to get from Sokolniki to Moskva-Siti, the station in Moscow’s business district, and compare its answer with the route through the center, measured in minutes: we made a rough estimate of travel times from the same data.

The wave chose the Big Circle line: ten edges instead of thirteen. But that route has two transfers instead of one, and its rides are almost twice as long as those in the center, so by our rough estimate it takes 33 minutes, while the route through the center, three stations longer, takes 26. To the wave every edge is the same: a short ride in the center, a long one on the outskirts and a walk down a transfer corridor each count as one step. Roads have lengths, and BFS can’t see them. A navigation app needs a search that spreads by time, like a fire through grass: quickly where the next stop is close, slowly where it is far. Edsger Dijkstra invented one, and we will build it in Chapter 24, together with the heap from the last chapter, which will tell it which junction is nearest.

First, though, we need two skills that neither a navigation app nor almost any program that handles data can do without: finding things quickly and putting things in order. How to do both, and why sorting by comparisons has a speed limit that no cleverness can get around, is the subject of the next chapter, a tournament of sorting algorithms.