tropical_gemm/types/
mod.rs

1//! Tropical semiring type definitions.
2//!
3//! This module defines the algebraic structures used for tropical matrix
4//! multiplication. A **tropical semiring** replaces the standard arithmetic
5//! operations (+, ×) with alternative operations, typically (max, +) or (min, +).
6//!
7//! # What is a Tropical Semiring?
8//!
9//! A semiring is an algebraic structure with two binary operations:
10//! - **Addition** (⊕): An associative, commutative operation with identity (zero)
11//! - **Multiplication** (⊗): An associative operation with identity (one)
12//!
13//! In tropical algebra, these become:
14//!
15//! | Type | ⊕ (add) | ⊗ (mul) | Zero | One | Use Case |
16//! |------|---------|---------|------|-----|----------|
17//! | [`TropicalMaxPlus<T>`] | max | + | -∞ | 0 | Longest path, Viterbi algorithm |
18//! | [`TropicalMinPlus<T>`] | min | + | +∞ | 0 | Shortest path, Dijkstra |
19//! | [`TropicalMaxMul<T>`] | max | × | 0 | 1 | Maximum probability paths |
20//! | [`TropicalAndOr`] | OR | AND | false | true | Graph reachability |
21//!
22//! # Tropical Matrix Multiplication
23//!
24//! For matrices A (m×k) and B (k×n), the tropical product C = A ⊗ B is:
25//!
26//! ```text
27//! C[i,j] = ⊕_{k} (A[i,k] ⊗ B[k,j])
28//! ```
29//!
30//! For MaxPlus, this becomes: `C[i,j] = max_k(A[i,k] + B[k,j])`
31//!
32//! # Core Traits
33//!
34//! - [`TropicalSemiring`]: Defines the semiring operations (add, mul, zero, one)
35//! - [`TropicalWithArgmax`]: Extends semiring with argmax tracking for backpropagation
36//! - [`TropicalScalar`]: Trait for scalar types that can be used in tropical operations
37//!
38//! # Example
39//!
40//! ```rust
41//! use tropical_gemm::types::{TropicalMaxPlus, TropicalSemiring};
42//!
43//! // Create tropical numbers
44//! let a = TropicalMaxPlus::from_scalar(3.0f32);
45//! let b = TropicalMaxPlus::from_scalar(5.0f32);
46//!
47//! // Tropical addition: max(3, 5) = 5
48//! let sum = TropicalMaxPlus::tropical_add(a, b);
49//! assert_eq!(sum.value(), 5.0);
50//!
51//! // Tropical multiplication: 3 + 5 = 8
52//! let product = TropicalMaxPlus::tropical_mul(a, b);
53//! assert_eq!(product.value(), 8.0);
54//! ```
55//!
56//! # Type Aliases
57//!
58//! For convenience, the crate provides shorter type aliases:
59//!
60//! ```rust
61//! use tropical_gemm::{MaxPlus, MinPlus, MaxMul, TropicalSemiring};
62//!
63//! let x: MaxPlus<f32> = MaxPlus::from_scalar(1.0);
64//! let y: MinPlus<f64> = MinPlus::from_scalar(2.0);
65//! let z: MaxMul<f32> = MaxMul::from_scalar(3.0);
66//! ```
67
68mod and_or;
69mod counting;
70mod max_mul;
71mod max_plus;
72mod min_plus;
73mod scalar;
74mod traits;
75
76pub use and_or::TropicalAndOr;
77pub use counting::CountingTropical;
78pub use max_mul::TropicalMaxMul;
79pub use max_plus::TropicalMaxPlus;
80pub use min_plus::TropicalMinPlus;
81pub use scalar::TropicalScalar;
82pub use traits::{SimdTropical, TropicalSemiring, TropicalWithArgmax};
tropical_gemm/types/mod.rs

tropical_gemm/types/
mod.rs
