Constructing a dictionary where the values are lists

Anonymous

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.

Comments

Shouldn't you spell

d.update(tupple(i):ll)

d[tupple(i)]=ll

I think the former is not valid python syntax (as the error would suggest).

nbruin ( 7 years ago )

It is always a good idea to keep the notations in code and in the description consistent. So if $A,B$ are the letters used in a mathematical formula, then the code should also use them with the same meaning. (A second programmer having to maintain the code some years after, possibly also the same one, has a simpler job to follow.)

For such a question it is always a good idea to give a situation that can be reproduced.

Isolating a minimal code, that keeps the issue, is also part of testing, and debugging, and making the things work.

Your style to implement something usually differs from the style of other programmers / mathematicians, so please always insert a comment at delicate places.

Is the minimal value not zero, taken for $A=B$ ? We build $\min_{A,B} w(A,B)\ ?$

dan_fulea ( 7 years ago )

@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".

kristi ( 7 years ago )

@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.

kristi ( 7 years ago )

Again the question, given $A_0$ in V, we want to store in a dictionary the possible $B$ 's realizing the minimal value for this $A_0$ , i.e. $\min_B w(A_0,B)\ ,$ or rather the total minimal value (if such a $B$ exists), $\min_{A,B}w(A,B)\ .$ The post mentions: "*for which the function $w(A,B) = \dots$ is minimized for $A\subset V$ (in code $A\subseteq V$ ) and $B\subset MI$ (in code $B\in$ MI) *"

dan_fulea ( 7 years ago )

see more comments

answered 7 years ago

dan_fulea
5650 ●5 ●44 ●97

Thanks for the comments in code, and for the parallel use of the same names in the description and in the code. The problem (SyntaxError) comes from the usage of the update method of a dictionary, as immediately noticed by nbruin . Let us have a simple example:

sage: dic = dict( [ (k, k^2) for k in range(10) ] )
sage: dic
{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81}
sage: dic[0] = 2018    # works
sage: dic
{0: 2018, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81}
sage: dic.update( {0: 2020} )    # works, proper use of the update method
sage: dic
{0: 2020, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81}
sage: dic.update( 0: 2525 )    # does not work (yet)
  File "<ipython-input-134-68ea6b059ae6>", line 1
    dic.update( Integer(0): Integer(2525) )    # does not work (yet)
                          ^
SyntaxError: invalid syntax

Making this change, the code works. Here, i will rewrite it, so that

The function generate has an input that makes it reproducible, the argument is a graph G.
The function $\omega$ will be a w in the code, and it will be placed outside of generate.
For the test we will fix a graph G with $10$ vertices, randomly generated as in the post, but then isolated.

First of all, let us fix a graph. We generate one, then fix its dictionary.

sage: G = graphs.RandomGNP(10, 0.4)
sage: graph_dict = dict( [ (k, G.neighbors(k)) for k in range(10) ] )
sage: graph_dict
{0: [1, 2, 3, 4, 7],
 1: [0, 2, 8],
 2: [0, 1, 4, 7],
 3: [0, 5, 7],
 4: [0, 2, 7, 8, 9],
 5: [3],
 6: [7, 9],
 7: [0, 2, 3, 4, 6, 8],
 8: [1, 4, 7, 9],
 9: [4, 6, 8]}

Now everybody can initialize this graph via:

graph_dict = {0: [1, 2, 3, 4, 7],
              1: [0, 2, 8],
              2: [0, 1, 4, 7],
              3: [0, 5, 7],
              4: [0, 2, 7, 8, 9],
              5: [3],
              6: [7, 9],
              7: [0, 2, 3, 4, 6, 8],
              8: [1, 4, 7, 9],
              9: [4, 6, 8]}
G = Graph(graph_dict, format='dict_of_lists')

We introduce the generate routine having as argument a "generic" G, like the one above.

from sage.graphs.independent_sets import IndependentSets

def omega(A, B):
    delta_AB = set(A).symmetric_difference(set(B))
    omega_AB = 0    # we initialize ω(A,B) and add futher contributions
    for k in delta_AB:
        omega_AB += 2^k    # add the contribution of this k to the function ω 
    return omega_AB

# A possible shorter definition, using list comprehension would be
def w(A, B):
    return sum( [0,] + [2^k for k in set(A).symmetric_difference(set(B)) ] )

def generate(G):
    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 in MI
        for B in MI:
            omega_A.append(omega(A, B))    # add the found value to omega_A

        # instead, the following use of the list comprehension leads to the same
        # omega_A = [ w(A, B) for B in MI ]

        ll = MI[ omega_A.index(min(omega_A)) ]    # find the max. ind. set minimizing ω(A,B)
        d.update( {tuple(A) : ll} )   # record ll in d

    return d

With this code, for the fixed G we get a long dictionary with $2^10$ keys. Among them:

d = generate(G)
d[ (2,3,4,5,6,7,8) ]

gives:

sage: d = generate(G)
....: d[ (2,3,4,5,6,7,8) ]
....: 
[2, 5, 6, 8]

Final note: Programmers have different ways to think and to style. For instance, in this case my choice would have been:

from sage.graphs.independent_sets import IndependentSets

    def w(A, B):
        return sum( [0,] + [2^k for k in set(A).symmetric_difference(set(B)) ] )

    def generate(G):
        V = set(G.vertices())
        MI = IndependentSets(G, maximal=True)
        dic = {}    # and we insert key, value pairs

        for A in Subsets(V):
            minimalizing_value  = min( [ w(A, B) for B in MI ] )
            minimalizing_B_list = [ B for B in MI if w(A, B) == minimalizing_value ]
            # yes, i compute it twice and do not include this result in the next line...
            dic[ tuple(A) ] = minimalizing_B_list[0]    # or of -1...

        return dic

And the special value is in a test the same:

sage: dic = generate(G)
sage: dic[ (2,3,4,5,6,7,8) ]
[2, 5, 6, 8]

link

Comments

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.

kristi ( 6 years ago )

add a comment

Your Answer

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

Constructing a dictionary where the values are lists

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Constructing a dictionary where the values are lists savecancel

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Constructing a dictionary where the values are lists