Shift Clock

I'm really happy with how this experiment turned out. It's a clock that spells out the time with squares, and then shifts those squares into their new positions whenever the time changes. It draws the time text into a hidden tiny canvas element at each minute, then uses getImageData to extract the individual pixels. Any pixel that has been drawn with an alpha > 0.5 is set as a destination for the next squares animation. The animations themselves are performed using d3.js.

The picture above is of the black-on-white version. There is also a grey-on-black version, if you prefer that color scheme.

In order to make the transitions look the best and happen the fastest, I wanted to pair source squares and destinations in the way that minimized the maximum distance any one square would travel. I first tried using a greedy algorithm that simply took the farthest-away source point and paired it with the closest destination, then removed that destination. (Essentially, for each source point, I sorted all destinations by distance. I then sorted all source points by minimum distance to any destination, and took the one that was farthest from its closest destination.) This algorithm, however, tended to choose destinations that forced the leftover sources to travel even longer distances, making it pretty ineffective.

As it turns out, the problem I wanted to solve has a name, and has been researched by others. It is called the Linear Bottleneck Assignment Problem and is part of a family of related problems known as assignment problems. Wikipedia describes it as follows:

There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task in such a way that the maximum cost among the individual assignments is minimized.

In this case, the "agents" are the source points, the "tasks" are the destinations, and the cost of an "agent-task assignment" is the taxicab distance between that source and destination.

There are a few different solutions to this problem. One of the simplest, which I chose to implement, is a thresholding binary-search solution:

1. Set the lower bound lbound to the smallest edge length and the upper bound ubound to the largest edge length.
2. While there are any edge lengths between ubound and lbound (not including lenghts equal to them):
   1. Set med to the median of all edge lengths between ubound and lbound.
   2. Find the maximum matching using only edges not longer than med (med is the threshold)
   3. If the maximum matching is perfect (if it successfully connects all sources to all destinations), set ubound to med (because we know every threshold >= med must result in a perfect match)
   4. Otherwise, set lbound to med (because we know every threshold <=med does not result in a perfect match)
3. At this point, usually ubound is the best threshold. If we have not tested lbound already (which can only happen if lbound is still the smallest edge length), however, we need to test it:
   1. Find the maximum matching using only edges not longer than lbound (lbound is the threshold)
   2. If the maximum matching is perfect, set ubound to lbound.
4. ubound is the final threshold. Return the maximum matching using using only edges not longer than ubound.

This solution essentially repeatedly divides the set of possible thresholds in half, ignoring the half that is guaranteed not to contain the optimal solution, until it narrows the set to only two possible edge lengths.

In order to implement this, however, we have to have a method for finding the maximum matching with a given threshold. To do this, I used the Hopcroft–Karp algorithm. The Wikipedia explanation is somewhat hard to understand, so I will explain it slightly differently (but with the equivalent result).

First, I will describe an augmenting path. From Wikipedia:

An alternating path is a path in which the edges belong alternatively to the matching and not to the matching.

and

An augmenting path is an alternating path that starts from and ends on free (unmatched) vertices.

Here's an example: Let A, B, and C be sources, and D, E, and F be destinations, such that:

• A can connect to D and E
• B can connect to D and F
• C can connect to E only
• A and E are already matched
• B and D are matched

We want a perfect matching, but C and F are not matched, and in this case we can't match them directly. We can, however, generate an augmenting path. If we write the connections out like this:

E-A D-B

we can then insert C and F like this:

C E-A D-B F

This is our augmenting path, and it is important because we can swap the connections to form a better matching:

C-E A-D B-F

The identification, construction, and swapping of augmenting paths is at the core of the Hopcroft-Karp algorithm.

1. Create a connections matrix, such that conn[i][j] is true if and only if source i and destination j have cost <= threshold. (This is not technically part of the Hopcroft-Karp algorithm, but is necessary to use it with thresholding.) Then, until a maximum matching has been found:
2. Collect all non-matched sources into sourcequeue, and label them all 1. Set nlevel to 2.
3. For each source in sourcequeue, find all destinations reachable from it using the conn matrix. Label those destinations with the value of nlevel, and add them into destqueue. Pop the sources off of sourcequeue after they are processed.
4. If there are no destinations in destqueue, STOP. This is the maximum matching.
5. If any of the destinations in destqueue are not matched, skip to step 10.
6. Increment nlevel.
7. For each dest in destqueue, add its currently-matched source to sourcequeue, and label it nlevel. Pop the dests off of destqueue after they are processed.
8. Increment nlevel.
9. Repeat from step 3.
10. At this point, we have identified some number of unmatched destinations that can be paired with some of the unmatched sources by using an alternating path. (We start on an unmatched source, alternately find already-matched destinations and their already-matched sources, and end on an unmatched destination.) We will now try to swap in as many as possible.
11. For each unmatched dest in destqueue:
    1. Find some source connected to this dest with label equal to its label minus one. (If there are none, STOP.)
    2. If this source is unmatched, we have an augmenting path! Swap the connections, delete all the labels along this path, and continue with the next dest in destqueue.
    3. Otherwise, find it's matched destination. Recursively run these three steps again on that destination. If they succeed, continue. If they fail, find the next source connected to this dest, repeat from 1 on that source.
    4. Once all possible sources have been tried without a solution, STOP.
12. If there are any more unmatched sources, repeat from step 2.

The Hopcroft-Karp algorithm and the threshold algorithm, used together, allow me to find the pairing of sources and destinations that can be reached in the least amount of time. It runs quite fast given that it is running in the browser. Most of the time, you can barely tell that it is processing. (Some of the larger animations take about a second, though. I might be able to optimize it more, but the delay doesn't bother me much.)

One thing I had to watch out for is the way that Google Chrome's V8 engine optimizes code. At one point, my threshold algorithm got stuck in an infinite loop because of a problem with how I calculated the median. Of course, Google Chrome did not know this was not intended behavior, and thus aggressively optimized the code for the loop. This meant that when I tried to add breakpoints and inspect variable values, it behaved erratically and did not allow me to debug effectively. My guess is that it had compiled that loop into machine code, and then couldn't translate the machine code's execution state back into an interactive debugger view and read-eval-print loop. Interestingly, adding calls to console.log() seemed to prevent this aggressive compilation.

In case the LBAP is relevant to anyone else's Javascript work, I've put the code for my implementation on GitHub, licensed under the MIT license.

---

Details on how to implement the thresholding solution taken from page 174 of Assignment Problems, by Rainer Burkard, Mauro Dell'Amico, and Silvano Martello.

Details on the Hopcroft–Karp algorithm taken from Wikipedia.