Possibly all the ways to get loop-finding in graphs wrong

[Simon Tatham, 2024-09-09]

• Introduction
• The algorithms
  • Vertex dsf
    • What’s wrong with it?
  • Graph pruning
    • What’s wrong with it?
  • Loop tracing
    • What’s wrong with it?
  • Face dsf
    • What’s wrong with it?
  • Footpath dsf
    • What’s wrong with it?
  • Tarjan’s bridge-finding algorithm
    • What’s wrong with it?
• But after all that…
• Footnotes

Introduction

In my puzzle collection, there are many games in which you have to connect points together by edges, making a graph, and the puzzle rules say you must avoid making any loop in the graph. Examples are Net, Slant, and some configurations of Bridges (although not the default one). Loopy and Pearl also care about whether there’s a loop in a graph, although those two are more subtle: your aim is to make a loop, and only wrong loops must be rejected.

Therefore, those puzzle programs need to be able to check whether a graph has a loop in it, in order to decide whether the puzzle solution is correct. If there is a loop, they also have to identify the edges that make up the loop, in order to point out to the player why their solution hasn’t been accepted.

Over the years I’ve been developing these puzzles, I’ve gone through an amazing number of algorithms for doing that job. Each one was unsatisfactory for some reason, and I threw it away, and moved on to the next.

I might by now have collected all the ways to do this job wrong! So I thought I’d write up all my mistakes, as a case study in all the ways you can solve this particular problem wrongly – and also in how much effort you can waste by not managing to find the existing solution in the literature.

The algorithms

Vertex dsf

When one of these puzzles is generated, the generator will run an automated solving algorithm, to check that its solution is unique. So the solving algorithm needs to check whether it’s accidentally made a loop in the graph.

Or, more precisely, it’s better if the solver can tell whether it’s about to make a loop: when it’s considering adding some edge to the graph, it wants to know if that edge would form a loop. If so, it decides not to add it at all, which is more efficient than adding it first, finding you’ve made a mess, and having to undo your work.

My automated solvers generally handle this by using an implementation of the disjoint-set forest data structure, otherwise known as a ‘union-find’ data structure, or just ‘disjoint-set data structure’¹I think, pedantically speaking, ‘disjoint-set forest’ refers to a specific technique for solving the problem of incremental equivalence tracking, whereas the other names without ‘forest’ in them refer to the problem itself without committing to a particular solution – in the same way that the Fast Fourier Transform is one particular algorithm for implementing the abstract mathematical operator called the Discrete Fourier Transform. In both cases, the distinction is often ignored, because the well-known algorithm is such a good way to solve the problem that nobody ever really wants to use a different one.1. My code refers to this as a ‘dsf’ throughout, which is much shorter, and I’ll follow that convention here too.

For those who haven’t encountered a dsf before, it’s a very fast data structure for tracking equivalence between elements of a set, as long as equivalences are added incrementally: you start with every element of the set being considered different, and you can update the data structure to make two elements equivalent to each other when they previously weren’t, but no elements ever stop being equivalent when they previously were. So the elements of the set are partitioned into equivalence classes, and an update can merge two classes, but a class never splits. You can efficiently add a new equivalence by telling the dsf that some pair of elements a and b will now be considered the same, and you can query it at any time to ask whether two elements are currently considered equivalent. It automatically tracks transitivity, so that (for example) if you’ve already told it that a = b and that c = d, and then you tell it that b = c, it will immediately know that a = d as well. It’s an absolute keystone of my entire puzzle collection: without that utility module most of it would fall down in a heap on the floor.

So when the automated solver for Slant – for example – is trying to solve a puzzle, it makes a dsf on the vertices of the grid. Every time it adds an edge, it tells the dsf to unify the two vertices at the ends of that edge. So the equivalence classes of the dsf precisely track the connected components of the graph: if two vertices are reachable from each other by a path, then the dsf will report them as ‘equivalent’, and if they aren’t, it won’t.

This means that before the solver adds an edge to the puzzle solution, it can query the dsf to see whether the two end vertices are considered equivalent. If the dsf says yes, then there’s already a path between those vertices, which can’t involve the edge we’re about to add (because we haven’t added it yet). Therefore, if we did add that edge, there would be two completely separate paths between the vertices – i.e. a loop.

