Enum Class PathCostSemiring
- All Implemented Interfaces:
Semiring<PathCost>,Serializable,Comparable<PathCostSemiring>,Constable
((ℝ ∪ {+∞}) × ℘(Route), ⊕, ⊗, (+∞, ∅), (0, {ε}))
— the combined cost-and-witness algebra: a single weighted
closure run carries both a path's
cheapest cost and the route(s) achieving it. It is the
standard arg-min / Viterbi "best value + witness set" construction lifted onto the
tropical cost, closing the gap that tropical
(cost, no route) and lineage (routes, no cost) leave when used alone.
⊕ keeps the cheaper alternative, unioning the witness routes on a
cost tie (so all co-cheapest routes survive); ⊗ composes two hops in
series — costs add and the route-sets multiply (each pair's edge sets
unioned). 0 is (+∞, ∅) (unreachable),
1 is (0.0, {ε}) (the free derivation). The laws hold:
⊕ is a min-with-union and ⊗ is cost-addition with route-set
union, both commutative and associative (a Route is an unordered edge
set precisely so ⊗ stays commutative — the K-relation contract a
sequence concatenation would break); ⊗ distributes over ⊕ (the
prepended cost shifts both branches equally, so the arg-min winner is unchanged); and
(+∞, ∅) annihilates ⊗ (the +∞ absorbs the cost, the empty
route-set empties the product).
Bounded representation (the degraded mode)
A cyclic graph can enumerate unboundedly many co-cheapest routes (mirroring
lineage/counting). To stay bounded, an operation leaving more than
MAX_ROUTES distinct routes keeps the smallest MAX_ROUTES (in
Route's deterministic order) and marks the result
truncated — a sound under-approximation (surviving
routes are real, and the cost stays exact because min is
idempotent; only the route-set can grow). Truncation is contagious. The
--max-fixpoint-rounds cut-off bounds iteration as for every weighted closure.
-
Nested Class Summary
Nested classes/interfaces inherited from class java.lang.Enum
Enum.EnumDesc<E extends Enum<E>> -
Enum Constant Summary
Enum Constants -
Field Summary
FieldsModifier and TypeFieldDescriptionstatic final intMaximum distinct co-cheapest routes retained before a result is truncated. -
Method Summary
Modifier and TypeMethodDescriptionReturns the annotation a base tuple lifts to.one()Returns the multiplicative identity1.Combines two annotations with⊕— the way alternative derivations of the same tuple (union, projection) are merged.Combines two annotations with⊗— the way the joint requirements of a tuple (join, product) are merged.static PathCostSemiringReturns the enum constant of this class with the specified name.static PathCostSemiring[]values()Returns an array containing the constants of this enum class, in the order they are declared.zero()Returns the additive identity0.
-
Enum Constant Details
-
INSTANCE
The singleton instance.
-
-
Field Details
-
MAX_ROUTES
public static final int MAX_ROUTESMaximum distinct co-cheapest routes retained before a result is truncated.- See Also:
-
-
Method Details
-
values
Returns an array containing the constants of this enum class, in the order they are declared.- Returns:
- an array containing the constants of this enum class, in the order they are declared
-
valueOf
Returns the enum constant of this class with the specified name. The string must match exactly an identifier used to declare an enum constant in this class. (Extraneous whitespace characters are not permitted.)- Parameters:
name- the name of the enum constant to be returned.- Returns:
- the enum constant with the specified name
- Throws:
IllegalArgumentException- if this enum class has no constant with the specified nameNullPointerException- if the argument is null
-
zero
Description copied from interface:SemiringReturns the additive identity0. It is the identity ofSemiring.plus(K, K)and the annihilator ofSemiring.times(K, K), and denotes an absent tuple. -
one
Description copied from interface:SemiringReturns the multiplicative identity1. It is the identity ofSemiring.times(K, K). -
plus
Description copied from interface:SemiringCombines two annotations with⊕— the way alternative derivations of the same tuple (union, projection) are merged. Associative and commutative, with identitySemiring.zero(). -
times
Description copied from interface:SemiringCombines two annotations with⊗— the way the joint requirements of a tuple (join, product) are merged. Associative and commutative, with identitySemiring.one(), annihilated bySemiring.zero(). -
base
Returns the annotation a base tuple lifts to. This is how a semiring reads the data: the engine hands over each leaf tuple and the semiring says what it is worth.The default lifts every base tuple to
Semiring.one(), which is correct for any semiring whose annotation does not depend on the data — boolean existence and the security lattice, whose answers are decided entirely by how derivations combine. Override it to readBaseTuple.weight()(a cost, a multiplicity, a probability) or to mint a per-occurrence token fromBaseTuple.source()andBaseTuple.ordinal()(a route, a lineage variable).A semiring that reads a weight must decide for itself what an absent one means, because the two defensible answers differ:
Semiring.one()leaves the tuple neutral, while a fixed constant makes an unweighted graph a defined special case rather than a degenerate one.Each base tuple is minted a token distinguishing it from every other edge, so that the cheapest route can name the edges it travelled rather than only its cost. An edge with no numeric weight costs
0— every route then weighs its hop count of zero, which makes an unweighted graph a defined reachability-with-witness rather than an error.
-