Reputation: 105
I'm trying to implement the max-plus semiring algebra in Julia (0.6.2), following this paper:
http://www.mit.edu/~kepner/pubs/JuliaSemiring_HPEC2013_Paper.pdf
The type definition for max-plus numbers and the definitions of all relevant operators, taken straight from the paper mentioned above, are as follows:
# define max-plus number type
immutable MPNumber{T} <: Number
val::T
end
+(a::MPNumber, b::MPNumber) = MPNumber(max(a.val, b.val))
*(a::MPNumber, b::MPNumber) = MPNumber(a.val + b.val)
show(io::IO, k::MPNumber) = show(io, k.val)
zero{T}(::MPNumber{T}) = MPNumber(typemin(T))
one{T}(::MPNumber{T}) = MPNumber(zero(T))
promote_rule{T<:Number}(::Type{MPNumber}, ::Type{T}) = MPNumber
mparray(A::Array) = map(MPNumber, A)
array{T}(A::Array{MPNumber{T}}) = map(x->x.val, A)
Basic tests of max-plus addition and multiplication work just fine, e.g.
MPNumber(1) + MPNumber(1)
gives MPNumber(1)
, as expected. Max-plus matrix exponentiation, as shown in the paper, also works like a charm:
A = mparray(Array([[1, 2] [3, 4]]))
A*A
gives
2×2 Array{MPNumber{Int64},2}:
MPNumber{Int64}(5) MPNumber{Int64}(7)
MPNumber{Int64}(6) MPNumber{Int64}(8)
However, when I try to multiply a max-plus vector with a max-plus matrix,
A = mparray(Array([[1, 2] [3, 4]]))
x = mparray([1, 2])
A*x
I get the following error:
MethodError: Cannot `convert` an object of type Int64 to an object of type MPNumber{Int64}
This may have arisen from a call to the constructor MPNumber{Int64}(...) since type constructors fall back to convert methods.
Stacktrace:
[1] generic_matvecmul!(::Array{MPNumber{Int64},1}, ::Char, ::Array{MPNumber{Int64},2}, ::Array{MPNumber{Int64},1}) at ./linalg/matmul.jl:434
[2] Ac_mul_B(::Array{MPNumber{Int64},1}, ::Array{MPNumber{Int64},2}) at ./linalg/rowvector.jl:227
I'm still fairly new to Julia, so I'm having a hard time working out exactly what it is that's going wrong here and how it can be fixed. Any help would be much appreciated.
Upvotes: 6
Views: 157
Reputation: 69879
This is tested under Julia 0.6.2. Use the following code:
struct MPNumber{T} <: Number
val::T
end
Base.:+(a::MPNumber, b::MPNumber) = MPNumber(max(a.val, b.val))
Base.:*(a::MPNumber, b::MPNumber) = MPNumber(a.val + b.val)
Base.show(io::IO, k::MPNumber) = show(io, k.val)
Base.zero(::MPNumber{T}) where T = MPNumber(typemin(T))
Base.one(::MPNumber{T}) where T = MPNumber(zero(T))
Base.zero(::Type{MPNumber{T}}) where T = MPNumber(typemin(T))
Base.one(::Type{MPNumber{T}}) where T = MPNumber(zero(T))
mparray(A::Array) = map(MPNumber, A)
(I recommend you to start with this part only as conversions and promotions are more tricky and not needed for your purposes).
Observe that the crucial part is that I am extending functions from Base
by prepending Base.
before them. For +
and *
you need to additionally use :
before function names.
Now you can run all you wanted:
julia> MPNumber(1) + MPNumber(1)
1
julia> A = mparray(Array([[1, 2] [3, 4]]))
2×2 Array{MPNumber{Int64},2}:
1 3
2 4
julia> A*A
2×2 Array{MPNumber{Int64},2}:
5 7
6 8
julia> A = mparray(Array([[1, 2] [3, 4]]))
2×2 Array{MPNumber{Int64},2}:
1 3
2 4
julia> x = mparray([1, 2])
2-element Array{MPNumber{Int64},1}:
1
2
julia> A*x
2-element Array{MPNumber{Int64},1}:
5
6
as wanted.
EDIT: I have made zero
and one
definitions in your code to be more complete and follow standard requirements.
Upvotes: 7