Redundant Rigidity¶

This module provides algorithms related to redundant rigidity.

pyrigi.graph._rigidity.redundant.is_k_redundantly_rigid(graph, k, dim=2, algorithm='default', prob=0.0001)[source]¶

Return whether the graph is k-redundantly dim-rigid.

Preliminary checks from Theorem 6, Theorem 5, Theorem 14, Theorem 15, Theorem 16 and Theorem 17 are used.

Definitions

k-redundant dim-rigidity

Parameters:

graph (Graph)
k (int) – Level of redundancy.
dim (int) – Dimension.
algorithm (str) – See is_rigid() for the possible algorithms used for checking rigidity in this function.
prob (float) –
A bound on the probability for false negatives of the rigidity testing when algorithm="randomized".

Warning: this is not the probability of wrong results in this function, but is just passed on to rigidity testing.

Return type:

bool

Examples

>>> G = Graph([[0, 1], [0, 2], [0, 3], [0, 5], [1, 2],
...            [1, 4], [2, 5], [3, 4], [3, 5], [4, 5]])
>>> is_k_redundantly_rigid(G, 1, 2)
True
>>> G = Graph([[0, 3], [0, 4], [1, 2], [1, 3], [1, 4],
...            [2, 3], [2, 4], [3, 4]])
>>> is_k_redundantly_rigid(G, 1, 2)
False
>>> G = Graph([[0, 1], [0, 2], [0, 3], [0, 4], [1, 2],
...            [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]])
>>> is_k_redundantly_rigid(G, 2, 2)
True

Suggested Improvements

Improve with pebble games.

pyrigi.graph._rigidity.redundant.is_k_vertex_redundantly_rigid(graph, k, dim=2, algorithm='default', prob=0.0001)[source]¶

Return whether the graph is k-vertex redundantly dim-rigid.

Preliminary checks from Theorem 21, Theorem 22, Theorem 23, Theorem 24, Theorem 25, Theorem 26 and Theorem 27 are used.

Definitions

k-vertex redundant dim-rigidity

Parameters:

graph (Graph)
k (int) – level of redundancy
dim (int) – dimension
algorithm (str) – See is_rigid() for the possible algorithms used for checking rigidity in this function.
prob (float) –
bound on the probability for false negatives of the rigidity testing when algorithm="randomized".

Warning: this is not the probability of wrong results in this function but is just passed on to rigidity testing.

Return type:

bool

Examples

>>> G = Graph([[0, 2], [0, 3], [0, 4], [1, 2], [1, 3],
...            [1, 4], [2, 3], [2, 4], [3, 4]])
>>> is_k_vertex_redundantly_rigid(G, 1, 2)
True
>>> is_k_vertex_redundantly_rigid(G, 2, 2)
False
>>> G = Graph([[0, 2], [0, 3], [0, 4], [1, 2], [1, 3], [1, 4], [2, 4], [3, 4]])
>>> is_k_vertex_redundantly_rigid(G, 1, 2)
False

pyrigi.graph._rigidity.redundant.is_min_k_redundantly_rigid(graph, k, dim=2, algorithm='default', prob=0.0001)[source]¶

Return whether the graph is minimally k-redundantly dim-rigid.

Preliminary checks from Theorem 18 are used.

Definitions

Minimal k-redundant dim-rigidity

Parameters:

graph (Graph)
k (int) – Level of redundancy.
dim (int) – Dimension.
algorithm (str) – See is_rigid() for the possible algorithms used for checking rigidity in this function.
prob (float) –
A bound on the probability for false negatives of the rigidity testing when algorithm="randomized".

Warning: this is not the probability of wrong results in this function, but is just passed on to rigidity testing.

Return type:

bool

Examples

>>> G = Graph([[0, 2], [0, 3], [0, 4], [1, 2],
...            [1, 3], [1, 4], [2, 4], [3, 4]])
>>> is_min_k_redundantly_rigid(G, 1, 2)
True
>>> is_min_k_redundantly_rigid(G, 2, 2)
False
>>> G = Graph([[0, 2], [0, 3], [0, 4], [1, 2], [1, 3],
...            [1, 4], [2, 3], [2, 4], [3, 4]])
>>> is_k_redundantly_rigid(G, 1, 2)
True
>>> is_min_k_redundantly_rigid(G, 1, 2)
False

pyrigi.graph._rigidity.redundant.is_min_k_vertex_redundantly_rigid(graph, k, dim=2, algorithm='default', prob=0.0001)[source]¶

Return whether the graph is minimally k-vertex redundantly dim-rigid.

Preliminary checks from Theorem 28, Theorem 29 are used.

Definitions

Minimal k-vertex redundant dim-rigidity

Parameters:

graph (Graph)
k (int) – Level of redundancy.
dim (int) – Dimension.
algorithm (str) – See is_rigid() for the possible algorithms used for checking rigidity in this function.
prob (float) –
A bound on the probability for false negatives of the rigidity testing when algorithm="randomized".

Warning: this is not the probability of wrong results in this function, but is just passed on to rigidity testing.

Return type:

bool

Examples

>>> G = Graph([[0, 3], [0, 4], [0, 5], [1, 3], [1, 4], [1, 5],
...            [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]])
>>> is_min_k_vertex_redundantly_rigid(G, 1, 2)
True
>>> is_min_k_vertex_redundantly_rigid(G, 2, 2)
False
>>> G = Graph([[0, 2], [0, 3], [0, 4], [0, 5], [1, 2], [1, 3],
...            [1, 4], [1, 5], [2, 4], [2, 5], [3, 4], [3, 5]])
>>> is_k_vertex_redundantly_rigid(G, 1, 2)
True
>>> is_min_k_vertex_redundantly_rigid(G, 1, 2)
False