Given a grouping of selected vertices in a mesh, how do I test if they form a contiguous edge loop?

Question

I'd like to be able to run a a test on a grouping of selected vertices in a mesh. The function would return a boolean result based on whether all the vertices in the grouping are connected in a linear fashion, thereby forming an edge loop.

To the best of my knowledge, there is no IsEdgeLoop operator in the API at this time. Bmesh seems to have some better mesh tools, but I don't see a solution as of yet. I'm thinking some clever algorithm to traverse an array of vertex indices is required, but could use some input from others.

Answer 1

I'd implement the following algorithm:

1. Give each vertex a unique ID.
2. Choose one of your grouping's vertices, and add its ID to a set() S.
3. Check all vertices ID that are connected by an edge to (2). Add these IDs to S.
4. Are any of the IDs in (3) the same as the ID in (2)? If yes, Return True.
5. If not, for each in (3), recursively do steps 2-5. If you run out of edges/vertices, return False.

Note: you use the vertices IDs in S to avoid choosing already processed vertices in step 5.

EDIT:

Pseudo-code could be something like:

grouping = [ selected vertices in a mesh ]

S = set()

for v in grouping.vertices():
    S.add(v.id)
    for vv in v.edges().vertex():
        if vv.id in S:
            return True
        else:
            S.add(vv.id)
return False

Answer 2

I did something similar for this addon and edited it.

import bpy
import bmesh

def is_edge_loop(bm):
    nof_verts = 0
    nof_leafs = 0
    start = None

    #maybe iterate over edges instead since edge count < vertex count        
    for vertex in bm.verts:
        if vertex.select:
            nof_verts += 1
            vertex.tag = False

            count = 0
            for edge in vertex.link_edges:
                if edge.select:
                    count += 1

            if count == 1:
                nof_leafs += 1
                if start is None:
                    start = vertex
                elif nof_leafs > 2:
                    return "More than two leaves"

            elif count == 2:
                if not vertex.is_boundary and not len(vertex.link_edges) == 4:
                    return "Not boundary and not linked to four edges"
                if nof_leafs == 0 and start is None:
                    start = vertex

            else:
                return "Invalid edge count: %d" % count
    if nof_leafs == 1:
        return "Only one leaf"

    #there might be additional independent cyclic loops

    vertex = start
    vertex.tag = True
    prev_edge = None
    count = 0

    while(count < nof_verts - 1):
        for edge in vertex.link_edges:
            if edge.select:
                w = edge.other_vert(vertex)
                if not w.tag:
                    if count and edges_share_face(edge, prev_edge):
                        return "edges share face"
                    vertex = w
                    vertex.tag = True
                    prev_edge = edge
                    count += 1
                    break
        else:
            return "Can not find vertex to advance to"
    return True

def edges_share_face(e1, e2):
    return any(f1 == f2 
        for f1 in e1.link_faces
        for f2 in e2.link_faces) 

mesh = bpy.context.active_object.data
bm = bmesh.from_edit_mesh(mesh)
print(is_edge_loop(bm))

There might be better solutions and i'm sure i have missed some cases but it worked ok when i tested it.