Recursive search for selected vertices

Question

i am working on a tool and need to get selection islands in the mesh. I want to keep only the biggest connected vertex selection in the mesh.

I wrote a function that recursively searches a bmesh for connected and selected vertices:

bm = bmesh.new()
bm.from_mesh(obj.data)

_verts = [v for v in bm.verts if v.select]
_edges = [e for e in bm.edges if e.select]

islands = [] # all selection islands

#iterate all selected verts in mesh
for v in _verts.copy():
    #check if that vert is already registered
    if not any([v in i for i in islands]):
        #new selection island
        _island = []

        def get_selected_connected_verts(v):
            '''
            recursive search vertices for connected and selected vertices
            @v : bmesh vertex
            '''
            #iterate all edges linked to the vertex
            for e in v.link_edges:
                #is edge selected
                if e in _edges:
                    #get adjacent vert
                    v_other = e.other_vert(v)
                    #register vert to island
                    if v_other not in _island:
                        _island.append(v_other)
                        #search again
                        get_selected_connected_verts(v_other)
        get_selected_connted_verts(v)
        #register island
        islands.append(_island)

This works great for most meshes. Sadly with higher vertex counts python returns the following error:

RecursionError: maximum recursion depth exceeded while calling a Python object

When i try to increase the recursion limit, the following error appears:

Error   : EXCEPTION_STACK_OVERFLOW
The terminal process terminated with exit code: 3221225725

Theoretically i know that i should be able to make the recursive function iterative... I am just not able to.. Also, if there is a totally different way to do this, please tell me!
I kindly ask for support of more talented programmers.

Thanks a lot!

Answer 1

Some code from this answer. But adapted for bmesh and the selection aspects of this question.

The principle is to start from selected vertices, and:

• Make a dictionary of possible links to other vertices
• Iterate available vertices and for each follow all possible remaining paths

The code with comments:

import bpy
import bmesh

def make_vert_paths( verts ):
    #Init a set for each vertex
    result = {v : set() for v in verts}
    #Loop over vertices to store connected other vertices
    for v in verts:
        for e in v.link_edges:
            other = e.other_vert( v )
            if other.select:
                result[v].add(other)
    return result

def make_island( starting_vert, paths ):
    #Initialize the island
    island = [starting_vert]
    #Initialize the current vertices to explore
    current = [starting_vert]

    follow = True
    while follow:
        #Get connected vertices that are still in the paths
        eligible = set( [v for v in current if v in paths] )
        if len( eligible ) == 0:
            follow = False #Stops if no more
        else:
            #Get the corresponding links
            next = [paths[i] for i in eligible]
            #Remove the previous from the paths
            for key in eligible:
                island.append( key ) 
                paths.pop( key )
            #Get the new links as new inputs
            current = set( [vert for sub in next for vert in sub] )

    return island

def make_islands( bm_verts ):
    paths = make_vert_paths( bm_verts )
    result = []
    found = True
    while found:
        try:
            #Get one input as long there is one
            vert = next( iter( paths.keys() ) )
            #Deplete the paths dictionary following this starting vertex
            result.append( make_island( vert, paths ) )               
        except:
            found = False
    return result


obj = bpy.context.object

bm = bmesh.new()
bm.from_mesh(obj.data)
bm.verts.ensure_lookup_table()

bm_verts = [v for v in bm.verts if v.select]

islands = make_islands( bm_verts )

print( len(islands) )
#print( islands )