Rotor Router Model

Introduction

Welcome to this page. We'd like to show off a mathematical model (the Rotor Router Model) using a java applet.

[a bug] The model involves a bug (represented by an empty black and while square) moving along a graph (represented by boxes linked by arrows).

[a rotor] Each box on the graph contains a rotor that can be in different states. These states are represented by colors and arrows. When a bug visits a box, that box's state will change.

To get started, jump to the Applet and click the step button repeatedly and watch how the bug moves around the graph.

If you are confused, try our walkthrough.

If your browser window is too small, try this.

small | medium | large.
No Double Buffer: small | medium | large.

The Rotor Router Applet

A description of the Algorithm

The Rotor Router Model is composed of a directed graph (infinite or finite) with a rotor attached to each vertex. The rotor at a given vertex is a pointer to one of the edges that leaves that vertex. In the model, a bug traverses the graph along the edges, following the direction of the rotor at each vertex.

The twist is that each time a bug visits a vertex, she rotates the rotor so that it points to the next edge, before following the rotor.

This is a deterministic system.

This model has two variations: the walk mode and the aggregation mode.

In the walk mode, the bug will traverse the graph until she encounters a sink. A sink is a vertex with no edges leaving it, If there is a sink in the system, it has no rotor on it. If a bug visits a sink, she disappears from the system. After that happens, we put a new bug on some specified vertex, called the source.

In the aggregation mode, all vertices start out empty; once a bug hits an empty vertex, the vertex is filled and it gets a normal rotor on it. Then the bug returns to the source. For this mode to be interesting, we need a graph with an infinite number of empty vertices.

Graphs and Modes

Instructions

To switch between graphs, choose one from the drop-down menu and hit “Reset”.

Pressing the Step button increments the system by one step. The bug alternates between moving to the next vertex and moving a rotor each step.

The Stage button increments the system until a bug hits a sink (or, in the case of aggregation, a new site becomes occupied). A stage is made of many steps.

The Reset button resets the system to the initial state and zeros out any counters.

The Pause/Unpause button controls the automated iterations. If the applet is unpaused, the system will increment by steps or stages, according to the Skip Each variable.

References

  1. James Propp, “Random walk and random aggregation, derandomized” (Talk given at Microsoft Research). http://murl.microsoft.com/LectureDetails.asp?1050. video: http://tinyurl.com/2vmmx
  2. James Propp, “Rotor-Router Automata” (An early write-up of derandomized aggregation). http://www.math.wisc.edu/~propp/hidden/rotor
  3. James Propp, “Rotor Router Walk” (Email-log of some messages sent out about derandomized walk). http://www.math.wisc.edu/~propp/hidden/test/rotorwalk.to
  4. Lionel Levine, “The Rotor-Router Model” (undergraduate thesis). http://www.math.berkeley.edu/~levine/rotorrouter.pdf
  5. Lionel Levine, “The Rotor-Router Model” (slides from a talk). http://www.math.berkeley.edu/~levine/slides/
  6. Lionel Levine and Adam Kampff. “Rotor-router aggregation blob after 270,000 particles have aggregated” (Image). http://www.math.berkeley.edu/~levine/private/rotorrouter/bigblob.bmp
  7. Lionel Levine and Adam Kampff. “Two close-ups of that same picture” (Image). http://www.math.berkeley.edu/~levine/private/rotorrouter/closeup.bmp
  8. Ed Pegg. “The rotor-router blob after 750,000 particles have aggregated” (Image). http://www.math.wisc.edu/~propp/proppcircle.gif
  9. Ander Holroyd. “The rotor-router blob after 1,000,000 particles have aggregated” (Image). http://www.math.wisc.edu/~propp/million.gif
  10. Vishal Sanwalani. “The state achieved by the abelian sandpile model when sixty thousand grains have been added” (Image). http://www.math.wisc.edu/~propp/hidden/501.gif

Errata.

Known Bugs

There is a display bug with Apple JVM 1.4, used by current versions of the Safari Browser. If you experince this issue, use the non-double buffered version of this applet:

Normal: small | medium | large.
No Double Buffer: small | medium | large.

There are built-in limits to how big the 2-D systems can become. When they hit that limit, they will stop, even if the stage is not done. For more information, read the code.

System Requirements

The applet as designed with Java 1.1 in mind, so all browsers back to 1998 should be supported. But we cannot make any guarantees. You may want to maximize your browser window if you want to see the whole applet.

Credits

This work is Copyright (C) 2003-2004 by Hal Canary and the University of Wisconsin-Madison.

Hal wrote most of the code while working for Professor Jim Propp, who is studying the Rotor Router System. Francis Wong has assisted.

This work was supported by the University of Wisconsin.

This work comes with ABSOLUTELY NO WARRANTY. This program is free software; you can redistribute it and/or modify it under the terms of version 2 of the GNU General Public License as published by the Free Software Foundation.

Source: tarball and zipfile. Programmer's documentation. Readme file.

Valid html?

Give us feedback! Send mail to Hal Canary «hal at ups dot physics dot wisc dot edu» and Jim Propp «propp at math dot wisc dot edu».

Back to Hal Canary's Math Applets