get_embedding(): remove vertices that do not exist #40057
Conversation
|
Documentation preview for this PR (built with commit 2bc85db; changes) is ready! 🎉 |
Good point. There appears to be a typo in G._embedding = {u: [v for v in embedding[u] if u in G] for u in G}
^^^^^^^^^but it should be G._embedding = {u: [v for v in embedding[u] if v in G] for u in G}
^^^^^^^^^Fixing this typo would be another way to fix #40054 and it would make this PR superfluous. But following the spirit of #33760, wouldn't it be better in terms of performance and code maintainability to remove this code from |
|
I agree with you that the code could be removed from subgraph (and may be other methods) and that method |
|
the CIs report several failing doctests. Please check |
An embedding is a Python dictionary d where d[v] is the list of neighbors of vertex v. When vertices get deleted, the embedding is not updated immediately so get_embedding() needs to remove all vertices in d[v] that no longer exist. This commit fixes sagemath#40054 where not enough vertices in d[v] were removed.
subgraph() can be lazy because get_embedding() will remove the old vertices of the supergraph from the embedding.
This generates a nicer error if the caller provided an invalid embedding. genus() call this function with `embedding=self._embedding` but `self._embedding` might no longer be valid after subgraph operations.
|
The CI was failing because I made a silly mistake. I force-pushed a new version of 44c58a3 where the embedding is preserved by |
|
The failing check Conda (ubuntu, Python 3.12, all, editable) is unrelated to this PR, see #40087. |
The behavior did not change. When a vertex is added, the old embedding becomes invalid, so emb = {0: [1], 1: [0]}
for ds in ("dense", "sparse"):
G = Graph("A_", data_structure=ds)
G.set_embedding(emb)
G.add_vertex()
assert G._embedding == emb
assert G._check_embedding_validity() == False
assert G.get_embedding() is None |
A graph embedding is a Python dictionary
dwhered[v]is the list of neighbors of vertex v. When vertices get deleted, the embedding is not updated soget_embedding()needs to remove all vertices ind[v]that no longer exist. This commit fixes #40054 where not enough vertices ind[v] were removed.This resulted in
LookupErrorbeing thrown byget_embedding()if the graph is immutable.📝 Checklist