Is there a way to get the embedding?

[jamartinh]

Hi, is there a way to get the embedding? for instance as a list of faces where each face is a list as well of its vertices?

Some time ago I had a code to get it from the original boyer code:

For some reason in this new version I am unable: I am putting the code I used:

Is there a way to do the same here ?

def is_planar_nx(G, set_embedding=True):
    """
    Calls Boyer's planarity algorithm to determine whether g is
    planar.
    """
    # First take care of a trivial case.  We ignore the set_pos,
    # set_embedding
    if G.size() == 0: return True

    # relabel vertices to the set {0,...,n-1}
    cdef list vertices, adjacency_list
    cdef dict embedding
    cdef int status, m, n, i, j
    cdef graphP theGraph

    theGraph = gp_New()
    status = gp_InitGraph(theGraph, G.order())

    if status != OK:
        raise RuntimeError("gp_InitGraph status is not ok.")

    vertices = sorted(G.nodes())
    for u, v in G.edges():
        m, n = vertices.index(u), vertices.index(v)
        status = gp_AddEdge(theGraph, m + 1, 0, n + 1, 0)
        if status == NOTOK:
            raise RuntimeError("gp_AddEdge status is not ok.")
        elif status == NONEMBEDDABLE:
            return False

    status = gp_Embed(theGraph, EMBEDFLAGS_PLANAR)

    if status == NOTOK:
        gp_Free(&theGraph)
        raise RuntimeError("Status is not ok.")
    if status == NONEMBEDDABLE:
        gp_Free(&theGraph)
        return False

    if not set_embedding:
        gp_Free(&theGraph)
        return True

    gp_SortVertices(theGraph)
    embedding = dict()

    for i from 1 <= i < theGraph.N + 1:
        adjacency_list = list()
        j = theGraph.V[i].link[0]  # the first edge
        while j >= 1:
            adjacency_list.append(vertices[theGraph.E[j].neighbor - 1])
            j = theGraph.E[j].link[0]  # the next edge

        embedding[vertices[i - 1]] = adjacency_list

    G.embedding = embedding

    gp_Free(&theGraph)
    return True

And then:

    def face_list(self):
        """
        List the faces of Graph (returned as a list of lists of edges (tuples) of
        the current embedding.

        """
        if not self.embedding:
            self.is_planar()  # get an embedding

        # Establish set of possible edges
        edgeset = set(map(tuple, self.edges))
        edgeset |= set(map(tuple, list(map(reversed, edgeset))))

        # Storage for face paths
        path = [edgeset.pop()]
        faces_sets = []

        # Trace faces
        while len(edgeset) > 0:
            neighbors = self.embedding[path[-1][-1]]
            next_node = neighbors[(neighbors.index(path[-1][-2]) + 1) % (len(neighbors))]
            tup = (path[-1][-1], next_node)

            if tup == path[0]:
                faces_sets.append(set(map(frozenset, path)))
                path = [edgeset.pop()]
            else:
                path.append(tup)
                edgeset.discard(tup)

        if len(path):
            faces_sets.append(set(map(frozenset, path)))

        return faces_sets

[hagberg]

It's been a long time since I looked at this code. Perhaps someone currently using it might be able to comment?

[hagberg]

This looks like a useful feature. Have you made any attempts to get it working?