Infinitesimal Rigidity

This module provides algorithms related to infinitesimal rigidity of frameworks.

pyrigi.framework._rigidity.infinitesimal.inf_flexes(framework, include_trivial=False, vertex_order=None, numerical=False, tolerance=1e-09, fixed_vertices=[])[source]

Return a basis of the space of infinitesimal flexes.

Return a lift of a basis of the quotient of the vector space of infinitesimal flexes modulo trivial infinitesimal flexes, if include_trivial=False. Return a basis of the vector space of infinitesimal flexes if include_trivial=True.

Definitions

Infinitesimal flex

Parameters:

  • framework (FrameworkBase)

  • include_trivial (bool) – Boolean that decides, whether the trivial flexes should be included.

  • vertex_order (Sequence[Vertex]) – A list of vertices, providing the ordering for the entries of the infinitesimal flexes. If none is provided, the list from Graph.vertex_list() is taken.

  • numerical (bool) – Determines whether the output is symbolic (default) or numerical.

  • tolerance (float) – Used tolerance when computing the infinitesimal flex numerically.

  • fixed_vertices (Sequence[Vertex]) – Fixed vertices are assigned a flex of length 0. The default value is an empty list. They can be provided as a sequence of vertices.

Return type:

list[MutableDenseMatrix] | list[list[float]]

Examples

>>> F = Framework.Complete([[0,0], [1,0], [1,1], [0,1]])
>>> F.delete_edges([(0,2), (1,3)])
>>> inf_flexes(F, include_trivial=False)
[Matrix([
[1],
[0],
[1],
[0],
[0],
[0],
[0],
[0]])]
>>> F = Framework(
...     Graph([[0, 1], [0, 3], [0, 4], [1, 3], [1, 4], [2, 3], [2, 4]]),
...     {0: [0, 0], 1: [0, 1], 2: [0, 2], 3: [1, 2], 4: [-1, 2]},
... )
>>> inf_flexes(F)
[Matrix([
[0],
[0],
[0],
[0],
[0],
[1],
[0],
[0],
[0],
[0]])]
pyrigi.framework._rigidity.infinitesimal.is_dict_inf_flex(framework, vert_to_flex, **kwargs)[source]

Return whether a dictionary specifies an infinitesimal flex of the framework.

Definitions

Infinitesimal flex

Parameters:
Return type:

bool

Examples

>>> F = Framework.Complete([[0,0], [1,1]])
>>> is_dict_inf_flex(F, {0:[0,0], 1:[-1,1]})
True
>>> is_dict_inf_flex(F, {0:[0,0], 1:["sqrt(2)","-sqrt(2)"]})
True

Notes

See is_vector_inf_flex().

pyrigi.framework._rigidity.infinitesimal.is_dict_nontrivial_inf_flex(framework, vert_to_flex, **kwargs)[source]

Return whether a dictionary specifies an infinitesimal flex which is nontrivial.

See is_vector_nontrivial_inf_flex() for details, particularly concerning the possible parameters.

Definitions

Nontrivial infinitesimal flex

Parameters:
Return type:

bool

Examples

>>> from pyrigi import frameworkDB as fws
>>> F = fws.Square()
>>> q = {0:[0,0], 1: [0,0], 2:[-2,0], 3:[-2,0]}
>>> is_dict_nontrivial_inf_flex(F, q)
True
>>> q = {0:[1,-1], 1: [1,1], 2:[-1,1], 3:[-1,-1]}
>>> is_dict_nontrivial_inf_flex(F, q)
False
pyrigi.framework._rigidity.infinitesimal.is_dict_trivial_inf_flex(framework, inf_flex, **kwargs)[source]

Return whether an infinitesimal flex specified by a dictionary is trivial.

See is_vector_trivial_inf_flex() for details, particularly concerning the possible parameters.

Definitions

Trivial infinitesimal flex

Parameters:
Return type:

bool

Examples

>>> from pyrigi import frameworkDB as fws
>>> F = fws.Square()
>>> q = {0:[0,0], 1: [0,0], 2:[-2,0], 3:[-2,0]}
>>> is_dict_trivial_inf_flex(F, q)
False
>>> q = {0:[1,-1], 1: [1,1], 2:[-1,1], 3:[-1,-1]}
>>> is_dict_trivial_inf_flex(F, q)
True
pyrigi.framework._rigidity.infinitesimal.is_inf_flexible(framework, **kwargs)[source]

Return whether the framework is infinitesimally flexible.

For implementation details and possible parameters, see is_inf_rigid().

Return type:

bool

Parameters:

framework (FrameworkBase)

Definitions

Infinitesimal rigidity

pyrigi.framework._rigidity.infinitesimal.is_inf_rigid(framework, numerical=False, tolerance=1e-09)[source]

Return whether the framework is infinitesimally rigid.

Definitions

