Minimum Diameter Spanning Subgraph

[aida]

Hello!

Does anybody sees where is the probleme with this code:

# Weights w and parameter B are given

def MinDiameterSpanningSubgraph(G, B):

    

    

    # ILP returns minimum diameter in a spanning subgraph

    I = MixedIntegerLinearProgram(maximization = False)

    # This part tells us if the edge uv is in subgraph G'

    x = I.new_variable(binary = True)

    # y[uv,ij] = 1,if the edge ij is on path from u to v

    y = I.new_variable(binary = True)

    # b[uv,k] = 1 if k is in the path from u to v 

    b = I.new_variable(binary = True)

    

    d = I.new_variable()

    

    I.set_objective(d[0])

    

    # Edge uv is labeled with Set(  [u,v]) if u and v are adjacent

    I.add_constraint( sum( x[ Set([u,v]) ]* w for u,v,w in G.edges()) <= B)

    

    for u,v in Combinations(G,2):

        

        for i,j in G.edges(labels=false):

            I.add_constraint( y[ (Set([u,v]), Set([i,j])) ] <= x[ Set([i,j]) ])

            

        

        # Sum of the the adjacent vertexes to u = u', that are on the path to v equals 1

        I.add_constraint( sum (y[ ( Set([u,v]), Set([u,j])) ] for j in G[u]) == 1)

        # Sum of the the adjacent vertexes to v =v', that are on the path to u equals 1

        I.add_constraint( sum (y[ ( Set([u,v]), Set([v,j])) ] for j in G[v]) == 1)

        

        for k in set(G) - set([u,v]):

            # If vertex is on the path from u to v, the number of edges from the vertex has to be 2, otherwise is 0 and it means the vertex is not on the path

            I.add_constraint ( sum( y[ (Set([u,v]), Set([k,l]) )] for l in G[k]) == 2*b[Set([u,v]),k])

        # d is the longest distance in graph

        I.add_constraint( d[0] >= sum( y[(Set([u,v]), Set([i,j]))] for i,j in G.edges(labels=false)) )

        

    return I,x

#za G(n,r)

for k in [4]:

    number = 2^k

    data = 'points-'+str(number)+'.txt'

    for r in [0.7]:

        G = Graph()

        for line in open(data):

            x,y = line.split(' ')

            G.add_vertex( (float(x), float(y)) )

        for x,y in Combinations(G, 2):

            if sqrt ( (x[0]-y[0])^2 + (x[1]-y[1])^2) <= r:

                G.add_edge(x,y)

        print G

        P=MinDiameterSpanningSubgraph(G, 0.8 * len(G.edges()))

        print 'Pisem za k in r', k , r

        P.write_lp('MinDiameterSpanningSubgraph-' + str(number) + '-' +str(r) + '-G(n,r)')

I get the same error for every k and r I try.

Thank you for your help!

[Dima Pasechnik]

It would help if you included that error message...

[Dominique Laurain]

+1 with Dima 

I cannot help if you don't write the message error and if you have not given points16-txt file content.

After copying your code in sageworksheet cell and running cell, I have only the error

IOError: [Errno 2] No such file or directory: 'points-16.txt'

Post too your computer environment : are you using sagemath cloud ?

Your code has no syntax error, and what you name "error" could be either a math/graph mistake or a algorithm coding one. 

Printing intermediate variables like x,y or I is strongly recommended (insert "print .... " lines) : you might be surprised by some results (for example : symbolic values where you guessed float values).

Dominique.