Audrey St. John |
## 2D Pebble Game DemoThis 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.
- Go to the
## Advanced usageTo run the demo locally on your machine (allowing theadditional feature of file saving/loading), simply download
pebblegame.jar and double-click it to run.
## Brief overview of Jacobs and Hendrickson's 2D pebble gameNote 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:
**Pebbles.**No more than 2 pebbles may be present on a vertex at any time.**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:
**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 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. |