diff options
| -rw-r--r-- | Homeworks.md | 14 | ||||
| -rw-r--r-- | src/act4e_solutions/posets_bounds.py | 22 | ||||
| -rw-r--r-- | src/act4e_solutions/posets_product.py | 39 | ||||
| -rw-r--r-- | src/act4e_solutions/posets_representation.py | 100 |
4 files changed, 158 insertions, 17 deletions
diff --git a/Homeworks.md b/Homeworks.md index faec500..1aefcb4 100644 --- a/Homeworks.md +++ b/Homeworks.md @@ -40,13 +40,13 @@ $ make docker-check - [>] TestFinitePosetRepresentation - [X] TestFinitePosetConstructionPower -- [ ] TestFinitePosetSubsetProperties -- [ ] TestFinitePosetMeasurement -- [ ] TestFinitePosetConstructionProduct -- [ ] TestFinitePosetConstructionSum -- [ ] TestFinitePosetConstructionOpposite -- [ ] TestFinitePosetConstructionTwisted -- [ ] TestFinitePosetConstructionArrow +- [>] TestFinitePosetSubsetProperties +- [?] TestFinitePosetMeasurement +- [X] TestFinitePosetConstructionProduct +- [?] TestFinitePosetConstructionSum +- [?] TestFinitePosetConstructionOpposite +- [?] TestFinitePosetConstructionTwisted +- [?] TestFinitePosetConstructionArrow - [ ] TestFiniteMonotoneMapProperties diff --git a/src/act4e_solutions/posets_bounds.py b/src/act4e_solutions/posets_bounds.py index e1f9d26..c1c6310 100644 --- a/src/act4e_solutions/posets_bounds.py +++ b/src/act4e_solutions/posets_bounds.py @@ -1,4 +1,6 @@ from typing import Any, List, Optional, overload, TypeVar +from itertools import product +from functools import cmp_to_key import act4e_interfaces as I @@ -20,10 +22,26 @@ class SolFinitePosetConstructionOpposite(I.FinitePosetConstructionOpposite): class SolFinitePosetSubsetProperties(I.FinitePosetSubsetProperties): def is_chain(self, fp: I.FinitePoset[X], s: List[X]) -> bool: - raise NotImplementedError() + try: + def cmp(a, b): + return fp._cmp(a, b) + + s_sorted = sorted(s, key=cmp_to_key(cmp)) + except RuntimeError as e: + return False + return True def is_antichain(self, fp: I.FinitePoset[X], s: List[X]) -> bool: - raise NotImplementedError() + # Comparison with itself should be ignored, since there is always a + # relation to itself by antisymmetry + not_the_same = lambda pair: not fp.carrier().equal(pair[0], pair[1]) + + # Check that no elements are comparable + for a, b in filter(not_the_same, product(s, s)): + assert fp.carrier().contains(a) and fp.carrier().contains(b) + if fp.holds(a, b): + return False + return True class SolFinitePosetSubsetProperties2(I.FinitePosetSubsetProperties2): diff --git a/src/act4e_solutions/posets_product.py b/src/act4e_solutions/posets_product.py index bf67efd..214a13a 100644 --- a/src/act4e_solutions/posets_product.py +++ b/src/act4e_solutions/posets_product.py @@ -1,10 +1,45 @@ -from typing import Any, Sequence, TypeVar +from typing import Any, Sequence, TypeVar, List + +from .sets_product import MyFiniteSetProduct import act4e_interfaces as I X = TypeVar("X") +C = TypeVar("C") # Type of the components +E = TypeVar("E") # Type of the product + +class MyFinitePosetProduct(I.FinitePosetProduct[C, E]): + _posets: List[I.FinitePoset[C]] + _carrier: I.FiniteSetProduct[C, E] + def __init__(self, posets: Sequence[I.FinitePoset[C]]): + self._posets = posets + + get_carrier = lambda p: p.carrier() + carriers = list(map(get_carrier, self._posets)) + self._carrier = MyFiniteSetProduct(carriers) + + def carrier(self): + return self._carrier + + def components(self) -> Sequence[I.FinitePoset[C]]: + return self._posets + + def holds(self, a: E, b: E) -> bool: + a = self._carrier.unpack(a) + b = self._carrier.unpack(b) + print(list(map(lambda p: p.carrier().elements(), self._posets)), a, b) + + # For all elements in both tuples, each element must be comparable with + # the element with the same index in the other tuple. If one is not + # comparable, then it is not comparable. + for ps, x, y in zip(self._posets, a, b): + if not ps.holds(x, y): + return False + + return True + class SolFinitePosetConstructionProduct(I.FinitePosetConstructionProduct): def product(self, ps: Sequence[I.FinitePoset[X]]) -> I.FinitePosetProduct[X, Any]: - raise NotImplementedError() + return MyFinitePosetProduct(ps) diff --git a/src/act4e_solutions/posets_representation.py b/src/act4e_solutions/posets_representation.py index ed3eaf9..9adc22e 100644 --- a/src/act4e_solutions/posets_representation.py +++ b/src/act4e_solutions/posets_representation.py @@ -1,4 +1,9 @@ -from typing import TypeVar, Any, List, Tuple +from typing import TypeVar, Any, List, Tuple, Dict, Set +from itertools import product +from pprint import pprint + +# do we have numpy here? +import numpy as np from .sets_representation import SolFiniteSetRepresentation @@ -9,23 +14,106 @@ X = TypeVar("X") class MyFinitePoset(I.FinitePoset[X]): _carrier: I.FiniteSet[X] - # This could be an adjacency list / matrix but I'm too lazy today, - # and python is sloooow so I doubt it would make a difference _values: List[Tuple[X,X]] + # Implementation using adjacency and reachability matrix + _adjacency: np.ndarray + _paths: np.ndarray + def __init__(self, carrier: I.FiniteSet[X], values: List[Tuple[X,X]]): self._carrier = carrier self._values = values + self._paths = np.eye(carrier.size(), dtype=bool) + + if self._values: + self._compute_paths_naive() + # self._compute_paths_fast() + + def _compute_paths_naive(self): + # Create adjancency matrix. Because poset can be represented as a hasse + # diagram, which is the same as a directed graph we can create an + # adjacency matrix for the graph of the relation. In particular when + # the graph is acyclic the adjancency matrix is nilpotent. Even if the + # graph contains cycles we can still precompute a reachability matrix + # and check in O(1) whether there is a relation between two elements + + n = self._carrier.size() + # We use booleans to avoid overflow, we do not care how long the path + # is, only whether it exists or not + self._adjacency = np.zeros((n, n), dtype=bool) + + # Build adjacency matrix + for a, b in self._values: + ia = self._carrier.elements().index(a) + ib = self._carrier.elements().index(b) + self._adjacency[ia][ib] = True + + # Compute the reachability matrix, i.e. a power series of the adjacency + # matrix if the adjacency matrix is nilpotent the power series is + # finite, otherwise it is not, but this is not a problem since we can + # upper bound the number of terms needed in this case with the number + # of nodes + self._paths = np.eye(n, dtype=bool) + adjpow = np.eye(n, dtype=bool) + for _ in range(n): + # compute the p-th power of the adjacency matrix and add it to the + # series. + adjpow = (adjpow @ self._adjacency > 0) + self._paths = np.logical_or(self._paths, adjpow) + + # if the graph is acylic we stop earlier + if np.allclose(adjpow, 0): + break + + # if not np.allclose(adjpow, 0): + # print(f"Adjacency matrix may not be nilpotent! Ran for {_} " + # + "iterations and there are nonzero entries, " + # + f"the graph ({n} nodes) may contain cycles") + + # print(f"Computed path matrix for poset with elements {self._carrier.elements()}:") + # print(self._paths.astype(int)) def carrier(self) -> I.FiniteSet[X]: return self._carrier def holds(self, a: X, b: X) -> bool: - for v in self._values: - if self.carrier().equal(v[0], a) and self.carrier().equal(v[1], b): - return True + # a is smaller than b, means that there is a path in the graph from a to b + if self._has_path(a, b): + return True + return False + def _cmp(self, a: X, b: X) -> bool: + assert self._carrier.contains(a) + assert self._carrier.contains(b) + + # a is both smaller and bigger than b + # i.e. they are equivalent + if self._has_path(a, b) and self._has_path(b, a): + return 0 + + # a is smaller than b + if self._has_path(a, b): + return 1 + + # b is smaller than a, or + # a is bigger than b + if self._has_path(b, a): + return -1 + + # else not comparable + raise RuntimeError(f"Cannot compare {a} with {b}.") + + + def _has_path(self, a: X, b: X) -> bool: + ia = self._carrier.elements().index(a) + ib = self._carrier.elements().index(b) + + # if self._paths[ia][ib] > 0: + # print(f"The path from {a = } to {b = } has length {self._paths[ia][ib]}") + + return self._paths[ia][ib] > 0 + class SolFinitePosetRepresentation(I.FinitePosetRepresentation): def load(self, h: I.IOHelper, s: I.FinitePoset_desc) -> I.FinitePoset[Any]: |