Skip to content

Posets

Poset

Bases: ABC, Generic[T]

The base class for Posets

Note

This class is only a general superclass for posets. It does not contain interface/information regarding the partial-order itself.

Source code in src/act4e_mcdp/posets.py 
 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
class Poset(ABC, Generic[T]):
    """

    The base class for Posets


    Note:
        This class is only a general superclass for posets.
        It does not contain interface/information
        regarding the partial-order itself.

    """

    @abstractmethod
    def leq(self, x: T, y: T) -> bool:
        """Returns True if x <= y."""
        ...

    @abstractmethod
    def join(self, values: Collection[T]) -> Optional[T]:
        """Returns the join (max) of objects, or None if not joinable."""
        ...

    @abstractmethod
    def meet(self, values: Collection[T]) -> Optional[T]:
        """Returns the meet (min) of objects, or None if not meetable."""
        ...

    @abstractmethod
    def largest_upperset_above(self, x: T) -> "UpperSet[T]":
        """Returns the largest upperset in this poset that contains the principal upper set of x."""
        ...

    @abstractmethod
    def largest_lowerset_below(self, x: T) -> "LowerSet[T]":
        """Returns the largest lowerset in this poset that contains the principal lower set of x."""
        ...

    @abstractmethod
    def global_minima(self) -> "UpperSet[T]":
        """Returns the global minima of the poset."""
        ...

    @abstractmethod
    def global_maxima(self) -> "LowerSet[T]":
        """Returns the global maxima of the poset."""
        ...

    @abstractmethod
    def belongs(self, x: T) -> bool:
        """Check if the element belongs to the poset."""
        ...

    def eq(self, x: T, y: T) -> bool:
        """Returns True if x == y."""
        return self.leq(x, y) and self.leq(y, x)

    def lt(self, x: T, y: T) -> bool:
        """Returns True if x < y."""
        return self.leq(x, y) and not self.leq(y, x)

    def gt(self, x: T, y: T) -> bool:
        """Returns True if x > y."""
        return self.lt(y, x)

    def geq(self, x: T, y: T) -> bool:
        """Returns True if x >= y."""
        return self.leq(y, x)

    def minimals(self, elements: Collection[T]) -> set[T]:
        """Returns the minimal elements of the set."""
        res: set[T] = set()
        for x in elements:
            # check if x is dominated by other things in res
            dominated = any(self.leq(already, x) for already in res)
            if dominated:
                continue

            # check if x dominates other things in res
            non_dominated = [already for already in res if not self.leq(x, already)]

            res = set(non_dominated + [x])
        return res

    def maximals(self, elements: Collection[T]) -> set[T]:
        """Returns the minimal elements of the set."""
        res: set[T] = set()
        for x in elements:
            # check if x is dominated by other things in res
            dominated = any(self.leq(x, already) for already in res)
            if dominated:
                continue

            # check if x dominates other things in res
            non_dominated = [already for already in res if not self.leq(already, x)]

            res = set(non_dominated + [x])
        return res

    @abstractmethod
    def close(self, x: T, y: T, /, *, atol: float, rtol: float) -> bool:
        """
        returns True if x and y are close enough according to the given absolute and relative tolerances.
        """

belongs(x) abstractmethod

Check if the element belongs to the poset.

Source code in src/act4e_mcdp/posets.py 
67
68
69
70
@abstractmethod
def belongs(self, x: T) -> bool:
    """Check if the element belongs to the poset."""
    ...

close(x, y, /, *, atol, rtol) abstractmethod

returns True if x and y are close enough according to the given absolute and relative tolerances.

Source code in src/act4e_mcdp/posets.py 
118
119
120
121
122
@abstractmethod
def close(self, x: T, y: T, /, *, atol: float, rtol: float) -> bool:
    """
    returns True if x and y are close enough according to the given absolute and relative tolerances.
    """

eq(x, y)

Returns True if x == y.