Infinitesimal rigidity

Parameters:

  • framework (FrameworkBase)

  • numerical (bool) –

    If True, the rigidity matrix rank computation for determining rigidity is numerical.

    Warning: For numerical=True the numerical rank computation may produce different results than the computation over symbolic coordinates.

  • tolerance (float) – Numerical tolerance used for computing the rigidity matrix rank.

Return type:

bool

Examples

>>> from pyrigi import frameworkDB
>>> F1 = frameworkDB.CompleteBipartite(4,4)
>>> is_inf_rigid(F1)
True
>>> F2 = frameworkDB.Cycle(4,dim=2)
>>> is_inf_rigid(F2)
False
pyrigi.framework._rigidity.infinitesimal.is_min_inf_rigid(framework, use_copy=True, **kwargs)[source]

Return whether the framework is minimally infinitesimally rigid.

For implementation details and possible parameters, see is_inf_rigid().

Definitions

Minimal infinitesimal rigidity

Parameters:

  • framework (FrameworkBase)

  • use_copy (bool) – If False, the framework’s edges are deleted and added back during runtime. Otherwise, a new modified framework is created, while the original framework remains unchanged (default).

Return type:

bool

Examples

>>> F = Framework.Complete([[0,0], [1,0], [1,1], [0,1]])
>>> is_min_inf_rigid(F)
False
>>> F.delete_edge((0,2))
>>> is_min_inf_rigid(F)
True
pyrigi.framework._rigidity.infinitesimal.is_nontrivial_flex(framework, inf_flex, **kwargs)[source]

Alias for is_vector_nontrivial_inf_flex() and is_dict_nontrivial_inf_flex().

It is distinguished between instances of list and instances of dict to call one of the alias methods.

Definitions

Nontrivial infinitesimal flex

Parameters:
Return type:

bool

pyrigi.framework._rigidity.infinitesimal.is_trivial_flex(framework, inf_flex, **kwargs)[source]

Alias for is_vector_trivial_inf_flex() and is_dict_trivial_inf_flex().

It is distinguished between instances of list and instances of dict to call one of the alias methods.

Definitions

Trivial infinitesimal flex

Parameters:
Return type:

bool

pyrigi.framework._rigidity.infinitesimal.is_vector_inf_flex(framework, inf_flex, vertex_order=None, numerical=False, tolerance=1e-09)[source]

Return whether a vector is an infinitesimal flex of the framework.

Definitions

Parameters:

  • framework (FrameworkBase)

  • inf_flex (Sequence[Number]) – An infinitesimal flex of the framework specified by a vector.

  • vertex_order (Sequence[Vertex]) – A list of vertices specifying the order in which inf_flex is given. If none is provided, the list from vertex_list() is taken.

  • numerical (bool) – A Boolean determining whether the evaluation of the product of the inf_flex and the rigidity matrix is symbolic or numerical.

  • tolerance (float) – Absolute tolerance that is the threshold for acceptable numerical flexes. This parameter is used to determine the number of digits, to which accuracy the symbolic expressions are evaluated.

Return type:

bool

Examples

>>> from pyrigi import frameworkDB as fws
>>> F = fws.Square()
>>> q = [0,0,0,0,-2,0,-2,0]
>>> is_vector_inf_flex(F, q)
True
>>> q[0] = 1
>>> is_vector_inf_flex(F, q)
False
>>> F = Framework.Complete([[0,0], [1,1]])
>>> is_vector_inf_flex(F, ["sqrt(2)","-sqrt(2)",0,0], vertex_order=[1,0])
True
pyrigi.framework._rigidity.infinitesimal.is_vector_nontrivial_inf_flex(framework, inf_flex, vertex_order=None, numerical=False, tolerance=1e-09)[source]

Return whether an infinitesimal flex is nontrivial.

Definitions

Nontrivial infinitesimal flex

Parameters:

  • framework (FrameworkBase)

  • inf_flex (Sequence[Number]) – An infinitesimal flex of the framework.

  • vertex_order (Sequence[Vertex]) – A list of vertices specifying the order in which inf_flex is given. If none is provided, the list from Graph.vertex_list() is taken.

  • numerical (bool) – A Boolean determining whether the evaluation of the product of the inf_flex and the rigidity matrix is symbolic or numerical.

  • tolerance (float) – Absolute tolerance that is the threshold for acceptable numerical flexes. This parameter is used to determine the number of digits, to which accuracy the symbolic expressions are evaluated.

Return type:

bool

Examples

>>> from pyrigi import frameworkDB as fws
>>> F = fws.Square()
>>> q = [0,0,0,0,-2,0,-2,0]
>>> is_vector_nontrivial_inf_flex(F, q)
True
>>> q = [1,-1,1,1,-1,1,-1,-1]
>>> is_vector_inf_flex(F, q)
True
>>> is_vector_nontrivial_inf_flex(F, q)
False

