Instantly share code, notes, and snippets.

# tkmharris/associahedron.py

Last active December 26, 2021 19:41
Show Gist options
• 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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 """ 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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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()