#The setup will be as follows: we will only list the preferences of the women, since they determine the whole setup.
#The people that a certain woman knows will be a list of integers between 1 and m
#So all the information is given as a list of lists.

#Just for fun, we'll make a converter that gives left preferences to right preferences
#LeftToRight: int list list -> int list list

LeftToRight:= proc(A)
local i,j,Alen,curlen,Aflat, right,m,curA:

Aflat:=ListTools[Flatten](A):

m:=max(op(Aflat)):
Alen:=nops(A):
right:=[]:

#The setup for the right
for i from 1 to m do
	right:=[[],op(right)]:
od:

for i from 1 to Alen do
	curA:=A[i]:
	curlen:=nops(curA):
	for j from 1 to curlen do
		right[curA[j]]:=[i,op(right[curA[j]])]:
	od:
od:

right:
end:

#MakeGraph
#It's simple - give the connections, we'll infer the left side and the right side, and make the graph from there
#Note: left side will be letters, right side will be numbers.
#MakeGraph: int list list -> Graph
MakeGraph := proc(conn)
local alphabet, curr,ncurr,i,j,n,G,right,nright:
alphabet:="abcdfghijklmnopqrstuvwxyz":
n:=nops(conn):                         #Number of people on the left side
networks[new](G):

for i from 1 to n do
	networks[addvertex](nprintf(StringTools[NthWord](alphabet,i)),G):
od:

right:={op(ListTools[Flatten](conn))}:
nright:=nops(right):

for i from 1 to nright do
	networks[addvertex](i,G):
od:

#Now we just go through the connections and add everything!

for i from 1 to n do
	curr:=conn[i]:
	ncurr:=nops(curr):
	for j from 1 to ncurr do
		networks[addedge]({nprintf(StringTools[NthWord](alphabet,i)),curr[j]},G):
	od:
od:

G:
end:




#DrawBipartite
#This procedure draws a bipartite graph - just give the lists: right list, and connections from the left side
#Note that the left side will be letters, as inferred from the conn list
#DrawBipartite: graph -> pictoral representation of graph
#IT IS ASSUMED THAT G WAS CREATED THROUGH MakeGraph

DrawBipartite := proc(G)
local verts,left,right,n,i:

verts:=networks[vertices](G):
n:=nops(verts):
left:=[]:
right:=[]:

for i from 1 to n do
	if type(verts[i],integer) then
		right:=[verts[i],op(right)]:
	else
		left:=[verts[i],op(left)]:
	fi:
od:

right:=ListTools[Reverse](sort(right)):
left:=ListTools[Reverse](sort(left)):

networks[draw](Linear(left,right),G):
end:

#ListLocation
#Finds index of element in the list - the first occurrence
#ListLocation: int * int list -> int

ListLocation := proc(target,L)

local i,n:

n:=nops(L):

for i from 1 to n do
	if L[i]=target then
		return i:
	fi:
od:

return 0:
end:
#CombinedMales
#This procedure inputs the data, all women, plus a subset of the women. It then returns the males that at least one of them know.
CombinedMales := proc(A,L,women)
local i,reduced_list,n,location,nL:

nL:=nops(L):
n := nops(women):
reduced_list:=[]:

for i from 1 to n do	
	location:=ListLocation(women[i],L):
	printf("The location is %d\n",location):
	reduced_list:=[op(reduced_list),A[location]]:
od:

[op({op(ListTools[Flatten](reduced_list))})]:
end:

#This is a helper function for Marriage. It takes the connections (of n) and a two lists whose union is 1..n
#It also inputs the males of the second list
#It returns two connections, one from each list, where they share no males in common
#marriageReduce : int list list * int list * int list * int list -> int list list * int list list

MarriageReduce := proc(conn,one,two,L)
local i,j,one_males,two_males,curr,ncurr,one_conn,two_conn,n_one,n_two,one_conn_old,two_conn_old,all_males,location:

all_males:=CombinedMales(conn,L,[op({op(one)} union {op(two)})]):
#These are the males that really matter.
two_males:=CombinedMales(conn,L,two):
one_males:=[op({op(all_males)} minus {op(two_males)})]:
one_conn_old:=[]:
two_conn_old:=[]:
n_one:=nops(one):
n_two:=nops(two):

