# Why does this error arise?

I want to relabell the vertices of a randomly generated graph in Sage. Let $v$ be the set of vertices ordered according to their appearance in the degree sequence. The labelling strategy is like this:

1. Initialize: $k=0$
2. While $v\neq \emptyset$ do:

3. Pick the first element $u$ of $v$, $u\to k$, $k=k+1$

4. For $i$ in neighbors of $u$: $i\to k$, $k=k+1$. Remove $u$ and its neighbors from $v$.

In order to achieve that I wrote the following code but it gives me the folowing error: ValueError: list.remove(x): x not in list, which I do not know how to fix. I know that the problem is in the last part because the rest of the code works. In my understanding, all the elements of $s$ are also elements of $v$. So I do not know why the error is coming up.

     def t(n,m):
G=graphs.RandomGNM(n,m)
G.show()

#***********forming the list b of tuples (vertex, deg(vertex))
a=[]
for i in G.vertices():
a.append((i,G.degree(i)))
b=sorted(a, key=lambda x: x[1],reverse=True)

#************** degree sequence  d of the graph G
d=[]
for i in xrange(0,len(b)):
d.append(b[i][1])
print("degree sequence",d)

#*************** sorting vertices in a list v according to the order they appear
#in the degree sequence
v=[]
for i in xrange(0,len(b)):
v.append(b[i][0])
print("vertices       ",v)

#**************** relabelling vertices
v_1=v[:]
v_2=list([0 for i in xrange(0,len(v))])  #~list which will hold the new labels
k=1
while v<>[]:
s=[]
v_2[v_1.index(v[0])]=k   #relabeling the vertex with the highest degree in v
s.append(v_1.index(v[0]))
k=k+1
for j in G.neighbors(v_1.index(v[0])): #~relabeling its neighbors
v_2[v_1.index(j)]=k
s.append(j)
k=k+1
for f in s:   #removing from v the relabeled vertices
v.remove(f)
print(v_2)


UPDATE: The new code:

    def ver(d):#the function returns the list v of vertices  of the
#Graph(d) in the order they appear in the degree sequence
G=Graph(d)
if G.vertices()<>[]:
G.show()

#*****forming the list b of tuples (vertex,deg(vertex))
a=[]
for i in G.vertices():
a.append((i,G.degree(i)))
b=sorted(a, key=lambda x: x[1],reverse=True)

#*****degree sequence  d of the graph G
d=[]
for i in xrange(0,len(b)):
d.append(b[i][1])

#*****sorting vertices in a list v according to
#**** the order they appear in the degree sequence
v=[]
for i in xrange(0,len(b)):
v.append(b[i][0])
print("vertices       ",v)
return(v)

G=graphs.RandomGNM(10,14)
v=ver(G.to_dictionary())
v_1=v[:]
v_2=[0 for i in xrange(0,len(v))]
k=0
while v<>[]:
v_2[v_1.index(v[0])]=k
k=k+1
for i in G.neighbors(v[0]):
v_2[v_1.index(i)]=k
k=k+1
G.delete_vertices(G.neighbors(v[0]))
G.delete_vertex(v[0])
v=ver(G.to_dictionary())
d=dict(zip(v_1,v_2))
G.relabel(d)
G.show()


It works but G.show() does not produce any output.

edit retag close merge delete

You remove vertices from the list v, but not from the graph. So you may later add a vertex j to the list s that has already been removed from v.

( 2018-09-24 11:47:00 -0500 )edit

Thank you for pointing that out. The mistake is naive indeed.

( 2018-09-24 15:07:22 -0500 )edit

I fixed the mistake you pointed out. I generate the dictionary $d$ according to which I want to relabel the graph $G$ but G.show() does not give any output. Due to the space restriction I will put the new code in the body of the question.

( 2018-09-25 05:18:45 -0500 )edit

Sort by » oldest newest most voted

Consider the following code. It follows the description of your relabeling method (I'm not sure of what you really want to get). I can display the relabeled graph.

def relabeling(G):
deg = sorted([(d,u) for u,d in G.degree_iterator(labels=True)], key=lambda x: x[0], reverse=True)
L = dict()
k = 0
for _,u in deg:
if u in L:
# The vertex has already been labeled
continue
L[u] = k
k += 1
for v in G.neighbor_iterator(u):
if v in L:
# v has already been labeled
continue
L[v] = k
k += 1
H = G.relabel(perm=L, inplace=False)
return H

G = graphs.RandomGNM(10,20)
H = relabeling(G)
H.show()

more

Yes, it does what I want. I would like to also understand why I do not get any output in my code. As a starter in programming I am not familiar with the underscore _ variable but your code looks neat. Unfortunately I can not upvote this answer because I have not enough reputation. Maybe I will post a new question related to my new problem.

( 2018-09-25 07:35:46 -0500 )edit

See for instance This stackoverflow discussion for understanding the use and meaning of _. Here I used it to mean that we don't care of that value.

Concerning your code, you remove vertices of the graph in the while loop. In the end, the graph is empty, and so G.show() has nothing to display.

( 2018-09-27 04:10:05 -0500 )edit