Proposal: a dedicated GraphStructure for "chained entity + fixed-entity DAG" (multi-entity declarative shadow variables)

[fodzal]

Proposal: a dedicated GraphStructure for "chained entity + fixed-entity DAG" (multi-entity declarative shadow variables)

Summary

I'd like to propose recognizing a new graph structure for declarative shadow variables: models with two entity classes, where one class forms chains via a single directional parent (PREVIOUS/NEXT) and the other forms a fixed, acyclic DAG that consumes the chain's results and pushes them forward.

Today this case is classified as ARBITRARY and pays a full Tarjan SCC recompute on every move, even though the structure is fully known up front and contains no real cycles. I already have a working fork that handles it as an O(k) chain-walk + a pre-computed DAG order, and I'd like to know whether a cleaned-up version would be welcome upstream.

My use case

In my VRP, I have successive VehicleShifts. Propagation flows along the visits of one shift, and the end state of that shift (end time, end location, last visit, …) must be pushed to the next shift, which itself does not move — the shift-to-shift ordering is a problem fact.

This pattern models several real needs:

• Multi-trip: a vehicle performs several successive shifts/trips in a day.
• Mid-day crew change on the same physical vehicle (e.g. ambulances: the vehicle keeps going, the team changes).
• Synchronized vehicles: time slots where two vehicles must be together. (e.g. 2 technicians should be together between 10:00 and 14:00 but are alone before and after --> So we have for each technician VehicleShift1 (alone), VehicleShiftTeam (shared with the other technicien) and then VehicleShift2 (alone).

I model it with declarative shadow variables (@ShadowVariable supplier methods) on two entity classes:

• Chained entity (Visit): arrivalTime / departureTime, computed from the previous element (a PREVIOUS source). Visits are a @PlanningListVariable on each shift.
• Fixed entity (VehicleShift): lastVisit / endTime / endLocation, plus a "previous shift" GROUP source that carries shiftA.end → shiftB.start.

So the instance-level dependency graph is: chains within each shift + an acyclic DAG across shifts (A → B → …). No cycles, fully determined by the model and the problem facts.

The problem

As soon as there are 2+ entity classes with declarative shadow variables, GraphStructure.determine() classifies the model as ARBITRARY:

var isArbitrary = multipleDeclarativeEntityClasses;

That routes everything through DefaultVariableReferenceGraph, whose innerUpdateChanged() runs, on every move:

void innerUpdateChanged() {
    if (changeTracker.isEmpty()) return;
    graph.commitChanges(changeTracker);            // full Tarjan SCC recompute (DefaultTopologicalOrderGraph)
    affectedEntitiesUpdater.accept(changeTracker); // propagation (already incremental)
}

The propagation step (AffectedEntitiesUpdater) is already incremental and short-circuits on no-change. The cost is the commitChanges() call: a full Tarjan SCC recompute over the whole instance graph, O(V + E) per move.

For my models (large number of visits) this dominates runtime — it's the difference between unusable and fine. And it's pure overhead here: there are no cycles to detect, and the structure never changes shape, only the dynamic PREVIOUS/NEXT edges do.

This is the same kind of situation the existing SINGLE_DIRECTIONAL_PARENT structure already optimizes — but that one only applies to a single entity class.

What I've built (working fork)

A new structure MULTI_ENTITY_SINGLE_DIRECTIONAL_PARENT and a MultiEntityChainedVariableReferenceGraph that handles exactly this shape, with no generic instance graph and no Tarjan.

Classification (once, at build time) — in GraphStructure.determine(), the multi-entity case is accepted when:

• there are multiple declarative entity classes, and no INDIRECT sources;
• exactly one directional type (PREVIOUS/NEXT) on one entity class (the "chained" entity);
• the chained entity uses only PREVIOUS/NEXT/NO_PARENT (+ INVERSE allowed only if it targets the fixed entity, e.g. visit.vehicleShift);
• the "fixed" entity uses only VARIABLE/GROUP/NO_PARENT.

Anything outside these preconditions falls back to ARBITRARY safely.

Fixed-entity DAG order — computed once via Kahn's algorithm from the GROUP sources (A → B edges), stored as a fixed topological order.

Per move:

• group dirty entities; for each dirty shift, find the earliest/latest dirty visit;
• process shifts in DAG topological order via a PriorityQueue (handles DAG merges correctly);
• for each shift: pre-chain updaters (sources that are GROUP-only, e.g. previousEndPosition) → chain-walk the visits in list order (O(k), with change-detection short-circuit) → post-chain updaters (lastVisit / endTime / endLocation);
• only enqueue successor shifts when a shift's shadow variable actually changed.

Result: no Tarjan, no per-node instance graph, no SCC/looped tracking. Complexity per move ≈ O(k + V_affected · log V), where k = affected chain length and V_affected = number of shifts whose shadows changed.

The fork also handles two correctness details that come with walking the chain directly: resetting shadow values on unassign (undo), and not terminating the walk early when there are non-contiguous dirty visits on the same shift after a swap.

Open questions before I clean this up for a PR

1. Enterprise — Faster Shadow variables features in Enterprise would solve this?
2. Generality — my current code assumes exactly two entity classes (one chained, one fixed) and a single inverse relation. Would you prefer it generalized (N fixed classes / multiple chains), or is a well-bounded two-class case with a safe ARBITRARY fallback acceptable as a first step?

I'm happy to open a draft PR, share the fork, and provide benchmarks on a representative model. Would a contribution along these lines be welcome?

[triceo]

Hello @fodzal!

Interesting idea - we will review and get back to you. Please understand that this may take a while, as we'll need to look at this very carefully.