The automated solvers usually only add an edge to the graph if they’re sure it’s correct, which means they never need to change their mind and remove it again. So as they go along, they only need to maintain a single dsf, initialised at the start of the solving process when the grid is empty, and update it as they go along.

But to use the same system during play, when the player might add or remove edges in any way they like, you have to start from scratch every time you want to check for errors, i.e. every time the player makes a move. Each time, you make a new dsf; iterate through the player’s game state unifying the endpoints of each edge the player has filled in; in each case, check beforehand whether the endpoints were already equivalent, and if so, disallow the player’s solution, because it has a loop.

What’s wrong with it?

This algorithm is correct, and very efficient. For automated solving, there’s nothing at all wrong with it, especially because you get to keep just one dsf for the whole run of the solver. So the automated solvers in Puzzles still do their loop detection this way.

But it won’t generate the nicely highlighted loops I showed in the introduction. This algorithm can only report ‘yes’ or ‘no’: either there is a loop, or there isn’t. It can’t automatically identify all the edges of the loop, to light them up and show them to the player. At most, it can find one edge of the loop: whichever one was added last. If the loop is complicated and twisty, it can be difficult for the player to pick out the rest of it by eye – it’s like trying to solve a maze on screen.

So, when this was the only loop-detector I had, players would fill in what they thought was a correct solution to a Slant puzzle, and the game wouldn’t flash to indicate victory, and it would be hard to figure out why not.

This algorithm is fine as far as it goes – but it doesn’t go far enough.

Graph pruning

So our revised problem is: don’t just say that a loop exists, but identify every edge involved in it. Ideally, if there are multiple loops, identify all their edges.

My first attempt to solve this problem worked by iteratively pruning the graph. Find a vertex with only one edge coming in to it. Then that edge can’t be part of a loop. So we can remove it, without destroying any loops in the graph.

Once you start removing edges, you reduce the degree of further vertices, so now maybe more of them have degree 1. So keep pruning, until you can’t find any more degree-1 vertices.

If the graph had no loops in it at all, then this procedure ends up having pruned away all the edges, leaving an empty graph, in which all the vertices are isolated. But if there is a loop, then no edge of the loop can possibly be pruned. So highlight all the remaining edges as errors.

What’s wrong with it?

This algorithm correctly identifies whether there’s a loop, and it guarantees to highlight every edge involved in any loop. Unfortunately, that’s not all that it highlights.

If the graph contains a ‘dumb-bell’ shaped subgraph consisting of two loops connected by a path, then the loops can’t ever be pruned, but neither can the connecting path. So that will be highlighted in addition to the loops themselves.

This algorithm highlights too many edges!

Loop tracing

So I thought about how to solve this ‘dumb-bell’ problem, and after some pondering, came up with a completely different approach.

To begin with, we go back to the ‘vertex dsf’ idea. To check the player’s solution for errors during play, we make a fresh dsf with all vertices separate, and iterate through the graph edges, unifying the two endpoints of each edge. Before each unification, we query the dsf to see whether the two endpoints were already connected to each other. If they were, we know that the edge we’re currently processing is part of a loop.

But this time, we don’t stop there. Once we’ve identified one edge that’s part of a loop, we do a graph search around the rest of the graph to find an alternative path between its endpoints. Then we’ve identified a specific loop involving that edge, and we can light up every part of that loop as an error.

Once you’ve done that, don’t stop there: return to the main iteration that adds the rest of the edges to the dsf, in case there are more loops you can find and trace round.

What’s wrong with it?

This algorithm solves the dumb-bell problem: it only ever lights up an edge when it’s found an actual loop in the graph, with that edge being part of it. So it definitely can’t light up any edge that is not part of a loop. The central bar of the dumb-bell graph is safe from accidental highlighting.

But I couldn’t convince myself that this technique would catch all the loops in the graph. What if there are several loops that touch, or intersect each other? If you’re looking for a path between the two endpoints of some particular edge, and there’s more than one such path, the tracing will only find one of them. Might there be a situation in which an edge is part of a loop, but we somehow missed it, because every tracing operation happened to choose some other route?

I never saw this happen – but I also never managed to convince myself that it couldn’t, and that was unsatisfying.

