SparseMatrixColorings.jl/test/suitesparse.jl at e843c73f467d0b7a46c53f24094f7d4a6e6e4cdc · JuliaDiff/SparseMatrixColorings.jl · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
using CSV
using DataFrames
using LinearAlgebra
using MatrixDepot
using SparseArrays
using SparseMatrixColorings
using SparseMatrixColorings:
    AdjacencyGraph,
    BipartiteGraph,
    degree,
    minimum_degree,
    maximum_degree,
    nb_vertices,
    nb_edges,
    neighbors,
    partial_distance2_coloring,
    star_coloring,
    vertices
using Test

nbunique(x) = length(unique(x))

_N() = NaturalOrder()
_LF() = LargestFirst()
_SL() = SmallestLast(; reproduce_colpack=true)
_ID() = IncidenceDegree(; reproduce_colpack=true)
_DLF() = DynamicLargestFirst(; reproduce_colpack=true)

## Distance-2 coloring

#=
Comparison with Tables VI and VII of the ColPack paper
=#

colpack_table_6_7 = CSV.read(
    joinpath(@__DIR__, "reference", "colpack_table_6_7.csv"), DataFrame
)

@testset verbose = true "Distance-2 coloring (ColPack paper)" begin
    @testset "$(row[:name])" for row in eachrow(colpack_table_6_7)
        original_mat = matrixdepot("$(row[:group])/$(row[:name])")
        mat = dropzeros(original_mat)
        bg = BipartiteGraph(mat)
        @testset "Graph features" begin
            @test nb_vertices(bg, Val(1)) == row[:V1]
            @test nb_vertices(bg, Val(2)) == row[:V2]
            @test nb_edges(bg) == row[:E]
            @test maximum_degree(bg, Val(1)) == row[:Δ1]
            @test maximum_degree(bg, Val(2)) == row[:Δ2]
        end
        @testset "Natural" begin
            @test nbunique(partial_distance2_coloring(bg, Val(1), _N())) == row[:N1]
            @test nbunique(partial_distance2_coloring(bg, Val(2), _N())) == row[:N2]
        end
        yield()
        @testset "LargestFirst" begin
            @test nbunique(partial_distance2_coloring(bg, Val(1), _LF())) == row[:LF1]
            @test nbunique(partial_distance2_coloring(bg, Val(2), _LF())) == row[:LF2]
        end
        yield()
        if row[:name] == "af23560"
            # orders differ for this one, not sure why
            continue
        end
        if row[:E] > 200_000
            # just to spare computational resources, but the larger tests pass too
            continue
        end
        @testset "SmallestLast" begin
            @test nbunique(partial_distance2_coloring(bg, Val(1), _SL())) == row[:SL1]
            @test nbunique(partial_distance2_coloring(bg, Val(2), _SL())) == row[:SL2]
        end
        yield()
        @testset "IncidenceDegree" begin
            @test nbunique(partial_distance2_coloring(bg, Val(1), _ID())) == row[:ID1]
            @test nbunique(partial_distance2_coloring(bg, Val(2), _ID())) == row[:ID2]
        end
        yield()
        @testset "DynamicLargestFirst" begin
            @test nbunique(partial_distance2_coloring(bg, Val(1), _DLF())) == row[:DLF1]
            @test nbunique(partial_distance2_coloring(bg, Val(2), _DLF())) == row[:DLF2]
        end
        yield()
    end
end;

#=
Comparison with Tables 3.1 and 3.2 of "What color is your Jacobian?"
=#

what_table_31_32 = CSV.read(
    joinpath(@__DIR__, "reference", "what_table_31_32.csv"), DataFrame
)

@testset "Distance-2 coloring (survey paper)" begin
    @testset "$(row[:name])" for row in eachrow(what_table_31_32)
        ismissing(row[:group]) && continue
        original_mat = matrixdepot("$(row[:group])/$(row[:name])")
        mat = original_mat  # no dropzeros
        bg = BipartiteGraph(mat)
        @test nb_vertices(bg, Val(1)) == row[:m]
        @test nb_vertices(bg, Val(2)) == row[:n]
        @test nb_edges(bg) == row[:nnz]
        @test minimum_degree(bg, Val(1)) == row[:ρmin]
        @test maximum_degree(bg, Val(1)) == row[:ρmax]
        @test minimum_degree(bg, Val(2)) == row[:κmin]
        @test maximum_degree(bg, Val(2)) == row[:κmax]
        color_Nb = partial_distance2_coloring(bg, Val(2), NaturalOrder())
        if length(unique(color_Nb)) == row[:K]
            @test length(unique(color_Nb)) == row[:K]
        else
            @test_broken length(unique(color_Nb)) == row[:K]
        end
        yield()
    end
end;

## Star coloring

what_table_41_42 = CSV.read(
    joinpath(@__DIR__, "reference", "what_table_41_42.csv"), DataFrame
)

@testset "Star coloring (survey paper)" begin
    @testset "$(row[:name])" for row in eachrow(what_table_41_42)
        ismissing(row[:group]) && continue
        original_mat = matrixdepot("$(row[:group])/$(row[:name])")
        mat = dropzeros(sparse(original_mat))
        ag = AdjacencyGraph(mat)
        bg = BipartiteGraph(mat)
        @test nb_vertices(ag) == row[:V]
        @test nb_edges(ag) == row[:E]
        @test maximum_degree(ag) == row[:Δ]
        @test minimum_degree(ag) == row[:δ]
        postprocessing = false
        color_N, _ = star_coloring(ag, NaturalOrder(), postprocessing)
        @test_skip row[:KS1] <= length(unique(color_N)) <= row[:KS2]  # TODO: find better
        yield()
    end
end;