Ask Your Question
0

delete_edge() Won't Delete Edges from Graph

asked 2015-08-07 22:47:11 +0200

Samuel Yusim gravatar image

updated 2015-08-07 22:48:00 +0200

Title says it all, really. The following code only outputs complete graphs and I can't figure out why.

def SR(G):
H = G
for a in G.vertices():
    for b in G.vertices():
        H.add_edge(a,b)

for v in G.vertices():
    for w in G.vertices():
        for n in G[v]:
            for m in G[w]:
                if H.distance(v, m) >= H.distance(v, w):
                    G.delete_edge(v , w)

                elif H.distance(n, w)  H.distance(v, w):
                    G.delete_edge(v , w)

return G

This is supposed to output the strong resolving graph of a particular graph $G$, which can be defined to be the graph formed by taking the vertices of $G$ and making a pair $u,v$ adjacent if for all $n \in N(u)$ and all $n' \in N(v)$, we have $d(n, v) \leq d(u, v)$ and $d(u, n') \leq d(u, v)$. In other words we connect vertices if nothing in their neighborhoods in the original graph is farther. Being new to sage I have no idea why my code above wouldn't work. What do I do?

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
2

answered 2015-08-07 23:56:11 +0200

Nathann gravatar image

H = G does not make a copy of the graph. G and H are the very same object in memory, and if you modify one the other also contains the modification. It is the very same memory address. If you want to copy your graph, use H = copy(G).

This is a behaviour that you should expect in any object-oriented language.

edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools

Stats

Asked: 2015-08-07 22:47:11 +0200

Seen: 1,440 times

Last updated: Aug 07 '15