However, even supposing this algorithm has a flaw of that kind, it’s not too bad. It will at least reliably identify whether or not there are any loops at all. A loop-free graph will be correctly reported as OK, and a loopy graph will have at least one loop highlighted.

And I never saw the tracing algorithm miss a loop in practice, or had any report of a failure from a user. So this version stayed around for some years, until I had a better idea.

Face dsf

In 2008, a contributor sent me a patch making major changes to Loopy. Before the changes, it only supported playing on square grids, like conventional Slitherlink. Afterwards, it supported a wide variety of other periodic²Since then, Loopy has been enhanced further, so that not all the tilings are even periodic. You can also play Loopy on a fragment of Penrose tiling, or the Hat and Spectre tilings discovered in 2023. I have a whole series of other articles about that!2 tilings – triangular grids, hexagonal honeycombs, various tilings of mixed shapes, etc – using a general system for representing the game grid as a planar graph.

While I was discussing that patch with its author, I realised that there’s a neat algorithm for loop detection, using the fact that all the graphs involved are planar.

As well as vertices and edges, a graph embedded in the plane has a concept of ‘faces’: the regions of the plane separated by the graph edges. If a planar graph contains no loops, then there’s only one face: from any part of the plane you can reach any other part, without having to cross a graph edge. You might have to take a roundabout route, but there always is a route.

Conversely, if a planar graph does contain a loop, then that loop separates the plane into two regions: the inside and the outside. To get from one to the other, you’d have to cross an edge of the loop.

So my new idea was: instead of making a dsf on the vertices of the grid to find a loop that joins them to each other, we make a dsf on the faces of the grid – to find a loop that separates them from each other.

In detail: to scan a grid for loops, you divide the plane into regions that no grid edge can possibly intersect, and then you iterate over every edge of the grid graph. For each grid-graph edge that is not part of the user’s solution, you tell the dsf to merge the two regions on opposite sides of that edge, representing the fact that it’s possible to walk from one region to the other without having to cross a solution edge.

When you’re done, you’ve partitioned the regions into their connected components. Any two regions in the same component can be reached without crossing a solution edge. But regions in different components can’t be.

So the boundary of any component is precisely a loop. In other words: a solution edge is part of a loop if and only if the regions on either side of it are not equivalent in the dsf!

For Loopy, it’s most obvious how to apply this principle. The ‘regions’ I discuss here are precisely the faces of the grid graph – the squares, hexagons, triangles (or whatever) of the starting grid, as in the diagrams above. For Net, it’s almost as simple: the solution graph connects the centres of grid squares, so the ‘regions’ must be offset from that: they’re squares centred on the grid vertices.

It’s slightly more complicated for Slant, because the set of possible solution edges doesn’t form a planar graph: the two different diagonals you can put in a square cross each other. But that’s OK: we can imagine turning it back into a planar graph by dividing each edge in two at the midpoint of the square, so that the player’s move fills in two of those half-edges in a single mouse click. Then the ‘regions’ are the faces of that subdivided planar graph: each region is a diamond surrounding one of the original grid edges.

What’s wrong with it?

When I thought of this approach, I was really pleased with it! It’s the first algorithm in this list that I was 100% confident was right. It’s easy to prove that it picks out precisely the loop edges: no extra ones, and no missing ones. And it’s incredibly easy to implement: you just make a dsf (which I already had code for), and then do two simple loops over the grid: once to unify regions, and once to check each edge to see if it needs to be highlighted. I was convinced I’d finally put this long-term annoyance to rest.

Some years later, a friend of mine asked, “Simon, is there any chance you could make Net highlight loops as errors?” Net was one of the very first puzzles in my collection, and until this point, I’d never got round to going back to it and adding loop highlighting³In one sense, Net doesn’t exactly need loop highlighting. In Net, the solution to the puzzle is an acyclic graph connecting all the squares of the grid. And if you manage to make any graph at all that connects all the squares, it can’t have a loop, because a graph on that many vertices with a loop would have the wrong number of edges, and the Net user interface doesn’t let you change how many edges exist. So if you do make a loop, you’ll find you can’t light up all the squares of the grid, so it will at least be obvious why the game doesn’t think you’ve won. But that doesn’t give you any help finding the loop – all it proves is that there must be one somewhere. So highlighting it is still useful for that.3.

