# Author: Marshall Ossi Shires
# Date: 10 SEP 2017
# SA403 Graph and Network Algorithms
#
# Cell 1 creates a maximum matching, while cell 2 creates a minimum cover.



B = BipartiteGraph({0:[4,5,6,7], 1:[5,6], 2:[7], 3:[4,7]})
B.plot()
incMat = Matrix([[1,1,1,1,0,0,0,0,0],   #0
                 [0,0,0,0,1,1,0,0,0],   #1
                 [0,0,0,0,0,0,1,0,0],   #2
                 [0,0,0,0,0,0,0,1,1],   #3
                 [1,0,0,0,0,0,0,1,0],   #4
                 [0,1,0,0,1,0,0,0,0],   #5
                 [0,0,1,0,0,1,0,0,0],   #6
                 [0,0,0,1,0,0,1,0,1]]); #7
incMat;

p1 = MixedIntegerLinearProgram(maximization=True, solver = "GLPK");
x = p1.new_variable(integer=True, nonnegative=True);
p1.add_constraint(x[0] + x[1] + x[2] + x[3] <= 1); #0
p1.add_constraint(x[4] + x[5] <= 1);               #1
p1.add_constraint(x[6] <= 1);                      #2
p1.add_constraint(x[7] + x[8] <= 1);               #3
p1.add_constraint(x[0] + x[7] <= 1);               #4
p1.add_constraint(x[1] + x[4] <= 1);               #5
p1.add_constraint(x[2] + x[5] <= 1);               #6
p1.add_constraint(x[3] + x[6] + x[8] <= 1);        #7
p1.set_objective(x[0] + x[1] + x[2] + x[3] + x[4] + x[5] + x[6] + x[7] + x[8]);
p1.show();
print('Objective Value: {}'.format(p1.solve()));
for c, cc in p1.get_values(x).iteritems():
    print('x_%s = %s' % (c, int(round(cc))));

B = BipartiteGraph({0:[4,5,6,7], 1:[5,6], 2:[7], 3:[4,7]})
B.plot()
incMat = Matrix([[1,1,1,1,0,0,0,0,0],   #0
                 [0,0,0,0,1,1,0,0,0],   #1
                 [0,0,0,0,0,0,1,0,0],   #2
                 [0,0,0,0,0,0,0,1,1],   #3
                 [1,0,0,0,0,0,0,1,0],   #4
                 [0,1,0,0,1,0,0,0,0],   #5
                 [0,0,1,0,0,1,0,0,0],   #6
                 [0,0,0,1,0,0,1,0,1]]); #7
incMat;

p2 = MixedIntegerLinearProgram(maximization=False, solver = "GLPK");
y = p2.new_variable(integer=True, nonnegative=True);
p2.add_constraint(y[0] + y[4] >= 1);        #04
p2.add_constraint(y[0] + y[5] >= 1)         #05
p2.add_constraint(y[0] + y[6] >= 1);        #06
p2.add_constraint(y[0] + y[7] >= 1);        #07
p2.add_constraint(y[1] + y[5] >= 1);        #15
p2.add_constraint(y[1] + y[6] >= 1);        #16
p2.add_constraint(y[2] + y[7] >= 1);        #27
p2.add_constraint(y[3] + y[4] >= 1);        #34
p2.add_constraint(y[3] + y[7] >= 1);        #37
p2.set_objective(y[0] + y[1] + y[2] + y[3] + y[4] + y[5] + y[6] + y[7] + y[8]);
p2.show();
print('Objective Value: {}'.format(p2.solve()));
for c, cc in p2.get_values(y).iteritems():
    print('x_%s = %s' % (c, int(round(cc))));