Non-deterministic coloring?

[gdalle]

Is there an explanation for coloring to be non-deterministic with the natural order?

julia> using ColPack, SparseArrays, StableRNGs

julia> J = sprand(StableRNG(63), 100, 200, 0.04)
100×200 SparseMatrixCSC{Float64, Int64} with 828 stored entries:
...

julia> for i in 1:10
           println(maximum(get_colors(ColPackPartialColoring(J, "COLUMN_PARTIAL_DISTANCE_TWO", "NATURAL"))))
       end
19
23
22
21
22
22
23
21
22
22

[gdalle]

Even more surprising, it's the same with matrix from files:

julia> using MatrixMarket

julia> MatrixMarket.mmwrite("J.mtx", J)

julia> for i in 1:10
           println(maximum(get_colors(ColPackPartialColoring("J.mtx", "COLUMN_PARTIAL_DISTANCE_TWO", "NATURAL"))))
       end
Found file J.mtx
Graph of Market Market type: [matrix coordinate real general]
22
Found file J.mtx
Graph of Market Market type: [matrix coordinate real general]
23
Found file J.mtx
Graph of Market Market type: [matrix coordinate real general]
22
Found file J.mtx
Graph of Market Market type: [matrix coordinate real general]
20
Found file J.mtx
Graph of Market Market type: [matrix coordinate real general]
22
Found file J.mtx
Graph of Market Market type: [matrix coordinate real general]
24
Found file J.mtx
Graph of Market Market type: [matrix coordinate real general]
23
Found file J.mtx
Graph of Market Market type: [matrix coordinate real general]
23
Found file J.mtx
Graph of Market Market type: [matrix coordinate real general]
22
Found file J.mtx
Graph of Market Market type: [matrix coordinate real general]
22

[gdalle]

I just checked that the command line interface of ColPack consistently returns a coloring with 19 colors for that setup, so the problem lies with our Julia - C++ bindings

[amontoison]

I checked with the PR #22 and I confirm:

using ColPack, SparseArrays, StableRNGs
using MatrixMarket

J = sprand(StableRNG(63), 100, 200, 0.04)
MatrixMarket.mmwrite("./myfile.mtx", J)

for i in 1:10
    colpack("./myfile.mtx", "ROW_PARTIAL_DISTANCE_TWO", "NATURAL")
end

for i in 1:10
    colpack("./myfile.mtx", "COLUMN_PARTIAL_DISTANCE_TWO", "NATURAL")
end


for i in 1:10
  obj = ColPackPartialColoring(J, "ROW_PARTIAL_DISTANCE_TWO", "NATURAL")
  ncolors(obj) |> println
end

for i in 1:10
  obj = ColPackPartialColoring(J, "COLUMN_PARTIAL_DISTANCE_TWO", "NATURAL")
  ncolors(obj) |> println
end

[gdalle]

What do you confirm? That the binary is deterministic and we screwed up somewhere else in the interface?

[amontoison]

What do you confirm? That the binary is deterministic and we screwed up somewhere else in the interface?

Yes, I did something wrong in the C interface.

[gdalle]

Here is a more recent example using the binary and the latest version of everything (master branch of ColPack.jl):

julia> using ColPack, MatrixDepot, MatrixMarket

julia> name  = "LPnetlib/lp_ken_11";

julia> path = joinpath(@__DIR__, "tempmat.mtx");

julia> MatrixMarket.mmwrite(path, MatrixDepot.matrixdepot(name))

julia> for _ in 1:10
           ColPack.colpack(path, "COLUMN_PARTIAL_DISTANCE_TWO", "NATURAL"; verbose=false);
       end
125
124
125
127
124
125
125
124
124
127

[amontoison]

@gdalle
The ordering is deterministic.
I still have a different number coloring but also always the same ordering.

for i in 1:10
	ref = ColPackPartialColoring(J, "COLUMN_PARTIAL_DISTANCE_TWO", "NATURAL")
	colors = get_colors(ref)
    println(colors |> maximum)
    order = get_ordering(ref)
    if i == 1
      ordering .= order
      coloring .= colors
    end
    @assert norm(order - ordering) == 0
    # if norm(colors - coloring) != 0
    # 	for k = 1:200
    # 	  @printf("%2d | %2d\n", coloring[k], colors[k])
    # 	end
    # end
    println()
end