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!
--
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.
