In this post we learned how to find all the triangles in a graph. The reason I wanted such an algorithm was that in computational topology/geometry, we are often dealing with graphs that represent triangulations of a manifold, and so the first step in this process is to get your hands on the triangles.

**What’s a Manifold?**

This is a much bigger topic than can be addressed in this post, but for those who want the gist: a manifold is a space that looks locally like some nice space. For instance a 2-manifold looks locally like . What does ‘looks like’ mean?

Well there are various strengths of similarity, a simple one is homeomorphism: a continuous mapping that is invertible with continuous inverse. These are transformations that mold the space without creating holes, creating disconnections, and preserve open and closed sets. As a first approximation, you can think of open sets as being sets that don’t include their boundaries, and closed sets as those that do.

What we are going to be concerned with are 2-manifolds, spaces that locally look flat. Meaning that locally you can put a little x and y coordinate system on a patch of the manifold. Apart from each point in the manifold having a patch around it that looks more or less flat, we also require that the patches overlap ‘nicely’. This has been just to give an intuitive idea for those who have never encountered manifolds and topology.

**What’s a triangulation?**

A triangulation is a way of criss-crossing a manifold with paths (edges), that meet at points (vertices), so that each region in the manifold is surrounded by 3 paths meeting at 3 points, in other words, every point in the manifold is on the edge or interior of a triangle. These need not be geometric triangles of course, but once we have such a triangulation, we can build the abstract graph it defines. From this graph we can find out many properties of interest of the manifold.

**The Data Structure**

We want to map the connectivity of the triangles, where two triangles are adjacent if they share an edge. So a nodes keeps track of which pair of vertices is shared with which other triangle. The other thing we would like is for the triangle to be able to keep track of an ordering of the vertices, clockwise or anticlockwise. Both these tasks are achieved using dictionaries.

class Triangle_Node(tig.BasicNode, object): def __init__(self, A, B, C, **kwargs): #We call the vertices A,B,C. super(Triangle_Node, self).__init__(**kwargs) self.A=A self.B=B self.C=C self.neighbors ={} #This takes a tuple of two vertices to adjacent triangle. self.orientation0={self.A:self.B, self.B:self.C, self.C:self.A} #One ordering of the vertices. self.orientation1={self.B:self.A, self.C:self.B, self.A:self.C} #The opposite ordering. self.orientation={} #A choice of orientation 1 or 2. self.number_boundary_edges=3 #Keeps track of how many edges are next to nothing. def set_orientation(self, A, B): #Choose an orientation so that A comes before B. if self.orientation0[A]==B: self.orientation=self.orientation0 elif self.orientation1[A]==B: self.orientation=self.orientation1 else: print 'Problem, seems like A,B are not in this triangle.' #Just in case.

Ok now we have all the tools to represent a triangulation. Next time we will show how to turn a graph into a triangulation. Mostly what we need to do is read in a list of triangles from the graph, create the triangle nodes, then we need to make consistent choices for vertex A,B,C in each triangle so that the directed triangles interact properly.

###### Related articles

- Finding Triangles in a Graph (triangleinequality.wordpress.com)

[…] so last time we introduced the data structure for representing a triangulation of a manifold, and here we showed […]