Global Rigidity

This module provides algorithms related to global rigidity.

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

Return whether the graph is globally dim-rigid.

Definitions

Global dim-rigidity

Parameters:

  • graph (Graph)

  • dim (int) – Dimension.

  • algorithm (str) –

    If "graphic" (only if dim=1), then 2-connectivity is checked.

    If "redundancy" (only if dim=2), then Theorem 5 is used.

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

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

  • 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,0)])
>>> is_globally_rigid(G)
True
>>> import pyrigi.graphDB as graphs
>>> J = graphs.ThreePrism()
>>> is_globally_rigid(J, dim=3)
False
>>> is_globally_rigid(J)
False
>>> K = graphs.Complete(6)
>>> is_globally_rigid(K)
True
>>> is_globally_rigid(K, dim=3)
True
>>> C = graphs.CompleteMinusOne(5)
>>> is_globally_rigid(C)
True
>>> is_globally_rigid(C, dim=3)
False
pyrigi.graph._rigidity.global_.is_weakly_globally_linked(graph, u, v, dim=2)[source]

Return whether the vertices u and v are weakly globally dim-linked.

Theorem 11 is used for the check.

Definitions

Weakly globally linked pair

Parameters:

  • graph (Graph)

  • u (Vertex)

  • v (Vertex)

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

Return type:

bool

Examples

>>> G = Graph([[0,4],[0,6],[0,7],[1,3],[1,6],[1,7],[2,6],[2,7],[3,5],[4,5],[4,7],[5,6],[5,7],[6,7]])
>>> is_weakly_globally_linked(G, 0,1)
True
>>> is_weakly_globally_linked(G, 1,5)
True
>>> import pyrigi.graphDB as graphs
>>> G = graphs.Complete(10)
>>> is_weakly_globally_linked(G, 0,1)
True

The following example is Figure 1 of the article [JV24]

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