graph/tests/Data/GraphTests.elm at e14cf9ecb29af5a1508cda47428d65b006bf8b39 · guida-lang/graph · 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
141
142
143
144
module Data.GraphTests exposing (suite)

import Data.Graph as G
import Data.Graph.Internal as I
import Expect
import Test exposing (Test)
import Tree


suite : Test
suite =
    Test.describe "Data.Graph"
        [ Test.describe "vertices"
            [ Test.test "vertices (buildG (0,-1) []) == []" <|
                \_ ->
                    G.vertices (G.buildG ( 0, -1 ) [])
                        |> Expect.equal []
            , Test.test "G.vertices (buildG (0,2) [(0,1),(1,2)]) == [0,1,2]" <|
                \_ ->
                    G.vertices (G.buildG ( 0, 2 ) [ ( 0, 1 ), ( 1, 2 ) ])
                        |> Expect.equal [ 0, 1, 2 ]
            ]
        , Test.describe "edges"
            [ Test.test "edges (buildG (0,-1) []) == []" <|
                \_ ->
                    G.edges (G.buildG ( 0, -1 ) [])
                        |> Expect.equal []
            , Test.test "edges (buildG (0,2) [(0,1),(1,2)]) == [(0,1),(1,2)]" <|
                \_ ->
                    G.edges (G.buildG ( 0, 2 ) [ ( 0, 1 ), ( 1, 2 ) ])
                        |> Expect.equal [ ( 0, 1 ), ( 1, 2 ) ]
            ]
        , Test.describe "buildG"
            [ Test.test "buildG (0,-1) [] == array (0,-1) []" <|
                \_ ->
                    G.buildG ( 0, -1 ) []
                        |> Expect.equal (I.array ( 0, -1 ) [])
            , Test.test "buildG (0,2) [(0,1), (1,2)] == array (0,2) [(0,[1]),(1,[2]),(2,[])]" <|
                \_ ->
                    G.buildG ( 0, 2 ) [ ( 0, 1 ), ( 1, 2 ) ]
                        |> Expect.equal (I.array ( 0, 2 ) [ ( 0, [ 1 ] ), ( 1, [ 2 ] ), ( 2, [] ) ])
            , Test.test "buildG (0,2) [(0,1), (0,2), (1,2)] == array (0,2) [(0,[2,1]),(1,[2]),(2,[])]" <|
                \_ ->
                    G.buildG ( 0, 2 ) [ ( 0, 1 ), ( 0, 2 ), ( 1, 2 ) ]
                        |> Expect.equal (I.array ( 0, 2 ) [ ( 0, [ 2, 1 ] ), ( 1, [ 2 ] ), ( 2, [] ) ])
            ]
        , Test.describe "transposeG"
            [ Test.test "transposeG (buildG (0,2) [(0,1), (1,2)]) == array (0,2) [(0,[]),(1,[0]),(2,[1])]" <|
                \_ ->
                    G.transposeG (G.buildG ( 0, 2 ) [ ( 0, 1 ), ( 1, 2 ) ])
                        |> Expect.equal (I.array ( 0, 2 ) [ ( 0, [] ), ( 1, [ 0 ] ), ( 2, [ 1 ] ) ])
            ]
        , Test.describe "outdegree"
            [ Test.test "outdegree (buildG (0,-1) []) == array (0,-1) []" <|
                \_ ->
                    G.outdegree (G.buildG ( 0, -1 ) [])
                        |> Expect.equal (I.array ( 0, -1 ) [])
            , Test.test "outdegree (buildG (0,2) [(0,1), (1,2)]) == array (0,2) [(0,1),(1,1),(2,0)]" <|
                \_ ->
                    G.outdegree (G.buildG ( 0, 2 ) [ ( 0, 1 ), ( 1, 2 ) ])
                        |> Expect.equal (I.array ( 0, 2 ) [ ( 0, 1 ), ( 1, 1 ), ( 2, 0 ) ])
            ]
        , Test.describe "indegree"
            [ Test.test "indegree (buildG (0,-1) []) == array (0,-1) []" <|
                \_ ->
                    G.indegree (G.buildG ( 0, -1 ) [])
                        |> Expect.equal (I.array ( 0, -1 ) [])
            , Test.test "indegree (buildG (0,2) [(0,1), (1,2)]) == array (0,2) [(0,0),(1,1),(2,1)]" <|
                \_ ->
                    G.indegree (G.buildG ( 0, 2 ) [ ( 0, 1 ), ( 1, 2 ) ])
                        |> Expect.equal (I.array ( 0, 2 ) [ ( 0, 0 ), ( 1, 1 ), ( 2, 1 ) ])
            ]
        , Test.describe "graphFromEdges"
            [ Test.test "An empty graph" <|
                \_ ->
                    let
                        ( graph, _, _ ) =
                            G.graphFromEdges []
                    in
                    graph
                        |> Expect.equal (I.array ( 0, -1 ) [])
            , Test.test "A graph where the out-list references unspecified nodes ('c'), these are ignored." <|
                \_ ->
                    let
                        ( graph, _, _ ) =
                            G.graphFromEdges [ ( "a", 'a', [ 'b' ] ), ( "b", 'b', [ 'c' ] ) ]
                    in
                    graph
                        |> Expect.equal (I.array ( 0, 1 ) [ ( 0, [ 1 ] ), ( 1, [] ) ])
            , Test.test "A graph with 3 vertices: ('a') -> ('b') -> ('c')" <|
                \_ ->
                    let
                        ( graph, nodeFromVertex, vertexFromKey ) =
                            G.graphFromEdges [ ( "a", 'a', [ 'b' ] ), ( "b", 'b', [ 'c' ] ), ( "c", 'c', [] ) ]
                    in
                    ( graph, nodeFromVertex 0, vertexFromKey 'a' )
                        |> Expect.equal
                            ( I.array ( 0, 2 ) [ ( 0, [ 1 ] ), ( 1, [ 2 ] ), ( 2, [] ) ]
                            , Just ( "a", 'a', [ 'b' ] )
                            , Just 0
                            )
            , Test.test "Get the label for a given key" <|
                \_ ->
                    let
                        getNodePart : ( a, b, c ) -> a
                        getNodePart ( n, _, _ ) =
                            n

                        ( _, nodeFromVertex, vertexFromKey ) =
                            G.graphFromEdges [ ( "a", 'a', [ 'b' ] ), ( "b", 'b', [ 'c' ] ), ( "c", 'c', [] ) ]
                    in
                    Maybe.andThen (Maybe.map getNodePart << nodeFromVertex) (vertexFromKey 'a')
                        |> Expect.equal (Just "a")
            ]
        , Test.test "stronglyConnComp" <|
            \_ ->
                G.stronglyConnComp [ ( "a", 0, [ 1 ] ), ( "b", 1, [ 2, 3 ] ), ( "c", 2, [ 1 ] ), ( "d", 3, [ 3 ] ) ]
                    |> Expect.equal
                        [ G.CyclicSCC [ "d" ]
                        , G.CyclicSCC [ "b", "c" ]
                        , G.AcyclicSCC "a"
                        ]
        , Test.test "stronglyConnCompR" <|
            \_ ->
                G.stronglyConnCompR [ ( "a", 0, [ 1 ] ), ( "b", 1, [ 2, 3 ] ), ( "c", 2, [ 1 ] ), ( "d", 3, [ 3 ] ) ]
                    |> Expect.equal
                        [ G.CyclicSCC [ ( "d", 3, [ 3 ] ) ]
                        , G.CyclicSCC [ ( "b", 1, [ 2, 3 ] ), ( "c", 2, [ 1 ] ) ]
                        , G.AcyclicSCC ( "a", 0, [ 1 ] )
                        ]
        , Test.test "scc" <|
            \_ ->
                G.scc (G.buildG ( 0, 3 ) [ ( 3, 1 ), ( 1, 2 ), ( 2, 0 ), ( 0, 1 ) ])
                    |> Expect.equal
                        [ Tree.tree 0 [ Tree.tree 1 [ Tree.tree 2 [] ] ]
                        , Tree.tree 3 []
                        ]
        , Test.test "dfs (RangeError: Maximum call stack size exceeded)" <|
            \_ ->
                List.repeat 2000 ()
                    |> List.indexedMap (\i _ -> i)
                    |> G.dfs (G.buildG ( 0, 0 ) [])
                    |> always Expect.pass
        ]