Skip to content

relation.py

from pymwp import Relation

Relation

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.

Source code in pymwp/relation.py 
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
class Relation:
    """
    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`](polynomial.md#pymwp.polynomial)
    and represents the current state of the analysis.

    """

    def __init__(self, variables: Optional[List[str]] = None,
                 matrix: Optional[List[List[Polynomial]]] = None):
        """Create a relation.

        When constructing 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.

        Also see: [`Relation.identity()`](relation.md#pymwp.relation
        .Relation.identity) for creating a relation whose matrix is an
        identity matrix.

        Example:

        Create a new relation from a list of variables:

        ```python
        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
        ```

        Arguments:
            variables: program variables
            matrix: relation matrix
        """
        self.variables = [str(v) for v in (variables or []) if v]
        self.matrix = matrix or matrix_utils \
            .init_matrix(len(self.variables))

    @staticmethod
    def 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:

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

        # Creates relation with identity matrix with and specified variables:
        #
        #  X0  |  m  0  0  0
        #  X1  |  0  m  0  0
        #  X2  |  0  0  m  0
        #  X3  |  0  0  0  m
        ```

        Arguments:
            variables: list of variables

        Returns:
             Generated relation of given variables and an identity matrix.
        """
        matrix = matrix_utils.identity_matrix(len(variables))
        return Relation(variables, matrix)

    @property
    def is_empty(self):
        return not self.variables or not self.matrix

    @property
    def matrix_size(self):
        return 0 if not self.variables else len(self.variables)

    def __str__(self):
        return Relation.relation_str(self.variables, self.matrix)

    def __add__(self, other):
        return self.sum(other)

    def __mul__(self, other):
        return self.composition(other)

    @staticmethod
    def relation_str(variables: List[str], matrix: List[List[any]]):
        """Formatted string of variables and matrix."""
        right_pad = len(max(variables, key=len)) if variables else 0
        return '\n'.join(
            [var.ljust(right_pad) + ' | ' + (' '.join(poly)).strip()
             for var, poly in
             [(var, [str(matrix[i][j]) for j in range(len(matrix))])
              for i, var in enumerate(variables)]])

    def replace_column(self, vector: List, variable: str) -> Relation:
        """Replace identity matrix column by a vector.

        Arguments:
            vector: vector by which a matrix column will be replaced.
            variable: program variable, column replacement
                will occur at the index of this variable.

        Raises:
              ValueError: if variable is not found in this relation.

        Returns:
            new relation after applying the column replacement.
        """
        new_relation = Relation.identity(self.variables)
        if variable in self.variables:
            j = self.variables.index(variable)
            for idx, value in enumerate(vector):
                new_relation.matrix[idx][j] = value
        return new_relation

    def while_correction(self, 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:

        ```text
           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 |
        ```

        This method is where $\\infty$ is introduced in a matrix.

        Related discussion: [issue #14](
        https://github.com/statycc/pymwp/issues/14).

        Arguments:
            dg: DeltaGraph instance
        """
        for i, vector in enumerate(self.matrix):
            for j, poly in enumerate(vector):
                for mon in poly.list:
                    if mon.scalar == "p" or (mon.scalar == "w" and i == j):
                        mon.scalar = "i"
                        dg.from_monomial(mon)

    def sum(self, other: Relation) -> Relation:
        """Sum two relations.

        Calling this method is equivalent to syntax `relation + relation`.

        Arguments:
            other: Relation to sum with self.

        Returns:
           A new relation that is a sum of inputs.
        """
        er1, er2 = Relation.homogenisation(self, other)
        new_matrix = matrix_utils.matrix_sum(er1.matrix, er2.matrix)
        return Relation(er1.variables, new_matrix)

    def composition(self, 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.

        Arguments:
            other: Relation to compose with current

        Returns:
           a new relation that is a product of inputs.
        """

        logger.debug("starting composition...")
        er1, er2 = Relation.homogenisation(self, other)
        logger.debug("composing matrix product...")
        new_matrix = matrix_utils.matrix_prod(er1.matrix, er2.matrix)
        logger.debug("...relation composition done!")
        return Relation(er1.variables, new_matrix)

    def equal(self, 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.

        See [`polynomial#equal`](
        polynomial.md#pymwp.polynomial.Polynomial.equal)
        for details on how to determine equality of two polynomials.

        Arguments:
            other: relation to compare

        Returns:
            true when two relations are equal
            and false otherwise.
        """

        # must have same variables in same order
        if set(self.variables) != set(other.variables):
            return False

        # not sure homogenisation is necessary here
        # --> yes we need it
        er1, er2 = Relation.homogenisation(self, other)

        for row1, row2 in zip(er1.matrix, er2.matrix):
            for poly1, poly2 in zip(row1, row2):
                if poly1 != poly2:
                    return False
        return True

    def fixpoint(self) -> Relation:
        """
        Compute sum of compositions until no changes occur.

        Returns:
            resulting relation.
        """
        fix_vars = self.variables
        matrix = matrix_utils.identity_matrix(len(fix_vars))
        fix = Relation(fix_vars, matrix)
        prev_fix = Relation(fix_vars, matrix)
        current = Relation(fix_vars, matrix)

        logger.debug(f"computing fixpoint for variables {fix_vars}")

        while True:
            prev_fix.matrix = fix.matrix
            current = current * self
            fix = fix + current
            if fix.equal(prev_fix):
                logger.debug(f"fixpoint done {fix_vars}")
                return fix

    def apply_choice(self, *choices: int) -> SimpleRelation:
        """Get the matrix corresponding to provided sequence of choices.

        Arguments:
            choices: tuple of choices

        Returns:
            New relation with simple-values matrix of scalars.
        """
        new_mat = [[self.matrix[i][j].choice_scalar(*choices)
                    for j in range(self.matrix_size)]
                   for i in range(self.matrix_size)]
        return SimpleRelation(self.variables.copy(), matrix=new_mat)

    def infty_vars(self) -> Dict[str, List[str]]:
        """Identify all variable pairs that for some choices, can raise
        infinity result.

        Returns:
            Dictionary of potentially infinite dependencies, where
                the key is source variable and value is list of targets.
                All entries are non-empty.
        """
        vars_ = self.variables
        return dict([(x, y) for x, y in [
            (src, [tgt for tgt, p in zip(vars_, polys) if p.some_infty])
            for src, polys in zip(vars_, self.matrix)] if len(y) != 0])

    def infty_pairs(self) -> str:
        """List of potential infinity dependencies."""
        fmt = [f'{s} ➔ {", ".join(t)}' for s, t in self.infty_vars().items()]
        return ' ‖ '.join(fmt)

    def to_dict(self) -> dict:
        """Get dictionary representation of a relation."""
        return {"matrix": matrix_utils.encode(self.matrix)}

    def show(self):
        """Display relation."""
        print(str(self))

    @staticmethod
    def 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.

        Arguments:
            r1: first relation to homogenise
            r2: second relation to homogenise

        Returns:
            Homogenised versions of the 2 inputs relations
        """

        # check equality
        if r1.variables == r2.variables:
            return r1, r2

        # check empty cases
        if r1.is_empty:
            return Relation.identity(r2.variables), r2

        if r2.is_empty:
            return r1, Relation.identity(r1.variables)

        logger.debug("matrix homogenisation...")

        # build a list of all distinct variables; maintain order
        extended_vars = r1.variables + [v for v in r2.variables
                                        if v not in r1.variables]

        # resize matrices to match new number of variables
        new_matrix_size = len(extended_vars)

        # first matrix: just resize -> this one is now done
        matrix1 = matrix_utils.resize(r1.matrix, new_matrix_size)

        # second matrix: create and initialize as identity matrix
        matrix2 = matrix_utils.identity_matrix(new_matrix_size)

        # index of each extended_vars iff variable exists in r2.
        # we will use this to mapping from old -> new matrix to fill
        # the new matrix; the indices may be in different order.
        index_dict = {index: r2.variables.index(var)
                      for index, var in enumerate(extended_vars)
                      if var in r2.variables}

        # generate a list of all valid <row, column> combinations
        index_map = [t1 + t2 for t1 in index_dict.items()
                     for t2 in index_dict.items()]

        # fill the resized matrix with values from original matrix
        for mj, rj, mi, ri in index_map:
            matrix2[mi][mj] = r2.matrix[ri][rj]

        return Relation(extended_vars, matrix1), Relation(extended_vars,
                                                          matrix2)

    def eval(self, choices: List[int], index: int) -> Choices:
        """Eval experiment: returns a choice object."""

        infinity_deltas = set()

        # get all choices leading to infinity
        for row in self.matrix:
            for poly in row:
                infinity_deltas.update(poly.eval)

        # generate valid choices
        return Choices.generate(choices, index, infinity_deltas)

