#hw1TijilKiran.txt: Jan. 26, 2025 Exp Math (Dr. Z.)
Help:=proc(): print(`Graphs(n), Tri(G) , TotTri(G) , AM(G), Image(pi, G), ULgraphs(n)`):   end:

with(combinat):

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

#Image(pi, G): the image of a graph under a permutation of vertices
Image := proc(pi, G)
    local n, E, permutedEdges, i, e:
    n := G[1]:
    E := G[2]:
    
    permutedEdges := {}:
    for e in E do
        permutedEdges := permutedEdges union { {pi[op(1, e)], pi[op(2, e)]} }:
    od:
    
    [n, permutedEdges]:
end:

#AM(G): the adjacency matrix of an undirected graph
AM := proc(G)
    local n, E, M, i, j, e:
    n := G[1]:
    E := G[2]:
    M := [seq([seq(0, j=1..n)], i=1..n)]:
    for e in E do
        i, j := op(e):
        M[i][j] := 1:
        M[j][i] := 1:
    od:
    M:
end:

Isomorphic := proc(G1, G2)
    local n, pi, E1, E2, permuted_G2:
    n := G1[1]:
    E1 := G1[2]:
    E2 := G2[2]:
    for pi in permute([seq(1..n)]) do
        permuted_G2 := Image(pi, G2):
        if permuted_G2[2] = E1 then
            return true:
        end if:
    end do:
    return false:
end proc:

#ULgraphs: returns the number of graphs of n unlabeled vertices
ULgraphs := proc(n)
    local all_graphs, unique_graphs, G, H:
    all_graphs := Graphs(n):
    unique_graphs := {}:
    for G in all_graphs do
        if not member(true, [seq(Isomorphic(G, H), H in unique_graphs)]) then
            unique_graphs := unique_graphs union {G}:
        end if:
    end do:
    return unique_graphs:
end proc:

# This is sequence A000088 [1, 2, 4, 11, 34, 156]