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:
- Initialize: $k=0$
While $v\neq \emptyset$ do:
Pick the first element $u$ of $v$, $u\to k$, $k=k+1$
- 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.
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.
Thank you for pointing that out. The mistake is naive indeed.
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.