Home » maths » graph theory » Turning a graph into a Triangulation

Turning a graph into a Triangulation

Ok so last time we introduced the data structure for representing a triangulation of a manifold, and here we showed how to find the triangles in a graph. Today we discuss how to take a graph and turn it into the triangulation data structure.

[SPOILERS:  Of course a graph cannot tell you which triangles (in the sense of subgraphs isomorphic to C_3) are considered triangles (in the sense of a two dimensional simplex or disc), so we assume that all of them are. What we are actually doing in this case is recovering the 2-skeleton of the Vietoris-Rips complex of which the given graph is the 1-skeleton. So in particular, this method will call a triangle a disc and not a circle. Please don’t worry if this paragraph doesn’t make any sense to you yet, this was written retrospectively! ]

 

First I’ll remind you of how we find all the triangles in a graph:

def iterate_triangles(graph):
    G=graph
    V=G.vertices
    V.sort(key=lambda x: G.get_degree(x), reverse=True)
    n=len(V)
    A={}
    for i in range(n):
        V[i].index=i
        A[V[i]]=set()
    for first_vertex in V:
        for second_vertex in G.get_vertex_neighbors(first_vertex):
            if first_vertex.index < second_vertex.index:
                for third_vertex in A[first_vertex].intersection(A[second_vertex]):
                    yield [first_vertex.index, second_vertex.index, third_vertex.index]
                A[second_vertex].add(first_vertex)

Now we want to iterate through the triangles, make a Triangle_Node object for each one, and find out what its neighbors are. Each triangle is given to us as a list of three vertex indices, so for each pair of vertices, we use it as a key in a dictionary pointing to the triangle, that way when another triangle with one of these pairs is created, it can look up the triangle sharing that edge.

Like this:

class Triangulation(tig.UnDirGraph, object): #Having a special class will be convenient later.
    def __init__(self, **kwargs):
        super(Triangulation, self).__init__(Vertex=Triangle_Node,**kwargs) # Using Triangle_Nodes.

def triangulate(graph):
    G=Triangulation()
    shared_edge_dict={} #This will keep track of which triangles are adjacent to which as we
                        #read them in.
    for triangle in iterate_triangles(graph):
        node=Triangle_Node(A=triangle[0], B=triangle[1], C=triangle[2])
        node.seen_before=False #Not necessary, gets it ready for a depth first search later
                               #if we want to try and orientate the manifold.
        G.add_vertex(node)
        def init_nodes(nodes): #To save typing this tells the triangles about its neighbors
                               #that we know about so far, and conversely tells its neighbors
                               #that it is a neighbor.

            #Since there are two ways of writing the pair A,B, we put it in both ways.
            #We could just use a canonical ordering of the pair, but then
            #we have just traded space for time, the choice is yours.
            nodes=tuple(nodes)
            op_nodes=(nodes[1],nodes[0])
            try: #Looks to see if we have encounter this pair of vertices before.
                neighbor = shared_edge_dict[nodes]
                G.create_edge([neighbor, node])
                node.neighbors[nodes]=neighbor
                node.number_boundary_edges -=1
                node.neighbors[op_nodes]=neighbor
                neighbor.neighbors[nodes]=node
                neighbor.neighbors[op_nodes]=node
                neighbor.number_boundary_edges -= 1 #We know this edge is not on the boundary.
            except KeyError: #Haven't seen this pair of vertices before.
                node.neighbors[nodes]='BOUNDARY' #This is provisional, we will overwrite this
                                                 #later if it is truly not on the boundary.
                node.neighbors[op_nodes]='BOUNDARY'
                shared_edge_dict[nodes] = node #Adds the pair to the dictionary of seen pairs.
        nodes = [triangle[0], triangle[1]]
        init_nodes(nodes)
        nodes = [triangle[0], triangle[2]]
        init_nodes(nodes)
        nodes = [triangle[1], triangle[2]]
        init_nodes(nodes)
    return G

And we’re done! We can now take a graph of a triangulation and produce something much more useful. This part has been kind of boring, but we can use this, as you’ll see next time, to find out whether or not the manifold is orientable, extremely easily.

Advertisements

1 Comment

  1. […] it is time to reap the rewards of our efforts in turning a graph of a triangulated manifold into a triangulation data structure.  Using this data […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: