# copying lists, embedded multigraphs

I am working with planar, embedded, labelled multigraphs. I am trying to define a function face_modification that modifies the set of faces when an edge of the graph is deleted. I thought that when taking a copy of a list, and altering the copy, the original list would not change. However, when I evaluate the function face_modification below, with Gf=F1, my original list (F1) is being altered, and I can't figure out why or how to prevent it.

Here, G1 is the labelled graph without double edges, Gd is the graph of double edges, Gt is the graph of triple edges, and Gf is a list, the i-th entry of which is a list of labelled edges on the boundary of face i.

def edge_on_faces(j, S, Gf, G1, Gd, Gt):
variables = ([G1.edges()[i][2] for i in range(len(G1.edges()))] +
[Gd.edges()[i][2] for i in range(len(Gd.edges()))] +
[Gt.edges()[i][2] for i in range(len(Gt.edges()))])
if j in range(len(variables)):
if [str(Gf[n][q][2]) == str(variables[j])
for n in S for q in range(len(Gf[n]))].count(True) > 0:
return 1
else:
return 0
else:
return 0

def face_modification(i, Gf, G1, Gd, Gt):
variables = ([G1.edges()[k][2] for k in range(len(G1.edges()))] +
[Gd.edges()[k][2] for k in range(len(Gd.edges()))] +
[Gt.edges()[k][2] for k in range(len(Gt.edges()))])
l = [m for m in range(len(Gf)) if edge_on_faces(i, [m], Gf, G1, Gd, Gt)==1]
# PF: list of two faces in Gf with the ith edge on the boundary
PF = [Gf.copy()[l[p]] for p in range(len(l))]
GGf = Gf.copy()
for m in range(len(PF)):
GGf.remove(PF[m])
for k in range(len(PF[m])):
if str(PF[m][k][2]) == str(variables[i]):
PF[m].remove(PF[m][k])
else:
PF[m] = PF[m]
if len(PF) == 2:
B = GGf + [PF[0] + PF[1]]
return B
else:
return 'error'


Thanks a lot for your help!

edit retag close merge delete

Can you add an example of using the function?

It helps if one can reproduce the problem just by copying and pasting the code in the question.

( 2020-12-08 10:24:16 +0200 )edit

Sort by ยป oldest newest most voted

The thing is that when copying a list of lists, the inside lists are not copied but end up being the same lists as in the original list.

The workaround is to use deepcopy which recursively copies nested lists.

Here is a simpler illustration of that.

The problem with copying nested lists with copy:

sage: a = [[0, 0], [0, 0], [0, 0]]
sage: b = a.copy()
sage: b[0][0] = 1
sage: b
[[1, 0], [0, 0], [0, 0]]
sage: a
[[1, 0], [0, 0], [0, 0]]


How deepcopy avoids this problem:

sage: c =  [[0, 0], [0, 0], [0, 0]]
sage: d = deepcopy(c)
sage: d[0][0] = 1
sage: d
[[1, 0], [0, 0], [0, 0]]
sage: c
[[0, 0], [0, 0], [0, 0]]


Besides that, the code could be streamlined by iterating by values instead of by indices.

Suggestion: go through some of the tutorial at

in particular

• Programming in Python and Sage
• Comprehensions, iterators and iterables

Here is an attempt at making the code from the question more concise.

In this rewrite,

• edge_on_faces returns booleans rather than integers
• iterating by values insted of by index makes loop simpler
• vars are in string form since they are only used as such
• double comprehension avoids summing list when defining vars
• any avoids building the whole list if ot necessary
• raising an exception replaces returning the string 'error'
• copying Gf is done only once
• avoid summing lists and assigning to B; instead append to GGf and return it

Here we go. All that is missing is to fill in the documentation string for each function.

def edge_on_faces(j, S, Gf, G1, Gd, Gt):
r"""
Return whether ...
"""
vars = [str(e[2]) for G in (G1, Gd, Gt) for e in G.edges()]
return (0 <= j < len(vars)
and any(str(e[2]) == vars[j] for n in S for e in Gf[n]))

def face_modification(i, Gf, G1, Gd, Gt):
r"""
Return ...
"""
vars = [str(e[2]) for G in (G1, Gd, Gt) for e in G.edges()]
l = [m for m in range(len(Gf)) if edge_on_faces(i, [m], Gf, G1, Gd, Gt)]
# PF: list of two-faces in Gf that have edge i on their boundary
GGf = deepcopy(Gf)
PF = [GGf[e] for e in l]
for p in PF:
GGf.remove(p)
for k in range(len(p)):
if str(p[k][2]) == vars[i]:
p.remove(p[k])
if len(PF) == 2:
GGf.append(PF[0] + PF[1])
return GGf
else:
raise ValueError('unexpected situation in face_modification')


The changes should also make the code faster.

There might be ways to simplify further.

This part of the code modifies a list it is iterating on:

        for k in range(len(p)):
if str(p[k][2]) == vars[i]:
p.remove(p[k])


If vars[i] can occur only once in p it's all right; in that case one could exit the for loop as soon as the corresponding removal has been done: no need to keep checking the rest of the list.

If vars[i] can occur several times in p, the code as written may not be doing what was intended.

more

Thanks heaps!!!

( 2020-12-08 11:09:49 +0200 )edit