Eulerian path

On a winter night a snowplough leaves its depot, has to go along every street of its district and come back. Each street it goes along a second time is an empty run: fuel and time while the city waits. Can repeats be avoided? Almost never, but there is an exact answer to how much has to be repeated. Below is a square of 800 by 800 metres around Republic Square: 47 crossings and 5.5 km of streets. Press “Drive”, and the plough goes along the shortest possible route.

The red rings mark 22 crossings where an odd number of streets meet. They are what forces a second pass: 1.69 km, the bands under the streets. Less cannot be repeated, and the 7.19 km route cannot be improved. Switch to “greedy pairs”: the rule “join the nearest crossings” gives 1.94 km. Close some street: the parity at its ends changes, and the plan with it. Tap outside the square to move it elsewhere in the city.

The idea

An Eulerian path is a route that goes along every edge exactly once; if it ends where it began, it is an Eulerian circuit. Whether such a route exists can be seen without any search. Passing through a crossing, we use two of its streets: one in, one out. So a crossing where the route neither starts nor ends has an even number of streets. A connected graph where all degrees are even has a circuit; where there are exactly two odd vertices, a path from one to the other; where there are more, none. This is Euler's rule, and its proof in both directions is taken apart in “Mathematics, the Queen of the Sciences”, in the chapter on graphs.

The rule says whether a route exists, but does not build it. And if you simply drive along unvisited streets while you can, it is easy to get stuck: to return to the start while whole pieces of the graph are still untouched.

Go along unvisited edges while you can. You can get stuck only at the end of the route, where a vertex has run out of edges. Step back along your trail, putting vertices into the answer from the end, until you meet a vertex that still has unvisited edges. Start a new loop from it: it is bound to return to the same vertex and takes its place in the answer exactly there. This is Hierholzer's algorithm, and all the splicing of loops is done by an ordinary stack.

How it works step by step

A flower of three petals: in the centre the vertex O with six edges, the others with two each. There are no odd vertices, so there will be a circuit. The numbers at the vertices are their degrees, red for odd ones. Three edges of the outer ring are dashed: tap any of them to add it, and see how the degrees change and what Euler's rule says.

The search starts at A, goes to O, then to B, and returns to A. A has no more edges: a dead end. Without a stack one would have to give up here, since two petals are untouched. Hierholzer steps back: A goes into the answer as the last vertex of the route, B after it, and at O there are unvisited edges. From here a loop O → C → D → O → E → F → O begins; it comes back to O and takes its place in the route between O and B. The numbers on the edges are their places in the finished route: A O C D O E F O B A.

Add the edge B–C: B and C get three edges each, and the circuit turns into a path from one odd vertex to the other. It can start only at an odd vertex: tap any other, and the scene will say so. Add D–E as well: there are now four odd vertices, and one stroke is no longer enough. Two are needed: each stroke serves at most two odd vertices, its start and its end.

Why the route is right

Where exactly does the search first get stuck? We enter and leave every vertex except the starting one and the second odd one in pairs of edges, and having entered, an edge to leave by will be found. So the first dead end is the end of the route: with odd vertices, the second odd one; with even ones, the starting vertex itself. Start the search at an even vertex when there are two odd ones, and the first dead end falls on an odd vertex in the middle of the “route”, and the spliced sequence is no longer a path. That is why the listing starts at an odd vertex if there is one.

The trap: “don't burn bridges”

Hierholzer has an older rival, Fleury's rule of 1883. Go along edges, erasing them behind you, and never choose a bridge of the remaining graph if there is another way: having burnt a bridge, you cut yourself off from the part not yet walked. The rule is right and never gets stuck, but at every fork one has to check whether the edge is a bridge, and that is a traversal of the graph. Instead of O(E) it comes out O(E²). The Hierholzer method checks nothing: it lets itself get stuck and then repairs the route by splicing, and that is cheaper than being careful all the time. A measurement is in the section on cost.

The second trap is a disconnected graph with the right degrees, for example two separate triangles. Euler's rule requires connectivity, and a program must check it. In the listing the check is free: if the answer has fewer vertices than edges plus one, some edges were never found.

