print(`Version of March 7, 2025`):

print(`LineGraph.txt : a Maple packag accompanying the paper`):
print(`Experimenting with Graham's Reconstruction Conjecture for Trees`):
print(` by Kaylee Weatherspoon and Doron Zeilberger.`):

print(`For a list of the MAIN procedures type: Help();`):
print(`For Help with a procedure type: Help(ProcedureName); for example: Help(Trees);`):


print(`For a list of the SUPPORTING procedures type: Help1();`):
print(`For Help with a procedure type: Help(ProcedureName); for example: Help(Trees);`):


Help1:=proc(): 
if nargs=0 then
print(`The SUPPORTING functions are`):
print(`  Comps, DressUp,  ULRtreesS, ULRseq, ULRseqS, WilfTreeCounts `): 
else
Help(args):
fi:
end:

Help:=proc(): 
if nargs=0 then
print(`The functions are`):
print(`  GClist, LineGraph,   InnerSum, RTrees, Trees, TestingGrahamSeq,  ULRtrees,  ULtrees, `): 


elif nargs=1 and args[1]=DressUp then
print(`DressUp(C). Dresses up a mult-composition C. Try:`):
print(`DressUp(Comps([1,1,2,4],4)[1]);`):

elif nargs=1 and args[1]=ULRseqS then
print(`ULRseqS(N): same as ULRseq(N) but the stupid way. Try:`):
print(`ULRseqS(9);`):

elif nargs=1 and args[1]=ULRseq then
print(`ULRseq(N): The first N terms of the sequence enumerating rooted unlabeled trees. Try:`):
print(`ULRseq(20);`):

elif nargs=1 and args[1]=Comps then
print(`Comps(L,n): inputs a list of pos. intgers L of length k and output the list of length k, let's call it C, such that C[i] is  a list of`):
print(`non-negative integers of length L[i] and and such that add(i*add(C[i]),i=1..k)=n. Try:`):
print(`Comps([1,1,2,4],4);`):

elif nargs=1 and args[1]=LineGraph then
print(`LineGraph(G) G=[n,E]`):
print(`output the line graph [n',E']`):
print(`List the edges in some random order if their number is n'`):
print(`form the edges of the line graph`):
print(`e1 is adjacent to e2 if they share a vertex. Try:`):
print(`LineGraphs([4,{{1,2},{1,3},{2,3},{1,4}}]);`):


elif nargs=1 and args[1]=GClist then
print(`GClist(T,k): inputs a tree T and a spos. integer k and outputs the list of iterated line-graphs up to the k-th.Try`):
print(` GClist([4,{{1,2},{1,3},{1,4}}],5);`):
print(`Also try: S:=ULtrees(4): {seq(GClist([4,s],3), s in S)};`):


elif nargs=1 and args[1]=RTrees then
print(`RTrees(n): the set of all rooted labeled trees on n vertices. Try:`):
print(`RTrees(5);`):

elif nargs=1 and args[1]=Trees then
print(`Trees(n): the set of all labeled trees on n vertices. Try:`):
print(`Trees(5);`):

elif nargs=1 and args[1]=TestingGrahamSeq then
print(`TestingGrahamSeq(n,m,k)): inputs integers n,m, and k and outputs 'Conjecture Holds' if the number of distinct Graham sequences of length k+1 of trees of order from n to m is the number of distinct trees of order from n to m  Try:`):
print(`TestingGrahamSeq(3,6,3);`):

elif nargs=1 and args[1]=ULtrees then
print(`ULtrees(n): The set of unlabled trees on n vertices it contains one representaion of each equivalence class`):
print(`try:`):
print(`ULtrees(5);`):

elif nargs=1 and args[1]=ULtreesS then
print(`ULtreesS(n): The set of unlabled trees on n vertices it contains one representaion of each equivalence class, the Stupid way (only for checking) `):
print(`try:`):
print(`ULtreesS(5);`):


elif nargs=1 and args[1]=ULRtrees then
print(`ULRtrees(n): The set of unlabled ROOTED trees on n vertices it contains one representaion of each equivalence class`):
print(`try:`):
print(`ULRtrees(5);`):

elif nargs=1 and args[1]=ULRtreesS then
print(`ULRtreesS(n): The set of unlabled ROOTED trees on n vertices it contains one representaion of each equivalence class. The stupid way (just for checking)`):
print(`try:`):
print(`ULRtreesS(5);`):

elif nargs=1 and args[1]=InnerSum then
print(`InnerSum(m): The inner sum value in Wilf's recurrence for the number of random unlabeled trees on m vertices`):
print(`try:`):
print(`InnerSum(6);`):

elif nargs=1 and args[1]=WilfTreeCounts then
print(`WilfTreeCounts(n): The number of random unlabeled trees on n vertices using the Wilf Recurrence Formula`):
print(`try:`):
print(`WilfTreeCounts(6);`):



else
print(`There is no Help for`, args[1]):
fi:
end:


#LineGraph(G) G=[n,E]
#output the line graph [n',E']
#List the edges in some random order if their number is n'
#form the edges of the line graph
#e1 is adjacent to e2 if they share a vertex

