ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 08 Dec 2020 11:09:49 +0100copying lists, embedded multigraphshttps://ask.sagemath.org/question/54605/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!Tue, 08 Dec 2020 03:34:24 +0100https://ask.sagemath.org/question/54605/copying-lists-embedded-multigraphs/Comment by slelievre for <p>I am working with planar, embedded, labelled multigraphs.
I am trying to define a function <code>face_modification</code> 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 <code>face_modification</code> below, with <code>Gf=F1</code>,
my original list (<code>F1</code>) is being altered,
and I can't figure out why or how to prevent it.</p>
<p>Here, <code>G1</code> is the labelled graph without double edges,
<code>Gd</code> is the graph of double edges, <code>Gt</code> is the graph
of triple edges, and <code>Gf</code> is a list, the <code>i</code>-th entry
of which is a list of labelled edges on the boundary of face <code>i</code>.</p>
<pre><code>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'
</code></pre>
<p>Thanks a lot for your help!</p>
https://ask.sagemath.org/question/54605/copying-lists-embedded-multigraphs/?comment=54606#post-id-54606Can 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.Tue, 08 Dec 2020 10:24:16 +0100https://ask.sagemath.org/question/54605/copying-lists-embedded-multigraphs/?comment=54606#post-id-54606Answer by slelievre for <p>I am working with planar, embedded, labelled multigraphs.
I am trying to define a function <code>face_modification</code> 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 <code>face_modification</code> below, with <code>Gf=F1</code>,
my original list (<code>F1</code>) is being altered,
and I can't figure out why or how to prevent it.</p>
<p>Here, <code>G1</code> is the labelled graph without double edges,
<code>Gd</code> is the graph of double edges, <code>Gt</code> is the graph
of triple edges, and <code>Gf</code> is a list, the <code>i</code>-th entry
of which is a list of labelled edges on the boundary of face <code>i</code>.</p>
<pre><code>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'
</code></pre>
<p>Thanks a lot for your help!</p>
https://ask.sagemath.org/question/54605/copying-lists-embedded-multigraphs/?answer=54607#post-id-54607The 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
- [https://doc.sagemath.org/html/en/thematic_tutorials](https://doc.sagemath.org/html/en/thematic_tutorials)
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.Tue, 08 Dec 2020 10:34:08 +0100https://ask.sagemath.org/question/54605/copying-lists-embedded-multigraphs/?answer=54607#post-id-54607Comment by Ingrid for <p>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.</p>
<p>The workaround is to use <code>deepcopy</code>
which recursively copies nested lists.</p>
<p>Here is a simpler illustration of that.</p>
<p>The problem with copying nested lists with <code>copy</code>:</p>
<pre><code>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]]
</code></pre>
<p>How <code>deepcopy</code> avoids this problem:</p>
<pre><code>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]]
</code></pre>
<hr>
<p>Besides that, the code could be streamlined
by iterating by values instead of by indices.</p>
<p>Suggestion: go through some of the tutorial at</p>
<ul>
<li><a href="https://doc.sagemath.org/html/en/thematic_tutorials">https://doc.sagemath.org/html/en/thematic_tutorials</a></li>
</ul>
<p>in particular</p>
<ul>
<li>Programming in Python and Sage</li>
<li>Comprehensions, iterators and iterables</li>
</ul>
<hr>
<p>Here is an attempt at making the code from the question more concise.</p>
<p>In this rewrite,</p>
<ul>
<li><code>edge_on_faces</code> returns booleans rather than integers</li>
<li>iterating by values insted of by index makes loop simpler</li>
<li><code>vars</code> are in string form since they are only used as such</li>
<li>double comprehension avoids summing list when defining <code>vars</code></li>
<li><code>any</code> avoids building the whole list if ot necessary</li>
<li>raising an exception replaces returning the string <code>'error'</code></li>
<li>copying <code>Gf</code> is done only once</li>
<li>avoid summing lists and assigning to <code>B</code>; instead append to <code>GGf</code> and return it</li>
</ul>
<p>Here we go. All that is missing is to fill in
the documentation string for each function.</p>
<pre><code>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')
</code></pre>
<p>The changes should also make the code faster.</p>
<p>There might be ways to simplify further.</p>
<hr>
<p>This part of the code modifies a list it is iterating on:</p>
<pre><code> for k in range(len(p)):
if str(p[k][2]) == vars[i]:
p.remove(p[k])
</code></pre>
<p>If <code>vars[i]</code> can occur only once in <code>p</code> 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.</p>
<p>If <code>vars[i]</code> can occur several times in <code>p</code>, the code
as written may not be doing what was intended.</p>
https://ask.sagemath.org/question/54605/copying-lists-embedded-multigraphs/?comment=54608#post-id-54608Thanks heaps!!!Tue, 08 Dec 2020 11:09:49 +0100https://ask.sagemath.org/question/54605/copying-lists-embedded-multigraphs/?comment=54608#post-id-54608