Code

The graph is stored as adjacency lists with edge numbers. Each vertex has a pointer to the first edge that may not yet be walked. An edge of an undirected graph lies in two lists, and having walked it from one end, we mark it so that the other end skips it.

A vertex's pointer only grows, and each edge is skipped at most twice, once from each end. So the whole search is O(V + E), with no bridge checks at all. Euler's seven bridges the program dispatches in one line: four odd pieces of land, no route.

When repeats cannot be avoided: the postman problem

In a city odd crossings are everywhere: every T-junction and every dead end. So the district cannot be covered exactly once, and the question is a different one: which streets to drive twice so that the extra distance is smallest. This is the postman problem: it was posed in 1960 by Kwan Mei-Ko, who also proposed a way to solve it, thinking of a postman who has to walk every street of the round.

Hence the plan: find the distances between odd crossings with Dijkstra, split them into pairs with the smallest sum, duplicate the paths between pairs, and run Hierholzer on the doubled graph. Pairs cannot be chosen greedily, nearest first: in the scene the greedy choice loses 0.25 km out of 1.69. For 22 crossings the listing goes through the pairings with bitmask DP: the state is the set of crossings already paired, and the lowest free one is always paired first, so that the same pairing is not assembled in different orders. Of the 4,194,304 possible masks, only 28,656 occur under this rule.

odd crossings: 22
driven twice, pairs taken greedily: 1.94 km
driven twice, best pairing: 1.69 km (28656 states of the table out of 4194304 masks)
route: 82 pieces in a row, 7.19 km, 26 of them a second time

Masks are fine for two or three dozen odd crossings. For a whole city the best pairs are found by matching, only not bipartite but in a general graph, by Jack Edmonds's algorithm; its fast implementations run in O(n³). This is how Edmonds and Ellis Johnson solved the postman problem in polynomial time in 1973. If all streets are one-way, a minimum-cost flow is needed instead of pairs, and the problem is also solved quickly. But if only some are one-way, as in a real city, it is NP-hard; Christos Papadimitriou proved this in 1976.

Genome assembly

The most common sequencers do not read a DNA molecule from start to end. Many copies of it are cut into short pieces of a hundred or two letters, each piece is read separately, and the genome has to be assembled like a torn newspaper. One could make the pieces vertices and their overlaps edges, and look for a path through all the vertices. But that is a Hamiltonian path, an NP-hard problem. In 2001 Pavel Pevzner, Haixu Tang and Michael Waterman proposed looking at it the other way round (the idea goes back to a 1995 paper by Ramana Idury and Waterman). Cut all the pieces read into overlapping bits of length k, k-mers. The vertices are strings of length k − 1, and each k-mer is an edge from its beginning to its end: GATTA leads from GATT to ATTA. This is the de Bruijn graph, and the genome is a path going along every edge exactly once. An Eulerian one.

The directed version of Euler's rule is this (the graph, as before, being connected): if every vertex has as many incoming edges as outgoing, there is a circuit; if one has one more outgoing and another one more incoming, there is a path between them. A ring genome gives exactly the first case. Below is phage φX174, the first DNA-based genome read in full (Frederick Sanger and co-authors, 1977): a ring of 5386 letters. Its k-mers are shuffled and then assembled by Hierholzer's algorithm.

At k = 8 the assembly goes along each 8-mer exactly as many times as it occurs in the genome, but the ring comes out different: it diverges from the real one already after the ninth letter. Repeats are to blame. 965 different 7-mers occur in the genome more than once, and at each such place the Eulerian circuit is free to turn down any of several roads. As k grows there are fewer repeats: at k = 13 only two, but even they are enough for the pieces to fall into a different order. From k = 14 no string of length 13 repeats, each vertex of the graph has one way in and one way out, the graph is a single ring, and the assembly is unique. The longest repeat in φX174 is 12 letters, and to step over it a piece must be at least two letters longer. A suffix array helps find the length of the longest repeat in advance.

