Rotor Router Model
Welcome to this page. We'd like to show off a mathematical
model (the Rotor Router Model) using a java applet.
The model involves a bug (represented by an empty black and
while square) moving along a graph (represented by boxes
linked by arrows).
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
No Double Buffer:
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
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
- 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
- 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
- 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
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
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.
James Propp, “Random walk and random aggregation,
derandomized” (Talk given at Microsoft Research).
- James Propp, “Rotor-Router Automata” (An early
write-up of derandomized aggregation).
- James Propp, “Rotor Router Walk” (Email-log of some
messages sent out about derandomized walk).
- Lionel Levine, “The Rotor-Router Model” (undergraduate
- Lionel Levine, “The Rotor-Router Model” (slides from a
- Lionel Levine and Adam Kampff. “Rotor-router aggregation
blob after 270,000 particles have aggregated” (Image).
- Lionel Levine and Adam Kampff. “Two close-ups of that same
- Ed Pegg. “The rotor-router blob after 750,000 particles
have aggregated” (Image).
- Ander Holroyd. “The rotor-router blob after 1,000,000
particles have aggregated” (Image).
- Vishal Sanwalani. “The state achieved by the abelian
sandpile model when sixty thousand grains have been added”
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:
No Double Buffer:
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.
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.
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
Give us feedback! Send mail to
«hal at ups dot physics dot wisc dot edu»
«propp at math dot wisc dot edu».
to Hal Canary's Math Applets