Source code in src/act4e_mcdp/posets.py 
72
73
74
def eq(self, x: T, y: T) -> bool:
    """Returns True if x == y."""
    return self.leq(x, y) and self.leq(y, x)

geq(x, y)

Returns True if x >= y.

Source code in src/act4e_mcdp/posets.py 
84
85
86
def geq(self, x: T, y: T) -> bool:
    """Returns True if x >= y."""
    return self.leq(y, x)

global_maxima() abstractmethod

Returns the global maxima of the poset.

Source code in src/act4e_mcdp/posets.py 
62
63
64
65
@abstractmethod
def global_maxima(self) -> "LowerSet[T]":
    """Returns the global maxima of the poset."""
    ...

global_minima() abstractmethod

Returns the global minima of the poset.

Source code in src/act4e_mcdp/posets.py 
57
58
59
60
@abstractmethod
def global_minima(self) -> "UpperSet[T]":
    """Returns the global minima of the poset."""
    ...

gt(x, y)

Returns True if x > y.

Source code in src/act4e_mcdp/posets.py 
80
81
82
def gt(self, x: T, y: T) -> bool:
    """Returns True if x > y."""
    return self.lt(y, x)

join(values) abstractmethod

Returns the join (max) of objects, or None if not joinable.

Source code in src/act4e_mcdp/posets.py 
37
38
39
40
@abstractmethod
def join(self, values: Collection[T]) -> Optional[T]:
    """Returns the join (max) of objects, or None if not joinable."""
    ...

largest_lowerset_below(x) abstractmethod

Returns the largest lowerset in this poset that contains the principal lower set of x.

Source code in src/act4e_mcdp/posets.py 
52
53
54
55
@abstractmethod
def largest_lowerset_below(self, x: T) -> "LowerSet[T]":
    """Returns the largest lowerset in this poset that contains the principal lower set of x."""
    ...

largest_upperset_above(x) abstractmethod

Returns the largest upperset in this poset that contains the principal upper set of x.

Source code in src/act4e_mcdp/posets.py 
47
48
49
50
@abstractmethod
def largest_upperset_above(self, x: T) -> "UpperSet[T]":
    """Returns the largest upperset in this poset that contains the principal upper set of x."""
    ...

leq(x, y) abstractmethod

Returns True if x <= y.

Source code in src/act4e_mcdp/posets.py 
32
33
34
35
@abstractmethod
def leq(self, x: T, y: T) -> bool:
    """Returns True if x <= y."""
    ...

lt(x, y)

Returns True if x < y.

Source code in src/act4e_mcdp/posets.py 
76
77
78
def lt(self, x: T, y: T) -> bool:
    """Returns True if x < y."""
    return self.leq(x, y) and not self.leq(y, x)

maximals(elements)

Returns the minimal elements of the set.

Source code in src/act4e_mcdp/posets.py 
103
104
105
106
107
108
109
110
111
112
113
114
115
116
def maximals(self, elements: Collection[T]) -> set[T]:
    """Returns the minimal elements of the set."""
    res: set[T] = set()
    for x in elements:
        # check if x is dominated by other things in res
        dominated = any(self.leq(x, already) for already in res)
        if dominated:
            continue

        # check if x dominates other things in res
        non_dominated = [already for already in res if not self.leq(already, x)]

        res = set(non_dominated + [x])
    return res

meet(values) abstractmethod

Returns the meet (min) of objects, or None if not meetable.

Source code in src/act4e_mcdp/posets.py 
42
43
44
45
@abstractmethod
def meet(self, values: Collection[T]) -> Optional[T]:
    """Returns the meet (min) of objects, or None if not meetable."""
    ...

minimals(elements)

Returns the minimal elements of the set.

Source code in src/act4e_mcdp/posets.py 
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
def minimals(self, elements: Collection[T]) -> set[T]:
    """Returns the minimal elements of the set."""
    res: set[T] = set()
    for x in elements:
        # check if x is dominated by other things in res
        dominated = any(self.leq(already, x) for already in res)
        if dominated:
            continue

        # check if x dominates other things in res
        non_dominated = [already for already in res if not self.leq(x, already)]

        res = set(non_dominated + [x])
    return res

