Skip to content

bound.py

from pymwp import Bound

Bound

Represents an MWP bound for a relation.

There is one mwp-bound expression for each input variable.

Source code in pymwp/bound.py 
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
class Bound:
    """Represents an MWP bound for a relation.

    There is one mwp-bound expression for each input variable.
    """

    def __init__(self, bounds: dict = None):
        self.bound_dict = dict([
            (k, MwpBound(triple=v)) for k, v in bounds.items()]) \
            if bounds else {}

    def calculate(self, relation: SimpleRelation) -> Bound:
        """Calculate bound from a simple-valued matrix.

        Arguments
            relation: a simple-valued relation.

        Returns:
            The bound for the relation.
        """
        vars_, matrix = relation.variables, relation.matrix
        for col_id, name in enumerate(vars_):
            var_bound = MwpBound()
            for row_id in range(len(matrix)):
                var_bound.append(matrix[row_id][col_id], vars_[row_id])
            self.bound_dict[name] = var_bound
        return self

    def to_dict(self) -> dict:
        """Get serializable dictionary representation of a bound."""
        return dict([(k, v.bound_triple_str)
                     for k, v in self.bound_dict.items()])

    def show_poly(
            self, compact: bool = False, significant: bool = False
    ) -> str:
        """Format a nice display string of bounds.

        Arguments:
            compact: reduce whitespace in the output
            significant: omit bounds that depend only on self

        Returns:
            A formatted string of the bound.
        """
        return ' ∧ '.join([
            f'{k}′{"≤" if compact else " ≤ "}{v}'
            for k, v in self.bound_dict.items()
            if (not significant or str(k) != str(v))])

calculate(relation)

Calculate bound from a simple-valued matrix.

Arguments relation: a simple-valued relation.

Returns:

Type Description
Bound

The bound for the relation.
Source code in pymwp/bound.py 
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
def calculate(self, relation: SimpleRelation) -> Bound:
    """Calculate bound from a simple-valued matrix.

    Arguments
        relation: a simple-valued relation.

    Returns:
        The bound for the relation.
    """
    vars_, matrix = relation.variables, relation.matrix
    for col_id, name in enumerate(vars_):
        var_bound = MwpBound()
        for row_id in range(len(matrix)):
            var_bound.append(matrix[row_id][col_id], vars_[row_id])
        self.bound_dict[name] = var_bound
    return self

show_poly(compact=False, significant=False)

Format a nice display string of bounds.

Parameters:

Name Type Description Default
compact bool

reduce whitespace in the output

 False
significant bool

omit bounds that depend only on self

 False

Returns:

Type Description
str

A formatted string of the bound.
Source code in pymwp/bound.py 
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
def show_poly(
        self, compact: bool = False, significant: bool = False
) -> str:
    """Format a nice display string of bounds.

    Arguments:
        compact: reduce whitespace in the output
        significant: omit bounds that depend only on self

    Returns:
        A formatted string of the bound.
    """
    return ' ∧ '.join([
        f'{k}′{"≤" if compact else " ≤ "}{v}'
        for k, v in self.bound_dict.items()
        if (not significant or str(k) != str(v))])

to_dict()

Get serializable dictionary representation of a bound.

Source code in pymwp/bound.py 
146
147
148
149
def to_dict(self) -> dict:
    """Get serializable dictionary representation of a bound."""
    return dict([(k, v.bound_triple_str)
                 for k, v in self.bound_dict.items()])

HonestPoly

Models an honest polynomial.

Source code in pymwp/bound.py 
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class HonestPoly:
    """Models an honest polynomial."""

    def __init__(self, operator: str, *init_vars: str):
        self.variables = set(init_vars)
        self.op = operator
        self.var_fmt = None

    @property
    def empty(self) -> bool:
        return len(self.variables) == 0

    @property
    def vars(self) -> List[str]:
        var_list = [self.var_fmt(v) for v in self.variables] \
            if self.var_fmt else self.variables
        return sorted(list(var_list))

    @property
    def value(self) -> Union[int, str]:
        return 0 if self.empty else self.op.join(self.vars)

    def add(self, *identifier: str):
        for i in identifier:
            self.variables.add(i)

    def __str__(self):
        return str(self.value)

