SparseMatrixColorings.jl/test/suitesparse.jl at 97c602cc9108576fa358fe3eaa06c209a0ec916a · 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
using CSV
using DataFrames
using LinearAlgebra
using MatrixDepot
using SparseArrays
using SparseMatrixColorings:
    AdjacencyGraph,
    BipartiteGraph,
    LargestFirst,
    NaturalOrder,
    degree,
    minimum_degree,
    maximum_degree,
    nb_vertices,
    nb_edges,
    neighbors,
    partial_distance2_coloring,
    star_coloring,
    vertices
using Test

## 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 "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)
        @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]
        color_N1 = partial_distance2_coloring(bg, Val(1), NaturalOrder())
        color_N2 = partial_distance2_coloring(bg, Val(2), NaturalOrder())
        @test length(unique(color_N1)) == row[:N1]
        @test length(unique(color_N2)) == row[:N2]
        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;