# is_exist_complementary_hypergraph.sage: written by Stephen Hartke and Charles Viss 9/5/2018
# sage script for exploring the existence of primitive uniquely K_r^{k}-saturated hypergraphs

def is_exist_complementary_hypergraph(n,t,s):
    # Creates an IP that has a feasible solution if and only if a desired complementary hypergraph R exists.
    # Assumptions: n>=t+2>=s+4 (so k>=3); s>=1; t>=s+1

    big_sets  =list(Combinations(n,t))    # big sets: t-sets of [n]
    small_sets=list(Combinations(n,t-s))  # small sets: (t-s)-sets of [n]

    max_codegree=binomial(n-(t-s),s)   #largest possible codegree of a small set in R
    num_small_sets_in_big_set=binomial(t,t-s) #number of small sets contained in a big set

    # test if CPLEX is installed
    try:
        test_LP=MixedIntegerLinearProgram(solver='CPLEX')
        solver='CPLEX'
    except ImportError:
        solver='GLPK'

    p=MixedIntegerLinearProgram(solver=solver)


    x=p.new_variable(name='x',binary=True)
    # create a binary x-variable for each big set, indexed by the position in big_sets
    # x[j]==1 if and only if big set j is an edge of R

    c=p.new_variable(name='c',nonnegative=True)
    # create c-variable for each small set, indexed by position in small_sets
    # c[j] is the codegree of small set j in R

    y=p.new_variable(name='y',binary=True)
    # create a binary y-variable for each small set, indexed by position in small_sets,
    # indicating whether or not small set j has codegree 1 in R (y[j]==1 if and only if c[j]==1)

    for i,S in enumerate(small_sets):
        containing_sets=[]
        for j,B in enumerate(big_sets):
            if set(S).issubset(set(B)):
                containing_sets.append(j)
        p.add_constraint(sum(x[j] for j in containing_sets)==c[i])  # compute the codegree of each small set
        p.add_constraint(c[i]>=1)  # force codegree to be >=1 for each small set (i.e. each small set is covered by an edge of R)

        # compute each y-variable based on the corresponding codegree
        p.add_constraint(y[i]>=2-c[i])  # if c[i]==1, then y[i]==1
        p.add_constraint(y[i]<=1-(c[i]-1)/(max_codegree-1)) #if c[i]>1, then y[i]==0

    for j,B in enumerate(big_sets):
        contained_subsets=[]
        for i,S in enumerate(small_sets):
            if set(S).issubset(set(B)):
                contained_subsets.append(i)
        # if x[j]==1, then we want exactly one contained (t-s)-subset of codegree 1
        p.add_constraint(sum(y[i] for i in contained_subsets)>=x[j])         #if x[j]==1, then some y[i]==1
        p.add_constraint(sum(y[i] for i in contained_subsets) <=(num_small_sets_in_big_set-1)*(1-x[j])+1)
        #if x[j]==1, then y[i]==1 for at most one of its contained small sets

    # add the constraint that there is no dominating vertex (no element appears in all edges of R)
    for i in range(n):
        containing_sets=[]
        for j,B in enumerate(big_sets):
            if set((i,)).issubset(set(B)):
                containing_sets.append(j)
        p.add_constraint(sum(x[j] for j in containing_sets) <= sum(x[j] for j in range( binomial(n,t)) ) - 1 )


    # break some of the symmetry
    p.add_constraint(x[0]==1)
    p.add_constraint(y[0]==1)  # force codegree
    p.add_constraint(c[0]==1)
    for j,B in enumerate(big_sets):
        if j==0:
            for i,S in enumerate(small_sets):
                if set(S).issubset(set(B)):
                    if i > 0:
                        p.add_constraint(y[i]==0)
                        p.add_constraint(c[i]>=2)
            break

    print('solving...')

    try:
        p.solve()
        #show edges of R if valid complementary hypergraph exists
        print('Complementary hypergraph for n=' + str(n) + ", t=" + str(t) + ", s=" + str(s) + ':')
        for j,B in enumerate(big_sets):
            if p.get_values(x[j]) > 0:
                print B,"x[%d]=" % j, p.get_values(x[j])
    except sage.numerical.mip.MIPSolverException:
        print('No complementary hypergraph exists for n=' + str(n) + ", t=" + str(t) + ", s=" + str(s) + '.')
        return False

    #alternatively, write an lp file for cplex to solve:
    #p.write_lp(str(n) + "_" + str(t) + "_" + str(s) + ".lp")

#end function is_exist_complementary_hypergraph(n,t,s)

#an example of a call to the function:
is_exist_complementary_hypergraph(7,4,1)