Spanning forest algorithm based on token circulation

This example implements a spanning forest algorithm based on the circulation of tokens.

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 (also called root) that performs a random walk inside the tree, switching parent-child relationships as it crosses edges. When two tokens are located on both sides of a same edge, their trees are merged upon this edge and one token disappears. Whenever an edge that belongs to a tree disappears, its child endpoint regenerates a new token instantly.

The demo can be launched in the top-right corner of this page.

Details can be found in this paper (graph-based) or this paper (synchronous message passing).