12285111698

Committed 11 Dec 2024 09:21PM UTC coverage: 81.699% (-2.5%) from 84.228%

Build # 12285111698

Build Type

push

github

Committed by

peekxc

Commit Message

Merge branch 'main' of ssh://github.com/peekxc/simplextree-py

Run Details

1 of 1 new or added line in 1 file covered. (100.0%)

47 existing lines in 4 files now uncovered.

250 of 306 relevant lines covered (81.7%)

4.08 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

77.78

/simplextree/SimplexTree.py

# ruff: noqa: PLR0904
from __future__ import annotations

import builtins
from numbers import Integral
from typing import Callable, Collection, Iterable, Iterator, Optional, Sequence, Union

import numpy as np
from _simplextree import SimplexTree as SimplexTreeCpp
from numpy.typing import ArrayLike


class SimplexTree(SimplexTreeCpp):
        """SimplexTree provides lightweight wrapper around a Simplex Tree data structure.

        This class exposes a native extension module wrapping a simplex tree implemented with modern C++.

        The Simplex Tree was originally introduced in the paper:
        > Boissonnat, Jean-Daniel, and Clément Maria. "The simplex tree: An efficient data structure for general simplicial complexes." Algorithmica 70.3 (2014): 406-427.

        Attributes:
                n_simplices: number of simplices
                dimension: maximal dimension of the complex
                id_policy: policy for generating new vertex ids
                vertices: 0-simplices in the complex.
                edges: 1-simplices in the complex.
                triangles: 2-simplices in the complex.
                quads: 3-simplices in the complex.
                connected_components: connected component ids.
        """

        def __init__(self, simplices: Optional[Iterable[Collection]] = None, s_type: Callable = tuple) -> None:
                assert callable(s_type), "Simplex type must have a constructor"
                SimplexTreeCpp.__init__(self)
                if simplices is not None:
                        self.insert(simplices)
                self.s_type = s_type

        def insert(self, simplices: Iterable[Collection]) -> None:
                """Inserts simplices into the Simplex Tree.

                By definition, inserting a simplex also inserts all of its faces. If the simplex already exists in the complex, the tree is not modified.

                Parameters:
                        simplices: Iterable of simplices to insert (each of which are SimplexLike)

                ::: {.callout-note}
                  If the iterable is an 2-dim np.ndarray, then a p-simplex is inserted along each contiguous p+1 stride.
                        Otherwise, each element of the iterable to casted to a Simplex and then inserted into the tree.
                :::

                Examples:
                        ```{python}
                        from simplextree import SimplexTree
                        st = SimplexTree([range(3)])
                        print(st)
                        ```
                        ```{python}
                        st.insert([[0,1]])
                        print(st)
                        ```
                """
                if isinstance(simplices, np.ndarray):
                        simplices = np.sort(simplices, axis=1).astype(np.uint16)
                        assert simplices.ndim in {1, 2}, "dimensions should be 1 or 2"
                        self._insert(simplices)
                else:
                        assert isinstance(simplices, Iterable), f"Invalid simplices type '{type(simplices)}' given"
                        self._insert_list(list(map(lambda x: np.asarray(x, dtype=np.uint16), simplices)))

        def remove(self, simplices: Iterable[Collection]):
                """Removes simplices into the Simplex Tree.

                By definition, removing a face also removes all of its cofaces. If the simplex does not exist in the complex, the tree is not modified.

                Parameters:
                        simplices: Iterable of simplices to insert (each of which are SimplexLike).

                ::: {.callout-note}
                        If the iterable is an 2-dim np.ndarray, then a p-simplex is removed along each contiguous p+1 stride.
                        Otherwise, each element of the iterable to casted to a Simplex and then removed from the tree.
                :::

                Examples:
                        ```{python}
                        from simplextree import SimplexTree
                        st = SimplexTree([range(3)])
                        print(st)
                        ```
                        ```{python}
                        st.remove([[0,1]])
                        print(st)
                        ```
                """
                if isinstance(simplices, np.ndarray):
                        simplices = np.sort(simplices, axis=1).astype(np.uint16)
                        assert simplices.ndim in {1, 2}, "dimensions should be 1 or 2"
                        self._remove(simplices)
                elif isinstance(simplices, Iterable):
                        self._remove_list(list(map(lambda x: np.asarray(x, dtype=np.uint16), simplices)))
                else:
                        raise ValueError("Invalid type given")

        def find(self, simplices: Iterable[Collection]) -> np.ndarray:
                """Finds whether simplices exist in Simplex Tree.

                Parameters:
                        simplices: Iterable of simplices to insert (each of which are SimplexLike)

                Returns:
                        found: boolean array indicating whether each simplex was found in the complex

                ::: {.callout-note}
                        If the iterable is an 2-dim np.ndarray, then the p-simplex to find is given by each contiguous p+1 stride.
                        Otherwise, each element of the iterable to casted to a Simplex and then searched for in the tree.
                :::
                """
                if isinstance(simplices, np.ndarray):
                        simplices = np.array(simplices, dtype=np.int16)
                        assert simplices.ndim in {1, 2}, "dimensions should be 1 or 2"
                        return self._find(simplices)
                elif isinstance(simplices, Iterable):
                        return self._find_list([tuple(s) for s in simplices])
                else:
                        raise ValueError("Invalid type given")

        def adjacent(self, vertices: Iterable[Collection]):
                """Finds adjacent vertices of a collection of vertices."""
                return self._adjacent(list(map(lambda x: np.asarray(x, dtype=np.uint16), vertices)))

        def collapse(self, sigma: Collection, tau: Collection) -> bool:
                r"""Performs an elementary collapse on two given simplices.

                Checks whether its possible to collapse $\sigma$ through $\tau$, and if so, both simplices are removed.
                A simplex $\sigma$ is said to be collapsible through one of its faces $\tau$ if $\sigma$ is the only coface of $\tau$ (excluding $\tau$ itself).

                Parameters:
                        sigma: maximal simplex to collapse
                        tau: face of sigma to collapse

                Returns:
                        whether the pair was collapsed

                Examples:
                        ```{python}
                        from simplextree import SimplexTree
                        st = SimplexTree([[0,1,2]])
                        print(st)
                        ```
                        ```{python}
                        st.collapse([0,1,2], [1,2])
                        print(st)
                        ```
                """
                if len(sigma) != (len(tau) + 1):  # , f"Simplex {tau} not in the boundary of simplex {sigma}"
                        return False
                success = self._collapse(tau, sigma)
                return success

        def contract(self, pair: Collection) -> None:
                r"""Performs an pair contraction.

                This function performs an pair contraction: given a pair of vertices $(va, vb)$, vertex $vb$ is said to *contract*
                to $va$ if $vb$ is removed from the complex and the link of $va$ is augmented with the link of $vb$.

                Some notes about `pair` are in order:
                        - `pair` is **not** sorted like other simplex inputs
                        - The second vertex is always contracted to the first
                        - `pair` need not be an existing simplex (edge) in the complex
                        - Contraction is not symmetric.

                Parameters:
                        pair: pair to contract

                Returns:
                        whether the pair was contracted

                Examples:
                        ```{python}
                        from simplextree import SimplexTree
                        st = SimplexTree([[0,1,2]])
                        st.print()
                        ```
                        ```{python}
                        st.contract([0,2])
                        st.print()
                        ```
                """
                success = self._contract(pair)
                return success

        def vertex_collapse(self, u: int, v: int, w: int) -> bool:
                """Maps a pair of vertices into a single vertex.

                Parameters:
                        u: the first vertex in the free pair.
                        v: the second vertex in the free pair.
                        w: the target vertex to collapse to.

                Returns:
                        collapsed: whether the collapse was performed.
                """
                u, v, w = int(u), int(v), int(w)
                assert all([isinstance(e, Integral) for e in [u, v, w]]), "Unknown vertex types given; must be integral"
                return self._vertex_collapse(u, v, w)

        def degree(self, vertices: Optional[ArrayLike] = None) -> Union[ArrayLike, int]:
                """Computes the degree of select vertices in the trie.

                Parameters:
                        vertices: If no vertices are specified, all degrees are computed. Non-existing vertices by default have degree 0.

                Returns:
                        degree of each vertex id given in 'vertices'.
                """
                if vertices is None:
                        return self._degree_default()
                elif isinstance(vertices, Iterable):
                        vertices = np.fromiter(iter(vertices), dtype=np.int16)
                        assert vertices.ndim == 1, "Invalid shape given; Must be flattened array of vertex ids"
                        return self._degree(vertices)
                else:
                        raise ValueError(f"Invalid type {type(vertices)} given")

        # PREORDER = 0, LEVEL_ORDER = 1, FACES = 2, COFACES = 3, COFACE_ROOTS = 4,
        # K_SKELETON = 5, K_SIMPLICES = 6, MAXIMAL = 7, LINK = 8
        def traverse(self, order: str = "preorder", f: Callable = builtins.print, sigma: Collection = [], p: int = 0) -> None:
                """Traverses the simplex tree in the specified order, calling `f` on each simplex encountered.

                Supported traversals include breadth-first / level order ("bfs", "levelorder"), depth-first / prefix ("dfs", "preorder").
                faces, cofaces, coface roots ("coface_roots"), p-skeleton, p-simplices, maximal simplices ("maximal"), and link.

                Where applicable, each traversal begins its traversal `sigma`, which defaults to the empty set (root node).

                Parameters:
                        order: the type of traversal of the simplex tree to execute.
                        f: a function to evaluate on every simplex in the traversal. Defaults to print.
                        sigma: simplex to start the traversal at, where applicable. Defaults to the root node (empty set).
                        p: dimension of simplices to restrict to, where applicable. Defaults to 0.

                Returns:
                        None
                """
                # todo: handle kwargs
                assert isinstance(order, str)
                order = order.lower()
                if order in {"dfs", "preorder"}:
                        order = 0
                elif order in {"bfs", "level_order", "levelorder"}:
                        order = 1
                elif order == "faces":
                        order = 2
                elif order == "cofaces":
                        order = 3
                elif order == "coface_roots":
                        order = 4
                elif order == "p-skeleton":
                        order = 5
                elif order == "p-simplices":
                        order = 6
                elif order == "maximal":
                        order = 7
                elif order == "link":
                        order = 8
                else:
                        raise ValueError(f"Unknown order '{order}' specified")
                assert isinstance(int(p), int), f"Invalid argument type '{type(p)}', must be integral"
                sigma = [] if sigma is None else sigma
                if p >= 0:
                        self._traverse(order, f, sigma, p)  # order, f, init, k

        def cofaces(self, sigma: Collection = []) -> list[Collection]:
                """Returns the cofaces of `sigma`.

                Note, by definition, `sigma` is defined as a coface of itself.

                Parameters:
                        sigma: the simplex to obtain cofaces of.

                Returns:
                        cofaces: the cofaces of `sigma`.
                """
                if sigma == [] or len(sigma) == 0:
                        return self.simplices()
                F = []
                self._traverse(3, lambda s: F.append(self.s_type(s)), sigma, 0)  # order, f, init, k
                return F

        def coface_roots(self, sigma: Collection = []) -> list[Collection]:
                """Returns the roots whose subtrees span the cofaces of `sigma`.

                Note that `sigma` itself is included in the set of its cofaces.

                Parameters:
                        sigma: the simplex to obtain cofaces of. Defaults to the empty set (root node).

                Returns:
                        coface_roots: the coface roots of `sigma`.
                """
                F = []
                self._traverse(4, lambda s: F.append(self.s_type(s)), sigma, 0)  # order, f, init, k
                return F

        def skeleton(self, p: Optional[int] = None, sigma: Collection = []) -> Iterable[Collection]:
                """Returns the simplices in the p-skeleton of `sigma`.

                Note that, when dim(`sigma`) <= `p`, `sigma` is included in the skeleton.

                Parameters:
                        p: the dimension of the skeleton.
                        sigma: the simplex to obtain cofaces of. Defaults to the empty set (root node).

                Returns:
                        list: the simplices in the p-skeleton of `sigma`.
                """
                p = self.dim() if p is None else p
                assert isinstance(int(p), int), f"Invalid argument type '{type(p)}', must be integral"
                F = []
                if p >= 0:
                        self._traverse(5, lambda s: F.append(self.s_type(s)), sigma, p)
                return F

        def simplices(self, p: Optional[int] = None) -> Iterable[Collection]:
                """Returns the p-simplices in the complex."""
                ## NOTE: in either case, to traverse all simplices, we use sigma = []
                F = []
                if p is None:
                        self.traverse("p-skeleton", lambda s: F.append(self.s_type(s)), sigma=[], p=self.dimension)
                else:
                        self.traverse("p-simplices", lambda s: F.append(self.s_type(s)), sigma=[], p=int(p))
                return F

        def faces(self, p: Optional[int] = None, sigma: Optional[Collection] = None) -> Iterable[Collection]:
                """Returns the p-faces of a given simplex."""
                if sigma is None:
                        return self.simplices(p=p)
                else:
                        F = []
                        self.traverse("faces", lambda s: F.append(self.s_type(s)), sigma=sigma)
                        if p is not None:
                                F = list(filter(lambda s: len(s) == (p + 1), F))
                        return F

        def maximal(self) -> Iterable[Collection]:
                """Returns the maximal simplices in the complex."""
                F = []
                self._traverse(7, lambda s: F.append(self.s_type(s)), [], 0)
                return F

        def link(self, sigma: Collection = []) -> Iterable[Collection]:
                """Returns the simplices in the link of `sigma`."""
                F = []
                self._traverse(8, lambda s: F.append(self.s_type(s)), sigma, 0)
                return F

        def expand(self, k: int, f: Optional[Callable[[Collection], bool]] = None) -> None:
                """Performs a k-expansion of the complex.

                This function is particularly useful for expanding clique complexes beyond their 1-skeleton.

                Parameters:
                        k: maximum dimension to expand to.
                        f: boolean predicate which returns whether a simplex should added to the complex (and further expanded).

                Examples:
                        ```{python}
                        from simplextree import SimplexTree
                        from itertools import combinations
                        st = SimplexTree(combinations(range(8), 2))
                        print(st)
                        ```
                        ```{python}
                        st.expand(2, lambda s: 2 in s)  # Expand only triangles containing 2 as a vertex
                        print(st)
                        ```
                        ```{python}
                        st.expand(2) # Expand all 2-cliques
                        print(st)
                        ```
                """
                assert int(k) >= 0, f"Invalid expansion dimension k={k} given"
                if f is None:
                        self._expand(int(k))
                else:
                        assert isinstance(f([]), bool), "Supplied callable must be boolean-valued"
                        self._expand_f(int(k), f)

        def reindex(self, labels: Optional[Sequence] = None) -> None:
                """Reindexes the vertex labels of the complex."""
                if len(self.n_simplices) == 0:
                        return
                labels = list(range(self.n_simplices[0])) if labels is None else list(labels)
                assert len(labels) == self.n_simplices[0]
                self._reindex(labels)

        def __repr__(self) -> str:
                if len(self.n_simplices) == 0:
                        return "< Empty simplex tree >"
                return f"Simplex Tree with {tuple(map(int, self.n_simplices))} {tuple(range(0,self.dimension+1))}-simplices"

        def __iter__(self) -> Iterator[Collection]:
                yield from self.simplices()

        def __contains__(self, s: Collection) -> bool:
                return bool(self.find([s])[0])

        def __len__(self) -> int:
                return int(sum(self.n_simplices))

        def dim(self) -> int:
                return len(self.n_simplices) - 1

        def card(self, p: Optional[int] = None) -> Union[int, tuple]:
                """Returns the cardinality of various skeleta of the complex.

                Parameters:
                        p: dimension parameter. Defaults to None.

                Returns:
                        cardinalities: if p is an integer, the number of p-simplices in the complex. Otherwise a tuple indicating the number of simplices of all dimensions.
                """
                if p is None:
                        return tuple(self.n_simplices)
                else:
                        assert isinstance(int(p), int), f"Invalid argument type '{type(p)}', must be integral"
                        return 0 if p < 0 or p >= len(self.n_simplices) else self.n_simplices[p]

        def print(self, **kwargs):
                ST = np.zeros(shape=(np.sum(self.n_simplices), self.dimension + 1), dtype="<U15")
                ST.fill(" ")
                for i, s in enumerate(self):
                        ST[i, : len(s)] = [str(si) for si in s]
                SC = np.apply_along_axis(lambda x: " ".join(x), axis=0, arr=ST)
                for i, s in enumerate(SC):
                        ending = "\n" if i != (len(SC) - 1) else ""
                        builtins.print(s, sep="", end=ending, **kwargs)

