feat(solver): graph decomposition for cluster-by-cluster solving (phase 3) #33

forbes · 2026-02-21T04:21:05Z

forbes commented

2026-02-21 04:21:05 +00:00

Summary

Add a Python decomposition layer using NetworkX that partitions the constraint graph into biconnected components (rigid clusters), orders them via a block-cut tree, and solves each cluster independently. Articulation-point bodies propagate as boundary conditions between clusters.

New: kindred_solver/decompose.py

DOF table: _RESIDUAL_COUNT mapping BaseJointKind to residual counts for all 24 joint types
Graph construction: build_constraint_graph() builds nx.MultiGraph from SolveContext
Biconnected decomposition: find_clusters() detects rigid clusters + articulation points
Solve ordering: build_solve_order() uses block-cut tree BFS (root-first from grounded cluster)
Cluster solver: solve_decomposed() solves cluster-by-cluster with boundary body fix/unfix cycling
Pebble game: classify_cluster_rigidity() bridges to GNN PebbleGame3D for per-cluster rigidity classification

Modified

params.py: Add unfix() method for boundary body cycling
solver.py: Extract _monolithic_solve(), add decomposition branch for assemblies >= 8 free bodies

Performance

For k clusters of ~n/k params each, total cost drops from O(n^3) to O(n^3/k^2).

Tests

220 passing (up from 207). New tests cover graph construction, biconnected decomposition, solve ordering, cluster solve vs monolithic, boundary propagation, pebble game classification, and large assemblies (20+ bodies).

## Summary Add a Python decomposition layer using NetworkX that partitions the constraint graph into biconnected components (rigid clusters), orders them via a block-cut tree, and solves each cluster independently. Articulation-point bodies propagate as boundary conditions between clusters. ## New: kindred_solver/decompose.py - **DOF table**: _RESIDUAL_COUNT mapping BaseJointKind to residual counts for all 24 joint types - **Graph construction**: build_constraint_graph() builds nx.MultiGraph from SolveContext - **Biconnected decomposition**: find_clusters() detects rigid clusters + articulation points - **Solve ordering**: build_solve_order() uses block-cut tree BFS (root-first from grounded cluster) - **Cluster solver**: solve_decomposed() solves cluster-by-cluster with boundary body fix/unfix cycling - **Pebble game**: classify_cluster_rigidity() bridges to GNN PebbleGame3D for per-cluster rigidity classification ## Modified - **params.py**: Add unfix() method for boundary body cycling - **solver.py**: Extract _monolithic_solve(), add decomposition branch for assemblies >= 8 free bodies ## Performance For k clusters of ~n/k params each, total cost drops from O(n^3) to O(n^3/k^2). ## Tests 220 passing (up from 207). New tests cover graph construction, biconnected decomposition, solve ordering, cluster solve vs monolithic, boundary propagation, pebble game classification, and large assemblies (20+ bodies).

forbes added 1 commit 2026-02-21 04:21:05 +00:00

feat(solver): graph decomposition for cluster-by-cluster solving (phase 3) 92ae57751f

Add a Python decomposition layer using NetworkX that partitions the
constraint graph into biconnected components (rigid clusters), orders
them via a block-cut tree, and solves each cluster independently.
Articulation-point bodies propagate as boundary conditions between
clusters.

New module kindred_solver/decompose.py:
- DOF table mapping BaseJointKind to residual counts
- Constraint graph construction (nx.MultiGraph)
- Biconnected component detection + articulation points
- Block-cut tree solve ordering (root-first from grounded cluster)
- Cluster-by-cluster solver with boundary body fix/unfix cycling
- Pebble game integration for per-cluster rigidity classification

Changes to existing modules:
- params.py: add unfix() for boundary body cycling
- solver.py: extract _monolithic_solve(), add decomposition branch
  for assemblies with >= 8 free bodies

Performance: for k clusters of ~n/k params each, total cost drops
from O(n^3) to O(n^3/k^2).

220 tests passing (up from 207).

forbes merged commit 3f5f7905b5 into main

2026-02-21 04:21:10 +00:00

forbes referenced this issue from a commit

2026-02-21 04:21:11 +00:00

Merge pull request 'feat(solver): graph decomposition for cluster-by-cluster solving (phase 3)' (#33) from feat/phase3-graph-decomposition into main

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: kindred/solver#33