closure.cppm File Reference

Single-source graph closure over a semiring, as a fold over its edges. More...

#include <concepts>
#include <cstddef>
#include <type_traits>
import dedekind.sequences;
import dedekind.category;
import dedekind.algebra;

Include dependency graph for closure.cppm:

Classes
struct	dedekind::optimization::Edge
	A directed edge of the graph: tail → head (node indices). More...
struct	dedekind::optimization::Relax< S, Cap, CostFn >
	Fold step of the single-source semiring closure: relax the potential at e.head through the edge e, d(v) ← d(v) ⊕ d(u) ⊗ c(u,v). More...
struct	dedekind::optimization::CriticalPathState< S, Cap >
	Fold accumulator of annotate: the transient potential net paired with the critical-path predecessor map it induces. More...
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. More...
struct	dedekind::optimization::FiniteNet< X, Cap >
	A finite net: a tabulated morphism size_t → X (an IsNet, since std::size_t is a directed set). Read as a function d(v); the std::array tabulation is private business, not the interface. More...
struct	dedekind::optimization::FiniteSeq< T, Cap >
	A finite sequence: an array-backed range of length n ≤ Cap — the compile-time extensional realization of a sequence. More...

Concepts
concept	dedekind::optimization::HasCriticalPathStep

Functions
template<std::size_t Nodes, std::size_t Cap, typename Pred>
constexpr FiniteSeq< Edge, Cap >	dedekind::optimization::ext (Pred edge)
	Materialise an intensional graph rule extensionally: the edge sequence { (u,v) : edge(u,v) } over nodes 0 … Nodes−1, in topological (tail-ascending) order. Where a rule becomes elements.
template<typename S, std::size_t Cap, typename Edges, typename CostFn> requires dedekind::category::IsSemiring< S, typename dedekind::algebra::semiring_ops<S>::add, typename dedekind::algebra::semiring_ops<S>::mult>
constexpr S	dedekind::optimization::semiring_closure (std::size_t source, std::size_t sink, const Edges &edges, CostFn cost)
	Single-source semiring closure: fold the edge sequence into the potential net, return its value at the sink. The semiring ops are the carrier's canonical semiring_ops.
template<typename S, std::size_t Cap, typename Edges, typename CostFn> requires dedekind::algebra::IsTropical< S, typename dedekind::algebra::semiring_ops<S>::add, typename dedekind::algebra::semiring_ops<S>::mult>
constexpr FiniteNet< std::size_t, Cap >	dedekind::optimization::annotate (std::size_t source, const Edges &edges, CostFn cost)
	Collapse the edge relation to the critical-path FUNCTION pred : V → V (each node's predecessor on the longest path). Gated on IsTropical (idempotent ⊕). Precondition beyond the gate: ⊕ must be selective (its result is one of its two operands), which is what makes argmax — and hence a single-valued pred — well defined. MaxPlus satisfies this; IsTropical alone does not guarantee it (a non-selective dioid such as powerset-union would yield a third value and need a set-valued pred). FIXME(#769): tighten the gate to a selectivity concept.
template<std::size_t Cap>
constexpr FiniteSeq< Edge, Cap >	dedekind::optimization::critical_path (const FiniteNet< std::size_t, Cap > &pred, std::size_t source, std::size_t sink)
	Iterate the pred net back from sink to source: the critical path as an edge sequence. A functional graph — one way between any two nodes — ready to fold for cost or query for criticality.

Detailed Description

Single-source graph closure over a semiring, as a fold over its edges.

@partition :closure

Copyright

2026 The Dedekind Authors Licensed under the Apache License, Version 2.0.

closure__Overview

A directed graph is a relation on nodes (IsDirectedGraph). Presented extensionally its edges are a FiniteSeq, and the closure threads a potential FiniteNet d : V → S over it by a fold, d(v) ← d(v) ⊕ d(u) ⊗ c. The choice of semiring is the choice of problem: bool (∨,∧) gives reachability, MaxPlus (max,+) the critical path. Over a selective tropical dioid (an IsTropical ⊕ that returns one of its two operands, e.g. MaxPlus) it also collapses the relation to a single-valued pred : V → V — the critical-path tree — which critical_path iterates back from the sink. Idempotence (IsTropical) alone is not enough: a non-selective dioid needs a set-valued predecessor (see the annotate precondition, FIXME(#769)). The O(V) memo lives inside FiniteNet and FiniteSeq (the compile-time :sequences realizations), not on display.

Wikipedia: Shortest path problem, Semiring, Algebraic path problem

Note

"This 'shadow' stands approximately in the same relation to the traditional mathematics as does classical physics to quantum theory." — G. L. Litvinov, "The Maslov Dequantization, Idempotent and Tropical Mathematics: a Brief Introduction", arXiv:math/0507014 (2005), §1. [Litvinov writes in English; the "shadow" is idempotent mathematics — the tropical (min/max-plus) dioid this closure runs the critical path over, obtained from the ordinary field by Maslov dequantization.]

See also

#319 undergraduate graph theory (work in progress): Dijkstra and Bellman-Ford beyond the DAG relaxation.

#330 undergraduate algorithms and data structures (work in progress): topological sort: ext lists the edges by ascending tail, so the single-pass DAG relaxation assumes the vertices numbered topologically.

Function Documentation

semiring_closure()

template<typename S, std::size_t Cap, typename Edges, typename CostFn>
requires dedekind::category::IsSemiring< S, typename dedekind::algebra::semiring_ops<S>::add, typename dedekind::algebra::semiring_ops<S>::mult>

S dedekind::optimization::semiring_closure ( std::size_t source, std::size_t sink, const Edges & edges, CostFn cost )

constexprexport

Single-source semiring closure: fold the edge sequence into the potential net, return its value at the sink. The semiring ops are the carrier's canonical semiring_ops.

Note

The semiring is the carrier's canonical semiring_ops; the ops are not parameters. A carrier that certifies more than one semiring (e.g. bool: (∨,∧) here, but also (⊕,∧)) uses only its canonical pair; a different semiring on the same carrier is out of scope — pick a distinct carrier type for it, as the graph-closure use does (bool / MaxPlus / MinPlus).

This is a value-level algebraic reduction over a semiring. The gate is IsSemiring, so a non-idempotent semiring is admitted too; only the idempotent (IsTropical) instantiations — reachability, critical path — are dioids. Its ⊗-over-⊕ distributivity is the same law the type-level term reducer (category:lattice_term, epic #890) normalises, and a tropical ⊕ (min/max) is a semilattice op — so the two share the algebraic substrate, but live on opposite sides of the phase wall (value fold here vs compile-time type rewrite there) and share no implementation today. A value-first reducer (#922) could subsume this closure as a semiring star (a dioid star in the idempotent case); the kinship is tracked in #926.