Skip to content

Instantly share code, notes, and snippets.

@tkmharris
Last active December 26, 2021 19:41
Show Gist options
  • Save tkmharris/cca3976c30a8ddb27297d8eaa731ae87 to your computer and use it in GitHub Desktop.
Save tkmharris/cca3976c30a8ddb27297d8eaa731ae87 to your computer and use it in GitHub Desktop.
Gist for generating Loday's integer-coordinate realisation of the the Stasheff polytope (associahedron) https://arxiv.org/abs/math/0212126
"""
Script to generate the (integer) vertices of Loday's realisation
of the n-associahedron in (n-1)-dimensional associahedron
as calculated using planar binary trees in:
https://arxiv.org/abs/math/0212126
(Realisation of the Stasheff Polytope)
Loday construction is as follows:
- each planar binary tree has a canonical "left to right" labelling of its internal nodes
- given a planar binary tree so labelled, Loday prescribes a rule for generating a vector (of integers)
- the set of all these integer vectors over all planar binary trees with n leaves is the set of vertices of the n-associahedron.
The BinTree class encapsulates binary trees as needed for the calculation.
We write custom functions for labelling the trees as described in Loday's paper outside the tree class.
A separate function generates all planar binary trees with a given number of leaves.
The main function is associahedron_vertices.
"""
## CUSTOM TREE CLASS
class BinTree(object):
def __init__(self, label=None):
# initialize a tree with one node, possibly labelled
self.left = None
self.right = None
self.label = label
# track number of leaves
self.num_leaves = 1 # in a more general class we could have to be careful
self.num_left_leaves = 0 # about managing these. Since we're only creating new
self.num_right_leaves = 0 # trees by initialising and "adding" them, we're safe.
def set_label(self, label):
self.label = label
def set_left(self, other):
"""
Set left child of self to be some other tree, update leaf counts
"""
self.left = other
# update leaf count
self.num_left_leaves = other.num_leaves
self.num_leaves = self.num_left_leaves + self.num_right_leaves
def set_right(self, other):
"""
Set right child of self to be some other tree, update leaf counts
"""
self.right = other
# update leaf count
self.num_right_leaves = other.num_leaves
self.num_leaves = self.num_left_leaves + self.num_right_leaves
def __add__(self, other):
"""
Sum of two trees is tree formed by grafting
left and right trees onto a new root node
rtype: BinTree
"""
new = BinTree()
new.set_left(self)
new.set_right(other)
return new
def isleaf(self):
"""
Check whether self is a leaf (has no children).
rtype: bool
"""
return not bool(self.left or self.right)
def get_nodes(self):
"""
Return a list of all the nodes (Tree objects) in a tree.
rtype: [BinTree]
"""
if self.isleaf():
return [self]
else:
return [self] + self.left.get_nodes() + self.right.get_nodes()
def get_leaves(self):
"""
Return a list of all the leaves (Tree objects with no children) in a tree.
rtype: [BinTree]
"""
return [node for node in self.get_nodes() if node.isleaf()]
def get_internal_nodes(self):
"""
Return a list of all the non-leaves (Tree objects with children) in a tree.
rtype: [BinTree]
"""
return [node for node in self.get_nodes() if not node.isleaf()]
## TREE FUNCTIONS
def label_leaves(tree, fst_label=0):
"""
Label leaves in the tree from left to right, starting with value fst_label and incrementing by one. Returns the final label + 1.
When called on the root with fst_label = 0 it labels the leaves 0,1,2,... from left to right and returns the number of leaves.
"""
if tree.isleaf():
tree.label = fst_label
return fst_label + 1
else:
num_left_leaves = label_leaves(tree.left, fst_label=fst_label)
num_leaves = label_leaves(tree.right, fst_label=num_left_leaves)
return num_leaves
def leftmost_leaf(tree):
"""
Helper function.
Return the "leftmost" leaf of a tree.
rtype: BinTree
"""
if tree.isleaf():
return tree
else:
return leftmost_leaf(tree.left)
def loday_label(tree, fst_leaf_label=0):
"""
Label the nodes of a binary tree as follows:
* label leaves 0, 1, 2, ... from left to right
* the (unique) internal node falling between leaf i-1 and leaf i is given label i
* equivalently, the label of an internal node is the label of the leftmost leaf of the node's right branch.
"""
# first label the leaves
label_leaves(tree)
# then label internal nodes
internal_nodes = tree.get_internal_nodes()
for node in internal_nodes:
node.label = leftmost_leaf(node.right).label
return
def associahedron_coord(tree):
"""
Given a binary tree (with n leaves), find the associated integer point
in (n-1)-d space as described in Loday's paper.
tree: BinTree
rtype: [int]
"""
# label tree
loday_label(tree)
# put internal leaves in order
internal_nodes_ordered = [None]*(tree.num_leaves - 1) # 1 fewer internal nodes than leaves in binary tree
for node in tree.get_internal_nodes():
i = node.label
internal_nodes_ordered[i-1] = node
# return (a_i*b_i), i = 1, .., n , where
# a_i | b_i = leaves on left|right branch of internal node i
return [
node.num_left_leaves*node.num_right_leaves
for node in internal_nodes_ordered
]
def all_trees(nleaves):
"""
Return a list of all Binary Trees with nleaves leaves.
(Length of the list should be the (nleaves-1)st Catalan number.)
nleaves: int
rtype: [BinTree]
"""
if nleaves < 1:
return []
elif nleaves == 1:
return [BinTree()]
else:
trees = []
for i in range(1, nleaves):
trees += [ltree + rtree
for ltree in all_trees(i)
for rtree in all_trees(nleaves-i)
]
return trees
## MAIN FUNCTION
def associahedron_vertices(degree):
"""
Get vertices of associahedron of degree degree
Vertices are integer-coordinate vectors in dimension degree-1
all lying in a hyperplane of dimension degree-2.
degree: int
rtype: [[int]], inner lists of length degree-1.
"""
trees = all_trees(degree)
coords = [
associahedron_coord(tree)
for tree in trees
]
return coords
import numpy as np
from trimesh import Trimesh
from associahedron import associahedron_vertices
def main(filename="repr/loday-5-associahedron.stl"):
# vertices of 5 associahedron in (3D subspace of) R^4
verticesR4 = associahedron_vertices(5)
# helper function to convert vertex coordinates to 3D
def toR3(vec):
"""
Send vector in R^4 to its image under an isometry of R^4 that sends
H = {vec|∑vec_i = 10} (hyperplace containing 5-associahedron) to {vec|vec_0 = 0}.
vec: np.array (in R^4,)
rtype: np.array (in)
"""
# check input is acceptable
if vec.shape != (4,):
raise ValueError("Input should be in R^4")
if sum(vec) != 10:
raise ValueError("Input should be in hyperplane {vec|∑vec_i = 10}")
# perform euclidean motion to hyperplane vec_0 = 0
t = np.array([5/2, 5/2, 5/2, 5/2]) # vector from origin to H, normal to H
M = np.array(
[
[1/2, 1/2, 1/2, 1/2],
[1/2, 1/2, -1/2, -1/2],
[1/np.sqrt(2), -1/np.sqrt(2), 0, 0],
[0, 0, 1/np.sqrt(2), -1/np.sqrt(2)]
]
) # orthogonal matrix sending normal to H to x_0 axis
vec = M @ (vec - t) # do motion
return vec[1:] # drop zero 1st coord
# transform associahedron vertices to R3
verticesR3 = [
toR3(np.array(coord))
for coord in verticesR4
]
# create mesh and fill in faces using convex hull
ass_mesh = Trimesh(vertices=verticesR3).convex_hull
# export
ass_mesh.export(filename, file_type='stl')
return
## MAIN
if __name__ == "__main__":
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment