Module com.darkcollective.relix.provenance
Package com.darkcollective.relix.provenance

Enum Class TropicalSemiring

java.lang.Object
java.lang.Enum<TropicalSemiring>
com.darkcollective.relix.provenance.TropicalSemiring
All Implemented Interfaces:
Semiring<Double>, Serializable, Comparable<TropicalSemiring>, Constable
public enum TropicalSemiring extends Enum<TropicalSemiring> implements Semiring<Double>
The tropical (min-plus) semiring (ℝ ∪ {+∞}, min, +, +∞, 0) — the cheapest-derivation algebra, i.e. shortest path when iterated by a weighted transitive closure.

⊕ is Math.min(int, int) (among alternative derivations, keep the cheapest), ⊗ is addition (the cost of a joint derivation is the sum of its parts), 0 is +∞ (unreachable / absent), and 1 is 0.0 (a free derivation). Annihilation holds because +∞ + x == +∞, and ⊗ distributes over ⊕ because min(a, b) + c == min(a + c, b + c).

Weights are non-negative finite doubles or +∞; NaN and -∞ are not valid annotations (they break the min/+ ordering).

Exactness

⊕ is exact for every weight: Math.min(int, int) chooses one of its operands rather than computing a new value, so there is nothing to round and the law (a ⊕ b) ⊕ c == a ⊕ (b ⊕ c) holds at any magnitude.

⊗ is double addition, and so is associative only where that addition is exact — integral weights below 2^53, which covers hop counts and whole-unit costs. It is not associative for weights that binary floating point cannot represent exactly: with a = b = 0.01 and c = 0.04, (a ⊗ b) ⊗ c is 0.06 while a ⊗ (b ⊗ c) is 0.060000000000000005. The consequence for a weighted closure is that a total cost may differ in its last bits depending on the order edges were combined; the path chosen by ⊕ is unaffected unless two routes are within one ulp of each other. Use integral weights — scaled to whole units, as money is usually held in cents — where an exact total matters.

  • Enum Constant Details

    • INSTANCE

      public static final TropicalSemiring INSTANCE
      The singleton instance.

  • Method Details

    • values

      public static TropicalSemiring[] 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

      public static TropicalSemiring valueOf(String name)
      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 name
      NullPointerException - if the argument is null

    • zero

      public Double zero()
      Description copied from interface: Semiring
      Returns the additive identity 0. It is the identity of Semiring.plus(K, K) and the annihilator of Semiring.times(K, K), and denotes an absent tuple.
      Specified by:
      zero in interface Semiring<Double>
      Returns:
      the additive identity 0

    • one

      public Double one()
      Description copied from interface: Semiring
      Returns the multiplicative identity 1. It is the identity of Semiring.times(K, K).
      Specified by:
      one in interface Semiring<Double>
      Returns:
      the multiplicative identity 1

    • plus

      public Double plus(Double a, Double b)
      Description copied from interface: Semiring
      Combines two annotations with ⊕ — the way alternative derivations of the same tuple (union, projection) are merged. Associative and commutative, with identity Semiring.zero().
      Specified by:
      plus in interface Semiring<Double>
      Parameters:
      a - the first annotation
      b - the second annotation
      Returns:
      a ⊕ b

    • times

      public Double times(Double a, Double b)
      Description copied from interface: Semiring
      Combines two annotations with ⊗ — the way the joint requirements of a tuple (join, product) are merged. Associative and commutative, with identity Semiring.one(), annihilated by Semiring.zero().
      Specified by:
      times in interface Semiring<Double>
      Parameters:
      a - the first annotation
      b - the second annotation
      Returns:
      a ⊗ b

    • base

      public Double base(BaseTuple tuple)
      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 read BaseTuple.weight() (a cost, a multiplicity, a probability) or to mint a per-occurrence token from BaseTuple.source() and BaseTuple.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.

      An edge's weight is its cost. An edge with no numeric weight costs 0, making it free rather than impassable — the reading under which an unweighted graph's shortest path is its hop count of zero.

      Specified by:
      base in interface Semiring<Double>
      Parameters:
      tuple - the base tuple; never null
      Returns:
      the tuple's base annotation; never null