SparseMatrixColorings.jl/test/forest.jl at 7b67d58b6c9fd213c05fa772f4061b04ee0bfc19 · 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
using SparseMatrixColorings: Forest, find_root!, root_union!
using Test

@testset "Constructor Forest" begin
    forest = Forest{Int}(5)
    @test forest.nt == 5
    @test length(forest.parents) == 5
    @test all(forest.parents .== 1:5)
    @test all(forest.ranks .== 0)
end

@testset "Find root" begin
    forest = Forest{Int}(5)
    @test find_root!(forest, 3) == 3
    @test find_root!(forest, 5) == 5
end

@testset "Root union" begin
    forest = Forest{Int}(5)
    root1 = find_root!(forest, 1)
    root3 = find_root!(forest, 3)
    @test root1 != root3

    root_union!(forest, root1, root3)
    @test find_root!(forest, 3) == 1
    @test forest.parents[1] == 1
    @test forest.parents[3] == 1
    @test forest.ranks[1] == 1
    @test forest.ranks[3] == 0
    @test forest.nt == 4

    root1 = find_root!(forest, 1)
    root2 = find_root!(forest, 2)
    @test root1 != root2

    root_union!(forest, root1, root2)
    @test find_root!(forest, 2) == 1
    @test forest.parents[1] == 1
    @test forest.parents[2] == 1
    @test forest.ranks[1] == 1
    @test forest.ranks[2] == 0
    @test forest.nt == 3
end