Reference

MaxPlus{T}(x::Number) where {T<:Number}
MaxPlus(x::Number)

Constructor for the type MaxPlus. If a type T is given, x is converted to that type, otherwise the type is inferred from x.

MinPlus{T}(x::Number) where {T<:Number}
MinPlus(x::Number)

Constructor for the type MinPlus. If a type T is given, x is converted to that type, otherwise the type is inferred from x.

elt(x::SemiRing)

Returns the tropical element.

isinfinite(x::SemiRing)

Returns true if x is the infinite element of the tropical field (ie the tropical 0), false otherwise.

Base.:(==)(x::S,y::S) where {S<:SemiRing}

Equality of tropical numbers.

Base.:(+)(x::S,y::S) where {S<:SemiRing}

Addition of tropical numbers.

Example

julia> using TPLib

julia> MaxPlus(3) + MaxPlus(8)
8

julia> MinPlus(4.) + MinPlus{Int64}(∞)
4.0

julia> MaxPlus(6.2) + 4
6.2

Base.:(*)(x::S,y::S) where {S<:SemiRing}

Multiplication of tropical numbers.

Example

julia> using TPLib

julia> MaxPlus(4) * MaxPlus(8)
12

julia> MinPlus(2) * MinPlus(-3.5)
-1.5

julia> MaxPlus(10.0) * -Inf
⋅

Base.isless(x::S,y::S) where {S<:SemiRing}

Comparison of tropical numbers.

compute_ext_rays(I::Matrix{<:SemiRing}, n::Integer)
compute_ext_rays(I::Matrix{<:Number}, n::Integer, semiring=:max)

Computes the set of the extreme rays of a tropical cone given by the inequalities I in dimension n, see [3]. Each row of I contains 2n coefficients. When written $[a_{i1} \, \dots \, a_{in} \, b_{i1} \, \dots \, b_{in}]$, they represent the tropical inequality

\[\max(a_{i1} + x_1, \dots, a_{in} + x_n) \geqslant \max(b_{i1} + x_1, \dots, b_{in} + x_n)\]

If the coefficients of I have type MaxPlus{T} or MinPlus{T}, then the computations are done in the max-plus or min-plus tropical semirings respectively. Otherwise, you can specify wether the coefficients should be converted to the semiring :max or :min. Returns a matrix G::Matrix{<:SemiRing} in which every line is a tropical point generating the cone.

References

[1] X. Allamigeon. Static analysis of memory manipulations by abstract interpretation – Algorithmics of tropical polyhedra, and application to abstract interpretation. PhD thesis.

[2] X. Allamigeon, S. Gaubert, E. Goubault. Computing the vertices of tropical polyhedra using directed hypergraphs. Discrete & Computational Geometry, 49(2):247–279, 2013. E-print arXiv:0904.3436v4.

compute_ext_rays_polar(M::Matrix{<:SemiRing}, n::Integer)
compute_ext_rays_polar(M::Matrix{<:Number}, n::Integer, semiring=:max)

Computes the set of the extreme rays of the polar of a tropical cone given by a generating set M in dimension n, see [3]. Each row of M contains n coefficients and represents a generator of the tropical cone. If the coefficients of M have type MaxPlus{T} or MinPlus{T}, then the computations are done in the max-plus or min-plus tropical semirings respectively. Otherwise, you can specify wether the coefficients should be converted to the semiring :max or :min. Returns a matrix ::Matrix{<:SemiRing} in which every row is a tropical point generating the polar cone.

References

[1] X. Allamigeon, S. Gaubert, and R. D. Katz. Tropical polar cones, hypergraph transversals, and mean payoff games. Linear Algebra Appl., 435(7):1549–1574, 2011. E-print arXiv:1004.2778.

compute_halfspaces(M::Matrix{<:SemiRing}, n::Integer)
compute_halfspaces(M::Matrix{<:Number}, n::Integer, semiring=:max)

Computes a minimal external representation by means of tropical half-spaces of a tropical cone given by a generating set M in dimension n, see [4]. The set of generators must be nonempty, ie M cannot be empty. It currently handles only the case of generating sets in which every vector has finite entries. Returns a pair (H::Matrix{<:SemiRing},A::Vector{Vector{Integer}}) where the rows of H are the equations for the tropical half-spaces and the vectors of A are the sectors of each half-space.

References

[1] X. Allamigeon and R.D. Katz. Minimal external representations of tropical polyhedra. Journal of Combinatorial Theory, Series A, 120(4):907–940, 2013. Eprint arXiv:1205.6314.

compute_tropical_complex(M::Matrix{<:SemiRing}, n::Integer)
compute_tropical_complex(M::Matrix{<:Number}, n::Integer, semiring=:max)

Computes the tropical complex associated with a tropical cone given by a generating set. Only generating sets which are minimal and in which every vector has finite entries are supported. Returns a pair (V::Matrix{<:Number},A::Vector{Vector{Int64}}) where the rows of V are the vertices of the complex, and A is the collection of maximal cells (defined by adjacency with vertices). Note that each cell is seen as a usual polytope, and not as a tropical one, and that the vertices are not necessarily unique.

References

[1] M. Develin and B. Sturmfels. Tropical convexity. Doc. Math., 9:1–27 (electronic), 2004. E-print arXiv:math.MG/0308254.

compute_tangent_hypergraph(M::Matrix{<:SemiRing}, P::Vector{<:SemiRing}, n::Integer)
compute_tangent_hypergraph(H::Matrix{<:SemiRing}, A::Vector{Vector{Int64}},  P::Vector{<:SemiRing}, n::Integer) 
compute_tangent_hypergraph(M::Matrix{<:Number}, P::Vector{<:Number}, n::Integer, semiring=:max)
compute_tangent_hypergraph(H::Matrix{<:Number}, A::Vector{Vector{Int64}},  P::Vector{<:Number}, n::Integer, semiring=:max)

Computes the tangent directed hypergraph of a point P in a tropical cone specified by its generators or inequalities M (the difference is made by wether M is composed of n or 2n columns) or by halfspaces H with their sectors A. Returns the number of vertices of the hypergraph, its hyperedges, and in the case where M was specified by inequalities or halfspaces, then the active inequalities or halfspaces associated to the hyperedges. Note that the vertices of the hypergraph are labeled starting at 1, whereas they are labeled starting at 0 in TPLib.

References

[1] X. Allamigeon. Static analysis of memory manipulations by abstract interpretation – Algorithmics of tropical polyhedra, and application to abstract interpretation. PhD thesis.

[2] X. Allamigeon, S. Gaubert, E. Goubault. Computing the vertices of tropical polyhedra using directed hypergraphs. Discrete & Computational Geometry, 49(2):247–279, 2013. E-print arXiv:0904.3436v4.