Real assemblers, Velvet, SPAdes and others, build the de Bruijn graph from the k-mers of the pieces read, but do not look for a whole Eulerian path. The reads contain errors, part of the genome is covered poorly, and repeats longer than k confuse the order anyway. So the graph is first cleaned of errors, and then the unambiguous stretches between forks, contigs, are output, leaving the forks unresolved.

What it costs

Each edge is walked once and pushed onto the stack once. Each vertex's pointer to the next edge only grows, and it skips each edge at most twice, once from each end. In total O(V + E) time and O(V + E) memory for the adjacency lists, the marks and the stack. The directed version is simpler still: an edge is visible only from its start, and no “walked” marks are needed. Fleury's rule checks for a bridge at every fork by traversing the remaining graph, and a measurement on a grid rolled into a torus shows this well:

Fleury's slope is about two: double the graph and the time grows fourfold. Hierholzer grows linearly. At three thousand edges Fleury in Python is five hundred times slower, and the gap grows with the graph. In the postman problem the most expensive part is not the Eulerian circuit but the search for pairs: the distances between odd vertices and the pairing itself.

Where it is used

Routes along streets. When it is roads that must be served rather than points, snow clearing, watering, rubbish collection, a postman's round, checking road markings, the problem reduces to Eulerian paths. In real life one-way streets, U-turns, vehicle capacity and several vehicles are added, and a whole family of arc routing problems grows from the pure postman problem. The pure problem is the simplest of them, and its answer serves as a lower bound for all the others: extra conditions do not shorten a route.

Sequence assembly. The de Bruijn graph is the workhorse of assembling genomes from short reads: SPAdes, Velvet and many others build exactly this.

Strings where everything occurs. The shortest string of digits in which every code of length n occurs is an Eulerian circuit in the de Bruijn graph whose vertices are strings of length n − 1. Its length is 10ⁿ + n − 1 instead of n·10ⁿ when going through the codes one by one. This is the first problem below.

In one stroke. A plotter's pen, an engraver's laser, a machine's cutter waste time on idle moves between lines. A drawing is a graph, and the fewest continuous passes is half the number of odd vertices, if there are any, and one pass if there are none. And a full set of 28 dominoes can be laid out in a ring: this is an Eulerian circuit in the graph whose seven vertices are the numbers from zero to six, every pair joined by an edge, and each number also has a double as a loop, so that all degrees are even.

History

In 1735 Leonhard Euler solved the problem of the seven bridges, whether a town can be walked crossing every bridge exactly once, and in passing proved that a graph with more than two odd vertices has no such walk. The story is told in detail in the chapter on graphs of “Mathematics, the Queen of the Sciences”. The converse, that with even degrees the walk exists, Euler considered clear and did not prove.

It was proved by Carl Hierholzer, in the very way of this article: go while you can, then splice the missed cycles into the route. Hierholzer told colleagues about the proof shortly before dying in 1871, aged thirty, and the paper came out after that, in 1873, together with the name of Christian Wiener. The rule “don't burn bridges” was published by Fleury in 1883.

Strings containing all codes were counted as early as 1894, when Camille Flye Sainte-Marie found how many there are for a binary alphabet. In 1934 Monroe Martin gave a simple rule that builds such a string for any alphabet, and in 1946 the problem was solved anew by Nicolaas de Bruijn, whose name the graph bears; de Bruijn later acknowledged Flye Sainte-Marie's priority. The postman problem was posed in 1960 by Kwan Mei-Ko, and a polynomial solution through matchings was given by Jack Edmonds and Ellis Johnson in 1973. De Bruijn graphs came into genome assembly in 1995 with Idury and Waterman and became its basis after the 2001 paper by Pevzner, Tang and Waterman.

Problems

In the first problem you find the shortest sequence of key presses that tries every code of a keypad lock, that is, build a de Bruijn string. In the second you assemble a ring genome from shuffled k-mers, and the tests include the real φX174 and human mitochondria. In the third the snowplough goes out onto the streets of Almaty: how many metres must it drive to cover every street of its district and come back.