import sys
import math
from data import *
from gurobipy import *


# Read data
(n,pairs) = read_instance_from_file("switchboard-0016-002.vlsi")

terminals = []
for t1,t2 in pairs:
    terminals.append(tuple(t1))
    terminals.append(tuple(t2))
nt = len(terminals)

#n=2
k=2


# Create vertices
points = []
for x in range(n):
    for y in range(n):
        for z in range(k):
            points.append((x,y,z))
np = len(points)

m = Model()

# Create variables
vars = {}

# Add wires between nodes
for i in range(np):
    for j in range(i + 1):
        x1,y1,z1 = points[i]
        x2,y2,z2 = points[j]
        cost = legal_wire_cost(x1,y1,z1, x2,y2,z2, n, k)
        if cost is None:
            continue
        #print(str(pi) + " " + str(pj) + " c=" + str(cost))
        vars[i,j] = m.addVar(obj=cost, vtype=GRB.BINARY,
                             name='e'+str(i)+'_'+str(j))
        vars[j,i] = vars[i,j]

# Add diagonal wires between the terminal node and the k nodes that it might connect to
t_vars = {}
for x,y in terminals:
    for z in range(k):
        t_vars[x,y,z] = m.addVar(obj=10, vtype=GRB.BINARY,
                                 name='t'+str(x)+'_'+str(y)+'_'+str(z))
        #t_vars[z,t] = t_vars[t,z]
        #print('t'+str(t)+'_'+str(z))

m.update()


# Add degree-1 constraint for terminals
for x,y in terminals:
    m.addConstr(quicksum(t_vars[x,y,z] for z in range(k)) == 1)


# Add degree 0 or 2 constraint
for i in range(np):
    vars_ij = []
    for j in range(np):
        if (i,j) in vars:
            vars_ij.append(vars[i,j])

    if points[i] in t_vars:
        vars_ij.append(t_vars[points[i]])

    m.addConstr(quicksum(vars_ij) * 0.5, GRB.LESS_EQUAL, 1)
    #m.addConstr(quicksum(vars_ij) == 2)

m.update()


# Optimize model
m.optimize()


solution = m.getAttr('x', vars)
for v in vars:
    if solution[v] > 0.5:
        print(str(v) + ' ' + str(solution[v]))

solution = m.getAttr('x', t_vars)
for v in t_vars:
    if solution[v] > 0.5:
        print(str(v) + ' ' + str(solution[v]))

print('')
print('Optimal cost: %g' % m.objVal)
print('')

@@ -16,16 +16,39 @@
 rt math%0A
+#import networkx as nx%0A
 from dat
@@ -82,16 +82,523 @@
 port *%0A%0A
+# data.legal_wire_cost doesn't return None for some illegal wires.%0A# Use is_legal_wire first.%0Adef is_legal_wire(x,y,z, x_,y_,z_, n,k):%0A    if z%3C0 or z%3E=k or z_%3C0 or z_%3E=k:%0A        return False%0A    if x%3C0 or x%3E=n or x_%3C0 or x_%3E=n or y%3C0 or y%3E=n or y_%3C0 or y_%3E=n:%0A        return False%0A%0A    if x==x_ and y==y_ and abs(z-z_)==1:%0A        return True%0A    if x==x_ and abs(y-y_)==1 and z==z_ and z%252==1:%0A        return True%0A    if abs(x-x_)==1 and y==y_ and z==z_ and z%252==0:%0A        return True%0A    return False%0A%0A
 %0A# Read 
@@ -792,16 +792,29 @@
 s)%0A%0A
-#n=2%0Ak=2
+k=2%0A%0A%0A#G = nx.Graph()
 %0A%0A%0A#
@@ -946,16 +946,64 @@
 x,y,z))%0A
+            #G.add_node(n*k*x+k*y+z, p=(x,y,z))%0A
 np = len
@@ -1012,16 +1012,17 @@
 oints)%0A%0A
+%0A
 m = Mode
@@ -1122,19 +1122,17 @@
  range(i
- + 
++
 1):%0A    
@@ -1197,15 +1197,18 @@
     
-cost = 
+if not is_
 lega
@@ -1213,21 +1213,16 @@
 gal_wire
-_cost
 (x1,y1,z
@@ -1240,11 +1240,11 @@
 , n,
- 
 k)
+:
 %0A   
@@ -1252,104 +1252,195 @@
     
-if cost is None:%0A            continue%0A        #print(str(pi) + %22 %22 + str(pj) + %22 c=%22 + str(cost)
+    continue%0A        cost = legal_wire_cost(x1,y1,z1, x2,y2,z2, n,k)%0A        #print(str(pi) + %22 %22 + str(pj) + %22 c=%22 + str(cost))%0A        #G.add_edge(n*k*x1+k*y1+z1, n*k*x2+k*y2+z2, c=cost
 )%0A  
@@ -1861,81 +1861,8 @@
 (z))
-%0A        #t_vars%5Bz,t%5D = t_vars%5Bt,z%5D%0A        #print('t'+str(t)+'_'+str(z))
 %0A%0Am.

Use is_legal_wire before legal_wire_cost.