|Audrey St. John||
2D Pebble Game Demo
This applet demonstrates the (2,3)-pebble game introduced by Jacobs and Hendrickson in 1997 and
used to solve the decision, spanning, extraction,
optimization, components, redundancy, and Henneberg problems for
2D bar-and-joint rigidity.
You may also be interested in the pebble game for
3D body-and-bar/hinge rigidity.
- Use the standard play controls at the top to play the pebble game (animate, step individually or "fast forward" to the end);
this will cause edges to be inserted in arbitrary order.
- To insert edges one at a time in a specific order, do not press the play controls after initializing the
graph; instead, simply click the edges in the left pane as you want them inserted. The play controls will become available
once the first edge has been chosen.
- Use the View menu to change the moves displayed for the game:
- Show all moves will show every move the game makes, including pebble searches and edge reversals.
- Show only one move per edge iteration will only show the outcome of each edge consideration (rejection or acceptance).
- Show only final configuration will only show the final outcome of the game.
- To load a predefined graph, select from Graphs menu
- To create a graph
- Go to the Create graph tab
- Add vertices by right clicking and selecting "Insert"
- Add edges by clicking first vertex (hover over center until you see a hand cursor, then click), then pull to second vertex
- Adjust radius by selecting vertex and pulling bounding box
- When finished, click "Set graph" button at the bottom
- Return to Play pebble game tab to run pebble game algorithm.
To run the demo locally on your machine (allowing the additional feature of file saving/loading), simply download
pebblegame.jar and double-click it to run.
Brief overview of Jacobs and Hendrickson's 2D pebble game
Note that, for simplicity, this description is an abbreviated version of the basic 2D pebble game;
additional features, such as maintaining components, result in a more powerful
and efficient algorithm.
Input: A graph G = (V;E), possibly with loops and multiple edges.
Output: Rigid or flexible.
Setup: Maintain, as an additional data structure, a directed graph D, on
which the game is played. Initialize D to be the empty graph on V , and
place k pebbles on each vertex.
- Pebbles. No more than 2 pebbles may be present on a vertex at any
- Edge acceptance. An edge between two vertices u and v is accepted
for insertion in D when a total of 4 pebbles are present
on the two endpoints u and v.
Algorithm: The edges of G are considered in an arbitrary order and the
edge acceptance condition is checked. Let e = uv be the current edge. If
the acceptance condition is not met for edge e, the algorithm attempts to
collect the required number of pebbles on its two endpoints u and v using
the following strategy: (a) Mark vertices u and v as visited for the depth-
first-search algorithm (so they will not be searched, and their pebbles are
protected from being moved); (b) Perform pebble collection using depth-
first-search. If one fails to collect 4 pebbles, the edge e is rejected,
otherwise it is accepted. An accepted edge is immediately inserted into D
as specified by the edge insertion move.
- Pebble collection. An additional pebble may be collected on a vertex
w by searching the directed graph D, e.g., via depth-first search. If a
pebble is found, the edges along the directed path leading to it are
reversed and the pebble is moved along the path until it reaches w.
- Edge insertion. If an edge between two vertices u and v is accepted,
then at least one of the vertices (say, u) contains a pebble. The edge
is inserted in D as a directed edge from u to v and a pebble is removed
The algorithm ends when all the edges have been processed. If exactly 3
pebbles remain in the game at the end, the input graph G is rigid; if more than
3 pebbles remain, the input graph G is flexible.