constraint islands

[thowell]

implement constraint islands

---

Island Discovery Implementation Plan

Objective

Discover disjoint constraint subgraphs by analyzing the constraint Jacobian structure.

---

PR Breakdown

PR	Branch	Description
#1100	tree_structure	Add tree structure to types.Model, import in io.py
#1101	edge_discovery	Edge discovery kernel in island.py
#1102	dfs_discovery	Data fields, DFS island assignment + forward.py integration

---

Tree Structure

Files: types.py, io.py

Add kinematic tree metadata to Model:

Field	Dimension	Description
ntree	scalar	Number of kinematic trees
tree_dofadr	(ntree,)	First DOF of each tree
tree_dofnum	(ntree,)	DOFs per tree
body_treeid	(nbody,)	Tree ID for each body (-1 for static)
dof_treeid	(nv,)	Tree ID for each DOF

---

Edge Discovery

Files: island.py

MuJoCo Reference: engine_island.c:L341-395 (findEdges())

Scan Jacobian rows to find tree pairs sharing constraints:

@wp.kernel
def _find_tree_edges(efc_J, dof_treeid, edges, nedge):
    """Find edges between trees that share constraints."""
    efcid = wp.tid()
    # Find first and last non-zero tree in this Jacobian row
    # Add edge if they differ

Output: Sparse adjacency list (tree1, tree2) pairs.

---

DFS Island Discovery

Files: island.py, types.py, forward.py

MuJoCo Reference: engine_island.c:L97-137 (mj_floodFill())

Algorithm: DFS (matching MuJoCo)

Uses edges from PR 1.2 to build CSR adjacency, then runs DFS to assign island IDs:

def _flood_fill(rownnz, rowadr, colind, tree_island, ntree):
    """DFS flood fill matching mj_floodFill."""
    nisland = 0
    stack = []
    
    for tree in range(ntree):
        if tree_island[tree] >= 0:  # already visited
            continue
        if rownnz[tree] == 0:  # unconstrained tree
            continue
        
        # Start new island
        stack.append(tree)
        while stack:
            t = stack.pop()
            if tree_island[t] >= 0:
                continue
            tree_island[t] = nisland
            
            # Add unvisited neighbors
            for j in range(rownnz[t]):
                neighbor = colind[rowadr[t] + j]
                if tree_island[neighbor] < 0:
                    stack.append(neighbor)
        
        nisland += 1
    
    return nisland

Data Fields

Field	Dimension	Description
nisland	(nworld,)	Number of islands
tree_island	(nworld, ntree)	Island ID per tree (-1 if unconstrained)
island_ntree	(nworld, max_nisland)	Trees per island

[vector-one]

Hi @thowell,

I just commented on #887 regarding sleeping islands, but I realized that feature heavily depends on the graph grouping logic from this issue.

Since the two are tightly coupled, could I be assigned this issue as well? I’d prefer to implement the constraint island generation here first, ensuring the data structures are compatible with the sleeping logic needed for #887.

[thowell]

thanks for your interest in contributing to mujoco warp!

i think this is a feature the mjwarp team will develop.

a good first issue to contribute to might be #750. if you are interested in that issue, please comment there. thanks!

[vector-one]

Understood!
Thanks for pointing me toward #750. I'll head over there and take a look at the fluid implementation instead.