Concrete posets

FinitePoset dataclass

Bases: Poset[str]

Represents a finite poset of elements

Attributes:

Name Type Description
elements set[str]

A set of strings
relations set[tuple[str, str]]

A set of pairs of strings that represent the relations between the elements

('a', 'b') in relations represents a <= b

Examples:

>>> FinitePoset(elements={'a', 'b', 'c'}, relations={('a', 'b'), ('b', 'c')})
Source code in src/act4e_mcdp/posets.py 
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
@dataclass
class FinitePoset(Poset[str]):
    """
    Represents a finite poset of elements


    Attributes:
        elements: A set of strings
        relations: A set of pairs of strings that represent the relations between the elements


    `('a', 'b')`  in relations represents `a <= b`

    Examples:

        >>> FinitePoset(elements={'a', 'b', 'c'}, relations={('a', 'b'), ('b', 'c')})

    """

    elements: set[str]
    relations: set[tuple[str, str]]

    def belongs(self, x: str) -> bool:
        if not isinstance(x, str):  # type: ignore
            raise TypeError(f"Expected str, got {type(x).__name__} = {x!r}")
        return x in self.elements

    def leq(self, x: str, y: str) -> bool:
        raise NotImplementedError("leq for FinitePoset")

    def join(self, values: Collection[str]) -> Optional[str]:
        raise NotImplementedError("join for FinitePoset")

    def meet(self, values: Collection[str]) -> Optional[str]:
        raise NotImplementedError("meet for FinitePoset")

    def largest_upperset_above(self, x: str) -> "UpperSet[str]":
        raise NotImplementedError("largest_upperset_above for FinitePoset")

    def largest_lowerset_below(self, x: str) -> "LowerSet[str]":
        raise NotImplementedError("largest_lowerset_below for FinitePoset")

    def close(self, x: str, y: str, /, *, atol: float, rtol: float) -> bool:
        return self.eq(x, y)

    def global_minima(self) -> "UpperSet[str]":
        raise NotImplementedError("global_minima for FinitePoset")

    def global_maxima(self) -> "LowerSet[str]":
        raise NotImplementedError("global_maxima for FinitePoset")

Numbers dataclass

Bases: Poset[Decimal]

This represents a closed interval of numbers.

The top and bottom are given as decimals. Top might be +inf.

The units are given as a string. If empty, the units are dimensionless.

The step is given as a decimal. If 0, the poset is "continuous", in the sense that all decimals are allowed. If non-zero, then it represents the steps. For example, the natural numbers are given by bottom=0, top=+inf, step=1.

The numbers [0.5, 1.0, 1.5, 2.0] are given by bottom=0.5, top=2.0, step=0.5.

Attributes:

Name Type Description
bottom Decimal

Lower bound of the interval.
top Decimal

Upper bound of the interval.
step Decimal

Step of the interval. If 0, the poset is "continuous".
units str

