1 | initial version |

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]
```

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.