LineGraph:=proc(G) local E, i, taggededges, tag_e, ledges, n, m, j, k, L:
n:=G[1]:
E:=G[2]:

taggededges:=[]:

for k from 1 to nops(E) do:
tag_e:=convert(E[k], list):
%print(tag_e);
taggededges:=[op(taggededges),[op(tag_e), k]]:
od:
%print(taggededges):

#now I have a list of tagged edges

#if two edges {x,y}, {x,z} share an endvertex in G, then find the 
#edges [x,y,i] and [x,z, j] and add the edge {i,j} to the edges of #L(G)
#equivalently, if there's any overlap in the list version

ledges:=[]:
m:=nops(E):
for i from 1 to m do 
    for j from i+1 to m do
	if taggededges[i][1]=taggededges[j][1] or taggededges[i]	[1]=taggededges[j][2] or taggededges[i][2]=taggededges[j][1] 	or taggededges[i][2]=taggededges[j][2] then 
	    ledges:=[op(ledges), {taggededges[i][3], taggededges[j][3]}]:
	fi:
    od:
od:

ledges:=convert(ledges, set):
L:=[nops(E), ledges]:

end:


#2. 
#GClist:=proc(T,k)
#inputs a tree and a pos. integer k and outputs the sequence
#nops(V(T)), nops(V(L(T)),..., nops(V(L^k(T))


GClist:=proc(T,k) local i, iterlist, newT, countlist, newG:
iterlist:=[T]:
newT:=T:

#for i from 1 to k do
for i from 1 to k do
 newT:=LineGraph(newT):
 iterlist:=[op(iterlist), newT]:
od:

countlist:=[]:
for i from 1 to nops(iterlist) do
countlist:=[op(countlist), iterlist[i][1]]:
od:
countlist;
end:

with(linalg):
with(combinat):

#Trees(n): the set of all labeled trees on n vertices
Trees:=proc(n) local f, i, j, k1, j1, a, T, treeSet, singleTree;

if n=1 then
 RETURN({{}}):
fi:

if n=2 then
 RETURN({[2,{{1,2}}]}):
fi:

f := expand(det([seq([seq(-a[i,j], j=2..i-1), add(a[i,j], j=1..n)-a[i,i], seq(-a[i,j], j=i+1..n)], i=2..n)])):
    
treeSet := {seq({seq({op(op(k1, op(j1, f)))}, k1=1..nops(op(j1, f)))}, j1=1..nops(f))}:
    
# Convert each tree into the correct format [n, {edges}]
{seq([n, convert(T, set)], T in treeSet)};
end:


#NonIsoTrees: inputs number n and outputs the set of nonisomorphic #trees on n vertices

#__________________________________________________________

#PROBLEM!!! We get isomorphic trees from Trees(n). 

#Solution: sort into buckets based on edge size, then implement
#AHU recursion algorithm 


#________________________________________________________


TestingGrahamSeq := proc(n,m,k) local treelist, listofGrseqs, i, j, setofGrseqs, T, totaltrees:
    
    # Generate list of trees for each size from n to m
treelist := []:
for i from n to m do 
  treelist := [op(treelist), op(Trees(i))]:
od:
    
print(treelist);
    
    # Generate set of Graham sequences
setofGrseqs := {}:
for T in treelist do
   setofGrseqs := {op(setofGrseqs), GClist(T,k)}:
od:
print(setofGrseqs);
    
    # Calculate total number of trees directly from treelist
totaltrees := add(nops(T), T in treelist):
print(totaltrees);
  
    # Check the conjecture
if totaltrees = nops(setofGrseqs) then 
"Conjecture Holds"
    else 
"Conjecture FAILS!!!"
fi:
end:


#ISSUE: we are comparing isomorphism classes to sets of trees
#Need treelist to account for isomorphism
#Need Trees(n) to account for isomorphism


#ULtreesS(n): The set of unlabled trees on n vertices it contains one representaion of each equivalence class the stupid way
#try:
#ULtreesS(5);
ULtreesS:=proc(n) local S,A,pi,UL,i1,s:
if n=1 then
 RETURN({{}}):
fi:

S:=Trees(n):
S:={seq(s[2],s in S)}:

A:=permute(n):
UL:={}:
while S<>{} do
UL:=UL union {S[1]}:
S:=S minus {seq(subs({seq(i1=pi[i1],i1=1..n)},S[1]),pi in A)}:
od:
UL:

end:


#Implementation of Wilf RANRUT algorithm
#Doing what I'm told: RANRUT is an algorithm for generating random #unlabeled trees, and while it may be useful for sampling, the RANRUT #algorithm is not a valid choice for generating a list of all #unlabeled graphs on n vertices. 

#uses recursive decomposition based on tree enumeration formulas

#expected polynomial time
#trees on up to n vertices
#we use array instead of list for improved speed



with(combinat):
with(numtheory):

t:=table():
t[1]:=1:

InnerSum:=proc(m) local d, t, innersum :

innersum:=0:

for d in divisors(m) do

 if not assigned(t[d]) then 
  t[d]:=WilfTreeCounts(d):
 fi:
 innersum:=innersum+d*t[d]:
