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.

[Christopher-Chianelli]

So if I am understanding you correctly:

1. Each visit only have its vehicle shift and the previous visit as inputs.
2. Each vehicle shift only have the last visit and fixed vehicle shift dependencies as inputs.

From the sounds of things, this optimization is an extension of SINGLE_DIRECTIONAL_PARENT for list variables where values (i.e. visits) can depend on its inverse's shadow variables and the entities (i.e. vehicle shifts) have a fixed order.

SINGLE_DIRECTIONAL_PARENT works by picking any value, compute all its shadows, then compute its successor's shadows if any change; when no change is detected or the end of the chain is reached, it pick the next unevaluated value.

With this new graph structure, it would behave similar, except:

1. The values must be sorted according to the fixed topological order of their inverses.
2. Once all of the values belonging to the same inverse are updated, you must update the shadow variables of the inverse.

The proposed optimization is valid, but I am pretty sure we don't support accessing a shadow variable from a @PlanningListVariable as an input yet. Thus, before this optimization would even make sense, accessing a shadow variable via a @PlanningListVariable must first be supported by Timefold Solver.

What did you put as @ShadowSources on your vehicle shifts' @ShadowVariable? It should fail-fast, and one need to be added if it isn't there yet.

For your open questions:

1. Enterprise uses a fully-dynamic incremental topological order algorithm that scales much better than community. But even so, avoiding a graph altogether is preferable when possible.
2. I think we can only safely apply this optimization when the shadow variables on on a PlanningListVariable entity (which is fixed) and its value shadow entity (which only go in one direction).

A contribution would be welcome, but based on your description, it seems to be using a feature we do not support yet (accessing a shadow variable via a planning list variable), and hence such a contribution would need to wait for that feature to be supported.

[fodzal]

Thanks, this is really helpful — and your reading of the structure is exactly right. Let me answer your @ShadowSources question directly, because it gets to the heart of it.

My shadow-variable graph

Two entity classes.

Visit (the list value):

@InverseRelationShadowVariable(sourceVariableName = "visits")
Vehicle vehicle;

@PreviousElementShadowVariable(sourceVariableName = "visits")
Visit previousVisit;

@ShadowSources({"vehicle", "vehicle.previousEndPosition", "previousVisit", "previousVisit.endServiceTime"})
LocalDateTime arrivalTime;

@ShadowSources({"vehicle", "arrivalTime", "previousVisit"})
LocalDateTime startServiceTime;

@ShadowSources({"vehicle", "startServiceTime", "previousVisit"})
LocalDateTime endServiceTime;

Vehicle (the list owner, with a fixed order between vehicles):

@ShadowSources({"visits"})
Visit lastVisit;

@ShadowSources({"lastVisit", "visits"})            // body reads lastVisit.getEndServiceTime()
LocalDateTime endTime;

@ShadowSources({"previousVehicles[].endPosition", "lastVisit", "endTime", "visits"})
Collection<LocationDeparture> endPosition;

@ShadowSources({"previousVehicles[].endPosition"})
Collection<LocationDeparture> previousEndPosition;

previousVehicles is a problem fact (Collection<Vehicle>), so the cross-vehicle hand-off is declared in two steps: previousVehicles[].endPosition → previousEndPosition (GROUP), then vehicle.previousEndPosition → the first visit's arrivalTime. That entry direction (a value depending on its inverse's shadow) is accepted today.

The Vehicle ← Visit shadow edge does not actually exist (on purpose)

This is the key point. The dependency "a Vehicle's endTime/endPosition depends on its visits' endServiceTime" is not declared. endTime only lists {"lastVisit", "visits"}, even though its body reads lastVisit.getEndServiceTime().

I left it undeclared deliberately, because the dependency cannot be expressed at all — both natural spellings fail-fast in RootVariableSource.from():

• visits[].endServiceTime → "The source path (visits[].endServiceTime) ... accesses a collection (visits[]) via a variable (visits), which is not allowed."
• lastVisit.endServiceTime → "The source path (lastVisit.endServiceTime) ... accesses a declarative shadow variable (endServiceTime) from another declarative shadow variable (lastVisit)."

So today I simply cannot express "this owner depends on its list elements' shadows".

Instead, my fork hard-codes that propagation. MultiEntityChainedVariableReferenceGraph doesn't rely on a declared edge for the back direction: per move it walks each vehicle's visit chain (the value shadows), and once the chain is fully iterated it recomputes the vehicle's "post-chain" shadows (lastVisit/endTime/endPosition), then pushes to the successor vehicles in fixed topological order. Correctness comes from the hard-coded ordering, not from the declarative graph.

That's exactly why it works for me but isn't a clean contribution as-is: on stock Timefold, the missing back-edge means the owner's aggregate shadow is never ordered after, nor retriggered by, its values, so it is computed incorrectly. My fork sidesteps that with the hard-coded ordering; stock currently can't express it.

So yes — "shadow via a list variable" is the missing primitive, and it has to come first

You are right, the missing piece is precisely that back-edge: once the cascade over a list owner's values is finished, trigger the owner's shadows (and from there the next owner). Declaratively that's visits[].endServiceTime as a source on the owner — the mirror of what already works on the value side (vehicle.previousEndPosition).

I didn't explore on what to do in the Timefold repo. Do you think it's easy to setup?

Then the optimization PR (MULTI_ENTITY_SINGLE_DIRECTIONAL_PARENT)

After that, we can then set up a new GraphStructure properly (as explained in my first post) to make it work