SparseMatrixColorings.jl/test/random.jl at ace3de0913a52f1ca463bd3b7478d5c3614cd21f · 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
using ADTypes: column_coloring, row_coloring, symmetric_coloring
using LinearAlgebra
using SparseArrays
using SparseMatrixColorings
using StableRNGs
using Test

rng = StableRNG(63)

asymmetric_params = vcat(
    [(10, 20, p) for p in (0.0:0.1:0.5)],
    [(20, 10, p) for p in (0.0:0.1:0.5)],
    [(100, 200, p) for p in (0.01:0.01:0.05)],
    [(200, 100, p) for p in (0.01:0.01:0.05)],
)

symmetric_params = vcat(
    [(10, p) for p in (0.0:0.1:0.5)], #
    [(100, p) for p in (0.01:0.01:0.05)],
)

@testset "Column coloring & decompression" begin
    problem = ColoringProblem(; structure=:nonsymmetric, partition=:column)
    algo = GreedyColoringAlgorithm(; decompression=:direct)
    @testset "$((; m, n, p))" for (m, n, p) in asymmetric_params
        A0 = sprand(rng, m, n, p)
        color0 = column_coloring(A0, algo)
        test_coloring_decompression(A0, problem, algo; color0)
    end
    @testset "$((; n, p))" for (n, p) in symmetric_params
        A0 = sparse(Symmetric(sprand(rng, n, n, p)))
        color0 = column_coloring(A0, algo)
        test_coloring_decompression(A0, problem, algo; color0)
    end
end;

@testset "Row coloring & decompression" begin
    problem = ColoringProblem(; structure=:nonsymmetric, partition=:row)
    algo = GreedyColoringAlgorithm(; decompression=:direct)
    @testset "$((; m, n, p))" for (m, n, p) in asymmetric_params
        A0 = sprand(rng, m, n, p)
        color0 = row_coloring(A0, algo)
        test_coloring_decompression(A0, problem, algo; color0)
    end
    @testset "$((; n, p))" for (n, p) in symmetric_params
        A0 = sparse(Symmetric(sprand(rng, n, n, p)))
        color0 = row_coloring(A0, algo)
        test_coloring_decompression(A0, problem, algo; color0)
    end
end;

@testset "Symmetric coloring & direct decompression" begin
    problem = ColoringProblem(; structure=:symmetric, partition=:column)
    @testset for algo in (
        GreedyColoringAlgorithm(; postprocessing=false, decompression=:direct),
        GreedyColoringAlgorithm(; postprocessing=true, decompression=:direct),
    )
        @testset "$((; n, p))" for (n, p) in symmetric_params
            A0 = sparse(Symmetric(sprand(rng, n, n, p)))
            color0 = algo.postprocessing ? nothing : symmetric_coloring(A0, algo)
            test_coloring_decompression(A0, problem, algo; color0)
        end
    end
end;

@testset "Symmetric coloring & substitution decompression" begin
    problem = ColoringProblem(; structure=:symmetric, partition=:column)
    @testset for algo in (
        GreedyColoringAlgorithm(; postprocessing=false, decompression=:substitution),
        GreedyColoringAlgorithm(; postprocessing=true, decompression=:substitution),
    )
        @testset "$((; n, p))" for (n, p) in symmetric_params
            A0 = sparse(Symmetric(sprand(rng, n, n, p)))
            # TODO: find tests for recoverability
            test_coloring_decompression(A0, problem, algo)
        end
    end
end;

@testset "Bicoloring & direct decompression" begin
    problem = ColoringProblem(; structure=:nonsymmetric, partition=:bidirectional)
    @testset for algo in (
        GreedyColoringAlgorithm(
            RandomOrder(StableRNG(0), 0); postprocessing=false, decompression=:direct
        ),
        GreedyColoringAlgorithm(
            RandomOrder(StableRNG(0), 0); postprocessing=true, decompression=:direct
        ),
    )
        @testset "$((; m, n, p))" for (m, n, p) in asymmetric_params
            A0 = sprand(rng, m, n, p)
            test_bicoloring_decompression(A0, problem, algo)
        end
        @testset "$((; n, p))" for (n, p) in symmetric_params
            A0 = sparse(Symmetric(sprand(rng, n, n, p)))
            test_bicoloring_decompression(A0, problem, algo)
        end
    end
end;

@testset "Bicoloring & substitution decompression" begin
    problem = ColoringProblem(; structure=:nonsymmetric, partition=:bidirectional)
    @testset for algo in (
        GreedyColoringAlgorithm(
            RandomOrder(StableRNG(0), 0); postprocessing=false, decompression=:substitution
        ),
        GreedyColoringAlgorithm(
            RandomOrder(StableRNG(0), 0); postprocessing=true, decompression=:substitution
        ),
    )
        @testset "$((; m, n, p))" for (m, n, p) in asymmetric_params
            A0 = sprand(rng, m, n, p)
            test_bicoloring_decompression(A0, problem, algo)
        end
        @testset "$((; n, p))" for (n, p) in symmetric_params
            A0 = sparse(Symmetric(sprand(rng, n, n, p)))
            test_bicoloring_decompression(A0, problem, algo)
        end
    end
end;