Still full of confidence, I said something along the lines of “Sure! This will be no problem. I know exactly how to do loop highlighting now – I’ve already gone through all the ways to do it wrong, and I’ve finally found the right algorithm. It’ll be a breeze. I’ll have it done tomorrow.”

Of course, after I said that, you just know there had to turn out to be a problem! But I don’t feel too bad about it, because it was a pretty subtle one.

The problem with Net, compared to all the other puzzles in my collection, is that it has a ‘wrapping’ mode, in which the left side of the grid is considered to be connected to the right side, and the top connects to the bottom. In topological terms, this game mode is played on a torus, instead of a region of the plane.

A torus has a property that makes it fundamentally different from a plane or a sphere, known in algebraic topology as a ‘nontrivial H₁ homology group’. This is a fancy way of saying that on a torus, it’s possible to have a loop that doesn’t divide the surface of the torus into two separate components. ‘Local’ loops in a small part of the torus still do that, but a ‘global’ loop that goes all the way around the torus doesn’t, because you can get from one side of the loop to the other by walking at right angles to the loop, and going all the way round the torus in the other direction.

So my face-dsf loop detection algorithm would spot small localised loops, but not – for example – a loop that goes off the right side of the grid, comes back on to the left, and returns to its starting point. And those loops are some of the most difficult ones to spot by eye, so it’s especially unhelpful that the algorithm can’t point them out to the player.

This incident is the current holder of my personal record for ‘most esoteric mathematical concept that I’ve ever seen cause a real software bug’. I’d learned about homology before, but I’d imagined it to be one of those abstract theoretical properties that you think about in order to prove theorems, but never find a practical application. I’d never have expected homology to be the cause of a bug!

Footpath dsf

I was quite embarrassed about getting this wrong when I’d been so confident. So I wanted to fix the bug in Net quickly. Therefore I looked for some kind of small change I could make to my existing idea – and found one.

In the previous section, where we saw a loop on a torus and a path from one side of it from the other, the path went a long way away from the loop – all the way round the far side of the torus, as far from the loop as you could possibly get. But where I showed a genuinely loop-free graph with a path from one side of an edge to the other, it would have been possible to walk that route staying close to the graph the whole time. So my idea was to use that difference to distinguish the two cases: find out whether you can reach one side of an edge from the other without going a long way away from any edge.

Put another way: imagine that each edge of our graph becomes a road with a pedestrian footpath down each side, and we’re interested in where pedestrians can walk if they stick only to the footpaths, and never cross any road.

When multiple edges meet at a vertex, a pedestrian can walk between the footpaths on the near sides of an adjacent pair of edges, but must cross one of the roads if they want to get to any other footpath while staying near that vertex.

A degenerate case of this is that if only one edge meets a vertex, then its two footpaths count as adjacent to each other, so they’re connected.

If a planar graph contains a loop, then the footpaths on one side of the loop are separated from the footpaths on the other side. That’s obvious, because the loop separates the whole plane into two components, and one footpath is on the inside and one on the outside. To get from one footpath to the other, you have to cross the road.

But if a graph doesn’t contain a loop, then all the footpaths around its edges are reachable from each other, because whenever you get to an endpoint with only one edge, you can walk round the end of the road and get to the footpath on the other side. This is also true of non-loop edges in constructions like the ‘dumb-bell’ graph that caused trouble in a previous algorithm.

So the new algorithm is to make a dsf on the segments of footpath on each side of each edge. At each vertex of the graph, you unify pairs of footpaths around the vertex. Then a graph edge is part of a loop iff its two footpaths are not in the same equivalence class.

This algorithm still works for planar graphs – and now it works for a graph on a torus too. Phew, Net was fixed!

What’s wrong with it?

This algorithm works for every puzzle currently in my collection – but I could already see a plausible way it might go wrong in future.

The footpath dsf technique doesn’t depend on a trivial H₁ homology group. But it does depend on the graph being embedded in some kind of surface that is orientable: if you go round any loop and come back to your starting point, you haven’t been ‘flipped over’ so that the surface is now in mirror image.

Two well-known examples of non-orientable surfaces are a Möbius strip, and a Klein bottle. Both of those can be represented as a rectangle with opposite edges identified in particular ways – and it seemed quite plausible that some day I might end up with a puzzle game played on either or both of those surfaces.