Notes

This is done by solving a linear system composed of a matrix \(A\) whose columns are given by a basis of the trivial flexes and the vector \(b\) given by the input flex. \(b\) is trivial if and only if there is a linear combination of the columns in \(A\) producing \(b\). In other words, when there is a solution to \(Ax=b\), then \(b\) is a trivial infinitesimal motion. Otherwise, \(b\) is nontrivial.

In the numerical=True case we compute a least squares solution \(x\) of the overdetermined linear system and compare the values in \(Ax\) to the values in \(b\).

pyrigi.framework._rigidity.infinitesimal.is_vector_trivial_inf_flex(framework, inf_flex, **kwargs)[source]

Return whether an infinitesimal flex is trivial.

See also is_vector_nontrivial_inf_flex() for details, particularly concerning the possible parameters.

Definitions

Trivial infinitesimal flex

Parameters:
Return type:

bool

Examples

>>> from pyrigi import frameworkDB as fws
>>> F = fws.Square()
>>> q = [0,0,0,0,-2,0,-2,0]
>>> is_vector_trivial_inf_flex(F, q)
False
>>> q = [1,-1,1,1,-1,1,-1,-1]
>>> is_vector_trivial_inf_flex(F, q)
True
pyrigi.framework._rigidity.infinitesimal.nontrivial_inf_flexes(framework, **kwargs)[source]

Return non-trivial infinitesimal flexes.

See inf_flexes() for possible keywords.

Return type:

list[MutableDenseMatrix]

Parameters:

framework (FrameworkBase)

Definitions

Infinitesimal flex

Examples

>>> import pyrigi.graphDB as graphs
>>> F = Framework.Circular(graphs.CompleteBipartite(3, 3))
>>> nontrivial_inf_flexes(F)
[Matrix([
[       3/2],
[-sqrt(3)/2],
[         1],
[         0],
[         0],
[         0],
[       3/2],
[-sqrt(3)/2],
[         1],
[         0],
[         0],
[         0]])]
pyrigi.framework._rigidity.infinitesimal.rigidity_matrix(framework, vertex_order=None, edge_order=None)[source]

Construct the rigidity matrix of the framework.

Definitions

Parameters:

  • framework (FrameworkBase)

  • vertex_order (Sequence[Vertex]) – A list of vertices, providing the ordering for the columns of the rigidity matrix. If none is provided, the list from Graph.vertex_list() is taken.

  • edge_order (Sequence[Edge]) – A list of edges, providing the ordering for the rows of the rigidity matrix. If none is provided, the list from Graph.edge_list() is taken.

Return type:

MutableDenseMatrix

Examples

>>> F = Framework.Complete([(0,0),(2,0),(1,3)])
>>> rigidity_matrix(F)
Matrix([
[-2,  0, 2,  0,  0, 0],
[-1, -3, 0,  0,  1, 3],
[ 0,  0, 1, -3, -1, 3]])
pyrigi.framework._rigidity.infinitesimal.rigidity_matrix_rank(framework, numerical=False, tolerance=1e-09)[source]

Return the rank of the rigidity matrix.

Definitions

Rigidity matrix

Parameters:

  • framework (FrameworkBase)

  • numerical (bool) –

    If True, the rank of the rigidity matrix with entries as floats is computed.

    Warning: For numerical=True the numerical rank computation may produce different results than the computation over exact coordinates.

  • tolerance (float) – Numerical tolerance used for computing the rigidity matrix rank.

Return type:

int

Examples

>>> K4 = Framework.Complete([[0,0], [1,0], [1,1], [0,1]])
>>> rigidity_matrix_rank(K4)   # the complete graph is a circuit
5
>>> K4.delete_edge([0,1])
>>> rigidity_matrix_rank(K4)   # deleting a bar gives full rank
5
>>> K4.delete_edge([2,3])
>>> rigidity_matrix_rank(K4)   #so now deleting an edge lowers the rank
4
pyrigi.framework._rigidity.infinitesimal.trivial_inf_flexes(framework, vertex_order=None)[source]

Return a basis of the vector subspace of trivial infinitesimal flexes.

Definitions

Trivial infinitesimal flexes

Parameters:

  • framework (FrameworkBase)

  • vertex_order (Sequence[Vertex]) – A list of vertices, providing the ordering for the entries of the infinitesimal flexes.

Return type:

list[MutableDenseMatrix]

Examples

>>> F = Framework.Complete([(0,0), (2,0), (0,2)])
>>> trivial_inf_flexes(F)
[Matrix([
[1],
[0],
[1],
[0],
[1],
[0]]), Matrix([
[0],
[1],
[0],
[1],
[0],
[1]]), Matrix([
[ 0],
[ 0],
[ 0],
[ 2],
[-2],
[ 0]])]