Revision history [back]

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?

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?