And on a non-orientable surface, even this algorithm won’t work. A loop going all the way round a Möbius strip would return to its starting point the other way round, so that the footpaths on the two sides of it would become connected to each other – and so the algorithm would wrongly conclude that those edges weren’t part of any loop.

So this algorithm was fine as an emergency fix, but by now, I was convinced that I wanted to avoid depending on any kind of topological embedding of the graph at all, if I could.

Update, 2024-09-10: a comment on Mastodon corrects me. It wasn’t fine: there’s still a bug in this algorithm, in the torus case. It won’t spot this pair of loops, going round the torus at right angles, and meeting at a point.

You can walk between the footpaths on either side of one of these loops, by turning at right angles and going round one of the footpaths of the other loop. In fact, if you trace round the footpaths of this pair of loops, you find they’re all one single rectangular footpath. So this algorithm would miss both of these loops. Good thing I’ve already moved on to another one!

Tarjan’s bridge-finding algorithm

At this point – much, much later than I probably should have – I stopped trying to solve the problem from scratch myself, and found a solution somebody else had already invented and proved correct.

One of the reasons I hadn’t found this algorithm before is that it’s phrased the opposite way round. A bridge in a graph is an edge which is the only way to get between some pair of vertices. So if you remove the bridge, those vertices become disconnected from each other. On the other hand, a loop edge is precisely one which, if you remove it, doesn’t disconnect any pair of vertices from each other, because there’s still some other route between its two endpoints.

In other words, an edge is a bridge if and only if it is not part of a loop. I was thinking in terms of ‘finding all the loops’, but of course finding all the edges that aren’t part of a loop is just as good – you just invert all the answers once you’re done.

Tarjan’s bridge-finding algorithm starts by finding a spanning forest of the graph – a spanning tree of each of its connected components. That is, we find a subset of the edges which provide a route between any two vertices that the original graph linked, but which don’t contain any loops.

Once we’ve done that, every bridge must be one of the edges of the spanning forest, because a bridge is the only route between some pair of vertices, and whichever vertices those are, the spanning forest contains a path between them – so it must contain the bridge. So any edge not in our spanning forest can’t be a bridge – it must be a loop edge instead.

But that’s the easy part. The hard part is that some of the spanning-forest edges are also loop edges. So the problem is to identify which.

The next step is to root the spanning forest: for each component, choose a vertex (it doesn’t matter which one) to consider to be the root of the tree, so that every edge has an ‘upward’ direction (towards the root) and a ‘downward’ direction (away from it), and the subtree of that edge is all the vertices further ‘down’. Then an edge e is a bridge if and only if nothing in its subtree connects to anything outside that subtree, by any route other than leaving the subtree out of the very top, via e itself.

To determine that, you iterate over these rooted trees labelling each vertex with a number, in a way that makes every subtree into a consecutive interval, say containing numbers from a to b inclusive. Then, for each subtree, you find the smallest and largest labels of any neighbour of anything in the subtree, say u and v. From those bounds, you can immediately tell whether anything in the subtree has a neighbour outside it: if it does, then that neighbour will have a label outside the range [a, b], which will either make the smallest reachable label u smaller than a, or make the largest reachable label v larger than b.

So the edge at the top of the subtree is a bridge if and only if a ≤ u ≤ v ≤ b, and we’re done!

What’s wrong with it?

As far as I know, there’s nothing wrong with this algorithm. But then, I’ve believed that before and been wrong!

That previous time, the problem was that I was depending on an extra property of the graph, namely its planar embedding. Tarjan’s algorithm definitely doesn’t depend on any such thing: it’s a ‘pure’ graph algorithm, requiring nothing except a list of neighbours for each vertex. You could run it on a graph embedded on a torus, or on a Möbius strip, or even something inherently not two-dimensional like a cubic lattice in three-dimensional space, or n-dimensional space if you wanted. It wouldn’t care.

So, at the time of writing this, Tarjan’s algorithm lives in findloop.c in my puzzles’ source tree, and I hope not to discover any more fundamental problems that mean I have to throw it away and start again!

But after all that…