__init__(variables=None, matrix=None)

Create a relation.

When constructing 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.

Also see: Relation.identity() for creating a relation whose matrix is an identity matrix.

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[List[List[Polynomial]]]

relation matrix

 None
Source code in pymwp/relation.py 
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
def __init__(self, variables: Optional[List[str]] = None,
             matrix: Optional[List[List[Polynomial]]] = None):
    """Create a relation.

    When constructing 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.

    Also see: [`Relation.identity()`](relation.md#pymwp.relation
    .Relation.identity) for creating a relation whose matrix is an
    identity matrix.

    Example:

    Create a new relation from a list of variables:

    ```python
    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
    ```

    Arguments:
        variables: program variables
        matrix: relation matrix
    """
    self.variables = [str(v) for v in (variables or []) if v]
    self.matrix = matrix or matrix_utils \
        .init_matrix(len(self.variables))

apply_choice(*choices)

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.
Source code in pymwp/relation.py 
277
278
279
280
281
282
283
284
285
286
287
288
289
def apply_choice(self, *choices: int) -> SimpleRelation:
    """Get the matrix corresponding to provided sequence of choices.

    Arguments:
        choices: tuple of choices

    Returns:
        New relation with simple-values matrix of scalars.
    """
    new_mat = [[self.matrix[i][j].choice_scalar(*choices)
                for j in range(self.matrix_size)]
               for i in range(self.matrix_size)]
    return SimpleRelation(self.variables.copy(), matrix=new_mat)

