feat(graph): constraint graph builder from SolveContext #24

New Issue

forbes · 2026-02-20T22:24:46Z

forbes commented

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

Summary

Implement constraint_graph.py — the bridge between the KCSolve API types and the graph library. Translates a SolveContext (parts + constraints) into a weighted igraph graph using the body-bar-hinge model.

Context

The body-bar-hinge model maps 1:1 to how CAD assemblies actually work: each assembly part is a rigid body (6 DOF in 3D), each joint is a set of bars/hinges connecting two bodies. Crucially, Tay's theorem (1984) provides a complete combinatorial rigidity characterization for body-bar-hinge frameworks in all dimensions — sidestepping the 3D Laman gap that defeats bar-joint models.

Depends on: #23 (scaffolding)

Design

Graph construction

Nodes = parts from SolveContext.parts
- Attribute dof_weight: 6 for free bodies, 0 for grounded parts
- Attribute part_id: string ID from Part.id
Edges = constraints from SolveContext.constraints
- Attribute constraint_weight: DOF removed by this joint type
- Attribute constraint_id: string ID from Constraint.id
- Attribute joint_kind: the BaseJointKind enum value
- Connects part_i → part_j

DOF weight table (all 24 BaseJointKind values)

BaseJointKind	DOF Removed	Notes
Fixed	6	Full lock
Revolute	5	1 rotational DOF remains
Cylindrical	4	1 rot + 1 trans remain
Slider	5	1 translational DOF remains
Ball	3	3 rotational DOF remain
Screw	5	Coupled rot+trans, 1 DOF remains
Universal	4	2 rotational DOF remain
Coincident	3	Point-on-point
PointOnLine	2	Point constrained to line
PointInPlane	1	Point constrained to plane
Concentric	4	Axis alignment + radial lock
Tangent	1	Surface contact
Planar	3	Face-on-face
LineInPlane	2	Line constrained to plane
Parallel	2	Axis alignment
Perpendicular	2	Axis orthogonality
Angle	1	Relative angle
Gear	1	Coupled rotation
RackPinion	1	Coupled rot/trans
Cam	1	Profile-following
Slot	2	Constrained to slot path
DistancePointPoint	1	Distance constraint
DistanceCylSph	1	Distance constraint
Custom	0	Must be specified per-instance

API

class ConstraintGraph:
    @classmethod
    def from_context(cls, ctx: SolveContext) -> "ConstraintGraph"

    @property
    def graph(self) -> igraph.Graph

    def part_node(self, part_id: str) -> int  # vertex index
    def constraint_edge(self, constraint_id: str) -> int  # edge index
    def total_dof(self) -> int  # sum of free part DOFs
    def total_constraints(self) -> int  # sum of constraint DOFs removed
    def dof_balance(self) -> int  # total_dof - total_constraints - 6 (ground frame)
    def subgraph_for_parts(self, part_ids: list[str]) -> "ConstraintGraph"

Tasks

Implement ConstraintGraph class in solver/decomposition/constraint_graph.py
DOF weight lookup table for all 24 BaseJointKind values
Handle multi-edge cases (multiple constraints between same part pair)
Handle self-referencing constraints gracefully (part_i == part_j, skip or warn)
Subgraph extraction method for decomposition downstream
Unit tests in tests/decomposition/test_graph.py:
- Two parts + one revolute → correct node/edge weights
- Chain of 5 parts → correct DOF balance
- Overconstrained pair (Fixed + Revolute between same parts) → negative DOF balance
- Grounded part gets weight 0
- Subgraph extraction preserves attributes

Acceptance criteria

ConstraintGraph.from_context(ctx) produces correct igraph graph for all test fixtures
DOF balance calculation matches manual computation for known assemblies
All 24 BaseJointKind values have defined weights (no KeyError)

## Summary Implement `constraint_graph.py` — the bridge between the KCSolve API types and the graph library. Translates a `SolveContext` (parts + constraints) into a weighted igraph graph using the body-bar-hinge model. ## Context The body-bar-hinge model maps 1:1 to how CAD assemblies actually work: each assembly part is a rigid body (6 DOF in 3D), each joint is a set of bars/hinges connecting two bodies. Crucially, **Tay's theorem (1984)** provides a complete combinatorial rigidity characterization for body-bar-hinge frameworks in all dimensions — sidestepping the 3D Laman gap that defeats bar-joint models. Depends on: #23 (scaffolding) ## Design ### Graph construction - **Nodes** = parts from `SolveContext.parts` - Attribute `dof_weight`: 6 for free bodies, 0 for grounded parts - Attribute `part_id`: string ID from `Part.id` - **Edges** = constraints from `SolveContext.constraints` - Attribute `constraint_weight`: DOF removed by this joint type - Attribute `constraint_id`: string ID from `Constraint.id` - Attribute `joint_kind`: the `BaseJointKind` enum value - Connects `part_i` → `part_j` ### DOF weight table (all 24 BaseJointKind values) | BaseJointKind | DOF Removed | Notes | |---|---|---| | Fixed | 6 | Full lock | | Revolute | 5 | 1 rotational DOF remains | | Cylindrical | 4 | 1 rot + 1 trans remain | | Slider | 5 | 1 translational DOF remains | | Ball | 3 | 3 rotational DOF remain | | Screw | 5 | Coupled rot+trans, 1 DOF remains | | Universal | 4 | 2 rotational DOF remain | | Coincident | 3 | Point-on-point | | PointOnLine | 2 | Point constrained to line | | PointInPlane | 1 | Point constrained to plane | | Concentric | 4 | Axis alignment + radial lock | | Tangent | 1 | Surface contact | | Planar | 3 | Face-on-face | | LineInPlane | 2 | Line constrained to plane | | Parallel | 2 | Axis alignment | | Perpendicular | 2 | Axis orthogonality | | Angle | 1 | Relative angle | | Gear | 1 | Coupled rotation | | RackPinion | 1 | Coupled rot/trans | | Cam | 1 | Profile-following | | Slot | 2 | Constrained to slot path | | DistancePointPoint | 1 | Distance constraint | | DistanceCylSph | 1 | Distance constraint | | Custom | 0 | Must be specified per-instance | ### API ```python class ConstraintGraph: @classmethod def from_context(cls, ctx: SolveContext) -> "ConstraintGraph" @property def graph(self) -> igraph.Graph def part_node(self, part_id: str) -> int # vertex index def constraint_edge(self, constraint_id: str) -> int # edge index def total_dof(self) -> int # sum of free part DOFs def total_constraints(self) -> int # sum of constraint DOFs removed def dof_balance(self) -> int # total_dof - total_constraints - 6 (ground frame) def subgraph_for_parts(self, part_ids: list[str]) -> "ConstraintGraph" ``` ## Tasks - [ ] Implement `ConstraintGraph` class in `solver/decomposition/constraint_graph.py` - [ ] DOF weight lookup table for all 24 `BaseJointKind` values - [ ] Handle multi-edge cases (multiple constraints between same part pair) - [ ] Handle self-referencing constraints gracefully (part_i == part_j, skip or warn) - [ ] Subgraph extraction method for decomposition downstream - [ ] Unit tests in `tests/decomposition/test_graph.py`: - Two parts + one revolute → correct node/edge weights - Chain of 5 parts → correct DOF balance - Overconstrained pair (Fixed + Revolute between same parts) → negative DOF balance - Grounded part gets weight 0 - Subgraph extraction preserves attributes ## Acceptance criteria - `ConstraintGraph.from_context(ctx)` produces correct igraph graph for all test fixtures - DOF balance calculation matches manual computation for known assemblies - All 24 BaseJointKind values have defined weights (no KeyError)

forbes referenced this issue

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

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

forbes referenced this issue

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

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

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: kindred/solver#24