For one of the above algorithms, I didn’t list a definite flaw – only a possible one. I didn’t know for sure that the loop tracing approach wasn’t right, only that I hadn’t proved it was right. I switched from that to the face-dsf approach because the latter was much easier to be certain of.

But, since then, I’ve been thinking about it, and I think that with one tiny modification, the loop tracing algorithm can be proved correct.

The tweak is: when the dsf detects that the edge you’re currently adding is part of a loop, and you trace round the loop to highlight it, limit your trace to only the already processed edges – don’t use any edge that your iteration has yet to come to.

With that tweak, I’m convinced that this algorithm would highlight every edge that’s part of any loop at all. We can prove this by induction, by showing that at every stage in the algorithm that property is true for the set of edges we’ve already processed.

At the start of the algorithm, that’s vacuously true: there aren’t any loops at all in the set of edges we’ve processed, so of course we’ve highlighted all of them. When we find the first loop, it’s almost as easy: the previous edges form an acyclic graph, so if there’s a route between any two vertices at all, then it’s the only route. So the first time the dsf reports an edge as being part of a loop, there’s only one possible loop it can be part of, and the tracing step must find that one.

The hard case is: what happens later on, when we find an edge that has more than one path between its endpoints?

If there’s more than one path in a graph between two vertices u and v, then imagine taking the ‘symmetric difference’ of any two of them, eliminating edges common to both, and keeping only the edges in exactly one of the loops. This symmetric difference is a subgraph in which every vertex has even degree, which means its edges are the union of some set of loops. But, by the inductive hypothesis, that means we’ve already highlighted all of those edges. So the only possible new loop edges we haven’t highlighted yet are the ones that don’t appear in any such symmetric-difference graph – because they’re part of every possible route between u and v. And those edges are bound to be found by our current tracing step.

So if I’d only had that idea 19 years ago, I could have stopped there⁴In fact, going back and looking at my original path-tracing code, it traced round the loop by the maze-solving technique of ‘keeping one hand on the wall’. So the way I actually wrote it, it also depended on having a planar embedding of the graph. To get the same generality as Tarjan’s algorithm, I’d have had to replace that with a general path search like BFS or DFS. But that wouldn’t have been hard.4!

However, Tarjan’s algorithm surely has better performance, because it processes each edge a bounded number of times. This tracing approach might need a full search of the graph every time it traces a loop. So the extra work wasn’t totally a waste – plus, it gave me this story to tell.

Footnotes

With any luck, you should be able to read the footnotes of this article in place, by clicking on the superscript footnote number or the corresponding numbered tab on the right side of the page.

But just in case the CSS didn’t do the right thing, here’s the text of all the footnotes again:

1. I think, pedantically speaking, ‘disjoint-set forest’ refers to a specific technique for solving the problem of incremental equivalence tracking, whereas the other names without ‘forest’ in them refer to the problem itself without committing to a particular solution – in the same way that the Fast Fourier Transform is one particular algorithm for implementing the abstract mathematical operator called the Discrete Fourier Transform. In both cases, the distinction is often ignored, because the well-known algorithm is such a good way to solve the problem that nobody ever really wants to use a different one.

2. Since then, Loopy has been enhanced further, so that not all the tilings are even periodic. You can also play Loopy on a fragment of Penrose tiling, or the Hat and Spectre tilings discovered in 2023. I have a whole series of other articles about that!

3. In one sense, Net doesn’t exactly need loop highlighting. In Net, the solution to the puzzle is an acyclic graph connecting all the squares of the grid. And if you manage to make any graph at all that connects all the squares, it can’t have a loop, because a graph on that many vertices with a loop would have the wrong number of edges, and the Net user interface doesn’t let you change how many edges exist. So if you do make a loop, you’ll find you can’t light up all the squares of the grid, so it will at least be obvious why the game doesn’t think you’ve won. But that doesn’t give you any help finding the loop – all it proves is that there must be one somewhere. So highlighting it is still useful for that.

4. In fact, going back and looking at my original path-tracing code, it traced round the loop by the maze-solving technique of ‘keeping one hand on the wall’. So the way I actually wrote it, it also depended on having a planar embedding of the graph. To get the same generality as Tarjan’s algorithm, I’d have had to replace that with a general path search like BFS or DFS. But that wouldn’t have been hard.