Units of the interval. If an empty string, the units are dimensionless.
Source code in src/act4e_mcdp/posets.py 
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
@dataclass
class Numbers(Poset[Decimal]):
    """

    This represents a closed interval of numbers.

    The top and bottom are given as decimals. Top might be +inf.

    The units are given as a string. If empty, the units are dimensionless.

    The **step** is given as a decimal. If 0, the poset is "continuous", in the
    sense that all decimals are allowed. If non-zero, then it represents the steps.
    For example, the natural numbers are given by bottom=0, top=+inf, step=1.

    The numbers [0.5, 1.0, 1.5, 2.0] are given by bottom=0.5, top=2.0, step=0.5.


    Attributes:
        bottom (Decimal): Lower bound of the interval.
        top (Decimal): Upper bound of the interval.
        step (Decimal): Step of the interval. If 0, the poset is "continuous".
        units (str): Units of the interval. If an empty string, the units are dimensionless.

    """

    bottom: Decimal
    top: Decimal
    step: Decimal  # if 0 = "continuous"
    units: str  # if empty = dimensionless

    def belongs(self, x: Decimal) -> bool:
        if not isinstance(x, Decimal):  # type: ignore
            raise TypeError(f"Expected Decimal, got {type(x).__name__} = {x!r}")
        if x < self.bottom:
            return False
        if x > self.top:
            return False
        if self.step == 0:
            return True

        if x.is_infinite():
            return True

        p = (x - self.bottom) / self.step
        if not p == p.__ceil__():
            return False
        return True

    def leq(self, x: Decimal, y: Decimal) -> bool:
        assert isinstance(x, Decimal), x
        assert isinstance(y, Decimal), y
        return x <= y

    def largest_upperset_above(self, x: Decimal) -> "UpperSet[Decimal]":
        """Returns the largest upperset in this poset that contains the principal upper set of x."""

        if not isinstance(x, Decimal):  # type: ignore
            raise TypeError(f"Expected Decimal, got {type(x).__name__} = {x!r}")

        # if x is greater than the top, then the largest upperset is empty!
        if x > self.top:
            return cast(UpperSet[Decimal], UpperSet.empty())

        # this takes care also of the case x = +inf
        if x == self.top:
            return UpperSet.principal(self.top)

        if x.is_infinite():  # this is -inf
            return UpperSet.principal(self.bottom)

        # at this point, we know that x is finite
        assert x.is_finite(), x

        # first clamp x to the valid range
        x = max(x, self.bottom)
        x = min(x, self.top)

        # then round it UP to the nearest multiple of step
        if self.step == 0:
            x_rounded = x
        else:
            x_rounded = self.bottom + ((x - self.bottom) / self.step).__ceil__() * self.step

        # it could be that x_rounded is greater than the top
        if x_rounded > self.top:
            return cast(UpperSet[Decimal], UpperSet.empty())

        # then return the principal upper set of x_rounded
        return UpperSet.principal(x_rounded)

    def largest_lowerset_below(self, x: Decimal) -> "LowerSet[Decimal]":
        if not isinstance(x, Decimal):  # type: ignore
            raise TypeError(f"Expected Decimal, got {type(x).__name__} = {x!r}")

        # if x is smaller than the bottom, then the largest lowerset is empty!
        if x < self.bottom:
            return cast(LowerSet[Decimal], LowerSet.empty())

        # this takes care also of the case x = -inf
        if x == self.bottom:
            return LowerSet.principal(self.bottom)

        if x.is_infinite():  # this is +inf
            return LowerSet.principal(self.top)

        # at this point, we know that x is finite

        assert x.is_finite(), x

        # first clamp x to the valid range
        x = max(x, self.bottom)
        x = min(x, self.top)

        # then round it DOWN to the nearest multiple of step
        if self.step == 0:
            x_rounded = x
        else:
            x_rounded = self.bottom + ((x - self.bottom) / self.step).__floor__() * self.step

        # it could be that x_rounded is smaller than the bottom
        if x_rounded < self.bottom:
            return cast(LowerSet[Decimal], LowerSet.empty())

        # then return the principal lowerset of x_rounded
        return LowerSet.principal(x_rounded)

    def join(self, values: Collection[Decimal]) -> Decimal:
        return max(values)

    def meet(self, values: Collection[Decimal]) -> Decimal:
        return min(values)

    def close(self, x: Decimal, y: Decimal, /, *, atol: float, rtol: float) -> bool:
        if x == y:
            return True
        if x.is_infinite() and not y.is_infinite():
            return False
        if y.is_infinite() and not x.is_infinite():
            return False
        return abs(x - y) <= max(Decimal(atol), Decimal(rtol) * max(abs(x), abs(y)))

    def global_minima(self) -> "UpperSet[Decimal]":
        return UpperSet.principal(self.bottom)

    def global_maxima(self) -> "LowerSet[Decimal]":
        return LowerSet.principal(self.top)

largest_upperset_above(x)

Returns the largest upperset in this poset that contains the principal upper set of x.

