On Sunday, August 14, 2016 at 3:49:03 PM UTC+1, aida wrote:
>
> 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.
>
It would help if you included that error message...
> Thank you for your help!
>
--
You received this message because you are subscribed to the Google Groups
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.
