ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 22 Jul 2018 08:35:55 -0500Constructing a dictionary where the values are listshttp://ask.sagemath.org/question/41696/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.Wed, 21 Mar 2018 14:07:17 -0500http://ask.sagemath.org/question/41696/constructing-a-dictionary-where-the-values-are-lists/Comment by dan_fulea for <p>I want to construct a dictionary where the keys are the subsets of the vertex set <strong>$V$</strong> of a randomly generated graph and the values are the maximal indipendent sets (denoted <strong>MI</strong> in the code) for which the function:</p>
<p>$$\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) $$</p>
<p>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:</p>
<pre><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)
</code></pre>
<p>When I compile it I get </p>
<pre><code>Traceback (most recent call last):
...
SyntaxError: invalid syntax
</code></pre>
<p>Basically it wont let me use <code>MI[alpha_i.index(min(alpha_i))]</code> as a value. In other cases I tried to use lists as values and it seemed to work.</p>
http://ask.sagemath.org/question/41696/constructing-a-dictionary-where-the-values-are-lists/?comment=41710#post-id-41710The following is the needed dictionary construction?
from sage.graphs.independent_sets import IndependentSets
G = graphs.RandomGNP(8, 0.4)
V = set(G.vertices())
PV = Subsets(V)
MI = [ Set(B) for B in list(IndependentSets(G, maximal = True)) ]
dic = {} # dictionary
def w(A, B):
return sum( [0,] + [2^k for k in A.symmetric_difference(B)] )
for A in PV:
min_wAB = min( [ w(A,B) for B in MI ] ) # minimal for this A
minimalizing_list = [ B for B in MI if w(A,B) == min_wAB ]
dic[A] = minimalizing_list
print G.vertices()
print G.edges()
import pprint
pprint.pprint( dic )Wed, 21 Mar 2018 23:56:17 -0500http://ask.sagemath.org/question/41696/constructing-a-dictionary-where-the-values-are-lists/?comment=41710#post-id-41710Comment by dan_fulea for <p>I want to construct a dictionary where the keys are the subsets of the vertex set <strong>$V$</strong> of a randomly generated graph and the values are the maximal indipendent sets (denoted <strong>MI</strong> in the code) for which the function:</p>
<p>$$\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) $$</p>
<p>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:</p>
<pre><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)
</code></pre>
<p>When I compile it I get </p>
<pre><code>Traceback (most recent call last):
...
SyntaxError: invalid syntax
</code></pre>
<p>Basically it wont let me use <code>MI[alpha_i.index(min(alpha_i))]</code> as a value. In other cases I tried to use lists as values and it seemed to work.</p>
http://ask.sagemath.org/question/41696/constructing-a-dictionary-where-the-values-are-lists/?comment=41704#post-id-41704Again 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`) *"Wed, 21 Mar 2018 16:32:39 -0500http://ask.sagemath.org/question/41696/constructing-a-dictionary-where-the-values-are-lists/?comment=41704#post-id-41704Comment by kristi for <p>I want to construct a dictionary where the keys are the subsets of the vertex set <strong>$V$</strong> of a randomly generated graph and the values are the maximal indipendent sets (denoted <strong>MI</strong> in the code) for which the function:</p>
<p>$$\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) $$</p>
<p>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:</p>
<pre><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)
</code></pre>
<p>When I compile it I get </p>
<pre><code>Traceback (most recent call last):
...
SyntaxError: invalid syntax
</code></pre>
<p>Basically it wont let me use <code>MI[alpha_i.index(min(alpha_i))]</code> as a value. In other cases I tried to use lists as values and it seemed to work.</p>
http://ask.sagemath.org/question/41696/constructing-a-dictionary-where-the-values-are-lists/?comment=41701#post-id-41701@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.Wed, 21 Mar 2018 15:08:24 -0500http://ask.sagemath.org/question/41696/constructing-a-dictionary-where-the-values-are-lists/?comment=41701#post-id-41701Comment by kristi for <p>I want to construct a dictionary where the keys are the subsets of the vertex set <strong>$V$</strong> of a randomly generated graph and the values are the maximal indipendent sets (denoted <strong>MI</strong> in the code) for which the function:</p>
<p>$$\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) $$</p>
<p>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:</p>
<pre><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)
</code></pre>
<p>When I compile it I get </p>
<pre><code>Traceback (most recent call last):
...
SyntaxError: invalid syntax
</code></pre>
<p>Basically it wont let me use <code>MI[alpha_i.index(min(alpha_i))]</code> as a value. In other cases I tried to use lists as values and it seemed to work.</p>
http://ask.sagemath.org/question/41696/constructing-a-dictionary-where-the-values-are-lists/?comment=41699#post-id-41699@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".Wed, 21 Mar 2018 14:54:55 -0500http://ask.sagemath.org/question/41696/constructing-a-dictionary-where-the-values-are-lists/?comment=41699#post-id-41699Comment by dan_fulea for <p>I want to construct a dictionary where the keys are the subsets of the vertex set <strong>$V$</strong> of a randomly generated graph and the values are the maximal indipendent sets (denoted <strong>MI</strong> in the code) for which the function:</p>
<p>$$\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) $$</p>
<p>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:</p>
<pre><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)
</code></pre>
<p>When I compile it I get </p>
<pre><code>Traceback (most recent call last):
...
SyntaxError: invalid syntax
</code></pre>
<p>Basically it wont let me use <code>MI[alpha_i.index(min(alpha_i))]</code> as a value. In other cases I tried to use lists as values and it seemed to work.</p>
http://ask.sagemath.org/question/41696/constructing-a-dictionary-where-the-values-are-lists/?comment=41698#post-id-41698It 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)\ ?$$Wed, 21 Mar 2018 14:54:06 -0500http://ask.sagemath.org/question/41696/constructing-a-dictionary-where-the-values-are-lists/?comment=41698#post-id-41698Comment by nbruin for <p>I want to construct a dictionary where the keys are the subsets of the vertex set <strong>$V$</strong> of a randomly generated graph and the values are the maximal indipendent sets (denoted <strong>MI</strong> in the code) for which the function:</p>
<p>$$\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) $$</p>
<p>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:</p>
<pre><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)
</code></pre>
<p>When I compile it I get </p>
<pre><code>Traceback (most recent call last):
...
SyntaxError: invalid syntax
</code></pre>
<p>Basically it wont let me use <code>MI[alpha_i.index(min(alpha_i))]</code> as a value. In other cases I tried to use lists as values and it seemed to work.</p>
http://ask.sagemath.org/question/41696/constructing-a-dictionary-where-the-values-are-lists/?comment=41697#post-id-41697Shouldn't you spell
d.update(tupple(i):ll)
as
d[tupple(i)]=ll
I think the former is not valid python syntax (as the error would suggest).Wed, 21 Mar 2018 14:41:07 -0500http://ask.sagemath.org/question/41696/constructing-a-dictionary-where-the-values-are-lists/?comment=41697#post-id-41697Answer by dan_fulea for <p>I want to construct a dictionary where the keys are the subsets of the vertex set <strong>$V$</strong> of a randomly generated graph and the values are the maximal indipendent sets (denoted <strong>MI</strong> in the code) for which the function:</p>
<p>$$\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) $$</p>
<p>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:</p>
<pre><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)
</code></pre>
<p>When I compile it I get </p>
<pre><code>Traceback (most recent call last):
...
SyntaxError: invalid syntax
</code></pre>
<p>Basically it wont let me use <code>MI[alpha_i.index(min(alpha_i))]</code> as a value. In other cases I tried to use lists as values and it seemed to work.</p>
http://ask.sagemath.org/question/41696/constructing-a-dictionary-where-the-values-are-lists/?answer=41712#post-id-41712Thanks 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](https://ask.sagemath.org/users/62/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]
Thu, 22 Mar 2018 08:43:12 -0500http://ask.sagemath.org/question/41696/constructing-a-dictionary-where-the-values-are-lists/?answer=41712#post-id-41712Comment by kristi for <p>Thanks for the comments in code, and for the parallel use of the same names in the description and in the code.
The problem (<code>SyntaxError</code>) comes from the usage of the <code>update</code> method of a dictionary, as immediately noticed by <a href="https://ask.sagemath.org/users/62/nbruin/">nbruin</a> . Let us have a simple example:</p>
<pre><code>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
</code></pre>
<p>Making this change, the code works. Here, i will rewrite it, so that</p>
<ul>
<li>The function <code>generate</code> has an input that makes it reproducible, the argument is a graph <code>G</code>.</li>
<li>The function $\omega$ will be a <code>w</code> in the code, and it will be placed outside of <code>generate</code>.</li>
<li>For the test we will fix a graph <code>G</code> with $10$ vertices, randomly generated as in the post, but then isolated.</li>
</ul>
<p>First of all, let us fix a graph. We generate one, then fix its dictionary.</p>
<pre><code>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]}
</code></pre>
<p>Now everybody can initialize <em>this</em> graph via:</p>
<pre><code>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')
</code></pre>
<p>We introduce the <code>generate</code> routine having as argument a "generic" <code>G</code>, like the one above.</p>
<pre><code>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
</code></pre>
<p>With this code, for the fixed <code>G</code> we get a long dictionary with $2^10$ keys. Among them:</p>
<pre><code>d = generate(G)
d[ (2,3,4,5,6,7,8) ]
</code></pre>
<p>gives:</p>
<pre><code>sage: d = generate(G)
....: d[ (2,3,4,5,6,7,8) ]
....:
[2, 5, 6, 8]
</code></pre>
<p><strong>Final note:</strong> Programmers have different ways to think and to style. For instance, in this case my choice would have been:</p>
<pre><code>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
</code></pre>
<p>And the special value is in a test the same:</p>
<pre><code>sage: dic = generate(G)
sage: dic[ (2,3,4,5,6,7,8) ]
[2, 5, 6, 8]
</code></pre>
http://ask.sagemath.org/question/41696/constructing-a-dictionary-where-the-values-are-lists/?comment=43104#post-id-43104Thank 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.Sun, 22 Jul 2018 08:35:55 -0500http://ask.sagemath.org/question/41696/constructing-a-dictionary-where-the-values-are-lists/?comment=43104#post-id-43104