From 23c683fd1ae5360e2ac310afaceddfb5e1243933 Mon Sep 17 00:00:00 2001 From: Nao Pross Date: Wed, 15 Nov 2023 01:19:04 +0100 Subject: Mostly pass TestSemiCategoryRepresentation --- src/act4e_solutions/semicategory_representation.py | 166 +++++++++++++++++++++ 1 file changed, 166 insertions(+) create mode 100644 src/act4e_solutions/semicategory_representation.py (limited to 'src') diff --git a/src/act4e_solutions/semicategory_representation.py b/src/act4e_solutions/semicategory_representation.py new file mode 100644 index 0000000..e99f669 --- /dev/null +++ b/src/act4e_solutions/semicategory_representation.py @@ -0,0 +1,166 @@ +from typing import Callable, Generic, Optional, TypeVar, List, Dict, Iterator, Tuple + +import act4e_interfaces as I +from act4e_interfaces import EnumerableSet + +from .sets_representation import MyFiniteSet + +from itertools import tee +from dataclasses import dataclass + +E = TypeVar("E") +OD = TypeVar("OD") # Type of the objects +MD = TypeVar("MD") # Type of the morphisms + +ROD = I.RichObject[OD] +RMD = I.RichMorphism[MD] + +class Graph: + def __init__(self): + self.nodes = {} + self.edges = {} + + def add_node(self, name): + self.nodes[name] = [] + + def add_edge(self, source, target, name): + self.nodes[source].append((target, name)) + if name not in self.edges: + self.edges[name] = [] + self.edges[name].append((source, target)) + + def get_edge_nodes(self, name): + return self.edges[name][0] + + def find_all_paths(self, source, target, length): + paths = [] + def dfs(node, path, depth): + if depth == length: + if node == target: + paths.append(path) + return + + for neighbor, edge_name in self.nodes[node]: + new_path = path + [edge_name] + dfs(neighbor, new_path, depth + 1) + + dfs(source, [], 0) + return paths + + +class MySemiCategory(Generic[OD, MD], I.SemiCategory[ROD, RMD]): + """ Skeleton for a class implementing SemiCategory.""" + _objects: Dict[str, ROD] + _morphisms: Dict[str, RMD] + _graph: Graph + _composition: Callable[[OD, OD, OD, MD], MD] + _equations: Dict[List[str], str] + _identity: RMD + + def __init__( + self, + objects, + morphisms, + graph, + composition: Callable[[OD, OD, OD, MD, MD], MD], + equations: Dict[str, str], + identity: Optional[RMD] = None + ): + self._objects = objects + self._morphisms = morphisms + self._graph = graph + self._composition = composition + self._equations = equations + self._identity = identity + + def objects(self, uptolevel: Optional[int] = None) -> EnumerableSet[ROD]: + # FIXME: why uptolevel? + return MyFiniteSet(self._objects.values()) + + def hom(self, ob1: ROD, ob2: ROD, uptolevel: Optional[int] = None) -> EnumerableSet[RMD]: + morphisms, paths = [], [] + + for i in range(1, uptolevel + 2): + for p in self._graph.find_all_paths(ob1.label, ob2.label, i): + # Remove empty paths + if not p: + continue + + # Remove paths with identities (except the path [id]) + is_identity = lambda e: e.startswith("id_") + if any(map(is_identity, p)) and len(p) > 1: + continue + + paths.append(p) + + for path in paths: + # Create compositon by following path + f = self._morphisms[path[0]] + _, prev_target = self._graph.get_edge_nodes(f.label) + for g_label in path[1:]: + _, target = self._graph.get_edge_nodes(g_label) + g = self._morphisms[g_label] + f = self.compose(ob1, self._objects[prev_target], self._objects[target], f, g) + prev_target = target + + morphisms.append(f) + + return MyFiniteSet(morphisms) + + def compose(self, ob1: ROD, ob2: ROD, ob3: ROD, m1: RMD, m2: RMD) -> RMD: + m3 = self._composition(ob1.obdata, ob2.obdata, ob3.obdata, m1.mordata, m2.mordata) + rm3 = I.RichMorphism(";".join((m1.label, m2.label)), m3) + return rm3 + + def identity(self, ob: ROD) -> RMD: + if not self._identity: + raise I.InvalidValue() + return self._identity + + +class SolSemiCategoryRepresentation(I.SemiCategoryRepresentation): + def load( + self, + h: I.IOHelper, + data: I.FiniteSemiCategory_desc, + ObData: I.Setoid[OD], + MorData: I.Setoid[MD], + compose: Callable[[OD, OD, OD, MD, MD], MD], + ) -> I.SemiCategory[I.RichObject[OD], I.RichMorphism[MD]]: + if not all(k in data.keys() for k in ["objects", "morphisms", "equations"]): + raise I.InvalidFormat() + + # Create an empty diagram + graph = Graph() + + # Prepare dictionaries for O(1) access and identity + objects, morphisms, identity = {}, {}, None + + # Get the objects + for obname, ob in data["objects"].items(): + if not "obdata" in ob.keys(): + raise I.InvalidFormat() + + objects[obname] = I.RichObject(obname, ob["obdata"]) + graph.add_node(obname) + + if "identity" in ob.keys(): + # is not None + if ob["identity"]: + idname = f"id_{obname}" + morphisms[idname] = I.RichMorphism(idname, ob["identity"]["mordata"]) + graph.add_edge(obname, obname, idname) + + # Get the morphisms + for morname, mor in data["morphisms"].items(): + if not all(k in mor.keys() for k in ["mordata", "source", "target"]): + raise I.InvalidFormat() + + morphisms[morname] = I.RichMorphism(morname, mor["mordata"]) + graph.add_edge(mor["source"], mor["target"], morname) + + equations = data["equations"] + + return MySemiCategory(objects, morphisms, graph, compose, equations, identity) + + -- cgit v1.2.1