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:

combine the variables of two relations, and
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:

the same variables (independent of order), and
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.

relation.py¶

Relation ¶

apply_choice ¶

composition ¶

equal ¶

eval ¶

fixpoint ¶

homogenisation staticmethod ¶

identity staticmethod ¶

infty_pairs ¶

infty_vars ¶

loop_correction ¶

relation_str staticmethod ¶

replace_column ¶

show ¶

sum ¶

to_dict ¶

var_eval ¶

while_correction ¶

SimpleRelation ¶

homogenisation `staticmethod` ¶

identity `staticmethod` ¶

relation_str `staticmethod` ¶