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.
Shouldn't you spell
as
I think the former is not valid python syntax (as the error would suggest).
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)\ ?$$
@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".
@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.
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) *"