for i from 1 to n_one do
	location:=ListLocation(one[i],L):
	one_conn_old:=[op(one_conn_old),conn[location]]:
od:

for i from 1 to n_two do
	location:=ListLocation(two[i],L):
	two_conn_old:=[op(two_conn_old),conn[location]]:
od:

n_one:=nops(one_conn_old):
n_two:=nops(two_conn_old):
one_conn:=[]:
two_conn:=[]:

for i from 1 to n_one do
	curr:=one_conn_old[i]:
	one_conn:=[op(one_conn),[]]:
	ncurr:=nops(curr):
	for j from 1 to ncurr do
		if ListTools[Occurrences](curr[j],two_males) = 0 then
			one_conn[i] := [op(one_conn[i]),curr[j]]:
		fi:
	od:
od:

for i from 1 to n_two do
	curr:=two_conn_old[i]:
	two_conn:=[op(two_conn),[]]:
	ncurr:=nops(curr):
	for j from 1 to ncurr do
		if ListTools[Occurrences](curr[j],one_males) = 0 then
			two_conn[i] := [op(two_conn[i]),curr[j]]:
		fi:
	od:
od:

one_conn,two_conn:
end: 



#An attempt to solve the marriage problem! 
#Marriage: int list list -> int list
#Returns a list of males for each woman, or gives an error if it is not possible.

Marriage:= proc(L,A)
local i,j,numRight,Aflat,n,leftIndex,nmale,S,curr,ncurr,leftover,leftover_males,males,nleftover,one,two,two_conn,n_one,one_conn,newA,X,Y,newguy,newnewA,X1,X2,Y1,Y2,Z1,Z2,newL:

n:=nops(A):
Aflat:= ListTools[Flatten](A):
numRight:=max(op(Aflat)):
leftover_males:=[]:
males:=[]:

#We really need some sort of base case!
if n=1 and A[1]=[] then
	error("Marriage Impossible!"):
fi:
if n=1 then
	printf("%d hooked up with %d\n",L[1],A[1][1]);
	return [L[1]],[A[1][1]]:
fi:

for i from 1 to n do
	if A[i]=[] then
	error("Marriage Impossible!"):
	fi:
od:

S:=combinat[subsets](L):

while not S[finished] do 
	curr:=S[nextvalue]():
	if curr=[] then
		curr:=S[nextvalue]():
	fi:	
	printf("Looking at "):
	print(curr):
	nmale:=nops(CombinedMales(A,L,curr)):
	ncurr:=nops(curr):
	#First case: we're screwed
	if nmale < ncurr then
		error("Marriage Impossible!"):
	fi:
	#Second case: gotta do a bit of work.
	if nmale = ncurr and curr<>L then
		one:=[op({op(L)} minus {op(curr)})]:
		two:=curr:
		printf("MarriageReduce input:"):
		print(A,one,two,L):
		X,Y:=MarriageReduce(A,one,two,L):
		printf("Splitting up\n"):
		print(X,Y):
		X1,X2:=Marriage(one,X):
		Y1,Y2:=Marriage(two,Y):
		return [op(X1),op(Y1)],[op(X2),op(Y2)];
	fi:
od:
		
printf("Do we get here??\n");

#If we get all the way over here, then we just take the first girl, take her first guy, and go from there.
newA:=[op(2..n,A)]:
newL:=[op(2..nops(L),L)]:
newnewA:=[]:
newguy:=A[1][1]:

for i from 1 to n-1 do
	curr:=newA[i]:
	newnewA:=[op(newnewA),[]]:
	ncurr:=nops(curr):
	for j from 1 to ncurr do
		if evalb(curr[j]<>newguy) then
			newnewA[i]:=[op(newnewA[i]),curr[j]]:
		fi:
	od:
od:
printf("We took a girl out, what's left is "):
print(newL,newnewA):
Z1,Z2:=Marriage(newL,newnewA):
return [L[1],op(Z1)],[newguy,op(Z2)]:
end:	
#We need to separate the males along with the females, sadly! :(

Marry := proc(conn)
Marriage([seq(i, i in 1..nops(conn))],conn):
end: