Ask Your Question

kristi's profile - activity

2023-01-24 09:13:17 +0100 received badge  Famous Question (source)
2022-03-26 09:31:06 +0100 received badge  Famous Question (source)
2021-03-25 08:42:28 +0100 received badge  Notable Question (source)
2020-03-09 17:42:07 +0100 received badge  Famous Question (source)
2019-11-18 16:24:24 +0100 received badge  Supporter (source)
2019-11-18 16:23:16 +0100 received badge  Popular Question (source)
2019-10-30 23:00:39 +0100 received badge  Notable Question (source)
2019-09-29 03:17:09 +0100 received badge  Notable Question (source)
2019-01-10 21:50:02 +0100 received badge  Popular Question (source)
2018-09-25 14:35:46 +0100 commented answer Why does this error arise?

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 12:52:44 +0100 received badge  Associate Editor (source)
2018-09-25 12:43:15 +0100 received badge  Commentator
2018-09-25 12:18:45 +0100 commented question Why does this error arise?

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-24 22:07:22 +0100 commented question Why does this error arise?

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

2018-09-24 18:33:14 +0100 asked a question 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.

2018-07-22 23:26:10 +0100 received badge  Popular Question (source)
2018-07-22 19:49:07 +0100 commented answer Preserving the rooted tree layout in graphs

Thank you! Unfortunately I do not have enough reputation to upvote this answer.

2018-07-22 18:58:15 +0100 received badge  Nice Question (source)
2018-07-22 17:07:38 +0100 asked a question Preserving the rooted tree layout in graphs

I am working in a research project where I deal with rooted trees. I want to be able to add edges to the rooted tree and somehow "preserve" the rooted tree layout. More precisely, if I add the edges $(2,8)$ and $(3,6)$ in the rooted tree produced by the code below

G=Graph({0:[1,2,3,4],1:[5,6,7],4:[8,9,10],6:[11,12],9:[13,14]})
G.show(layout='tree',tree_root=0)
G.add_edges([(3,9),(2,6)])
G.show()

the layout of the updated graph is kind of messy and it gets worse if the order of the tree is increased. I want to add the new edges in a different color but without affecting the layout of the initial tree. I want the updated graph to look like the output of this tikzpicture:

  \begin{tikzpicture}[
   V/.style = {% V as Vortex
        circle,thick,fill=orange},scale=0.4]


   %drawing nodes
    \node[V] (0) at (-9,11) [scale=0.5,draw] {0};
    \node[V] (1) at (-3,8) [scale=0.5,draw] {1};
    \node[V] (2) at (-7,8) [scale=0.5,draw] {2};
    \node[V] (3) at (-11,8)[scale=0.5,,draw] {3};
    \node[V] (4) at (-15,8) [scale=0.5,draw] {4};
    \node[V] (5) at (-1,5) [scale=0.5,draw] {5};
    \node[V] (6) at (-3,5) [scale=0.5,draw] {6};
    \node[V] (7) at (-5,5) [scale=0.5,draw] {7};
    \node[V] (8) at (-13,5) [scale=0.5,draw] {8};
    \node[V] (9) at (-15,5) [scale=0.5,draw] {9};
    \node[V] (10) at (-17,5) [scale=0.4,draw] {10};
    \node[V] (11) at (-2,2) [scale=0.4,draw] {11};
    \node[V] (12) at (-4,2) [scale=0.4,draw] {12};
    \node[V] (13) at (-14,2) [scale=0.4,draw] {13};
    \node[V] (14) at (-16,2) [scale=0.4,draw] {14};

    \draw[black,very thick]
    (0) to (1)
    (0) to (2)
    (0) to (3)
    (0) to (4)
    (1) to (5)
    (1) to (6)
    (1) to (7)
    (6) to (11)
    (6) to (12)
    (4) to (8)
    (4) to (9)
    (4) to (10)
    (9) to (13)
    (9) to (14);

     \draw[green,very thick,dotted]
     (3) to (9)
     (2) to (6);
\end{tikzpicture}

Is this even possible?

2018-07-22 15:35:55 +0100 commented answer Constructing a dictionary where the values are lists