Source code in src/act4e_mcdp/posets.py 
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
def largest_upperset_above(self, x: Decimal) -> "UpperSet[Decimal]":
    """Returns the largest upperset in this poset that contains the principal upper set of x."""

    if not isinstance(x, Decimal):  # type: ignore
        raise TypeError(f"Expected Decimal, got {type(x).__name__} = {x!r}")

    # if x is greater than the top, then the largest upperset is empty!
    if x > self.top:
        return cast(UpperSet[Decimal], UpperSet.empty())

    # this takes care also of the case x = +inf
    if x == self.top:
        return UpperSet.principal(self.top)

    if x.is_infinite():  # this is -inf
        return UpperSet.principal(self.bottom)

    # at this point, we know that x is finite
    assert x.is_finite(), x

    # first clamp x to the valid range
    x = max(x, self.bottom)
    x = min(x, self.top)

    # then round it UP to the nearest multiple of step
    if self.step == 0:
        x_rounded = x
    else:
        x_rounded = self.bottom + ((x - self.bottom) / self.step).__ceil__() * self.step

    # it could be that x_rounded is greater than the top
    if x_rounded > self.top:
        return cast(UpperSet[Decimal], UpperSet.empty())

    # then return the principal upper set of x_rounded
    return UpperSet.principal(x_rounded)

Composite posets

PosetProduct dataclass

Bases: Generic[T], Poset[tuple[T, ...]]

Represents the product of 0 or more posets. Its elements are tuples of elements of the posets.

Source code in src/act4e_mcdp/posets.py 
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
@dataclass
class PosetProduct(Generic[T], Poset[tuple[T, ...]]):
    """
    Represents the product of 0 or more posets.
    Its elements are tuples of elements of the posets.

    """

    def belongs(self, x: tuple[T, ...]) -> bool:
        if not isinstance(x, tuple):  # type: ignore
            raise TypeError(f"Expected tuple, got {type(x).__name__} = {x!r}")
        if len(x) != len(self.subs):
            raise ValueError(f"Expected tuple of length {len(self.subs)}, got {len(x)}")

        # logger.debug('belongs x %s  subs %s', x, self.subs)
        for xi, Pi in zip(x, self.subs):
            if not Pi.belongs(xi):
                return False
        return True

    subs: list[Poset[T]]

    def leq(self, x: tuple[T, ...], y: tuple[T, ...]) -> bool:
        assert len(x) == len(y)
        for P_i, x_i, y_i in zip(self.subs, x, y):
            if not P_i.leq(x_i, y_i):
                return False
        return True

    def join(self, values: Collection[tuple[T, ...]]) -> Optional[tuple[T, ...]]:
        raise NotImplementedError("join for PosetProduct")

    def meet(self, values: Collection[tuple[T, ...]]) -> Optional[tuple[T, ...]]:
        raise NotImplementedError("meet for PosetProduct")

    def largest_upperset_above(self, x: tuple[T, ...]) -> "UpperSet[tuple[T, ...]]":
        above = [P.largest_upperset_above(x_i) for P, x_i in zip(self.subs, x)]
        return UpperSet.product(above)

    def largest_lowerset_below(self, x: tuple[T, ...]) -> "LowerSet[tuple[T, ...]]":
        below = [P.largest_lowerset_below(x_i) for P, x_i in zip(self.subs, x)]
        return LowerSet.product(below)

    def close(self, x: tuple[T, ...], y: tuple[T, ...], /, *, atol: float, rtol: float) -> bool:
        for P_i, x_i, y_i in zip(self.subs, x, y):
            if not P_i.close(x_i, y_i, atol=atol, rtol=rtol):
                return False

        return True

    def global_minima(self) -> "UpperSet[tuple[T, ...]]":
        minima = [P.global_minima() for P in self.subs]
        return UpperSet.product(minima)

    def global_maxima(self) -> "LowerSet[tuple[T, ...]]":
        maxima = [P.global_maxima() for P in self.subs]
        return LowerSet.product(maxima)