MaxVar

Bases: HonestPoly

m-variables

Source code in pymwp/bound.py 
37
38
39
40
41
class MaxVar(HonestPoly):
    """m-variables"""

    def __init__(self, *init_vars):
        super().__init__(',', *init_vars)

MwpBound

Represents MWP bound.

Source code in pymwp/bound.py 
 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
class MwpBound:
    """Represents MWP bound."""

    def __init__(self, triple=None):
        x, y, z = self.parse_triple_str(triple)
        self.x = MaxVar(*x)
        self.y = HonestPoly('+', *y)
        self.z = HonestPoly('*', *z)

    def __str__(self):
        return self.bound_poly(self)

    @property
    def bound_triple(self) -> Tuple[Tuple[str], Tuple[str], Tuple[str]]:
        """Alternative bounds representation.

        Example:
            ```
            (X1,) (,) (X4, X5)
            ```

        Returns:
            Current bound as $(m_1,...m_n), (w_1,...w_n), (p_1,...p_n)$
                where the first contains list of variables in m,
                second contains variables in w, and last in p (if any).
        """
        return tuple(self.x.vars), tuple(self.y.vars), tuple(self.z.vars)

    @property
    def bound_triple_str(self) -> str:
        """Alternative bounds representation.

        Example:
            ```
            X1;;X4,X5
            ```

        Returns:
            Current bound as `m;w;p` where the first section contains
                list of variables in m, second contains variables in w,
                and last in p (if any).
        """
        return f'{";".join([",".join(v) for v in self.bound_triple])}'

    @staticmethod
    def parse_triple_str(value: str = None):
        """Restore bound from triple format"""
        return [v.split(',') if v else [] for v in value.split(";")] \
            if value else ([], [], [])

    @staticmethod
    def bound_poly(mwp: MwpBound):
        x, y, z, term = mwp.x, mwp.y, mwp.z, None
        # Any of the three variable lists might be empty
        if not x.empty and not y.empty:
            term = f'max({x},{y})'
        elif not x.empty:
            term = f'max({x})' if len(x.vars) > 1 else str(x)
        elif not y.empty:
            term = str(y)
        if term:
            return str(term) if z.empty else f'{term}+{z}'
        return str(z)

    def append(self, scalar: str, var_name: str):
        """Append variable dependency in the right list by scalar."""
        if scalar == 'm':
            self.x.add(var_name)
        if scalar == 'w':
            self.y.add(var_name)
        if scalar == 'p':
            self.z.add(var_name)

bound_triple: Tuple[Tuple[str], Tuple[str], Tuple[str]] property

Alternative bounds representation.

Example 
(X1,) (,) (X4, X5)

Returns:

Type Description
Tuple[Tuple[str], Tuple[str], Tuple[str]]

Current bound as \((m_1,...m_n), (w_1,...w_n), (p_1,...p_n)\) where the first contains list of variables in m, second contains variables in w, and last in p (if any).

bound_triple_str: str property

Alternative bounds representation.

Example 
X1;;X4,X5

Returns:

Type Description
str

Current bound as m;w;p where the first section contains list of variables in m, second contains variables in w, and last in p (if any).

append(scalar, var_name)

Append variable dependency in the right list by scalar.

Source code in pymwp/bound.py 
108
109
110
111
112
113
114
115
def append(self, scalar: str, var_name: str):
    """Append variable dependency in the right list by scalar."""
    if scalar == 'm':
        self.x.add(var_name)
    if scalar == 'w':
        self.y.add(var_name)
    if scalar == 'p':
        self.z.add(var_name)

parse_triple_str(value=None) staticmethod

Restore bound from triple format

Source code in pymwp/bound.py 
88
89
90
91
92
@staticmethod
def parse_triple_str(value: str = None):
    """Restore bound from triple format"""
    return [v.split(',') if v else [] for v in value.split(";")] \
        if value else ([], [], [])