Thank you for your effort! I like especially the idea of the generic argument. I know this comes quite a while after you wrote the answer but it is better late than never. By the way, I am not a programmer and I know that my way of coding is far away from optimal. I use coding to test mathematical conjectures. Hoping to get better with practice.

2018-03-21 21:08:24 +0100 commented question Constructing a dictionary where the values are lists

@dan_fuela I did mention where $A$ and $B$ are moving. Since in the loops we use bound variables to explore the subsets of $V$ and the set of maximale independent sets $MI$ of the randomly generated graph, I found that clarification kind of enough. I will try to adapt the code so it correlates with the terminology of the formula.

2018-03-21 20:54:55 +0100 commented question Constructing a dictionary where the values are lists

@nbruin Thank you! You are right, I did the updating procedure of the dictionary according to a fast googling. The instruction I followed is clearly wrong. In my code there is also a typo, it should be "tuple" not "tupple".

2018-03-21 20:07:17 +0100 asked a question Constructing a dictionary where the values are lists

I want to construct a dictionary where the keys are the subsets of the vertex set $V$ of a randomly generated graph and the values are the maximal indipendent sets (denoted MI in the code) for which the function:

$$\omega (A,B)=\sum\limits_{i\in A\triangle B}2^i \quad \text{where} \quad A\triangle B=(A\setminus B) \cup (B\setminus A) $$

is minimized, for $A\subset V$ and $B \in MI$. I am having difficulties on encoding the information in a dictionary. I have spent quite some time and I can not figure out how to do it. Here is the code:

sage: from sage.graphs.independent_sets import IndependentSets
sage: def generate(n):
...       n_0=randint(1,n)
...       G=graphs.RandomGNP(n_0,0.4)
...       V=set(G.vertices())
...       MI=list(IndependentSets(G, maximal = True))
...       d={}
...       
...       for A in Subsets(V):
...           omega_A=[]         #omega_A will contain  the values ω(A,B) for B⊂MI

...           print(A)
...           for B in MI:

...               delta_AB=set(A).symmetric_difference(set(B))
...               print(delta_AB)
...               
...               omega_AB=0         #we initialize ω(A,B) for a pair (A,B)
...               for k in delta_AB:
...                   omega_AB=omega_AB+2^k      #calculate the function ω 
...               print(omega_AB) 
...               omega_A.append(omega_AB)      #add the found value to omega_A

...           print(omega_A)

...          
...           ll=MI[omega_A.index(min(omega_A))]  #find the max. ind. set which 
                                                                       #minimizes ω(A,B)
...           d.update(tuple(A):ll)   #add the found element to the dictionary d 
...           print('*******')
...       
...       print("dictionary",d)

When I compile it I get

Traceback (most recent call last):
...
SyntaxError: invalid syntax

Basically it wont let me use MI[alpha_i.index(min(alpha_i))] as a value. In other cases I tried to use lists as values and it seemed to work.

2018-03-21 15:15:23 +0100 commented answer TypeError: 'sage.rings.integer.Integer' object is not iterable

Thank you, it works. Somehow I thought that I can treat the variable i in the third loop more or less like a bound variable in the predicate logic.

2018-03-21 15:09:34 +0100 marked best answer TypeError: 'sage.rings.integer.Integer' object is not iterable

This is my code

m=[1,2,3,4]
c=[[1,3],[2,3],[1,2],[3,4]]

for i in Subsets(m):
    print(i)
    alpha_ij=0
    for j in c:
        delta_ij=set(i).symmetric_difference(set(j))
        print(delta_ij)

        for i in delta_ij:
            alpha_ij=alpha_ij+2^i
    print(alpha_ij)

When I compile it I get

{}
set([1, 3])
Traceback (most recent call last):        for j in c:
  File "", line 1, in <module>

  File "/tmp/tmpgaYE70/___code___.py", line 10, in <module>
    delta_ij=set(i).symmetric_difference(set(j))
TypeError: 'sage.rings.integer.Integer' object is not iterable

Which I do not understand because I do not think that I have iterated over any integer in any part of the code. The problem seem to be the last three lines because if delete them and compile the code there does not appear any error.

2018-03-21 15:09:34 +0100 received badge  Scholar (source)