Revision history [back]

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]