Ask Your Question
1

Why does this error arise?

asked 2018-09-24 11:33:14 -0600

kristi gravatar image

updated 2018-09-25 07:38:33 -0600

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 flag offensive close merge delete

Comments

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.

David Coudert gravatar imageDavid Coudert ( 2018-09-24 11:47:00 -0600 )edit

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

kristi gravatar imagekristi ( 2018-09-24 15:07:22 -0600 )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.

kristi gravatar imagekristi ( 2018-09-25 05:18:45 -0600 )edit

1 answer

Sort by ยป oldest newest most voted
1

answered 2018-09-25 06:26:21 -0600

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()
edit flag offensive delete link more

Comments

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.

kristi gravatar imagekristi ( 2018-09-25 07:35:46 -0600 )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.

David Coudert gravatar imageDavid Coudert ( 2018-09-27 04:10:05 -0600 )edit

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-09-24 11:33:14 -0600

Seen: 64 times

Last updated: Sep 25