Spanning Forest Algorithm

This example implements a spanning forest algorithm based on the circulation of tokens (see the video).

The algorithm relies on a perpetual alternation of topology-induced splittings and computation-induced mergings of a forest of trees. Each tree in the forest hosts exactly one token (seen as a root) that performs a random walk inside the tree, switching the parent-child relationships as it circulates. When two tokens are located at the two endpoints of a same edge, their trees are merged and one token is eliminated. When an edge that belongs to a tree disappears, the child endpoint regenerates a new token instantly.

More details about the algorithm can be found in this article (or the author version if you don't have access). The version in the video corresponds to the graph-level version described in Section 1.2, also covered in this tutorial (FR).