dedekind::optimization::CriticalPathStep< S, Cap, CostFn > Struct Template Reference

Fold step of annotate: relax through e and, when the candidate wins the (selective) join, record e.tail as e.head's predecessor. More...

Public Types
using	Add = typename dedekind::algebra::semiring_ops<S>::add
	The carrier's canonical additive op ⊕ (semiring_ops).
using	Mult = typename dedekind::algebra::semiring_ops<S>::mult
	The carrier's canonical multiplicative op ⊗ (semiring_ops).

Public Member Functions
constexpr CriticalPathState< S, Cap >	operator() (CriticalPathState< S, Cap > acc, const Edge &e) const
	Relax e.head and, when the candidate d(tail) ⊗ c(tail,head) wins the selective join, record e.tail as its predecessor; returns the new state — the fold step op(acc, Edge).

Public Attributes
CostFn	cost
	The edge-cost function c(tail,head); the only captured state.

Detailed Description

template<typename S, std::size_t Cap, typename CostFn = S (*)(std::size_t, std::size_t)>
requires dedekind::algebra::IsTropical< S, typename dedekind::algebra::semiring_ops<S>::add, typename dedekind::algebra::semiring_ops<S>::mult> && requires(const CostFn& cost, std::size_t u, S s) { { cost(u, u) } -> std::convertible_to<S>; { s != s } -> std::convertible_to<bool>; }
struct dedekind::optimization::CriticalPathStep< S, Cap, CostFn >

Fold step of annotate: relax through e and, when the candidate wins the (selective) join, record e.tail as e.head's predecessor.

The named replacement for the capturing step lambda (#920). The selective ⊕ test (d(head) ⊕ cand != d(head)) is what makes the recorded pred single-valued; see annotate for the further selectivity precondition. The ops are fixed by the carrier S (semiring_ops), so cost is the only captured state. Models the fold step op(acc, Edge), returning the new state.

Note

Gated on IsTropical (idempotent ⊕), NOT bare IsSemiring: the update overwrites d(head) with cand alone when (d(head) ⊕ cand) differs from d(head). Storing cand recovers the true join only when ⊕ is selective (a ⊕ b ∈ {a,b}): the changed result is then cand itself. Idempotence (a ⊕ a = a), the IsTropical gate, is necessary but not sufficient — a non-selective idempotent ⊕ (a lattice join to a third value) would store cand and lose that value; and an ordinary non-idempotent + would detect (old + cand != old) and then WRONGLY store cand instead of the sum. MaxPlus is selective; the gate is only the tight-enough idempotence proxy pending a selectivity concept (FIXME(#769), as annotate states).

As in Relax, cost is a bare binary callable gated structurally, not via IsArrow; the gate also requires the selective != that the argmax test needs.

---

The documentation for this struct was generated from the following file:

• src/main/modules/dedekind/optimization/closure.cppm