JBotSim 1.0-beta has been released with some API changes. All examples have been updated accordingly. Please make sure you are using version 1.0 beta.

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).