staticgraphs.jl

@testset "Static graphs" begin
    @testset "DiGraphs" begin
        g = @inferred(complete_digraph(5))
        @test nv(g) == 5 && ne(g) == 20
        @test isvalid_simplegraph(g)
        # tests for extreme values
        g = complete_digraph(0)
        @test nv(g) == 0 && ne(g) == 0
        g = complete_digraph(1)
        @test nv(g) == 1 && ne(g) == 0
        g = complete_digraph(2)
        @test nv(g) == 2 && ne(g) == 2
        g = @inferred complete_digraph(Int8(127))
        @test nv(g) == 127 && ne(g) == 127 * (127 - 1)
        @test eltype(g) == Int8
    end

    @testset "Graphs" begin
        g = @inferred(complete_graph(5))
        @test nv(g) == 5 && ne(g) == 10
        @test isvalid_simplegraph(g)
        # tests for extreme values
        g = complete_graph(0)
        @test nv(g) == 0 && ne(g) == 0
        g = complete_graph(1)
        @test nv(g) == 1 && ne(g) == 0
        g = complete_graph(2)
        @test nv(g) == 2 && ne(g) == 1
        g = @inferred complete_graph(Int8(127))
        @test nv(g) == 127 && ne(g) == 127 * (127 - 1) ÷ 2
        @test eltype(g) == Int8
    end

    @testset "Bipartite Graphs" begin
        g = @inferred(complete_bipartite_graph(5, 8))
        @test nv(g) == 13 && ne(g) == 40
        @test isvalid_simplegraph(g)
        # tests for extreme values
        g = complete_bipartite_graph(0, 0)
        @test nv(g) == 0 && ne(g) == 0
        g = complete_bipartite_graph(5, 0)
        @test nv(g) == 5 && ne(g) == 0
        g = complete_bipartite_graph(0, 5)
        @test nv(g) == 5 && ne(g) == 0
        g = @inferred complete_bipartite_graph(Int8(100), Int8(27))
        @test nv(g) == 127 && ne(g) == 100 * 27
        @test eltype(g) == Int8
        g = complete_bipartite_graph(Int8(127), Int8(0))
        @test nv(g) == 127 && ne(g) == 0
        g = complete_bipartite_graph(Int8(0), Int8(127))
        @test nv(g) == 127 && ne(g) == 0
    end

    function iscompletemultipartite(g, partitions)
        sum(partitions) != nv(g) && return false
        n = nv(g)

        edges = 0
        for p in partitions
            edges += p * (Int(n) - p)
        end
        edges = div(edges, 2)

        edges != ne(g) && return false

        cur = 1
        for p in partitions
            currange = cur:(cur + p - 1)
            lowerrange = 1:(cur - 1)
            upperrange = (cur + p):n
            for u in currange
                for v in currange # check that no vertices are connected to vertices in the same partition
                    has_edge(g, u, v) && return false
                end

                for v in lowerrange # check all lower partition vertices
                    !has_edge(g, u, v) && return false
                end

                for v in upperrange # check all higher partition vertices
                    !has_edge(g, u, v) && return false
                end
            end
            cur += p
        end
        return true
    end

    @testset "Multipartite Graphs" begin
        g = @inferred(complete_multipartite_graph([5, 8, 3]))
        @test nv(g) == 16 && ne(g) == 79
        @test isvalid_simplegraph(g)
        @test iscompletemultipartite(g, [5, 8, 3])
        # tests for extreme values
        g = complete_multipartite_graph([0, 0, 0])
        @test nv(g) == 0 && ne(g) == 0
        g = complete_multipartite_graph(Int[])
        @test nv(g) == 0 && ne(g) == 0
        g = complete_multipartite_graph([5, 0, 3])
        @test nv(g) == 8 && ne(g) == 15
        @test iscompletemultipartite(g, [5, 0, 3])
        g = complete_multipartite_graph(Int8[100, 25, 2])
        @test nv(g) == 127 && ne(g) == 2750
        @test eltype(g) == Int8
        @test iscompletemultipartite(g, [100, 25, 2])
        g = complete_multipartite_graph([0, 10, 0, 2, 0, 3, 0, 0, 6, 0])
        @test nv(g) == 21 && ne(g) == 146
        @test iscompletemultipartite(g, [0, 10, 0, 2, 0, 3, 0, 0, 6, 0])
        g = complete_multipartite_graph([5, 3, -1])
        @test nv(g) == 0 && ne(g) == 0
        g = complete_multipartite_graph([-5, 0, -11])
        @test nv(g) == 0 && ne(g) == 0
        g = complete_multipartite_graph([5, 3])
        h = complete_multipartite_graph([5, 0, 3])
        j = complete_multipartite_graph([0, 5, 0, 3, 0, 0])
        @test g == h == j
        @test_throws InexactError complete_multipartite_graph(Int8[100, 20, 20])
    end

    function retrievepartitions(n, r)
        partitions = partitions = Vector{Int}(undef, r)
        c = cld(n, r)
        f = fld(n, r)
        for i in 1:(n % r)
            partitions[i] = c
        end
        for i in ((n % r) + 1):r
            partitions[i] = f
        end
        return partitions
    end

    @testset "Turan Graphs" begin
        g = @inferred(turan_graph(13, 4))
        @test nv(g) == 13 && ne(g) == 63
        @test isvalid_simplegraph(g)
        @test iscompletemultipartite(g, retrievepartitions(13, 4))
        # testing smaller int types
        g = turan_graph(Int8(11), Int8(6))
        @test nv(g) == 11 && ne(g) == 50
        @test iscompletemultipartite(g, retrievepartitions(11, 6))
        g = turan_graph(Int16(35), Int16(17))
        @test nv(g) == 35 && ne(g) == 576
        @test iscompletemultipartite(g, retrievepartitions(35, 17))
        # tests for extreme values
        g = turan_graph(15, 15)
        @test nv(g) == 15 && ne(g) == 105
        @test iscompletemultipartite(g, retrievepartitions(15, 15))
        g = turan_graph(10, 1)
        @test nv(g) == 10 && ne(g) == 0
        @test iscompletemultipartite(g, retrievepartitions(10, 1))
        @test_throws DomainError turan_graph(3, 0)
        @test_throws DomainError turan_graph(0, 4)
        @test_throws DomainError turan_graph(3, 4)
        @test_throws DomainError turan_graph(-1, 5)
        @test_throws DomainError turan_graph(3, -6)
    end

    @testset "Star Graphs" begin
        g = @inferred(star_graph(5))
        @test nv(g) == 5 && ne(g) == 4
        @test isvalid_simplegraph(g)
        # tests for extreme values
        g = star_graph(0)
        @test nv(g) == 0 && ne(g) == 0
        g = star_graph(1)
        @test nv(g) == 1 && ne(g) == 0
        g = star_graph(2)
        @test nv(g) == 2 && ne(g) == 1
        g = @inferred star_graph(Int8(127))
        @test nv(g) == 127 && ne(g) == 127 - 1
        @test eltype(g) == Int8
    end

    @testset "Star DiGraphs" begin
        g = @inferred(star_digraph(5))
        @test nv(g) == 5 && ne(g) == 4
        @test isvalid_simplegraph(g)
        # tests for extreme values
        g = star_digraph(0)
        @test nv(g) == 0 && ne(g) == 0
        g = star_digraph(1)
        @test nv(g) == 1 && ne(g) == 0
        g = star_digraph(2)
        @test nv(g) == 2 && ne(g) == 1
        @test first(edges(g)) == Edge(1, 2) # edges should point outwards from vertex 1
        g = @inferred star_digraph(Int8(127))
        @test nv(g) == 127 && ne(g) == 127 - 1
        @test eltype(g) == Int8
    end

    @testset "Path DiGraphs" begin
        g = @inferred(path_digraph(5))
        @test nv(g) == 5 && ne(g) == 4
        @test isvalid_simplegraph(g)
        # tests for extreme values
        g = path_digraph(0)
        @test nv(g) == 0 && ne(g) == 0
        g = path_digraph(1)
        @test nv(g) == 1 && ne(g) == 0
        g = @inferred path_digraph(Int8(127))
        @test nv(g) == 127 && ne(g) == 126
        @test eltype(g) == Int8
    end

    @testset "Path Graphs" begin
        g = @inferred(path_graph(5))
        @test nv(g) == 5 && ne(g) == 4
        @test isvalid_simplegraph(g)
        # tests for extreme values
        g = path_graph(0)
        @test nv(g) == 0 && ne(g) == 0
        g = path_graph(1)
        @test nv(g) == 1 && ne(g) == 0
        g = @inferred path_graph(Int8(127))
        @test nv(g) == 127 && ne(g) == 126
        @test eltype(g) == Int8
    end

    @testset "Cycle DiGraphs" begin
        g = @inferred(cycle_digraph(5))
        @test nv(g) == 5 && ne(g) == 5
        @test isvalid_simplegraph(g)
        # tests for extreme values
        g = cycle_digraph(0)
        @test nv(g) == 0 && ne(g) == 0
        g = cycle_digraph(1)
        @test nv(g) == 1 && ne(g) == 0
        g = cycle_digraph(2)
        @test nv(g) == 2 && ne(g) == 2
        g = @inferred cycle_digraph(Int8(127))
        @test nv(g) == 127 && ne(g) == 127
        @test eltype(g) == Int8
    end

    @testset "Cycle Graphs" begin
        g = @inferred(cycle_graph(5))
        @test nv(g) == 5 && ne(g) == 5
        @test isvalid_simplegraph(g)
        # tests for extreme values
        g = cycle_graph(0)
        @test nv(g) == 0 && ne(g) == 0
        g = cycle_graph(1)
        @test nv(g) == 1 && ne(g) == 0
        g = cycle_graph(2)
        @test nv(g) == 2 && ne(g) == 1
        g = @inferred cycle_graph(Int8(127))
        @test nv(g) == 127 && ne(g) == 127
        @test eltype(g) == Int8
    end

    @testset "Wheel DiGraphs" begin
        g = @inferred(wheel_digraph(5))
        @test nv(g) == 5 && ne(g) == 8
        @test isvalid_simplegraph(g)
        # tests for extreme values
        g = wheel_digraph(0)
        @test nv(g) == 0 && ne(g) == 0
        g = wheel_digraph(1)
        @test nv(g) == 1 && ne(g) == 0
        g = wheel_digraph(2)
        @test nv(g) == 2 && ne(g) == 1
        g = wheel_digraph(3)
        @test nv(g) == 3 && ne(g) == 4
        g = @inferred wheel_digraph(Int8(127))
        @test nv(g) == 127 && ne(g) == 2 * 126
        @test eltype(g) == Int8
    end

    @testset "Wheel Graphs" begin
        g = @inferred(wheel_graph(5))
        @test nv(g) == 5 && ne(g) == 8
        @test isvalid_simplegraph(g)
        # tests for extreme values
        g = wheel_graph(0)
        @test nv(g) == 0 && ne(g) == 0
        g = wheel_graph(1)
        @test nv(g) == 1 && ne(g) == 0
        g = wheel_graph(2)
        @test nv(g) == 2 && ne(g) == 1
        g = wheel_graph(3)
        @test nv(g) == 3 && ne(g) == 3
        g = @inferred wheel_graph(Int8(127))
        @test nv(g) == 127 && ne(g) == 2 * 126
        @test eltype(g) == Int8
    end

    @testset "grids" begin
        g = @inferred(grid([3, 3, 4]))
        @test nv(g) == 3 * 3 * 4
        @test ne(g) == 75
        @test Δ(g) == 6
        @test δ(g) == 3
        @test isvalid_simplegraph(g)

        g2 = @inferred(grid((3, 3, 4)))
        @test g2 == g

        g = @inferred(grid([3, 3, 4], periodic=true))
        @test nv(g) == 3 * 3 * 4
        @test ne(g) == 108
        @test Δ(g) == 6
        @test δ(g) == 6
        @test isvalid_simplegraph(g)

        g2 = @inferred(grid((3, 3, 4), periodic=true))
        @test g2 == g
    end

    @testset "Clique Graphs" begin
        g = @inferred(clique_graph(3, 5))
        @test nv(g) == 15 && ne(g) == 20
        @test g[1:3] == complete_graph(3)
        @test isvalid_simplegraph(g)
    end

    @testset "Binary Trees" begin
        g = @inferred(crosspath(3, binary_tree(2)))
        # f = Vector{Vector{Int}}[[2 3 4];
        # [1 5];
        # [1 6];
        # [1 5 6 7];
        # [2 4 8];
        # [3 4 9];
        # [4 8 9];
        # [5 7];
        # [6 7]
        # ]
        I = [1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 9, 9]
        J = [2, 3, 4, 1, 5, 1, 6, 1, 5, 6, 7, 2, 4, 8, 3, 4, 9, 4, 8, 9, 5, 7, 6, 7]
        V = ones(Int, length(I))
        Adj = sparse(I, J, V)
        @test Adj == sparse(g)
        @test isvalid_simplegraph(g)
        @test_throws DomainError binary_tree(Int8(8))

        g = @inferred(double_binary_tree(3))
        # [[3, 2, 8]
        # [4, 1, 5]
        # [1, 6, 7]
        # [2]
        # [2]
        # [3]
        # [3]
        # [10, 9, 1]
        # [11, 8, 12]
        # [8, 13, 14]
        # [9]
        # [9]
        # [10]
        # [10]]
        I = [
            1,
            1,
            1,
            2,
            2,
            2,
            3,
            3,
            3,
            4,
            5,
            6,
            7,
            8,
            8,
            8,
            9,
            9,
            9,
            10,
            10,
            10,
            11,
            12,
            13,
            14,
        ]
        J = [
            3,
            2,
            8,
            4,
            1,
            5,
            1,
            6,
            7,
            2,
            2,
            3,
            3,
            10,
            9,
            1,
            11,
            8,
            12,
            8,
            13,
            14,
            9,
            9,
            10,
            10,
        ]
        V = ones(Int, length(I))
        Adj = sparse(I, J, V)
        @test Adj == sparse(g)
        @test isvalid_simplegraph(g)
    end

    @testset "Regular Trees" begin
        g = @inferred(regular_tree(3, 3))
        I = [1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
        J = [2, 3, 4, 1, 5, 6, 7, 8, 1, 9, 10, 1, 11, 12, 13, 2, 2, 2, 3, 3, 3, 4, 4, 4]
        V = ones(Int, length(I))
        Adj = sparse(I, J, V)
        @test Adj == sparse(g)
        @test isvalid_simplegraph(g)
        @test_throws DomainError regular_tree(Int8(4), Int8(4))
        # test that setting z = 2 recovers a binary tree
        @test all(regular_tree(k, 2) == binary_tree(k) for k in 0:10)
    end

    @testset "Roach Graphs" begin
        rg3 = @inferred(roach_graph(3))
        # [3]
        # [4]
        # [1, 5]
        # [2, 6]
        # [3, 7]
        # [4, 8]
        # [9, 8, 5]
        # [10, 7, 6]
        # [11, 10, 7]
        # [8, 9, 12]
        # [9, 12]
        # [10, 11]
        I = [
            1,
            2,
            3,
            3,
            4,
            4,
            5,
            5,
            6,
            6,
            7,
            7,
            7,
            8,
            8,
            8,
            9,
            9,
            9,
            10,
            10,
            10,
            11,
            11,
            12,
            12,
        ]
        J = [
            3,
            4,
            1,
            5,
            2,
            6,
            3,
            7,
            4,
            8,
            9,
            8,
            5,
            10,
            7,
            6,
            11,
            10,
            7,
            8,
            9,
            12,
            9,
            12,
            10,
            11,
        ]
        V = ones(Int, length(I))
        Adj = sparse(I, J, V)
        @test Adj == sparse(rg3)
        @test isvalid_simplegraph(rg3)
    end

    function isladdergraph(g)
        n = nv(g) ÷ 2
        !(degree(g, 1) == degree(g, n) == degree(g, n + 1) == degree(g, 2 * n) == 2) &&
            return false
        !(has_edge(g, 1, n + 1) && has_edge(g, n, 2 * n)) && return false
        !(
            has_edge(g, 1, 2) &&
            has_edge(g, n, n - 1) &&
            has_edge(g, n + 1, n + 2) &&
            has_edge(g, 2 * n, 2 * n - 1)
        ) && return false
        for i in 2:(n - 1)
            !(degree(g, i) == 3 && degree(g, n + i) == 3) && return false
            !(has_edge(g, i, i % n + 1) && has_edge(g, i, i + n)) && return false
            !(has_edge(g, n + i, n + (i % n + 1)) && has_edge(g, n + i, i)) && return false
        end
        return true
    end

    @testset "Ladder Graphs" begin
        g = @inferred(ladder_graph(5))
        @test nv(g) == 10 && ne(g) == 13
        @test isvalid_simplegraph(g)
        @test isladdergraph(g)
        # tests for extreme values
        g = ladder_graph(0)
        @test nv(g) == 0 && ne(g) == 0
        g = ladder_graph(1)
        @test nv(g) == 2 && ne(g) == 1
        g = @inferred ladder_graph(-1)
        @test nv(g) == 0 && ne(g) == 0
        g = ladder_graph(Int8(63))
        @test nv(g) == 126 && ne(g) == 187
        @test eltype(g) == Int8
        @test isladdergraph(g)
        # tests for errors
        @test_throws InexactError ladder_graph(Int8(64))
    end

    function iscircularladdergraph(g)
        n = nv(g) ÷ 2
        for i in 1:n
            !(degree(g, i) == 3 && degree(g, n + i) == 3) && return false
            !(has_edge(g, i, i % n + 1) && has_edge(g, i, i + n)) && return false
            !(has_edge(g, n + i, n + (i % n + 1)) && has_edge(g, n + i, i)) && return false
        end
        return true
    end

    @testset "Circular Ladder Graphs" begin
        g = @inferred(circular_ladder_graph(5))
        @test nv(g) == 10 && ne(g) == 15
        @test isvalid_simplegraph(g)
        @test iscircularladdergraph(g)
        # tests for extreme values
        g = circular_ladder_graph(3)
        @test nv(g) == 6 && ne(g) == 9
        @test iscircularladdergraph(g)
        g = circular_ladder_graph(Int8(63))
        @test nv(g) == 126 && ne(g) == 189
        @test eltype(g) == Int8
        @test iscircularladdergraph(g)
        # tests for errors
        @test_throws InexactError circular_ladder_graph(Int8(64))
        @test_throws DomainError circular_ladder_graph(-1)
        @test_throws DomainError circular_ladder_graph(0)
        @test_throws DomainError circular_ladder_graph(1)
        @test_throws DomainError circular_ladder_graph(2)
    end

    # checking that the nodes are organized correctly
    # see the docstring implementation notes for lollipop_graph
    function isbarbellgraph(g, n1, n2)
        nv(g) != n1 + n2 && return false
        ne(g) != n1 * (n1 - 1) ÷ 2 + n2 * (n2 - 1) ÷ 2 + 1 && return false
        for i in 1:n1
            for j in (i + 1):n1
                !has_edge(g, i, j) && return false
            end
        end

        for i in (n1 .+ 1):n2
            for j in (i + 1):(n1 + n2)
                !has_edge(g, i, j) && return false
            end
        end

        !has_edge(g, n1, n1 + 1) && return false
        return true
    end

    @testset "Barbell Graphs" begin
        g = @inferred(barbell_graph(5, 6))
        @test nv(g) == 11 && ne(g) == 26
        @test isvalid_simplegraph(g)
        @test isbarbellgraph(g, 5, 6)
        g = barbell_graph(Int8(5), Int8(6))
        @test nv(g) == 11 && ne(g) == 26
        @test isvalid_simplegraph(g)
        @test isbarbellgraph(g, 5, 6)
        # extreme values
        g = barbell_graph(1, 5)
        @test nv(g) == 6 && ne(g) == 11
        @test isbarbellgraph(g, 1, 5)
        g = barbell_graph(5, 1)
        @test nv(g) == 6 && ne(g) == 11
        @test isbarbellgraph(g, 5, 1)
        g = barbell_graph(1, 1)
        @test nv(g) == 2 && ne(g) == 1
        @test isbarbellgraph(g, 1, 1)
        @test_throws OverflowError barbell_graph(Int8(100), Int8(50))
        @test_throws DomainError barbell_graph(1, 0)
        @test_throws DomainError barbell_graph(0, 1)
        @test_throws DomainError barbell_graph(-1, -1)
    end

    # checking that the nodes are organized correctly
    # see the docstring implementation notes for lollipop_graph
    function islollipopgraph(g, n1, n2)
        nv(g) != n1 + n2 && return false
        ne(g) != n1 * (n1 - 1) ÷ 2 + n2 && return false
        for i in 1:n1
            for j in (i + 1):n1
                !has_edge(g, i, j) && return false
            end
        end

        for i in (n1 .+ 1):(n2 - 1)
            !has_edge(g, i, i + 1) && return false
        end

        !has_edge(g, n1, n1 + 1) && return false

        return true
    end

    @testset "Lollipop Graphs" begin
        g = @inferred(lollipop_graph(3, 5))
        @test nv(g) == 8 && ne(g) == 8
        @test isvalid_simplegraph(g)
        @test islollipopgraph(g, 3, 5)
        g = lollipop_graph(Int8(7), Int8(6))
        @test nv(g) == 13 && ne(g) == 27
        @test isvalid_simplegraph(g)
        @test islollipopgraph(g, 7, 6)
        # extreme values
        g = lollipop_graph(1, 3)
        @test nv(g) == 4 && ne(g) == 3
        @test islollipopgraph(g, 1, 3)
        g = lollipop_graph(3, 1)
        @test nv(g) == 4 && ne(g) == 4
        @test islollipopgraph(g, 3, 1)
        g = lollipop_graph(1, 1)
        @test nv(g) == 2 && ne(g) == 1
        @test islollipopgraph(g, 1, 1)
        @test_throws OverflowError lollipop_graph(Int8(100), Int8(50))
        @test_throws DomainError lollipop_graph(1, 0)
        @test_throws DomainError lollipop_graph(0, 1)
        @test_throws DomainError lollipop_graph(-1, -1)
    end
end