# OK to post homework
# Aurora Hiveley, 1/25/25, Assignment 1

Help:=proc(): print(`Graphs(n), Tri(G) , TotTri(G), AM(G), Image(pi,G), ULgraphs(n) `):   end:

with(combinat):

## adjacency matrices
# AM(G): inputs a graph [n,E] and outputs the adjacency matrix, represented as a list of length n 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,e,M:
n := G[1]:
E := G[2]:

M := [[0$n]$n]:     # initialize n x n matrix of all 0's

for e in E do
    M[e[1]][e[2]]++:
    M[e[2]][e[1]]++:
od:

M:
end:


## test call:
# AM([2,{{1,2}}]); 
# output [[0,1],[1,0]] 



## image of G under permutation
# Image(pi,G): inputs a permutation pi of {1,...,n} and a graph G=[n,E] 
# outputs the image under pi.

Image := proc(pi,G) local n,E,e,F,i,j:
# error checking
if nops(pi)<>G[1] then 
    error `Permutation length and size of vertex set do not agree.`
fi:

n := G[1]:
E := G[2]:
F := {}:    # initialize edge set of permuted graph

# pi(i) = position of i in pi 
for e in E do 
    member(e[1], pi, 'i'):
    member(e[2], pi, 'j'):

    F := F union {{i,j}}:
od:

[n, F]:
end:


## test call: 
# Image([2,3,4,1],[4,{{1,2},{1,3},{1,4}}]);
# output: [4, {{1, 4}, {2, 4}, {3, 4}}]



## unlabelled graphs 
#  an unlabelled graph is an equivalene class of labeled graphs under graph isomorphism (i.e. mapping under the symmetric group)
# ULgraphs(n): outputs a set of graphs with ONE member of each equivalence class

# slow and inefficient, but it'll do the trick
ULgraphs := proc(n) local setG, seenG, G, H, P, p:
setG := Graphs(n):  # start with set of all graphs on n vertices
seenG := {}:  # graphs we've already seen -- will prevent us from accidentally deleting an equiv class rep later

P := permute(n)[2..-1]:     # permutations of [n], minus trivial permutation

for G in setG do 
    seenG := seenG union {G}:   # we've seen the graph G now
    for p in P do 
        H := Image(p,G):

        if not H in seenG then 
            setG := setG minus {H}: # remove mapped duplicates that AREN'T equiv class reps
        fi:
    od:
od:

setG:
end:


## what is [seq(nops(ULgraphs(i)),i=1..6)] in the OEIS?
# [1, 2, 4, 11, 34, 156]:
# this is A000088







## copied from C1.txt

#An undirected  graph is a set of vertices V and a set of edges
#[V,E]   and edge e={i,j} where i and j belong to V
#Our vertices are labeled {1,2,...,n}
#Our data structure is [n,E] where E is the set of edges
#[3,{{1,2},{1,3},{2,3}}];

#If there are n vertices how many (undirected) graphs there

#Graphs(n): inputs a non-neg. integer and outputs the set of ALL
#graphs on {1,...,n} 
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:

#Tri(G): inputs a graph [n,E] and outputs the set of all triples {i,j,k}
#such {{i,j},{i,k},{j,k}} is a subset of E
Tri:=proc(G) local n,S,E,i,j,k:
n:=G[1]:
E:=G[2]:
#S is the set of love triangles
S:={}:
for i from  1 to n do
 for j from i+1 to n do
   for k from j+1 to n do
    #if member({i,j},E) and member({i,k},E), and member({j,k},E) then
     if {{i,j},{i,k},{j,k}} minus E={} then
       S:=S union {{i,j,k}}:
    fi:
   od:
 od:
od:

S:
end:

#Comp(G): the complement of G=[n,E]
Comp:=proc(G) local n,i,j,E:
n:=G[1]:
E:=G[2]:
[n,{seq(seq({i,j},j=i+1..n),   i=1..n)} minus E]:
end:
#Tot(G): the total number of love triangles and hate triangles
TotTri:=proc(G)
nops(Tri(G))+nops(Tri(Comp(G))):
end: