Ask Your Question
1

copying lists, embedded multigraphs

asked 2020-12-08 03:34:24 +0200

Ingrid gravatar image

updated 2020-12-08 10:21:33 +0200

slelievre gravatar image

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 flag offensive close merge delete

Comments

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.

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

1 Answer

Sort by ยป oldest newest most voted
1

answered 2020-12-08 10:34:08 +0200

slelievre gravatar image

updated 2021-02-12 12:12:04 +0200

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.

edit flag offensive delete link more

Comments

Thanks heaps!!!

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

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2020-12-08 03:34:24 +0200

Seen: 147 times

Last updated: Feb 12