relation.py

from pymwp import Relation

Relation

Relation(
    variables: Optional[List[str]] = None, matrix: Optional[MATRIX] = None
)

A relation is made of a list of variables and a 2D-matrix:

• Variables of a relation represent the variables of the input program under analysis, for example: \(X_0, X_1, X_2\).
• Matrix holds Polynomials and represents the current state of the analysis.

Attributes:

Name	Type	Description
variables	List[str]	List of variables.
matrix	MATRIX	Matrix.

To construct a relation, provide a list of variables and an initial matrix.

If matrix is not provided, the relation matrix will be initialized to zero matrix of size matching the number of variables.

Example

Create a new relation from a list of variables:

r = Relation(['X0', 'X1', 'X2'])

Creates relation with 0-matrix with and specified variables:

X0  |  0  0  0
X1  |  0  0  0
X2  |  0  0  0

Parameters:

Name	Type	Description	Default
variables	Optional[List[str]]	Program variables.	None
matrix	Optional[MATRIX]	Relation matrix.	None

apply_choice

apply_choice(*choices: int) -> SimpleRelation

Get the matrix corresponding to provided sequence of choices.

Parameters:

Name	Type	Description	Default
choices	int	Tuple of choices.	()

Returns:

Type	Description
SimpleRelation	New relation with simple-values matrix of scalars.

composition

composition(other: Relation) -> Relation

Composition of current and another relation.

Calling this method is equivalent to syntax relation * relation.

Composition will:

1. combine the variables of two relations, and
2. produce a single matrix that is the product of matrices of the two input relations.

Parameters:

Name	Type	Description	Default
other	Relation	Relation to compose with current	required

Returns:

Type	Description
Relation	a new relation that is a product of inputs.

equal

equal(other: Relation) -> bool

Determine if two relations are equal.

For two relations to be equal they must have:

1. the same variables (independent of order), and
2. matrix polynomials must be equal element-wise.

Parameters:

Name	Type	Description	Default
other	Relation	relation to compare	required

Returns:

Type	Description
bool	true when two relations are equal
bool	and false otherwise.

eval

eval(choices: List[int], index: int, *scalars: str) -> Choices

Evaluate program matrix for possible derivation choices.

Parameters:

Name	Type	Description	Default
choices	List[int]	List of choices at each index, [0,1,2].	required
index	int	Accumulated program counter.	required
scalars	str	Exclude specified scalars.	()

Returns:

Type	Description
Choices	A choice object for the evaluated matrix.

fixpoint

fixpoint() -> Relation

Compute sum of compositions until no changes occur.

Returns:

Type	Description
Relation	resulting relation.

homogenisation staticmethod

homogenisation(r1: Relation, r2: Relation) -> Tuple[Relation, Relation]

Performs homogenisation on two relations.

After this operation both relations will have same variables and their matrices of the same size.

This operation will internally resize matrices as needed.

Parameters:

Name	Type	Description	Default
r1	Relation	First relation to homogenise.	required
r2	Relation	Second relation to homogenise.	required

Returns:

Type	Description
Tuple[Relation, Relation]	Homogenised versions of the 2 inputs relations.

identity staticmethod

identity(variables: List) -> Relation

Create an identity relation.

This method allows creating a relation whose matrix is an identity matrix.

This is an alternative way to construct a relation.

Example

Create a new identity relation from a list of variables:

r = Relation.identity(['X0', 'X1', 'X2', 'X3'])

Creates relation with identity matrix with and variables:

X0  |  m  0  0  0
X1  |  0  m  0  0
X2  |  0  0  m  0
X3  |  0  0  0  m

Parameters:

Name	Type	Description	Default
variables	List	A list of variables.	required

Returns:

Type	Description
Relation	Generated relation of given variables and an identity matrix.

infty_pairs

infty_pairs(only_incl: List[str] = None) -> str

List of potential infinity dependencies.

infty_vars

infty_vars(only_incl: List[str] = None) -> Dict[str, List[str]]

Identify all variable pairs that for some choices, can raise infinity result.

Returns:

Type	Description
Dict[str, List[str]]	Dictionary of potentially infinite dependencies, where the key is source variable and value is list of targets. All entries are non-empty.

loop_correction

loop_correction(x_var: str, dg: DeltaGraph) -> None

Loop correction to replace invalid scalars by \(\infty\).

Following computation of a loop fixpoint, this method checks the resulting matrix by rule L: scalars >\(m\) at the diagonal become \(\infty\). If exists M\(_ij\) = p then row X, col j => p.

Related discussion issue #5.

Parameters:

Name	Type	Description	Default
x_var	str	Loop control variable.	required
dg	DeltaGraph	DeltaGraph instance.	required

relation_str staticmethod

relation_str(variables: List[str], matrix: MATRIX)

Formatted string of variables and matrix.

replace_column

replace_column(vector: List, variable: str) -> Relation

Replace identity matrix column by a vector.

Parameters:

Name	Type	Description	Default
vector	List	vector by which a matrix column will be replaced.	required
variable	str	program variable, column replacement will occur at the index of this variable.	required

Raises:

Type	Description
ValueError	if variable is not found in this relation.

Returns:

Type	Description
Relation	new relation after applying the column replacement.

show

show()

Display relation.

sum

sum(other: Relation) -> Relation

Sum two relations.

Calling this method is equivalent to syntax relation + relation.

Parameters:

Name	Type	Description	Default
other	Relation	Relation to sum with self.	required

Returns:

Type	Description
Relation	A new relation that is a sum of inputs.

to_dict

to_dict() -> dict

Get dictionary representation of a relation.

var_eval

var_eval(
    choices: List[int],
    index: int,
    variables: Union[str, List[str]] = None,
    *scalars: str
) -> Union[Choices, Dict[str, Choices]]

Evaluate choices for each individual variable.

This is same as eval, except it generates the choice-vectors column-wise.

Parameters:

Name	Type	Description	Default
choices	List[int]	List of choices at each index, [0,1,2]	required
index	int	Accumulated program counter.	required
variables	Union[str, List[str]]	One or more variables to evaluate.	None
scalars	str	Exclude specified scalars.	()

Returns:

Type	Description
Union[Choices, Dict[str, Choices]]	A dictionary where the key is a variable name,
Union[Choices, Dict[str, Choices]]	and value is a choice object for the evaluated variable.

while_correction

while_correction(dg: DeltaGraph) -> None

Replace invalid scalars in a matrix by \(\infty\).

Following the computation of fixpoint for a while loop node, this method checks the resulting matrix and replaces all invalid scalars with \(\infty\) (W rule in MWP paper):

• scalar \(p\) anywhere in the matrix becomes \(\infty\)
• scalar \(w\) at the diagonal becomes \(\infty\)

Example

   Before:                After:

   | m  o  o  o  o |      | m  o  o  o  o |
   | o  w  o  p  o |      | o  i  o  i  o |
   | o  o  m  o  o |      | o  o  m  o  o |
   | w  o  o  m  o |      | w  o  o  m  o |
   | o  o  o  o  p |      | o  o  o  o  i |

Related discussion: issue #14.

Parameters:

Name	Type	Description	Default
dg	DeltaGraph	DeltaGraph instance.	required

SimpleRelation

SimpleRelation(
    variables: Optional[List[str]] = None,
    matrix: Optional[List[List[str]]] = None,
)

Bases: Relation

Specialized instance of relation, where matrix contains only scalar values, no polynomials.

A relation converts to a SimpleRelation by applying a derivation choice, see: Relation.apply_choice.