#Please do not post homework
#Jeffrey Tang, 1/26/25, Assignment 1

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

with(combinat):

#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:

#AM(G): inputs a undirected graph G and returns the adjacency matrix of its edges
AM := proc(G) local n, E, M, i, j, edge:
    
    # Extract the number of vertices and the edge set from G
    n := G[1]:
    E := G[2]:
    
    # Initialize the adjacency matrix with zeros
    M := [seq([seq(0, j = 1 .. n)], i = 1..n)]:
    
    # Populate the adjacency matrix
    for edge in E do
	i,j := op(edge):
	M[i][j] := 1:
        M[j][i] := 1: #reverse edge
    od:
    
    M:
end:

#Image(pi,G): 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, newE, i, edge;
    
    n := G[1]:
    E := G[2]:
    
    newE := {};
    
    for edge in E do
        # Apply the permutation to each vertex in the edge
        newE := newE union { {pi[op(1, edge)], pi[op(2, edge)]} };
    od;
    
    [n, newE]:
end:

#Isomorphic: input two graphs and determines if they are isomorphic graphs
Isomorphic := proc(G1, G2) local n1, E1, n2, E2, pi, perm, newG1:
    
    # Extract vertices and edges of the graphs
    n1 := G1[1]: E1 := G1[2]:
    n2 := G2[1]: E2 := G2[2]:
    
    # Graphs must have the same number of vertices
    if n1 <> n2 then 
	return false:
    fi:
    
    for pi in permute({$1..n1}) do
        # Apply the permutation to G1
        newG1 := Image([op(pi)], G1):
        
        # If the permuted graph matches G2, they are isomorphic
        if newG1[2] = E2 then 
		return true:
	fi:
    od:
    
    return false:
end:

#ULGraphs(n): input an integer and return each unique unlabel graph
ULGraphs := proc(n) local Gset, ULset, G, is_new, H:
    
    # Generate all labelled graphs on n vertices
    Gset := Graphs(n):
    
    ULset := {}:
    
    for G in Gset do
        is_new := true:
        
        # Check if G is isomorphic to any graph in ULset
        for H in ULset do
            if Isomorphic(G, H) then
                is_new := false:
                break:
            fi:
        od:
        
        if is_new then
            ULset := ULset union {G}:
        fi:
    od:
    
    ULset:
end:


#A000088