Unlabeled Trees

The following code, written by my student Andrew Meier, quickly generates all unlabeled trees on the specified number of vertices. The algorithm is based on “Constant Time Generation of Free Trees” by McKay, Wright, Ozlyzko, and Richmond (Siam J. Computing 15, 1986).

Specify the number of vertices by changing the value of num_vertices.

Change print_images to “false” (no quotes) if you wish to suppress the graphical output.





# Use this cell to generate the spanning trees of the complete bipartite graph
# for all bipartitions of num_vertices vertices.
num_vertices = 5
print_images = True
####################################################################################
# DO NOT EDIT BELOW THIS LINE
####################################################################################
def starting_tree(n):
if n%2==0:
L=range(0,(n/2)+1)
for i in range ((n/2)+1,n+1):
L.append(i-(n/2))
return L
else:
L=range(0,(n/2)+2)
for i in range ((n/2)+2,n+1):
L.append(i-n+((n-1)/2))
return L
def jump(L):
m = 0
while L[m] != 1:
m = m+1
if L[m] == 1:
m = m+1
while L[m] != 1:
m = m+1
m = m-1
if L[m]<=2: q = m - 1 while (L[m]-L[q]) != 1: q = q -1 S = L[0:m] for i in range(m,len(L)): S.append(S[i - (m-q)]) return S else: q = m - 1 while (L[m]-L[q]) != 1: q = q -1 S = L[0:m] for i in range(m,len(L)): S.append(S[i - (m-q)]) t = max(S) U = S[0:len(S)-t] for i in range (0,t): U.append(i+1) return U def successor(L): p = len(L)-1 while L[p] == 1: p = p - 1 q = p-1 while (L[p]-L[q]) != 1: q = q -1 S = L[0:p] for i in range(p,len(L)): S.append(S[i - (p-q)]) return S def end_condition(n): L=[1]*(n-1) L.insert(0,0) return L def is_free_tree(T): global L1 m = 0 while T[m] != 1: m = m+1 if T[m] == 1: m = m+1 while T[m] != 1: m = m+1 n = 1 U=T[n:m] L1=[elem-1 for elem in U] L2=T[m:len(T)] L2.insert(0,0) if max(L2) > max(L1):
return true
if max(L1) == max(L2):
if len(L1) < len(L2): return true if len(L1) == len(L2): if cmp(L1,L2) <= 0: return true return false def adjacency_matrix(L): p=len(L)-1 A=matrix(p+1) while p!=0: q=p-1 while (L[p]-L[q]) != 1: q = q -1 A[p,q]=1 A[q,p]=1 p=p-1 return A L=starting_tree(num_vertices - 1) count = 0 trees = [None]*floor(num_vertices/2) bipartite_count=[None]*floor(num_vertices/2) for i in range (0,floor(num_vertices/2)): trees[i]=[] bipartite_count[i]=0 while (L != end_condition(num_vertices)): if is_free_tree(L): bipartite=[0 if x % 2 == 0 else 1 for x in L] x = bipartite.count(1) y = bipartite.count(0) index = min(x,y)-1 trees[index].append(L) bipartite_count[index]=bipartite_count[index]+1 L = successor(L) else: L = jump(L) bipartite=[0 if x % 2 == 0 else 1 for x in L] x = bipartite.count(1) y = bipartite.count(0) index = min(x,y)-1 trees[index].append(L) bipartite_count[index]=bipartite_count[index]+1 # image printing control for i in range(len(trees)): s = i + 1 t = num_vertices - s print '' print '' print 'There are ' + str(bipartite_count[i]) + ' distinct unlabeled spanning trees of K(' + str(s) + ',' + str(t) + ')' for L in trees[i]: M = adjacency_matrix(L) tree = Graph(M) # Burnside's Lemma st_fact = factorial(s) * factorial(t) if s == t: st_fact = st_fact * 2 autSize = tree.automorphism_group(order=true, return_group=false) numTrees = st_fact / autSize heading = format(int(numTrees), ",d") + " Distinct Labelings" if print_images: show(plot(tree,title=heading,vertex_labels=False,layout='tree',figsize=4)) else: print heading