od:

RETURN(innersum):

end:

WilfTreeCounts:=proc(n) local m, outersum, innersum, t, innersumm:
option remember:
 if assigned(t[n]) then 
  RETURN(t[n]):
 fi:

if n=1 then RETURN(1); fi:

outersum:=0:
for m from 1 to n-1 do
 if not assigned(t[n-m]) then 
  t[n-m]:=WilfTreeCounts(n-m): 
 fi:

innersumm:=InnerSum(m):

outersum:=outersum+t[n-m]*innersumm:

od: 

t[n]:=outersum/(n-1):
RETURN(t[n]):
end:

#First 10 terms are 1, 1, 2, 4, 9, 20, 48, 115, 286, 719
#This is A000081 in the OEIS

#_________________________________________


(* 
WilfRANRUT:=proc(n) local STACK, TREE:

T:=Array(1..n, 1):
STACK:=Array(1..2, 1..n, 0):
TREE:=Array(1..n, 0):

N:= n:
IS1:=0:
IS2:=0:

if n<=2 then
 RETURN(TREE):
fi:



end:
*)

#RTrees(n): the set of all rooted labeled trees on n vertices
RTrees:=proc(n) local gu,i,gu1:
gu:=Trees(n):
gu:={seq(gu1[2],gu1 in gu)}:
{seq(seq([i,gu1],i=1..n),gu1 in gu)}:
end:



#ULRtreesS(n): The set of unlabled rooted trees on n vertices it contains one representaion of each equivalence class
#The stupid way (brute force, only for checking)
#try:
#ULRtreesS(5);
ULRtreesS:=proc(n) local S,A,pi,UL,i1:
if n=1 then
 RETURN({[1,{}]}):
fi:
S:=RTrees(n):
A:=permute(n):
UL:={}:
while S<>{} do
UL:=UL union {S[1]}:
S:=S minus {seq(subs({seq(i1=pi[i1],i1=1..n)},S[1]),pi in A)}:
od:
UL:
end:


#Comps(L,n): inputs a list of pos. intgers L of length k and output the list of length k, let's call it C, such that C[i] is  a list of
#non-negative integers of length L[i] and and such that add(i*add(C[i]),i=1..k)=n. Try:
#Comps([1,1,2,4],4);
Comps:=proc(L,n) local k,m,gu,lu,lu1:
option remember:
k:=nops(L):

if n<0 then
 RETURN({}):
fi:

if L=[] then
if n=0 then
 RETURN({[]}):
else
 RETURN({}):
fi:
fi:

if L[k]=0 then
 lu:=Comps([op(1..k-1,L)],n):
 RETURN({seq([op(lu1),[]],lu1 in lu)}):
fi:

gu:={}:

for m from 0 to trunc(n/k) do
lu:=Comps([op(1..k-1,L),L[k]-1],n-m*k):
for lu1 in lu do
 gu:=gu union {[op(1..k-1,lu1),[op(lu1[-1]),m]]}:
od:
od:
gu:
end:


#ULRseq(N): The first N terms of the sequence enumerating rooted unlabeled trees. Try:
#ULRseq(20);
ULRseq:=proc(N) local n:
[seq(WilfTreeCounts(n),n=1..N)]:
end:

#ULRseqS(N): Same as ULRseq(N) but the stupid way
ULRseqS:=proc(N) local L,n:
L:=[1]:
for n from 2 to N do
L:=[op(L),nops(Comps(L,n-1))]:
od:
L:
end:


#ULRtrees(n):representative rooted labled trees with n vertices for each equivalence class . Try:
#ULRtrees(4);
ULRtrees:=proc(n) local lu,i1,i:
option remember:
if n=1 then
 RETURN([[1,{}]]):
fi:
lu:=Comps([seq(nops(ULRtrees(i)),i=1..n-1)],n-1):
[seq(DressUp(lu[i1]),i1=1..nops(lu))]:
end:

#DressUp(C). Dresses up a mult-composition C. Try:
#DressUp(Comps([1,1,2,4],4)[1]);
DressUp:=proc(C) local n,katan,i,j,k,i1,m1,V,lu:
katan:=1:
n:=nops(C)+1:
V:={}:
for i from 1 to nops(C) do
 for j from 1 to nops(C[i]) do
 k:=C[i][j]:
 for i1 from 1 to  k do
 lu:=ULRtrees(i)[j]:
 lu:=subs({seq(m1=katan-1+m1,m1=1..i)},lu):
 V:=V union {{n,lu[1]}} union lu[2]:
 katan:=katan+i:
 od:
od:
od: 
[n,V]:
end:


#ULtrees(n): the set of unlabeled trees on n vertices (with random labeling). Try:
#ULtrees(6);
ULtrees:=proc(n) local S,A,UL,i1,pi:
S:=ULRtrees(n):
S:={seq(S[i][2],i=1..nops(S))}:

A:=permute(n):
UL:={}:
while S<>{} do
UL:=UL union {S[1]}:
S:=S minus {seq(subs({seq(i1=pi[i1],i1=1..n)},S[1]),pi in A)}:
od:
UL:


end: