Generic Rigidity

This module provides algorithms related to generic rigidity.

pyrigi.graph._rigidity.generic.is_linked(graph, u, v, dim=2)[source]

Return whether a pair of vertices is dim-linked.

Lemma 2 is used for the check.

Definitions

dim-linked pair

Parameters:

  • graph (Graph)

  • u (Vertex)

  • v (Vertex)

  • dim (int) – Currently, only the dimension dim=2 is supported.

Return type:

bool

Examples

>>> H = Graph([[0, 1], [0, 2], [1, 3], [1, 5], [2, 3], [2, 6], [3, 5], [3, 7], [5, 7], [6, 7], [3, 6]])
>>> is_linked(H, 1,7)
True
>>> H = Graph([[0, 1], [0, 2], [1, 3], [2, 3]])
>>> is_linked(H, 0,3)
False
>>> is_linked(H, 1,3)
True

Suggested Improvements

Implement also for other dimensions.

pyrigi.graph._rigidity.generic.is_min_rigid(graph, dim=2, algorithm='default', use_precomputed_pebble_digraph=False, prob=0.0001)[source]

Return whether the graph is minimally dim-rigid.

Definitions

Minimal dim-rigidity

Parameters:

  • graph (Graph)

  • dim (int) – Dimension.

  • algorithm (str) –

    If "graphic" (only if dim=1), then the graphic matroid is used, namely, it is checked whether the graph is a tree.

    If "sparsity" (only if dim=2), then (2,3)-tightness and Theorem 1 are used.

    If "randomized", a probabilistic check is performed. It may give false negatives (with probability at most prob), but no false positives. See Theorem 4.

    If "extension_sequence" (only if dim=2), then the existence of a sequence of rigidity preserving extensions is checked, see has_extension_sequence().

    If "default", then "graphic" is used for dim=1 and "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.

  • prob (float) – Only relevant if algorithm="randomized". It determines the bound on the probability of the randomized algorithm to yield false negatives.

Return type:

bool

Examples

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

Suggested Improvements

Implement algorithm="numerical".

pyrigi.graph._rigidity.generic.is_rigid(graph, dim=2, algorithm='default', use_precomputed_pebble_digraph=False, prob=0.0001)[source]

Return whether the graph is dim-rigid.

Definitions

Generic dim-rigidity

Parameters:

  • graph (Graph)

  • dim (int) – Dimension.

  • algorithm (str) –

    If "graphic" (only if dim=1), then the graphic matroid is used, namely, it is checked whether the graph is connected.

    If "sparsity" (only if dim=2), then the existence of a spanning (2,3)-tight subgraph and Theorem 1 are used with the pebble game algorithm (Algorithm 2).

    If "randomized", a probabilistic check is performed. It may give false negatives (with probability at most prob), but no false positives. See Theorem 4.

    If "numerical", a numerical check on the rigidity matrix rank is performed. See Framework.is_inf_rigid() for further details.

    If "default", then "graphic" is used for dim=1 and "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.

  • prob (float) – Only relevant if algorithm="randomized". It determines the bound on the probability of the randomized algorithm to yield false negatives.

Return type:

bool

Examples

>>> from pyrigi import Graph
>>> G = Graph([(0,1), (1,2), (2,3), (3,0)])
>>> is_rigid(G)
False
>>> G.add_edge(0,2)
>>> is_rigid(G)
True
pyrigi.graph._rigidity.generic.max_rigid_dimension(graph, algorithm='randomized', prob=0.0001)[source]

Compute the maximum dimension in which the graph is generically rigid.

For checking rigidity, the function uses a randomized algorithm, see is_rigid() for details.

Definitions

Generical rigidity

Parameters:

  • graph (Graph)

  • algorithm (str) –

    If "randomized", the rigidity of the graph is checked in each dimension using is_rigid() with algorithm="randomized". Since this is a randomized algorithm, false negatives are possible. However, the actual maximum rigid dimension is never lower than the output of this function.

    If "numerical", the rigidity of the graph is checked in each dimension using is_rigid() with algorithm="numerical". With this choice of algorithm, we do not have the guarantee that is mentioned above on the maximum rigid dimension.

  • prob (float) –

    A bound on the probability for false negatives of the rigidity testing.

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

Return type:

Union[int, Inf]

Examples

>>> import pyrigi.graphDB as graphs
>>> G = graphs.Complete(3)
>>> rigid_dim = max_rigid_dimension(G); rigid_dim
oo
>>> rigid_dim.is_infinite
True

>>> import pyrigi.graphDB as graphs
>>> G = graphs.Complete(4)
>>> G.add_edges_from([(0,4),(1,4),(2,4)])
>>> max_rigid_dimension(G)
3

Notes

This is done by taking the dimension predicted by the Maxwell count as a starting point and iteratively reducing the dimension until generic rigidity is found. This method returns sympy.oo (infinity) if and only if the graph is complete. It has the data type Inf.

pyrigi.graph._rigidity.generic.rigid_components(graph, dim=2, algorithm='default', prob=0.0001)[source]

Return the list of the vertex sets of dim-rigid components.

Definitions

Rigid components

Parameters:

  • graph (Graph)

  • dim (int) – The dimension that is used for the rigidity check.

  • algorithm (str) –

    If "graphic" (only if dim=1), then the connected components are returned.

    If "subgraphs-pebble" (only if dim=2), then all subgraphs are checked using is_rigid() with algorithm="pebble".

    If "pebble" (only if dim=2), then Rd_closure() with algorithm="pebble" is used.

    If "randomized", all subgraphs are checked using is_rigid() with algorithm="randomized".

    If "numerical", all subgraphs are checked using is_rigid() with algorithm="numerical".

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

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

list[list[Vertex]]

Examples

>>> G = Graph([(0,1), (1,2), (2,3), (3,0)])
>>> rigid_components(G, algorithm="randomized")
[[0, 1], [0, 3], [1, 2], [2, 3]]

>>> G = Graph([(0,1), (1,2), (2,3), (3,4), (4,5), (5,0), (0,2), (5,3)])
>>> is_rigid(G)
False
>>> rigid_components(G, algorithm="randomized")
[[0, 5], [2, 3], [0, 1, 2], [3, 4, 5]]

Notes

If the graph itself is rigid, it is clearly maximal and is returned. Every edge is part of a rigid component. Isolated vertices form additional rigid components.

For the pebble game algorithm we use the fact that the R2_closure consists of edge disjoint cliques, so we only have to determine them.