Lecture 5: Simplicial maps and filtrations#
To save time, all the exercises are solved already. So please read the code and the comments, run it, and play with the examples.
As in the previous notebooks, plotting and example data are in a separate python file:
lecture5_helpers.py.
⚠️ Vertices IDs. To avoid confusing vertex ids with filtration values, we name vertices with letters, as in the lecture ⚠️. You should be mindful about this:
We will use
SimplexTreewhich needs integers for its vertices, so we convert with two helpers:letter2int('A')is0('B'is1, …) andint2letter(0)is'A'.You have to be careful, as to insert a simplex you have to write:
insert([letter2int('A'), letter2int('C'), letter2int('E')]), notinsert(['A', 'C', 'E']). The same goes forassign_filtration,findand the other methods.Similarly, you get back from a
SimplexTree(e.g. fromget_simplices()) has integer vertices: useint2letterto turn them back into letters.
import matplotlib.pyplot as plt
import gudhi
from lecture5_helpers import (
letter2int, int2letter, # 'A' -> 0 and 0 -> 'A': SimplexTree vertices are integers
plot_map, plot_filtration, # pictures of a vertex map and of a filtration
K, K_COORDS, L, L_COORDS, # slide 16: K sits inside L
GRAPH_COORDS, # slides 5-9
)
plt.rcParams["figure.dpi"] = 110
1. Simplicial maps#
A vertex map \(f: V(K) \to V(L)\) is simplicial if every simplex of \(K\) goes to a simplex of \(L\).
In Python, we can represent such a map with a
Dict, where thekeysare the vertices of \(K\) and theirvaluesare their images \(f(K)\) (vertices in \(L\)).We could also use a Python function, or other objects, to represent the map, but the
Dictapproach is simple and enough to get the job done for finite simplicial complexes (or complexes without “too many” simplices).
# Below is a function that checks whether a given map f: K -> L is simplicial.
# It uses SimplexTree from GUDHI to represent the simplicial complexes K and L.
# Read through the code to familiarize yourself with the definitions from the lecture and with the GUDHI library.
def is_simplicial_map(K: gudhi.SimplexTree, L: gudhi.SimplexTree, f: dict[str, str]) -> bool:
# we check the images of all simplices in K, and see if they are simplices in L
for simplex, _ in K.get_simplices():
# the image of the simplex: the images of its vertices, without repeats
# the set data structure is useful here, because it automatically removes duplicates
image = set() # image of the current simplex under f
for v in simplex: # for each vertex in the current simplex (an int: SimplexTree stores integers)
image_letter = f[int2letter(v)] # f works with letters
image.add(letter2int(image_letter)) # back to an int, to look it up in L
# check if the image of the simplex is a simplex in L
if not L.find(list(image)):
return False
return True
We now visualize some maps using the helper plot_map that colours each vertex of \(K\) like its image in \(L\), and shadows in red the whole image of \(K\) in \(L\).
# Here is a collection of some maps for you to visualize and check whether they are valid simplicial maps.
maps = {
"inclusion": {"A": "A", "B": "B", "C": "C", "D": "D", "E": "E"},
"B goes to E": {"A": "A", "B": "E", "C": "C", "D": "D", "E": "E"},
"swap A and B": {"A": "B", "B": "A", "C": "C", "D": "D", "E": "E"},
# a constant map is always a simplicial map, whatever K, L and the vertex you pick.
# you can try to write the proof on paper: it is short!
"everything to F": {"A": "F", "B": "F", "C": "F", "D": "F", "E": "F"},
# Your turn: add your own map following the pattern above (vertex in K: image in L).
}
for name in maps:
f = maps[name]
plot_map(K, K_COORDS, L, L_COORDS, f, title=f"{name}: simplicial? {is_simplicial_map(K, L, f)}")
2. Filtrations#
In the first notebook of the course we explained that every simplex in a SimplexTree carries a number that we have been ignoring: its filtration value, the second entry of each pair in st.get_simplices(). Now we use it.
Today we have finally learned that a filtration is a nested sequence of subcomplexes \(\emptyset = K_0 \subseteq K_1 \subseteq \dots \subseteq K_n = K\).
A function \(f:K\rightarrow\mathbb{R}\) induces a filtration, \(K_i = \{\sigma : f(\sigma) \le a_i\}\), if if it is monotone: \(f(\tau) \le f(\sigma)\) whenever \(\tau\) is a face of \(\sigma\).
We will use plot_filtration to visualize filtrations: It draws each \(K_i\) using grey to represent vertices are not in \(K_i\) yet. Here is the example from slide 6:
example_2 = gudhi.SimplexTree()
for v in ["A", "C", "D", "F", "G"]:
example_2.insert([letter2int(v)], filtration=1) # insert(simplex, filtration=value)
example_2.insert([letter2int("A"), letter2int("C")], filtration=2)
example_2.insert([letter2int("D"), letter2int("F")], filtration=3)
example_2.insert([letter2int("A"), letter2int("F")], filtration=4)
example_2.insert([letter2int("B")], filtration=5)
# vertex E which we did not explicitly add yet gets filtration=5 too
# Remember that in SimplexTree, insert adds missing faces with the same value
example_2.insert([letter2int("E"), letter2int("G")], filtration=5)
example_2.insert([letter2int("A"), letter2int("D")], filtration=6)
plot_filtration(example_2, GRAPH_COORDS)
Is it monotone?#
Your turn: write the function is_monotone that checks that no face has a bigger value than its simplex.
TIP that for each simplex you can just compare its value to that of its faces with one vertex less, obtained with st.get_boundaries(simplex). Checking only this condition is enough, can you think of why?
def is_monotone(st: gudhi.SimplexTree) -> bool:
raise NotImplementedError("Your turn: implement this function to check whether the filtration is monotone.")
print("example_2 is monotone:", is_monotone(example_2))
Values on the vertices, extended with max#
If we have a function that gives each vertex a real value, we can always induce a valid filtration by assigning each simplex the biggest value of all its vertices.
def extend_with_max(st: gudhi.SimplexTree, vertex_values: dict[str, float]) -> None:
for simplex, value in st.get_simplices():
values = [vertex_values[int2letter(v)] for v in simplex] # the values of its vertices (vertex_values uses letters)
st.assign_filtration(simplex, max(values)) # assign_filtration replaces the old value
# Your turn: any values work. These are the heights of the vertices, so L grows from the bottom up.
my_values = {"A": 0.32, "B": 0.71, "C": 0.21, "D": 0.0, "E": 0.65, "F": 0.49, "G": 0.06}
my_L = gudhi.SimplexTree(L) # a copy, so that L doesn't change
extend_with_max(my_L, my_values)
print("monotone:", is_monotone(my_L))
plot_filtration(my_L, L_COORDS)