composition(other)

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.
Source code in pymwp/relation.py 
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
def composition(self, 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.

    Arguments:
        other: Relation to compose with current

    Returns:
       a new relation that is a product of inputs.
    """

    logger.debug("starting composition...")
    er1, er2 = Relation.homogenisation(self, other)
    logger.debug("composing matrix product...")
    new_matrix = matrix_utils.matrix_prod(er1.matrix, er2.matrix)
    logger.debug("...relation composition done!")
    return Relation(er1.variables, new_matrix)

equal(other)

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.

See polynomial#equal for details on how to determine equality of two polynomials.

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.
Source code in pymwp/relation.py 
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
def equal(self, 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.

    See [`polynomial#equal`](
    polynomial.md#pymwp.polynomial.Polynomial.equal)
    for details on how to determine equality of two polynomials.

    Arguments:
        other: relation to compare

    Returns:
        true when two relations are equal
        and false otherwise.
    """

    # must have same variables in same order
    if set(self.variables) != set(other.variables):
        return False

    # not sure homogenisation is necessary here
    # --> yes we need it
    er1, er2 = Relation.homogenisation(self, other)

    for row1, row2 in zip(er1.matrix, er2.matrix):
        for poly1, poly2 in zip(row1, row2):
            if poly1 != poly2:
                return False
    return True

eval(choices, index)

Eval experiment: returns a choice object.

Source code in pymwp/relation.py 
380
381
382
383
384
385
386
387
388
389
390
391
def eval(self, choices: List[int], index: int) -> Choices:
    """Eval experiment: returns a choice object."""

    infinity_deltas = set()

    # get all choices leading to infinity
    for row in self.matrix:
        for poly in row:
            infinity_deltas.update(poly.eval)

    # generate valid choices
    return Choices.generate(choices, index, infinity_deltas)

fixpoint()

Compute sum of compositions until no changes occur.

Returns:

Type Description
Relation

resulting relation.
Source code in pymwp/relation.py 
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
def fixpoint(self) -> Relation:
    """
    Compute sum of compositions until no changes occur.

    Returns:
        resulting relation.
    """
    fix_vars = self.variables
    matrix = matrix_utils.identity_matrix(len(fix_vars))
    fix = Relation(fix_vars, matrix)
    prev_fix = Relation(fix_vars, matrix)
    current = Relation(fix_vars, matrix)

    logger.debug(f"computing fixpoint for variables {fix_vars}")

    while True:
        prev_fix.matrix = fix.matrix
        current = current * self
        fix = fix + current
        if fix.equal(prev_fix):
            logger.debug(f"fixpoint done {fix_vars}")
            return fix

homogenisation(r1, r2) staticmethod

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
Source code in pymwp/relation.py 
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
@staticmethod
def 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.

    Arguments:
        r1: first relation to homogenise
        r2: second relation to homogenise

    Returns:
        Homogenised versions of the 2 inputs relations
    """

    # check equality
    if r1.variables == r2.variables:
        return r1, r2

    # check empty cases
    if r1.is_empty:
        return Relation.identity(r2.variables), r2

    if r2.is_empty:
        return r1, Relation.identity(r1.variables)

    logger.debug("matrix homogenisation...")

    # build a list of all distinct variables; maintain order
    extended_vars = r1.variables + [v for v in r2.variables
                                    if v not in r1.variables]

    # resize matrices to match new number of variables
    new_matrix_size = len(extended_vars)

    # first matrix: just resize -> this one is now done
    matrix1 = matrix_utils.resize(r1.matrix, new_matrix_size)

    # second matrix: create and initialize as identity matrix
    matrix2 = matrix_utils.identity_matrix(new_matrix_size)

    # index of each extended_vars iff variable exists in r2.
    # we will use this to mapping from old -> new matrix to fill
    # the new matrix; the indices may be in different order.
    index_dict = {index: r2.variables.index(var)
                  for index, var in enumerate(extended_vars)
                  if var in r2.variables}

    # generate a list of all valid <row, column> combinations
    index_map = [t1 + t2 for t1 in index_dict.items()
                 for t2 in index_dict.items()]

    # fill the resized matrix with values from original matrix
    for mj, rj, mi, ri in index_map:
        matrix2[mi][mj] = r2.matrix[ri][rj]

    return Relation(extended_vars, matrix1), Relation(extended_vars,
                                                      matrix2)

identity(variables) staticmethod

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 specified 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

list of variables

 required

Returns:

Type Description
Relation

Generated relation of given variables and an identity matrix.
Source code in pymwp/relation.py 
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
@staticmethod
def 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:

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

    # Creates relation with identity matrix with and specified variables:
    #
    #  X0  |  m  0  0  0
    #  X1  |  0  m  0  0
    #  X2  |  0  0  m  0
    #  X3  |  0  0  0  m
    ```

    Arguments:
        variables: list of variables

    Returns:
         Generated relation of given variables and an identity matrix.
    """
    matrix = matrix_utils.identity_matrix(len(variables))
    return Relation(variables, matrix)

infty_pairs()

List of potential infinity dependencies.

Source code in pymwp/relation.py 
305
306
307
308
def infty_pairs(self) -> str:
    """List of potential infinity dependencies."""
    fmt = [f'{s} ➔ {", ".join(t)}' for s, t in self.infty_vars().items()]
    return ' ‖ '.join(fmt)

infty_vars()

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.
Source code in pymwp/relation.py 
291
292
293
294
295
296
297
298
299
300
301
302
303
def infty_vars(self) -> Dict[str, List[str]]:
    """Identify all variable pairs that for some choices, can raise
    infinity result.

    Returns:
        Dictionary of potentially infinite dependencies, where
            the key is source variable and value is list of targets.
            All entries are non-empty.
    """
    vars_ = self.variables
    return dict([(x, y) for x, y in [
        (src, [tgt for tgt, p in zip(vars_, polys) if p.some_infty])
        for src, polys in zip(vars_, self.matrix)] if len(y) != 0])

relation_str(variables, matrix) staticmethod

Formatted string of variables and matrix.

Source code in pymwp/relation.py 
112
113
114
115
116
117
118
119
120
@staticmethod
def relation_str(variables: List[str], matrix: List[List[any]]):
    """Formatted string of variables and matrix."""
    right_pad = len(max(variables, key=len)) if variables else 0
    return '\n'.join(
        [var.ljust(right_pad) + ' | ' + (' '.join(poly)).strip()
         for var, poly in
         [(var, [str(matrix[i][j]) for j in range(len(matrix))])
          for i, var in enumerate(variables)]])

replace_column(vector, variable)

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.
Source code in pymwp/relation.py 
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
def replace_column(self, vector: List, variable: str) -> Relation:
    """Replace identity matrix column by a vector.

    Arguments:
        vector: vector by which a matrix column will be replaced.
        variable: program variable, column replacement
            will occur at the index of this variable.

    Raises:
          ValueError: if variable is not found in this relation.

    Returns:
        new relation after applying the column replacement.
    """
    new_relation = Relation.identity(self.variables)
    if variable in self.variables:
        j = self.variables.index(variable)
        for idx, value in enumerate(vector):
            new_relation.matrix[idx][j] = value
    return new_relation

show()

Display relation.

Source code in pymwp/relation.py 
314
315
316
def show(self):
    """Display relation."""
    print(str(self))

sum(other)

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.
Source code in pymwp/relation.py 
180
181
182
183
184
185
186
187
188
189
190
191
192
193
def sum(self, other: Relation) -> Relation:
    """Sum two relations.

    Calling this method is equivalent to syntax `relation + relation`.

    Arguments:
        other: Relation to sum with self.

    Returns:
       A new relation that is a sum of inputs.
    """
    er1, er2 = Relation.homogenisation(self, other)
    new_matrix = matrix_utils.matrix_sum(er1.matrix, er2.matrix)
    return Relation(er1.variables, new_matrix)

to_dict()

Get dictionary representation of a relation.

Source code in pymwp/relation.py 
310
311
312
def to_dict(self) -> dict:
    """Get dictionary representation of a relation."""
    return {"matrix": matrix_utils.encode(self.matrix)}

while_correction(dg)

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 |

This method is where \(\infty\) is introduced in a matrix.

Related discussion: issue #14.

Parameters:

Name Type Description Default
dg DeltaGraph

DeltaGraph instance

 required
Source code in pymwp/relation.py 
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
def while_correction(self, 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:

    ```text
       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 |
    ```

    This method is where $\\infty$ is introduced in a matrix.

    Related discussion: [issue #14](
    https://github.com/statycc/pymwp/issues/14).

    Arguments:
        dg: DeltaGraph instance
    """
    for i, vector in enumerate(self.matrix):
        for j, poly in enumerate(vector):
            for mon in poly.list:
                if mon.scalar == "p" or (mon.scalar == "w" and i == j):
                    mon.scalar = "i"
                    dg.from_monomial(mon)

SimpleRelation

Bases: Relation

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

Source code in pymwp/relation.py 
394
395
396
397
398
399
400
class SimpleRelation(Relation):
    """Specialized instance of relation, where matrix contains only
       scalar values, no polynomials."""

    def __init__(self, variables: Optional[List[str]] = None,
                 matrix: Optional[List[List[str]]] = None):
        super().__init__(variables, matrix)