1	# ruff: noqa: PLR0904
2	from __future__ import annotations	5✔
3
4	import builtins	5✔
5	from numbers import Integral	5✔
6	from typing import Callable, Collection, Iterable, Iterator, Optional, Sequence, Union	5✔
7
8	import numpy as np	5✔
9	from _simplextree import SimplexTree as SimplexTreeCpp	5✔
10	from numpy.typing import ArrayLike	5✔
11
12
13	class SimplexTree(SimplexTreeCpp):	5✔
14	"""SimplexTree provides lightweight wrapper around a Simplex Tree data structure.
15
16	This class exposes a native extension module wrapping a simplex tree implemented with modern C++.
17
18	The Simplex Tree was originally introduced in the paper:
19	> Boissonnat, Jean-Daniel, and Clément Maria. "The simplex tree: An efficient data structure for general simplicial complexes." Algorithmica 70.3 (2014): 406-427.
20
21	Attributes:
22	n_simplices: number of simplices
23	dimension: maximal dimension of the complex
24	id_policy: policy for generating new vertex ids
25	vertices: 0-simplices in the complex.
26	edges: 1-simplices in the complex.
27	triangles: 2-simplices in the complex.
28	quads: 3-simplices in the complex.
29	connected_components: connected component ids.
30	"""
31
32	def __init__(self, simplices: Optional[Iterable[Collection]] = None, s_type: Callable = tuple) -> None:	5✔
33	assert callable(s_type), "Simplex type must have a constructor"	5✔
34	SimplexTreeCpp.__init__(self)	5✔
35	if simplices is not None:	5✔
36	self.insert(simplices)	5✔
37	self.s_type = s_type	5✔
38
39	def insert(self, simplices: Iterable[Collection]) -> None:	5✔
40	"""Inserts simplices into the Simplex Tree.
41
42	By definition, inserting a simplex also inserts all of its faces. If the simplex already exists in the complex, the tree is not modified.
43
44	Parameters:
45	simplices: Iterable of simplices to insert (each of which are SimplexLike)
46
47	::: {.callout-note}
48	If the iterable is an 2-dim np.ndarray, then a p-simplex is inserted along each contiguous p+1 stride.
49	Otherwise, each element of the iterable to casted to a Simplex and then inserted into the tree.
50	:::
51
52	Examples:
53	```{python}
54	from simplextree import SimplexTree
55	st = SimplexTree([range(3)])
56	print(st)
57	```
58	```{python}
59	st.insert([[0,1]])
60	print(st)
61	```
62	"""
63	if isinstance(simplices, np.ndarray):	5✔
64	simplices = np.sort(simplices, axis=1).astype(np.uint16)	5✔
65	assert simplices.ndim in {1, 2}, "dimensions should be 1 or 2"	5✔
66	self._insert(simplices)	5✔
67	else:
68	assert isinstance(simplices, Iterable), f"Invalid simplices type '{type(simplices)}' given"	5✔
69	self._insert_list(list(map(lambda x: np.asarray(x, dtype=np.uint16), simplices)))	5✔
70
71	def remove(self, simplices: Iterable[Collection]):	5✔
72	"""Removes simplices into the Simplex Tree.
73
74	By definition, removing a face also removes all of its cofaces. If the simplex does not exist in the complex, the tree is not modified.
75
76	Parameters:
77	simplices: Iterable of simplices to insert (each of which are SimplexLike).
78
79	::: {.callout-note}
80	If the iterable is an 2-dim np.ndarray, then a p-simplex is removed along each contiguous p+1 stride.
81	Otherwise, each element of the iterable to casted to a Simplex and then removed from the tree.
82	:::
83
84	Examples:
85	```{python}
86	from simplextree import SimplexTree
87	st = SimplexTree([range(3)])
88	print(st)
89	```
90	```{python}
91	st.remove([[0,1]])
92	print(st)
93	```
94	"""
95	if isinstance(simplices, np.ndarray):	5✔
UNCOV 96	simplices = np.sort(simplices, axis=1).astype(np.uint16)	×
97	assert simplices.ndim in {1, 2}, "dimensions should be 1 or 2"	×
UNCOV 98	self._remove(simplices)	×
99	elif isinstance(simplices, Iterable):	5✔
100	self._remove_list(list(map(lambda x: np.asarray(x, dtype=np.uint16), simplices)))	5✔
101	else:
UNCOV 102	raise ValueError("Invalid type given")	×
103
104	def find(self, simplices: Iterable[Collection]) -> np.ndarray:	5✔
105	"""Finds whether simplices exist in Simplex Tree.
106
107	Parameters:
108	simplices: Iterable of simplices to insert (each of which are SimplexLike)
109
110	Returns:
111	found: boolean array indicating whether each simplex was found in the complex
112
113	::: {.callout-note}
114	If the iterable is an 2-dim np.ndarray, then the p-simplex to find is given by each contiguous p+1 stride.
115	Otherwise, each element of the iterable to casted to a Simplex and then searched for in the tree.
116	:::
117	"""
118	if isinstance(simplices, np.ndarray):	5✔
UNCOV 119	simplices = np.array(simplices, dtype=np.int16)	×
UNCOV 120	assert simplices.ndim in {1, 2}, "dimensions should be 1 or 2"	×
121	return self._find(simplices)	×
122	elif isinstance(simplices, Iterable):	5✔
123	return self._find_list([tuple(s) for s in simplices])	5✔
124	else:
125	raise ValueError("Invalid type given")	×
126
127	def adjacent(self, vertices: Iterable[Collection]):	5✔
128	"""Finds adjacent vertices of a collection of vertices."""
UNCOV 129	return self._adjacent(list(map(lambda x: np.asarray(x, dtype=np.uint16), vertices)))	×
130
131	def collapse(self, sigma: Collection, tau: Collection) -> bool:	5✔
132	r"""Performs an elementary collapse on two given simplices.
133
134	Checks whether its possible to collapse $\sigma$ through $\tau$, and if so, both simplices are removed.
135	A simplex $\sigma$ is said to be collapsible through one of its faces $\tau$ if $\sigma$ is the only coface of $\tau$ (excluding $\tau$ itself).
136
137	Parameters:
138	sigma: maximal simplex to collapse
139	tau: face of sigma to collapse
140
141	Returns:
142	whether the pair was collapsed
143
144	Examples:
145	```{python}
146	from simplextree import SimplexTree
147	st = SimplexTree([[0,1,2]])
148	print(st)
149	```
150	```{python}
151	st.collapse([0,1,2], [1,2])
152	print(st)
153	```
154	"""
155	if len(sigma) != (len(tau) + 1): # , f"Simplex {tau} not in the boundary of simplex {sigma}"	5✔
156	return False	5✔
157	success = self._collapse(tau, sigma)	5✔
158	return success	5✔
159
160	def contract(self, pair: Collection) -> None:	5✔
161	r"""Performs an pair contraction.
162
163	This function performs an pair contraction: given a pair of vertices $(va, vb)$, vertex $vb$ is said to contract
164	to $va$ if $vb$ is removed from the complex and the link of $va$ is augmented with the link of $vb$.
165
166	Some notes about `pair` are in order:
167	- `pair` is not sorted like other simplex inputs
168	- The second vertex is always contracted to the first
169	- `pair` need not be an existing simplex (edge) in the complex
170	- Contraction is not symmetric.
171
172	Parameters:
173	pair: pair to contract
174
175	Returns:
176	whether the pair was contracted
177
178	Examples:
179	```{python}
180	from simplextree import SimplexTree
181	st = SimplexTree([[0,1,2]])
182	st.print()
183	```
184	```{python}
185	st.contract([0,2])
186	st.print()
187	```
188	"""
189	success = self._contract(pair)	5✔
190	return success	5✔
191
192	def vertex_collapse(self, u: int, v: int, w: int) -> bool:	5✔
193	"""Maps a pair of vertices into a single vertex.
194
195	Parameters:
196	u: the first vertex in the free pair.
197	v: the second vertex in the free pair.
198	w: the target vertex to collapse to.
199
200	Returns:
201	collapsed: whether the collapse was performed.
202	"""
UNCOV 203	u, v, w = int(u), int(v), int(w)	×
UNCOV 204	assert all([isinstance(e, Integral) for e in [u, v, w]]), "Unknown vertex types given; must be integral"	×
UNCOV 205	return self._vertex_collapse(u, v, w)	×
206
207	def degree(self, vertices: Optional[ArrayLike] = None) -> Union[ArrayLike, int]:	5✔
208	"""Computes the degree of select vertices in the trie.
209
210	Parameters:
211	vertices: If no vertices are specified, all degrees are computed. Non-existing vertices by default have degree 0.
212
213	Returns:
214	degree of each vertex id given in 'vertices'.
215	"""
216	if vertices is None:	5✔
217	return self._degree_default()	5✔
218	elif isinstance(vertices, Iterable):	5✔
219	vertices = np.fromiter(iter(vertices), dtype=np.int16)	5✔
220	assert vertices.ndim == 1, "Invalid shape given; Must be flattened array of vertex ids"	5✔
221	return self._degree(vertices)	5✔
222	else:
UNCOV 223	raise ValueError(f"Invalid type {type(vertices)} given")	×
224
225	# PREORDER = 0, LEVEL_ORDER = 1, FACES = 2, COFACES = 3, COFACE_ROOTS = 4,
226	# K_SKELETON = 5, K_SIMPLICES = 6, MAXIMAL = 7, LINK = 8
227	def traverse(self, order: str = "preorder", f: Callable = builtins.print, sigma: Collection = [], p: int = 0) -> None:	5✔
228	"""Traverses the simplex tree in the specified order, calling `f` on each simplex encountered.
229
230	Supported traversals include breadth-first / level order ("bfs", "levelorder"), depth-first / prefix ("dfs", "preorder").
231	faces, cofaces, coface roots ("coface_roots"), p-skeleton, p-simplices, maximal simplices ("maximal"), and link.
232
233	Where applicable, each traversal begins its traversal `sigma`, which defaults to the empty set (root node).
234
235	Parameters:
236	order: the type of traversal of the simplex tree to execute.
237	f: a function to evaluate on every simplex in the traversal. Defaults to print.
238	sigma: simplex to start the traversal at, where applicable. Defaults to the root node (empty set).
239	p: dimension of simplices to restrict to, where applicable. Defaults to 0.
240
241	Returns:
242	None
243	"""
244	# todo: handle kwargs
245	assert isinstance(order, str)	5✔
246	order = order.lower()	5✔
247	if order in {"dfs", "preorder"}:	5✔
248	order = 0	5✔
249	elif order in {"bfs", "level_order", "levelorder"}:	5✔
250	order = 1	5✔
251	elif order == "faces":	5✔
UNCOV 252	order = 2	×
253	elif order == "cofaces":	5✔
254	order = 3	5✔
255	elif order == "coface_roots":	5✔
256	order = 4	5✔
257	elif order == "p-skeleton":	5✔
258	order = 5	5✔
259	elif order == "p-simplices":	5✔
260	order = 6	5✔
261	elif order == "maximal":	5✔
262	order = 7	5✔
263	elif order == "link":	×
UNCOV 264	order = 8	×
265	else:
UNCOV 266	raise ValueError(f"Unknown order '{order}' specified")	×
267	assert isinstance(int(p), int), f"Invalid argument type '{type(p)}', must be integral"	5✔
268	sigma = [] if sigma is None else sigma	5✔
269	if p >= 0:	5✔
270	self._traverse(order, f, sigma, p) # order, f, init, k	5✔
271
272	def cofaces(self, sigma: Collection = []) -> list[Collection]:	5✔
273	"""Returns the cofaces of `sigma`.
274
275	Note, by definition, `sigma` is defined as a coface of itself.
276
277	Parameters:
278	sigma: the simplex to obtain cofaces of.
279
280	Returns:
281	cofaces: the cofaces of `sigma`.
282	"""
283	if sigma == [] or len(sigma) == 0:	5✔
UNCOV 284	return self.simplices()	×
285	F = []	5✔
286	self._traverse(3, lambda s: F.append(self.s_type(s)), sigma, 0) # order, f, init, k	5✔
287	return F	5✔
288
289	def coface_roots(self, sigma: Collection = []) -> list[Collection]:	5✔
290	"""Returns the roots whose subtrees span the cofaces of `sigma`.
291
292	Note that `sigma` itself is included in the set of its cofaces.
293
294	Parameters:
295	sigma: the simplex to obtain cofaces of. Defaults to the empty set (root node).
296
297	Returns:
298	coface_roots: the coface roots of `sigma`.
299	"""
300	F = []	5✔
301	self._traverse(4, lambda s: F.append(self.s_type(s)), sigma, 0) # order, f, init, k	5✔
302	return F	5✔
303
304	def skeleton(self, p: Optional[int] = None, sigma: Collection = []) -> Iterable[Collection]:	5✔
305	"""Returns the simplices in the p-skeleton of `sigma`.
306
307	Note that, when dim(`sigma`) <= `p`, `sigma` is included in the skeleton.
308
309	Parameters:
310	p: the dimension of the skeleton.
311	sigma: the simplex to obtain cofaces of. Defaults to the empty set (root node).
312
313	Returns:
314	list: the simplices in the p-skeleton of `sigma`.
315	"""
316	p = self.dim() if p is None else p	5✔
317	assert isinstance(int(p), int), f"Invalid argument type '{type(p)}', must be integral"	5✔
318	F = []	5✔
319	if p >= 0:	5✔
320	self._traverse(5, lambda s: F.append(self.s_type(s)), sigma, p)	5✔
321	return F	5✔
322
323	def simplices(self, p: Optional[int] = None) -> Iterable[Collection]:	5✔
324	"""Returns the p-simplices in the complex."""
325	## NOTE: in either case, to traverse all simplices, we use sigma = []
326	F = []	5✔
327	if p is None:	5✔
328	self.traverse("p-skeleton", lambda s: F.append(self.s_type(s)), sigma=[], p=self.dimension)	5✔
329	else:
330	self.traverse("p-simplices", lambda s: F.append(self.s_type(s)), sigma=[], p=int(p))	5✔
331	return F	5✔
332
333	def faces(self, p: Optional[int] = None, sigma: Optional[Collection] = None) -> Iterable[Collection]:	5✔
334	"""Returns the p-faces of a given simplex."""
UNCOV 335	if sigma is None:	×
336	return self.simplices(p=p)	×
337	else:
UNCOV 338	F = []	×
UNCOV 339	self.traverse("faces", lambda s: F.append(self.s_type(s)), sigma=sigma)	×
UNCOV 340	if p is not None:	×
UNCOV 341	F = list(filter(lambda s: len(s) == (p + 1), F))	×
UNCOV 342	return F	×
343
344	def maximal(self) -> Iterable[Collection]:	5✔
345	"""Returns the maximal simplices in the complex."""
346	F = []	5✔
347	self._traverse(7, lambda s: F.append(self.s_type(s)), [], 0)	5✔
348	return F	5✔
349
350	def link(self, sigma: Collection = []) -> Iterable[Collection]:	5✔
351	"""Returns the simplices in the link of `sigma`."""
352	F = []	5✔
353	self._traverse(8, lambda s: F.append(self.s_type(s)), sigma, 0)	5✔
354	return F	5✔
355
356	def expand(self, k: int, f: Optional[Callable[[Collection], bool]] = None) -> None:	5✔
357	"""Performs a k-expansion of the complex.
358
359	This function is particularly useful for expanding clique complexes beyond their 1-skeleton.
360
361	Parameters:
362	k: maximum dimension to expand to.
363	f: boolean predicate which returns whether a simplex should added to the complex (and further expanded).
364
365	Examples:
366	```{python}
367	from simplextree import SimplexTree
368	from itertools import combinations
369	st = SimplexTree(combinations(range(8), 2))
370	print(st)
371	```
372	```{python}
373	st.expand(2, lambda s: 2 in s) # Expand only triangles containing 2 as a vertex
374	print(st)
375	```
376	```{python}
377	st.expand(2) # Expand all 2-cliques
378	print(st)
379	```
380	"""
381	assert int(k) >= 0, f"Invalid expansion dimension k={k} given"	5✔
382	if f is None:	5✔
383	self._expand(int(k))	5✔
384	else:
385	assert isinstance(f([]), bool), "Supplied callable must be boolean-valued"	5✔
386	self._expand_f(int(k), f)	5✔
387
388	def reindex(self, labels: Optional[Sequence] = None) -> None:	5✔
389	"""Reindexes the vertex labels of the complex."""
390	if len(self.n_simplices) == 0:	5✔
UNCOV 391	return	×
392	labels = list(range(self.n_simplices[0])) if labels is None else list(labels)	5✔
393	assert len(labels) == self.n_simplices[0]	5✔
394	self._reindex(labels)	5✔
395
396	def __repr__(self) -> str:	5✔
397	if len(self.n_simplices) == 0:	5✔
398	return "< Empty simplex tree >"	5✔
399	return f"Simplex Tree with {tuple(map(int, self.n_simplices))} {tuple(range(0,self.dimension+1))}-simplices"	5✔
400
401	def __iter__(self) -> Iterator[Collection]:	5✔
402	yield from self.simplices()	5✔
403
404	def __contains__(self, s: Collection) -> bool:	5✔
405	return bool(self.find([s])[0])	5✔
406
407	def __len__(self) -> int:	5✔
UNCOV 408	return int(sum(self.n_simplices))	×
409
410	def dim(self) -> int:	5✔
UNCOV 411	return len(self.n_simplices) - 1	×
412
413	def card(self, p: Optional[int] = None) -> Union[int, tuple]:	5✔
414	"""Returns the cardinality of various skeleta of the complex.
415
416	Parameters:
417	p: dimension parameter. Defaults to None.
418
419	Returns:
420	cardinalities: if p is an integer, the number of p-simplices in the complex. Otherwise a tuple indicating the number of simplices of all dimensions.
421	"""
422	if p is None:	5✔
423	return tuple(self.n_simplices)	5✔
424	else:
425	assert isinstance(int(p), int), f"Invalid argument type '{type(p)}', must be integral"	5✔
426	return 0 if p < 0 or p >= len(self.n_simplices) else self.n_simplices[p]	5✔
427
428	def print(self, **kwargs):	5✔
UNCOV 429	ST = np.zeros(shape=(np.sum(self.n_simplices), self.dimension + 1), dtype="<U15")	×
UNCOV 430	ST.fill(" ")	×
UNCOV 431	for i, s in enumerate(self):	×
UNCOV 432	ST[i, : len(s)] = [str(si) for si in s]	×
UNCOV 433	SC = np.apply_along_axis(lambda x: " ".join(x), axis=0, arr=ST)	×
UNCOV 434	for i, s in enumerate(SC):	×
UNCOV 435	ending = "\n" if i != (len(SC) - 1) else ""	×
UNCOV 436	builtins.print(s, sep="", end=ending, **kwargs)	×

peekxc / simplextree-py / 12285111698

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous