#3. Write a procedure AM(G) that inputs a graph [n,E] and outputs the #adjacency matrix, represented as a list of lengthn of lists of length #n, such that M[i][j]=1 if {i,j} belongs to E and 0 otherwise. For #example

#AM([2,{{1,2}});
#should output [[0,1],[1,0]] .


AM:=proc(G) local n,E,M, i, j:

n:=G[1]:
E:=G[2]:
M:=[seq([seq(0, j=1..n), i=1..n])]:

for i from 1 to n do
 for j from 1 to n do
  if {i,j} in E then 
   M[i][j] := 1:
   M[j][i] := 1:
  fi:
 od:
od:
M;

end:



#4 write a procedue Image(pi,G) that 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, E2, x, y:

n:=G[1]:
E:=G[2]:
E2:={}:

for (x,y) in E do 
 E2:= E2 union {pi[x], pi[y]}:
od:
[n, E2];

end:


#5 By definition an unlabelled graph is an equivalence class of #labeled #graphs under graph isomorphism (i.e. mapping under the #symmetric #group). Write a procedure
#ULgraphs(n)
#that outputs a set of graphs with ONE member of each equivalence #class.

with(combinat)

proc:=ULgraphs(n) local E, labeledgraphs, equivclasses, repG, newG, equivs, count, i, listtt:

#generating the equivalence classes
for i from 1 to n do:

E:=powerset({seq({i,j}, i=1..n, j=i+1..n)}):
labeledgraphs:=[{n, e} $ e in E]:

equivclasses:={}:
perms:=permute([seq(1..n)]):
listtt:=[]
for G in labeledgraphs do
 counts:=0
 equivs:=[]
 repG:=G:
 for pi in perms do 
  newG:= Image(pi, G):
  equivs:=[op(equivs), newG]:
 od:
 labeledgraphs:=convert(convert(labeledgraphs, set) minus       convert(equivs, set), list): 
 count:= count+1
 listtt:=[op(listtt), count]:
od:
end: 



#NOTE: THIS INCLUDES DISCONNECTED GRAPHS

#What is [seq(nops(ULgraphs(i)),i=1..6)]
#Is is in the OEIS? What is its A-number.

A000088: 1,1,2,4,11,34,156,...