Open gdalle opened 3 weeks ago
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
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...
You mean in ColPack.jl?
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.
I still don't understand how you can rule out an error in the way Julia provides the CSR input or reads the output
It's not Julia Guillaume, it's the C++ code inside ColPack that do CSR -> graph storage used by ColPack.
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?
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 with1
(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.