ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 27 Sep 2018 11:10:05 +0200Why does this error arise?https://ask.sagemath.org/question/43736/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.Mon, 24 Sep 2018 18:33:14 +0200https://ask.sagemath.org/question/43736/why-does-this-error-arise/Comment by David Coudert for <p>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: </p>
<ol>
<li>Initialize: $k=0$</li>
<li><p>While $v\neq \emptyset$ do:</p></li>
<li><p>Pick the first element $u$ of $v$, $u\to k$, $k=k+1$</p></li>
<li>For $i$ in neighbors of $u$: $i\to k$, $k=k+1$. Remove $u$ and its neighbors from $v$.</li>
</ol>
<p>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. </p>
<pre><code> 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)
</code></pre>
<p>UPDATE: The new code:</p>
<pre><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()
</code></pre>
<p>It works but <code>G.show()</code> does not produce any output.</p>
https://ask.sagemath.org/question/43736/why-does-this-error-arise/?comment=43737#post-id-43737You 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.Mon, 24 Sep 2018 18:47:00 +0200https://ask.sagemath.org/question/43736/why-does-this-error-arise/?comment=43737#post-id-43737Comment by kristi for <p>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: </p>
<ol>
<li>Initialize: $k=0$</li>
<li><p>While $v\neq \emptyset$ do:</p></li>
<li><p>Pick the first element $u$ of $v$, $u\to k$, $k=k+1$</p></li>
<li>For $i$ in neighbors of $u$: $i\to k$, $k=k+1$. Remove $u$ and its neighbors from $v$.</li>
</ol>
<p>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. </p>
<pre><code> 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)
</code></pre>
<p>UPDATE: The new code:</p>
<pre><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()
</code></pre>
<p>It works but <code>G.show()</code> does not produce any output.</p>
https://ask.sagemath.org/question/43736/why-does-this-error-arise/?comment=43740#post-id-43740Thank you for pointing that out. The mistake is naive indeed.Mon, 24 Sep 2018 22:07:22 +0200https://ask.sagemath.org/question/43736/why-does-this-error-arise/?comment=43740#post-id-43740Comment by kristi for <p>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: </p>
<ol>
<li>Initialize: $k=0$</li>
<li><p>While $v\neq \emptyset$ do:</p></li>
<li><p>Pick the first element $u$ of $v$, $u\to k$, $k=k+1$</p></li>
<li>For $i$ in neighbors of $u$: $i\to k$, $k=k+1$. Remove $u$ and its neighbors from $v$.</li>
</ol>
<p>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. </p>
<pre><code> 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)
</code></pre>
<p>UPDATE: The new code:</p>
<pre><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()
</code></pre>
<p>It works but <code>G.show()</code> does not produce any output.</p>
https://ask.sagemath.org/question/43736/why-does-this-error-arise/?comment=43751#post-id-43751I 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.Tue, 25 Sep 2018 12:18:45 +0200https://ask.sagemath.org/question/43736/why-does-this-error-arise/?comment=43751#post-id-43751Answer by David Coudert for <p>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: </p>
<ol>
<li>Initialize: $k=0$</li>
<li><p>While $v\neq \emptyset$ do:</p></li>
<li><p>Pick the first element $u$ of $v$, $u\to k$, $k=k+1$</p></li>
<li>For $i$ in neighbors of $u$: $i\to k$, $k=k+1$. Remove $u$ and its neighbors from $v$.</li>
</ol>
<p>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. </p>
<pre><code> 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)
</code></pre>
<p>UPDATE: The new code:</p>
<pre><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()
</code></pre>
<p>It works but <code>G.show()</code> does not produce any output.</p>
https://ask.sagemath.org/question/43736/why-does-this-error-arise/?answer=43757#post-id-43757Consider 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()Tue, 25 Sep 2018 13:26:21 +0200https://ask.sagemath.org/question/43736/why-does-this-error-arise/?answer=43757#post-id-43757Comment by David Coudert for <p>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.</p>
<pre><code>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()
</code></pre>
https://ask.sagemath.org/question/43736/why-does-this-error-arise/?comment=43780#post-id-43780See for instance [This stackoverflow discussion](https://stackoverflow.com/questions/5893163/what-is-the-purpose-of-the-single-underscore-variable-in-python) 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.Thu, 27 Sep 2018 11:10:05 +0200https://ask.sagemath.org/question/43736/why-does-this-error-arise/?comment=43780#post-id-43780Comment by kristi for <p>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.</p>
<pre><code>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()
</code></pre>
https://ask.sagemath.org/question/43736/why-does-this-error-arise/?comment=43758#post-id-43758Yes, 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.Tue, 25 Sep 2018 14:35:46 +0200https://ask.sagemath.org/question/43736/why-does-this-error-arise/?comment=43758#post-id-43758