More tests from SparseMatrixColorings [SEGFAULT]

[gdalle]

To diagnose the nondeterministic behavior of #21, I added some coloring correctness tests from SparseMatrixColorings.jl.

On my machine, the test file with this random seed causes a reproducible segfault, which is clearly not on me because I don't use @inbounds anywhere in my Julia code.
With other random seeds, I observe other kinds of failures, like colorings that don't start with 1 (which should be impossible).

I temporarily disabled the tests on 1.6 because they failed for other reasons before the segfault could occur on 1.10.

[gdalle]

Since I'm a good person, here's the guilty matrix for which bipartite partial coloring failed so badly. GitHub doesn't support .mtx so I just copied the file contents below

%%MatrixMarket matrix coordinate pattern general
20 10 74
2 1
8 1
10 1
11 1
12 1
13 1
18 1
2 2
6 2
9 2
10 2
12 2
13 2
17 2
19 2
7 3
12 3
13 3
15 3
3 4
4 4
5 4
6 4
14 4
16 4
18 4
19 4
3 5
7 5
8 5
11 5
14 5
17 5
18 5
20 5
8 6
9 6
10 6
11 6
12 6
17 6
19 6
20 6
1 7
5 7
6 7
8 7
10 7
18 7
2 8
4 8
5 8
8 8
10 8
11 8
14 8
20 8
2 9
4 9
6 9
10 9
13 9
14 9
17 9
18 9
19 9
2 10
3 10
4 10
7 10
10 10
11 10
14 10
15 10

[amontoison]

julia> colpack("./gdalle.mtx", "COLUMN_PARTIAL_DISTANCE_TWO", "NATURAL", verbose=true)
Found file ./gdalle.mtx
Graph of Market Market type: [matrix coordinate pattern general]

graph: ./gdalle.mtx
order: NATURAL
methd: COLUMN_PARTIAL_DISTANCE_TWO
Partial Distance Two Bipartite Graph Coloring
order+color time = 0.000000 = 0.000000+0.000000
number of colors: 9

Bipartite Graph | Column Partial Coloring | Column Vertices | Vertex Colors | gdalle.mtx

1	 : 1
2	 : 2
3	 : 3
4	 : 3
5	 : 4
6	 : 5
7	 : 6
8	 : 7
9	 : 8
10	 : 9

[Total Column Colors = 9]

julia> colpack("./gdalle.mtx", "ROW_PARTIAL_DISTANCE_TWO", "NATURAL", verbose=true)
Found file ./gdalle.mtx
Graph of Market Market type: [matrix coordinate pattern general]

graph: ./gdalle.mtx
order: NATURAL
methd: ROW_PARTIAL_DISTANCE_TWO
Partial Distance Two Bipartite Graph Coloring
order+color time = 0.000000 = 0.000000+0.000000
number of colors: 12

Bipartite Graph | Row Partial Coloring | Row Vertices | Vertex Colors gdalle.mtx

1	 : 1
2	 : 1
3	 : 2
4	 : 3
5	 : 4
6	 : 5
7	 : 4
8	 : 6
9	 : 2
10	 : 7
11	 : 5
12	 : 3
13	 : 8
14	 : 9
15	 : 6
16	 : 1
17	 : 10
18	 : 11
19	 : 12
20	 : 8

[Total Row Colors = 12]

The issue is the CSR parser in ColPack...

[gdalle]

You mean in ColPack.jl?

[amontoison]

No ColPack, we have multiple way to provide a sparse matrix (ADOL-C, path of a .mtx file, RB matrix, CSR matrix, ...) and it is converted into a graph.
The internal parser of a CSR -> Graph is wrong.

It's why it's only worning with the binary.

[gdalle]

I still don't understand how you can rule out an error in the way Julia provides the CSR input or reads the output

[amontoison]

It's not Julia Guillaume, it's the C++ code inside ColPack that do CSR -> graph storage used by ColPack.

[gdalle]

I still don't understand how the code snippets you posted above prove that, and I'm a bit skeptical that there could be such a bad bug inside a (once) frequently used library. Any idea how we could demonstrate it?