#OK to post homework
#Nick Belov, 1/26/2025, Assignment 1
with(combinat):

#Graphs(n): inputs a non-neg. integer and outputs the set of ALL
#graphs on {1,...,n} 
#stole this from thursdays class :>
Graphs:=proc(n) local i,j,S,E,s:
	E:={seq(seq({i,j},j=i+1..n),   i=1..n)};
	S:=powerset(E):
	{seq([n,s],s in S)}:
end:

#Graphs [n,E]
#E is of the form {{u,v},{u2,v2}, ...}

AM := proc(G)
	local n, E, M, e, i, j,u,v;
	n := G[1];
	E := G[2];	
	
	M := [seq([seq(0, j=1..n)], i=1..n)];
	
	for e in E do
		u:=op(1,e);
		v:=op(2,e);
		M[u][v]:=1;
		M[v][u]:=1;	
	od;

	return M		
end:

#il represent a permutation as a list length n
#consisting of only elements in 1..n where each one appears once

#inputs a permutation pi of {1,...,n} and a graph G=[n,E] and outputs the image under pi.
Image := proc(pi,G)
	local n,E,E1,e,G1;
	n := G[1];
	E := G[2];
	
	E1 := {seq({pi[op(1,e)],pi[op(2,e)]},e in E)};
	G1 := [n,E1];
	
	return G1;
end:

#outputs a representitive of each isomorphism class for graphs of size n
ULgraphs := proc(n):
	local labeledG,uG,flag,pi,g,g1;
	labeledG:=Graphs(n);
	uG:={};
	for g in labeledG do
		flag:=1;
		for pi in permute([seq(1..n)]) do
			g1:=Image(pi,g);
			if g1 in uG then
				flag:=0;
			fi;			
		od;
		if flag = 1 then
			uG:= uG union {g};	
		fi;
	od;
	return uG;
end:
#output of [seq(nops(ULgraphs(i)), i = 1 .. 6)] is below
#[1, 2, 4, 11, 34, 156]
#yes this is in OEIS! A000088