Matroidal Rigidity

This module provides algorithms related to the generic rigidity matroid.

pyrigi.graph._rigidity.matroidal.Rd_closure(graph, dim=2, algorithm='default')

Return the set of edges given by closure in the generic dim-rigidity matroid.

Definitions

• Rd-closure

• Generic rigidity matroid

Parameters:

• graph (Graph)

• dim (int) – Dimension of the rigidity matroid.

• algorithm (str) –

  If "graphic" (only if dim=1), then the closure is computed using connected components.

  If "pebble" (only if dim=2), then pebble games are used (see notes below and Algorithm 2).

  If "randomized", then adding non-edges is tested one by one on a random framework.

  If "default", then "graphic" is used for dim=1, "pebble" for dim=2 and "randomized" for dim>=3.

Return type:

list[Edge]

Examples

>>> G = Graph([(0,1),(0,2),(3,4)])
>>> Rd_closure(G, dim=1)
[[0, 1], [0, 2], [1, 2], [3, 4]]

Notes

The pebble game algorithm proceeds as follows: Iterate through the vertex pairs of each connected component and check if there exists a rigid component containing both. This can be done by trying to add a new edge between the vertices. If there is such a rigid component, we can add every vertex pair from there: they are certainly within a rigid component.

Suggested Improvements

prob parameter for the randomized algorithm

pyrigi.graph._rigidity.matroidal.is_Rd_circuit(graph, dim=2, algorithm='default', use_precomputed_pebble_digraph=False)

Return whether the edge set is a circuit in the generic dim-rigidity matroid.

Definitions

• Circuit

• Generic rigidity matroid

Parameters:

• graph (Graph)

• dim (int) – Dimension of the rigidity matroid.

• algorithm (str) –

  If "graphic" (only if dim=1), it is checked whether the graph is a union of cycles.

  If "sparsity" (only if dim=2), a (2,3)-sparse spanning subgraph is computed (using pebble games) and checked whether it misses only a single edge whose fundamental circuit is the whole graph.

  If "randomized", it is checked using randomized is_Rd_independent() whether removing every single edge from the graph results in an Rd-independent graph.

  If "default", then "graphic" is used for dim=1, "sparsity" for dim=2, and "randomized" for dim>=3.

• use_precomputed_pebble_digraph (bool) – Only relevant if algorithm="sparsity". If True, the pebble digraph present in the cache is used. If False, recompute the pebble digraph. Use True only if you are certain that the pebble game digraph is consistent with the graph.

Return type:

bool

Examples

>>> from pyrigi import graphDB
>>> G = graphDB.K33plusEdge()
>>> is_Rd_circuit(G)
True
>>> G.add_edge(1,2)
>>> is_Rd_circuit(G)
False

Suggested Improvements

prob parameter for the randomized algorithm

pyrigi.graph._rigidity.matroidal.is_Rd_closed(graph, dim=2, algorithm='default')

Return whether the edge set is closed in the generic dim-rigidity matroid.

Definitions

• Rd-closed

• Generic rigidity matroid

Parameters:

• graph (Graph)

• dim (int) – Dimension of the rigidity matroid.

• algorithm (str) – See Rd_closure() for the options.

Return type:

bool

Examples

>>> G = Graph([(0,1),(1,2),(0,2),(3,4)])
>>> is_Rd_closed(G, dim=1)
True

pyrigi.graph._rigidity.matroidal.is_Rd_dependent(graph, dim=2, algorithm='default', use_precomputed_pebble_digraph=False)

Return whether the edge set is dependent in the generic dim-rigidity matroid.

See is_Rd_independent() for the possible parameters.

Return type:

bool

Parameters:

• graph (Graph)

• dim (int)

• algorithm (str)

• use_precomputed_pebble_digraph (bool)

Definitions

• Dependence

• Generic rigidity matroid

Examples

>>> from pyrigi import graphDB
>>> G = graphDB.K33plusEdge()
>>> is_Rd_dependent(G)
True

Notes

See is_independent() for details.

pyrigi.graph._rigidity.matroidal.is_Rd_independent(graph, dim=2, algorithm='default', use_precomputed_pebble_digraph=False)

Return whether the edge set is independent in the generic dim-rigidity matroid.

Definitions

• Independence

• Generic rigidity matroid

Parameters:

• graph (Graph)

• dim (int) – Dimension of the rigidity matroid.

• algorithm (str) –

  If "graphic" (only if dim=1), then the (non-)presence of cycles is checked.

  If "sparsity" (only if dim=2), then (2,3)-sparsity is checked using the pebble game algorithm.

  If "randomized", the following check is performed on a random framework: a set of edges forms an independent set in the rigidity matroid if and only if it has no self-stress, i.e., there are no linear relations between the rows of the rigidity matrix.

  If "default", then "graphic" is used for dim=1, "sparsity" for dim=2, and "randomized" for dim>=3.

• use_precomputed_pebble_digraph (bool) – Only relevant if algorithm="sparsity". If True, the pebble digraph present in the cache is used. If False, recompute the pebble digraph. Use True only if you are certain that the pebble game digraph is consistent with the graph.

Return type:

bool

Examples

>>> G = Graph([(0,1), (1,2), (2,3), (3,0)])
>>> is_Rd_independent(G)
True

Suggested Improvements

prob parameter for the randomized algorithm.