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.

Usage

  • 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.

Advanced usage

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.
Rules:
  1. Pebbles. No more than 2 pebbles may be present on a vertex at any time.
  2. 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.
Allowable moves:
  1. 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.
  2. 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 from u.
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.

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.