Rotor Router Model, version 1.0

Introduction

Welcome to this page. We'd like to show off a mathematical model (the Rotor Router Model) using a java applet. If you haven't installed Java on your computer, you can get it here. Please restart your browser after installation.

	The model involves a bug moving along a directed graph. The nodes of the directed graph are represented by boxes, and the arcs between nodes are represented by arrows (sometimes not shown). The bug itself is represented by a hollow square; a hollow square doesn't look much like a bug, but we chose this symbol because it enables you to see some information that's shown inside the box occupied by the bug.

	Each box in the graph contains a rotor that can be in different states. These states are represented by colors and arrows. (The color of a box conveys the same information as the arrow; but as you use the applet in a variety of modes you'll see why this redundancy is helpful.) When a bug arrives at a box, the state of that box changes: the arrow rotates to point in a new direction, and the color changes in a corresponding fashion. Then the bug leaves the box, traveling in the direction indicated by the (new) state of the arrow in that box.

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.

When you start to use the applet, you may find that it is the wrong size for the window. If changing the size of your window doesn't solve the problem, try changing the size of the applet. Allowed sizes are small (default), medium, and large.

If you cannot see the applet, please try the small, medium, or large non-double-buffered version. For more information on this issue, please refer to the Extras section.

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

1-D Walk: This infinite graph has a vertex for each nonnegative integer, and for each vertex n=2,3,4,5,... there is a (directed) edge from n to n+1 and from n to n-2. Vertices 0 and 1 are sinks; vertex 2 is the source. The ratio of the two sink counts approaches the golden ratio. Models of this kind have been studied by Holroyd and Propp. More information about 1-D Walk.
1-D Aggregation: Aggregation is another process that can be modeled using rotors. Here the underlying graph has a vertex for each non-negative integer, and for each vertex n there is an edge from n to n-1 and from n to n+1. In the aggregation scenario, all vertices start out empty; once a bug hits an empty vertex, the vertex is filled and it gets a normal rotor on it. If the newly occupied vertex is on the left side of 0, the vertex immediately to its left becomes occupied as well. During each stage, a bug is added to the system at 0, and it walks until it results in either one new occupied site (on the right) or two new occupied sites (on the left). The ratio between the number of occupied sites to the left of 0 and the number of occupied sites to the right of 0 approaches the square root of 2. Models of this kind have been studied by Levine and Propp. More information about 1-D Aggregation.
Walk on finite graph A
Walk on finite graph B
Walk on finite graph C
2-D Walk on a square grid. Each vertex is represented by a square and is connected to each of its four closest neighbors. There is a source at (0,0) (shown as a square with a white border) and a sink at (1,1) (shown as a solid black square). In each stage, the bug starts at the source, and takes a walk following the instructions given by successive rotors, until it either arrives at the sink (at which point it hops back to the source) or it arrives at the source; either way, the stage is over, and a new stage start. The applet keeps track of how many times the bug arrives at the source (by walking from one of the four cells adjoining the source, not by hopping from the sink) and how many times the bug arrives on the sink. The location of the bug is indicated by a square superimposed with the cell occupied by the bug. More information about 2-D Walk.
2-D Aggregation: Similar to 1-D Aggregation, but on a 2-D square grid. Each vertex is represented by a square. In the aggregation scenario, all vertices start out empty; once a bug hits an empty vertex, the vertex is filled and it gets a normal rotor on it. Each bug fills exactly one vertex when it reaches an empty vertex. It is interesting that the shape that is created is very round. In fact, if you compare the circle centered at the origin that goes through the filled vertex farthest from the origin and the smallest circle centered at the origin that goes through the empty vertex closest to the origin, the difference is very small. More information about 2-D Aggregation.

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

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
James Propp, “Rotor-Router Automata” (An early write-up of derandomized aggregation). http://www.math.wisc.edu/~propp/hidden/rotor
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
Lionel Levine, “The Rotor-Router Model” (undergraduate thesis). http://www.math.berkeley.edu/~levine/rotorrouter.pdf
Lionel Levine, “The Rotor-Router Model” (slides from a talk). http://www.math.berkeley.edu/~levine/slides/
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
Lionel Levine and Adam Kampff. “Two close-ups of that same picture” (Image). http://www.math.berkeley.edu/~levine/private/rotorrouter/closeup.bmp
Ed Pegg. “The rotor-router blob after 750,000 particles have aggregated” (Image). http://www.math.wisc.edu/~propp/proppcircle.gif
Ander Holroyd. “The rotor-router blob after 1,000,000 particles have aggregated” (Image). http://www.math.wisc.edu/~propp/million.gif
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

Extras

Known Bugs

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

Normal: small | medium | large.
No Double Buffer: small | medium | large.
You may notice another display bug when switching between the applet and other applications on Mac machines. We recommend staying on this page until you are done.
Because different browsers render the applet differently, in some cases the pull-down box after the "Skip Each:" label may get pushed down to the next row. You can still choose the step level from the pull-down box.
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 was written by Hal Canary and Francis Wong. It was supported by the University of Wisconsin-Madison.

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», Francis Wong «yutai at cae dot wisc dot edu, and Jim Propp «propp at math dot wisc dot edu».