Hamiltonian path, animated

CSS animations can be quite powerful when we want to explain things visually. They can be used not only to draw attention to a subject, but also to show the steps involved in the application of a certain method. Images can often show only the end result, but not how it has been reached. We could use multiple images with arrows between them to show a process, but this may require many images, wasting valuable screen space. An image that highlights the Hamiltonian path in a graph (a path which visits each vertex only once) doesn’t say anything about the start vertex, the direction of movement and how the end vertex is reached. Hence, the path isn’t illustrated by a movement along it.

Finding whether a Hamiltonian path exists in a graph is an NP-complete problem, but one that has potential applications in many areas. In the presence of too many vertices, it is often not clear how we should start. If we can find a simple path, we could animate it and show a possible solution that will be easy to understand. I tried to apply this to the figure seen on Wikipedia and the animation can be seen here.

The result is partially computed, partially adjusted for visual appearance. Initially, I tried to use SASS for this task, since this would give best results (I thought so at least), but at the end it didn’t suit my needs. I didn’t like the CSS it generated, the limited mathematical capabilities and the hard to decipher compilation errors. Being unable to subtract 1 from a variable within a for-loop kind of defeated me. Sometimes, a multi-line comment couldn’t disable a variable defined in it, which resulted in compilation errors. Additionally, constant switching to one additional tool further slowed me down. With using PHP, I saw that some calculations produced results with a need of rounding and it became clear to me that the result won’t be neither beautiful nor pixel-perfect if I wanted to complete this in a reasonable amount of time. The size of the vertices and edges themselves may have also contributed to this. So I replaced some computed coordinates with manual ones.

I hope that this is a good use of CSS animations, when a set of steps or instructions needs to be communicated.