Three phases per round, over the agents standing on each node. Unsettled agents fan out one per port to look at a neighbour, come back carrying one bit — does it have a settled agent — and then one of them settles where nobody has while the rest move on together through a port a probe reported empty. When every port has been tried the group backtracks through the settled agent's parent port, so the walk is a DFS whose tree is held by the settled agents.

It is meant for agents that all start on one node: from there, with no more agents than nodes, it always finishes. The code also accepts agents on several start nodes (as the Python reference did), but then a group can get stuck for good — see the notes.

canonicalize_ports is a compatibility decision rather than an algorithmic one: the Python reference replaced any supplied local port labels with canonical sorted-neighbour ones, so this port does too. It means Drop-and-Freeze ignores the port assignment the experiment asked for.

Also a DFS, but settled agents help. A settled agent whose node can spare it vacates and travels with the group as a scout, so more agents share the probing of a node's ports. When nobody is left unsettled, the scouts walk the tree depth first and each drops back onto its own node when the group reaches it, so the run ends with one settled agent on each occupied node.

Like the Python reference it is rooted: placements on several start nodes are not supported (a test records the reference's failure on them).

DFS_P1Tree from Pattanayak, Kshemkalyani, Kumar, Molla and Sharma, Optimal Dispersion Under Asynchrony. A DFS that builds a port-one tree: in a finished tree every vertex has an incident tree edge carrying port 1 at one of its ends. Among the ports probed so far, edges are preferred tp1 > t11 ~ t1q > tpq; a node that would be left without a port-1 tree edge is parked as partiallyVisited until its port-1 neighbour comes to claim it.

Two details carry the O(k) bound, and losing either makes the cost scale with the graph instead of with the agents:

• neighbourhood_search stops at the first batch that finds somewhere to go. Remark 1 bounds the search by the agent count, not the degree: at most k nodes are ever occupied, so when the degree allows, an empty neighbour turns up within the first k-1 probed ports at the root and k-2 elsewhere.
• traverse stops at dispersion. Section 5: "the process continues until no unsettled agents remain". The tree at that moment need not yet be a P1Tree — a parked node may still hold a tpq parent edge — and that is fine, because dispersion is the goal.

RootedDisp from Sudo, Shibata, Nakamura, Kim and Masuzawa, Near-linear Time Dispersion of Mobile Agents, Section 3 and Algorithm 1: the rooted HEO-DFS. The agent with the largest ID leads a depth-first search, and the smallest-ID explorer settles at each node it reaches. Every box that moves agents is exactly one synchronous step, committed through apply_move_intents; settling takes none. rooted-disp.md has the time model, the decisions taken where Algorithm 1 leaves a choice, and two worked traces.

What makes the search fast is probe_pass. Every agent at the node except its settler takes one port; a settler found at home comes back as a helper and probes in the next pass too, so the probers double until one finds an unsettled neighbour: O(log τ) passes per probe and O(k log τ) steps in all. probe resets next and checked on every call, so no cursor survives from an earlier visit.