Fix MyFinitePoset

Partially pass:

  TestFinitePosetRepresentation
  TestFinitePosetRepresentation
  TestFinitePosetConstructionProduct

3 files changed, 151 insertions, 10 deletions

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]: