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

New Issue

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

forbes commented

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

Summary

Implement decomposer.py — the three-stage graph decomposition pipeline that splits a constraint problem into a DAG of independent subproblems, ordered for bottom-up solving.

Context

This is Owen's core insight (1991): separating pairs in the constraint graph identify independent subproblems that can be solved separately. The decomposition pipeline uses three stages of increasing granularity, each reducing problem size. The output is a solve plan DAG whose shape matches Silo's existing feature DAG infrastructure, enabling parallel dispatch on workers.

Depends on: #24 (constraint graph), #25 (structural analyzer)

Design

Three-stage decomposition

Stage A — Connected components (trivial, O(V+E)):
Independent constraint clusters that share no parts. Each is a fully separate solve problem. Uses igraph.Graph.decompose() directly.

Example: Two sub-assemblies on the same ground plate with no joints between them → two independent problems.

Stage B — Biconnected components (Owen's method, O(V+E)):
Within each connected component, find biconnected subgraphs via Hopcroft-Tarjan. Articulation points (parts shared between biconnected components) are the "hinges" between subproblems. Each biconnected component becomes a subproblem node in the solve plan.

Uses igraph.Graph.biconnected_components() and igraph.Graph.articulation_points().

Example: A chain A—B—C—D where B and C are articulation points → three biconnected components {A,B}, {B,C}, {C,D} solved in dependency order.

Stage C — Pattern recognition (optional, fast):
Within each biconnected component, check for common mate patterns with closed-form solutions. These get extracted as leaf nodes in the solve plan, solved analytically without invoking N-R. Remaining non-pattern subgraph stays as a numerical subproblem.

Delegated to pattern matchers from #27 (closed-form patterns).

Solve plan DAG

@dataclass
class Subproblem:
    id: str
    part_ids: set[str]              # parts in this subproblem
    constraint_ids: set[str]        # constraints in this subproblem
    shared_parts: set[str]          # articulation points (hinge parts)
    pattern: str | None             # if matched to a closed-form pattern
    sub_context: SolveContext | None # built lazily by dispatcher

@dataclass
class SolvePlan:
    subproblems: dict[str, Subproblem]
    dependencies: dict[str, list[str]]  # subproblem_id → list of dependency IDs
    execution_order: list[str]          # topological sort (leaves first)

    def leaves(self) -> list[str]
    def roots(self) -> list[str]
    def is_trivial(self) -> bool  # single subproblem, no decomposition benefit

Key invariants

Every constraint appears in exactly one subproblem
Every part appears in at least one subproblem (shared parts appear in multiple)
The execution order is a valid topological sort of the dependency DAG
Solving leaf nodes first, then propagating upward, produces a valid global solution

Tasks

Implement Stage A: connected component splitting
Implement Stage B: biconnected component decomposition
- Identify articulation points as shared hinge parts
- Build subproblem nodes from biconnected components
- Establish dependency edges based on shared articulation points
Implement Stage C: pattern recognition hook (delegate to pattern matchers)
Implement SolvePlan data structure with topological sort
Implement Decomposer.decompose(ctx) -> SolvePlan
Handle edge cases:
- Single-part assembly → trivial plan
- Fully triconnected graph → single subproblem (no decomposition possible)
- Disconnected grounded parts
Unit tests in tests/decomposition/test_decomposer.py:
- Two disconnected clusters → Stage A splits into 2
- Chain of 4 parts → Stage B produces 3 biconnected components
- Fully connected 3-part triangle → single subproblem (triconnected)
- Mixed: two clusters, one with articulation point → correct DAG
- Execution order is valid topological sort

Acceptance criteria

Decomposer.decompose(ctx) returns a valid SolvePlan for all test fixtures
Every constraint and part is accounted for (no lost constraints)
Execution order is a valid topological sort
Decomposition of a 100-part chain completes in <5ms

## Summary Implement `decomposer.py` — the three-stage graph decomposition pipeline that splits a constraint problem into a DAG of independent subproblems, ordered for bottom-up solving. ## Context This is Owen's core insight (1991): **separating pairs in the constraint graph identify independent subproblems** that can be solved separately. The decomposition pipeline uses three stages of increasing granularity, each reducing problem size. The output is a solve plan DAG whose shape matches Silo's existing feature DAG infrastructure, enabling parallel dispatch on workers. Depends on: #24 (constraint graph), #25 (structural analyzer) ## Design ### Three-stage decomposition **Stage A — Connected components** (trivial, O(V+E)): Independent constraint clusters that share no parts. Each is a fully separate solve problem. Uses `igraph.Graph.decompose()` directly. Example: Two sub-assemblies on the same ground plate with no joints between them → two independent problems. **Stage B — Biconnected components** (Owen's method, O(V+E)): Within each connected component, find biconnected subgraphs via Hopcroft-Tarjan. Articulation points (parts shared between biconnected components) are the "hinges" between subproblems. Each biconnected component becomes a subproblem node in the solve plan. Uses `igraph.Graph.biconnected_components()` and `igraph.Graph.articulation_points()`. Example: A chain A—B—C—D where B and C are articulation points → three biconnected components {A,B}, {B,C}, {C,D} solved in dependency order. **Stage C — Pattern recognition** (optional, fast): Within each biconnected component, check for common mate patterns with closed-form solutions. These get extracted as leaf nodes in the solve plan, solved analytically without invoking N-R. Remaining non-pattern subgraph stays as a numerical subproblem. Delegated to pattern matchers from #27 (closed-form patterns). ### Solve plan DAG ```python @dataclass class Subproblem: id: str part_ids: set[str] # parts in this subproblem constraint_ids: set[str] # constraints in this subproblem shared_parts: set[str] # articulation points (hinge parts) pattern: str | None # if matched to a closed-form pattern sub_context: SolveContext | None # built lazily by dispatcher @dataclass class SolvePlan: subproblems: dict[str, Subproblem] dependencies: dict[str, list[str]] # subproblem_id → list of dependency IDs execution_order: list[str] # topological sort (leaves first) def leaves(self) -> list[str] def roots(self) -> list[str] def is_trivial(self) -> bool # single subproblem, no decomposition benefit ``` ### Key invariants - Every constraint appears in exactly one subproblem - Every part appears in at least one subproblem (shared parts appear in multiple) - The execution order is a valid topological sort of the dependency DAG - Solving leaf nodes first, then propagating upward, produces a valid global solution ## Tasks - [ ] Implement Stage A: connected component splitting - [ ] Implement Stage B: biconnected component decomposition - [ ] Identify articulation points as shared hinge parts - [ ] Build subproblem nodes from biconnected components - [ ] Establish dependency edges based on shared articulation points - [ ] Implement Stage C: pattern recognition hook (delegate to pattern matchers) - [ ] Implement `SolvePlan` data structure with topological sort - [ ] Implement `Decomposer.decompose(ctx) -> SolvePlan` - [ ] Handle edge cases: - [ ] Single-part assembly → trivial plan - [ ] Fully triconnected graph → single subproblem (no decomposition possible) - [ ] Disconnected grounded parts - [ ] Unit tests in `tests/decomposition/test_decomposer.py`: - Two disconnected clusters → Stage A splits into 2 - Chain of 4 parts → Stage B produces 3 biconnected components - Fully connected 3-part triangle → single subproblem (triconnected) - Mixed: two clusters, one with articulation point → correct DAG - Execution order is valid topological sort ## Acceptance criteria - `Decomposer.decompose(ctx)` returns a valid `SolvePlan` for all test fixtures - Every constraint and part is accounted for (no lost constraints) - Execution order is a valid topological sort - Decomposition of a 100-part chain completes in <5ms

forbes referenced this issue

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

feat(patterns): closed-form solvers for common mate patterns #27

forbes referenced this issue

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

feat(dispatch): subproblem dispatcher to backend solvers #28

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.