feat(analysis): structural analyzer with DOF counting and sparsity checks #25

New Issue

forbes · 2026-02-20T22:25:12Z

forbes commented

2026-02-20 22:25:12 +00:00

Summary

Implement structural_analyzer.py — pre-solve structural diagnostics that detect overconstrained, underconstrained, and redundant constraints using purely graph-based analysis, before any numerical solving occurs.

Context

This is the single biggest improvement over both OndselSolver and FreeCAD's PlaneGCS: per-constraint attribution of structural problems before N-R ever runs. Users currently get cryptic "solve failed" messages with no indication of which constraint is problematic. The structural analyzer provides actionable diagnostics mapped directly to ConstraintDiagnostic from the KCSolve API.

The analyzer uses sparsity counting on the body-bar-hinge constraint graph. For the (6,6)-sparsity condition (Tay's theorem), a subgraph with V vertices and E weighted edges is:

Well-constrained if Σ(edge weights) = 6·|V_free| - 6
Overconstrained if any subgraph has Σ(edge weights) > 6·|V_free| - 6
Underconstrained if Σ(edge weights) < 6·|V_free| - 6

Depends on: #24 (constraint graph builder)

Design

Analysis pipeline

Global DOF check — quick pass: ConstraintGraph.dof_balance(). If negative → overconstrained. If positive → underconstrained. If zero → potentially well-constrained.
Per-subgraph sparsity — for each subset of parts, check the (6,6)-sparsity condition. In practice, use the pebble game algorithm or incremental edge insertion to find the first violating subgraph.
Redundancy detection — constraints whose removal doesn't change the DOF count. Detected by:
- Incremental pebble game: if adding an edge fails to consume pebbles, it's redundant
- Or: scipy structural_rank() on the constraint Jacobian pattern matrix as a fast proxy
Under-constrained parts — parts with remaining DOF after all constraints. Identified by counting pebbles remaining on each node after the pebble game.
Diagnostic mapping — each finding maps to a ConstraintDiagnostic:
- Overconstrained subgraph → Kind.Conflicting on the excess constraints
- Redundant constraint → Kind.Redundant
- Malformed constraint (self-referencing, unknown type) → Kind.Malformed

API

class StructuralAnalyzer:
    def analyze(self, ctx: SolveContext) -> AnalysisResult
    def diagnose(self, ctx: SolveContext) -> list[ConstraintDiagnostic]

@dataclass
class AnalysisResult:
    status: SolveStatus  # Success, Failed (overconstrained), etc.
    global_dof: int
    underconstrained_parts: list[str]  # part IDs with remaining DOF
    overconstrained_subgraphs: list[set[str]]  # sets of constraint IDs
    redundant_constraints: list[str]  # constraint IDs
    diagnostics: list[ConstraintDiagnostic]

Pebble game implementation

The (6,6)-pebble game for body-bar-hinge rigidity:

Each body node starts with 6 pebbles (DOF)
For each constraint edge, try to collect dof_removed pebbles from the two endpoint nodes
If pebbles can be collected (via pebble search/reassignment) → constraint is independent
If not → constraint is redundant in that subgraph

Consider using TRAMbio's (k,l)-pebble game as a reference implementation, or implement a focused version for (6,6)-sparsity.

Tasks

Implement StructuralAnalyzer class
Global DOF balance check (fast path)
(6,6)-pebble game for body-bar-hinge sparsity analysis
Redundancy detection with per-constraint attribution
Under-constrained part identification
Map all findings to ConstraintDiagnostic instances
Unit tests in tests/decomposition/test_analyzer.py:
- Well-constrained assembly (e.g., 2 parts + Fixed joint) → Success, no diagnostics
- Overconstrained (Fixed + Revolute between same pair) → Conflicting diagnostic
- Underconstrained (2 parts + Ball joint only) → identifies remaining 3 DOF
- Redundant constraint detection (3 parallel constraints removing same DOF)
- Empty context → Success trivially

Acceptance criteria

diagnose() returns correct ConstraintDiagnostic list for all test fixtures
Every overconstrained/redundant constraint is attributed by ID
Analysis completes in <10ms for 100-part assemblies

## Summary Implement `structural_analyzer.py` — pre-solve structural diagnostics that detect overconstrained, underconstrained, and redundant constraints using purely graph-based analysis, before any numerical solving occurs. ## Context This is the single biggest improvement over both OndselSolver and FreeCAD's PlaneGCS: **per-constraint attribution of structural problems before N-R ever runs**. Users currently get cryptic "solve failed" messages with no indication of which constraint is problematic. The structural analyzer provides actionable diagnostics mapped directly to `ConstraintDiagnostic` from the KCSolve API. The analyzer uses sparsity counting on the body-bar-hinge constraint graph. For the (6,6)-sparsity condition (Tay's theorem), a subgraph with V vertices and E weighted edges is: - **Well-constrained** if Σ(edge weights) = 6·|V_free| - 6 - **Overconstrained** if any subgraph has Σ(edge weights) > 6·|V_free| - 6 - **Underconstrained** if Σ(edge weights) < 6·|V_free| - 6 Depends on: #24 (constraint graph builder) ## Design ### Analysis pipeline 1. **Global DOF check** — quick pass: `ConstraintGraph.dof_balance()`. If negative → overconstrained. If positive → underconstrained. If zero → potentially well-constrained. 2. **Per-subgraph sparsity** — for each subset of parts, check the (6,6)-sparsity condition. In practice, use the pebble game algorithm or incremental edge insertion to find the first violating subgraph. 3. **Redundancy detection** — constraints whose removal doesn't change the DOF count. Detected by: - Incremental pebble game: if adding an edge fails to consume pebbles, it's redundant - Or: scipy `structural_rank()` on the constraint Jacobian pattern matrix as a fast proxy 4. **Under-constrained parts** — parts with remaining DOF after all constraints. Identified by counting pebbles remaining on each node after the pebble game. 5. **Diagnostic mapping** — each finding maps to a `ConstraintDiagnostic`: - Overconstrained subgraph → `Kind.Conflicting` on the excess constraints - Redundant constraint → `Kind.Redundant` - Malformed constraint (self-referencing, unknown type) → `Kind.Malformed` ### API ```python class StructuralAnalyzer: def analyze(self, ctx: SolveContext) -> AnalysisResult def diagnose(self, ctx: SolveContext) -> list[ConstraintDiagnostic] @dataclass class AnalysisResult: status: SolveStatus # Success, Failed (overconstrained), etc. global_dof: int underconstrained_parts: list[str] # part IDs with remaining DOF overconstrained_subgraphs: list[set[str]] # sets of constraint IDs redundant_constraints: list[str] # constraint IDs diagnostics: list[ConstraintDiagnostic] ``` ### Pebble game implementation The (6,6)-pebble game for body-bar-hinge rigidity: - Each body node starts with 6 pebbles (DOF) - For each constraint edge, try to collect `dof_removed` pebbles from the two endpoint nodes - If pebbles can be collected (via pebble search/reassignment) → constraint is independent - If not → constraint is redundant in that subgraph Consider using TRAMbio's (k,l)-pebble game as a reference implementation, or implement a focused version for (6,6)-sparsity. ## Tasks - [ ] Implement `StructuralAnalyzer` class - [ ] Global DOF balance check (fast path) - [ ] (6,6)-pebble game for body-bar-hinge sparsity analysis - [ ] Redundancy detection with per-constraint attribution - [ ] Under-constrained part identification - [ ] Map all findings to `ConstraintDiagnostic` instances - [ ] Unit tests in `tests/decomposition/test_analyzer.py`: - Well-constrained assembly (e.g., 2 parts + Fixed joint) → Success, no diagnostics - Overconstrained (Fixed + Revolute between same pair) → Conflicting diagnostic - Underconstrained (2 parts + Ball joint only) → identifies remaining 3 DOF - Redundant constraint detection (3 parallel constraints removing same DOF) - Empty context → Success trivially ## Acceptance criteria - `diagnose()` returns correct `ConstraintDiagnostic` list for all test fixtures - Every overconstrained/redundant constraint is attributed by ID - Analysis completes in <10ms for 100-part assemblies

forbes referenced this issue

2026-02-20 22:25:46 +00:00

feat(decomp): biconnected component decomposition and solve plan DAG #26

forbes referenced this issue

2026-02-20 22:27:57 +00:00

feat(solver): DecompositionSolver entry point and kcsolve registration #30

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: kindred/solver#25