Constraints solver

How constraints from four sorters become one linear load order.

The constraint bag

After every sorter has run, the merger receives a flat list of constraints, each one tagged with source and priority. Types:

• load_after(A, B) — A must appear after B.
• load_before(A, B) — normalized at intake to load_after(B, A).
• tier(X, N) — X is in tier N (soft).

Merge step

For each pair of creations, the merger keeps the single highest-priority ordering constraint:

• If both sorters agree (same direction), it's not really a conflict — the winner's attribution is recorded but the order is the same.
• If they disagree, the higher-priority source wins and the loser is appended to a rejected list for display in the Hint dialog.

Tier constraints are considered last. For any creation not otherwise constrained against another, its tier defines its default group; within a tier, original read order is preserved.

Topological sort

The merged ordering constraints form a DAG. The solver runs a stable Kahn's algorithm:

1. Start with nodes of in-degree zero, ordered by (tier, original read index).
2. Repeatedly pop the smallest-key ready node, output it, and decrement its neighbours' in-degrees.
3. Any node becoming ready is inserted into the priority queue with the same key.

Stability means: if a creation is not constrained to move, it stays where it was. This is important for making the diff readable — the user should see moves only where the tool had a reason to move something.

Cycle detection

Cycles can happen: two rule books disagreeing, or an inconsistent masterlist entry. The solver detects them (any nodes remaining after Kahn's finishes) and reports the cycle to the diff as an error. Auto-Sort refuses to propose a partial ordering — the user is told which creations are involved and which constraints form the cycle, so they can disable one or edit the responsible rule book.

TES4 short-circuit

TES4 constraints are applied to the graph first and locked: subsequent merge passes cannot override them (their priority 100 exceeds every other source, but the solver also marks them immutable as a belt-and-braces check). Apply-time validation re-checks them on the final ordering.

Complexity

With a few hundred installed creations and a few thousand total constraints, the solve is essentially instantaneous — well under 100ms. The bottleneck in Auto-Sort is I/O (TES4 parsing and LOOT fetch), not the solver.