This repository has been archived by the owner on Aug 17, 2023. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
dag_test.go
341 lines (288 loc) · 11.2 KB
/
dag_test.go
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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
package daggo_test
import (
"testing"
daggo "github.com/open-trust/dag-go"
"github.com/stretchr/testify/assert"
)
type V string
func (v V) ID() string {
return string(v)
}
func (v V) Type() string {
return "test"
}
func TestDAG(t *testing.T) {
t.Run("should work", func(t *testing.T) {
assert := assert.New(t)
d := daggo.New()
assert.Equal(0, d.Len())
assert.True(d.GetVertice("test", "a") == nil)
assert.Equal(daggo.Vertices{}, d.Vertices(""))
assert.Equal(daggo.Vertices{}, d.StartingVertices())
assert.Equal(daggo.Vertices{}, d.EndingVertices())
assert.Equal(daggo.Vertices{}, d.ToVertices(nil))
assert.Equal(daggo.Vertices{}, d.FromVertices(nil))
assert.NotNil(d.AddEdge(nil, nil, 0))
assert.NotNil(d.AddEdge(V("a"), nil, 0))
assert.NotNil(d.AddEdge(V("a"), V("a"), 0))
assert.Nil(d.AddEdge(V("a"), V("b"), 0))
assert.Equal(2, d.Len())
assert.Equal("a", d.GetVertice("test", "a").ID())
assert.Equal("b", d.GetVertice("test", "b").ID())
assert.Equal(nil, d.GetVertice("test", "c"))
assert.Equal(daggo.Vertices{V("a")}, d.StartingVertices())
assert.Equal(daggo.Vertices{V("b")}, d.EndingVertices())
assert.Equal(daggo.Vertices{V("b")}, d.ToVertices(V("a")))
assert.Equal(daggo.Vertices{V("a")}, d.FromVertices(V("b")))
assert.Equal([]string{"a", "b"}, d.Vertices("").Sort().IDs())
assert.Equal([]string{"a", "b"}, d.Vertices("test").Sort().IDs())
assert.Equal([]string{}, d.Vertices("test1").Sort().IDs())
assert.Equal([]string{"b"}, d.Vertices("").Filter(func(v daggo.Vertice) bool {
return v.ID() == "b"
}).IDs())
assert.Nil(d.AddEdge(V("a"), V("c"), 0))
assert.Nil(d.AddEdge(V("x"), V("b"), 0))
assert.Equal(daggo.Vertices{V("a"), V("x")}, d.StartingVertices().Sort())
assert.Equal(daggo.Vertices{V("b"), V("c")}, d.EndingVertices().Sort())
assert.Equal(daggo.Vertices{V("b"), V("c")}, d.ToVertices(V("a")).Sort())
assert.Equal(daggo.Vertices{V("a"), V("x")}, d.FromVertices(V("b")).Sort())
assert.Nil(d.AddEdge(V("a"), V("x"), 0))
assert.NotNil(d.AddEdge(V("b"), V("a"), 0))
assert.Equal(daggo.Vertices{V("a")}, d.StartingVertices().Sort())
assert.Equal(daggo.Vertices{V("b"), V("c")}, d.EndingVertices().Sort())
d.RemoveEdge(V("a"), V("b"))
assert.NotNil(d.AddEdge(V("b"), V("a"), 0))
assert.Equal(daggo.Vertices{V("a")}, d.StartingVertices().Sort())
assert.Equal(daggo.Vertices{V("b"), V("c")}, d.EndingVertices().Sort())
assert.Equal(daggo.Vertices{V("c"), V("x")}, d.ToVertices(V("a")).Sort())
assert.Equal(daggo.Vertices{V("x")}, d.FromVertices(V("b")).Sort())
})
t.Run("DAG.ReachDAG", func(t *testing.T) {
assert := assert.New(t)
d := daggo.New()
assert.Nil(d.AddEdge(V("a"), V("b"), 0))
assert.Nil(d.AddEdge(V("a"), V("c"), 0))
assert.Nil(d.AddEdge(V("a"), V("d"), 0))
assert.Nil(d.AddEdge(V("a"), V("e"), 0))
assert.Nil(d.AddEdge(V("b"), V("d"), 0))
assert.Nil(d.AddEdge(V("c"), V("d"), 0))
assert.Nil(d.AddEdge(V("c"), V("e"), 0))
assert.Nil(d.AddEdge(V("d"), V("e"), 0))
assert.Nil(d.AddEdge(V("x"), V("b"), 0))
assert.Nil(d.AddEdge(V("d"), V("y"), 0))
x := daggo.New()
assert.Nil(x.AddEdge(V("a"), V("b"), 0))
assert.Nil(x.AddEdge(V("a"), V("c"), 0))
assert.Nil(x.AddEdge(V("a"), V("d"), 0))
assert.Nil(x.AddEdge(V("a"), V("e"), 0))
assert.Nil(x.AddEdge(V("b"), V("d"), 0))
assert.Nil(x.AddEdge(V("c"), V("d"), 0))
assert.Nil(x.AddEdge(V("c"), V("e"), 0))
assert.Nil(x.AddEdge(V("d"), V("e"), 0))
assert.Nil(x.AddEdge(V("d"), V("y"), 0))
assert.True(x.Equal(d.ReachDAG(V("a"))))
assert.Nil(x.AddEdge(V("a"), V("b"), 1))
assert.False(x.Equal(d.ReachDAG(V("a"))))
})
t.Run("DAG.CloseDAG", func(t *testing.T) {
assert := assert.New(t)
d := daggo.New()
assert.Nil(d.AddEdge(V("a"), V("b"), 0))
assert.Nil(d.AddEdge(V("a"), V("c"), 0))
assert.Nil(d.AddEdge(V("a"), V("d"), 0))
assert.Nil(d.AddEdge(V("a"), V("e"), 0))
assert.Nil(d.AddEdge(V("b"), V("d"), 0))
assert.Nil(d.AddEdge(V("c"), V("d"), 0))
assert.Nil(d.AddEdge(V("c"), V("e"), 0))
assert.Nil(d.AddEdge(V("d"), V("e"), 0))
assert.Nil(d.AddEdge(V("x"), V("b"), 0))
assert.Nil(d.AddEdge(V("d"), V("y"), 0))
x := daggo.New()
assert.Nil(x.AddEdge(V("a"), V("b"), 0))
assert.Nil(x.AddEdge(V("a"), V("c"), 0))
assert.Nil(x.AddEdge(V("a"), V("d"), 0))
assert.Nil(x.AddEdge(V("a"), V("e"), 0))
assert.Nil(x.AddEdge(V("b"), V("d"), 0))
assert.Nil(x.AddEdge(V("c"), V("d"), 0))
assert.Nil(x.AddEdge(V("c"), V("e"), 0))
assert.Nil(x.AddEdge(V("d"), V("e"), 0))
assert.True(x.Equal(d.CloseDAG(V("a"), V("e"))))
assert.Nil(d.AddEdge(V("z"), V("a"), 0))
assert.True(x.Equal(d.CloseDAG(V("a"), V("e"))))
x = daggo.New()
assert.Nil(x.AddEdge(V("a"), V("b"), 0))
assert.Nil(x.AddEdge(V("a"), V("c"), 0))
assert.Nil(x.AddEdge(V("a"), V("d"), 0))
assert.Nil(x.AddEdge(V("b"), V("d"), 0))
assert.Nil(x.AddEdge(V("c"), V("d"), 0))
assert.True(x.Equal(d.CloseDAG(V("a"), V("d"))))
})
t.Run("DAG.ReduceDAG", func(t *testing.T) {
assert := assert.New(t)
d := daggo.New()
assert.Nil(d.AddEdge(V("a"), V("b"), 0))
assert.Nil(d.AddEdge(V("a"), V("c"), 0))
assert.Nil(d.AddEdge(V("a"), V("d"), 0))
assert.Nil(d.AddEdge(V("a"), V("e"), 0))
assert.Nil(d.AddEdge(V("b"), V("d"), 0))
assert.Nil(d.AddEdge(V("c"), V("d"), 0))
assert.Nil(d.AddEdge(V("c"), V("e"), 0))
assert.Nil(d.AddEdge(V("d"), V("e"), 0))
assert.Nil(d.AddEdge(V("x"), V("b"), 0))
assert.Nil(d.AddEdge(V("d"), V("y"), 0))
x := daggo.New()
assert.Nil(x.AddEdge(V("a"), V("b"), 0))
assert.Nil(x.AddEdge(V("a"), V("c"), 0))
assert.Nil(x.AddEdge(V("b"), V("d"), 0))
assert.Nil(x.AddEdge(V("c"), V("d"), 0))
assert.Nil(x.AddEdge(V("d"), V("e"), 0))
assert.True(x.Equal(d.ReduceDAG(V("a"), V("e"))))
assert.Nil(d.AddEdge(V("z"), V("a"), 0))
assert.True(x.Equal(d.ReduceDAG(V("a"), V("e"))))
x = daggo.New()
assert.Nil(x.AddEdge(V("a"), V("b"), 0))
assert.Nil(x.AddEdge(V("a"), V("c"), 0))
assert.Nil(x.AddEdge(V("b"), V("d"), 0))
assert.Nil(x.AddEdge(V("c"), V("d"), 0))
assert.True(x.Equal(d.ReduceDAG(V("a"), V("d"))))
})
t.Run("DAG.Reverse", func(t *testing.T) {
assert := assert.New(t)
d := daggo.New()
assert.Nil(d.AddEdge(V("a"), V("b"), 0))
assert.Nil(d.AddEdge(V("a"), V("c"), 0))
assert.Nil(d.AddEdge(V("a"), V("d"), 0))
assert.Nil(d.AddEdge(V("a"), V("e"), 0))
assert.Nil(d.AddEdge(V("b"), V("d"), 0))
assert.Nil(d.AddEdge(V("c"), V("d"), 0))
assert.Nil(d.AddEdge(V("c"), V("e"), 0))
assert.Nil(d.AddEdge(V("d"), V("e"), 0))
assert.Nil(d.AddEdge(V("x"), V("b"), 0))
assert.Nil(d.AddEdge(V("d"), V("y"), 0))
x := daggo.New()
assert.Nil(x.AddEdge(V("b"), V("a"), 0))
assert.Nil(x.AddEdge(V("c"), V("a"), 0))
assert.Nil(x.AddEdge(V("d"), V("a"), 0))
assert.Nil(x.AddEdge(V("e"), V("a"), 0))
assert.Nil(x.AddEdge(V("d"), V("b"), 0))
assert.Nil(x.AddEdge(V("d"), V("c"), 0))
assert.Nil(x.AddEdge(V("e"), V("c"), 0))
assert.Nil(x.AddEdge(V("e"), V("d"), 0))
assert.Nil(x.AddEdge(V("b"), V("x"), 0))
assert.Nil(x.AddEdge(V("y"), V("d"), 0))
assert.True(x.Equal(d.Reverse()))
})
t.Run("DAG.Shortest & Longest", func(t *testing.T) {
assert := assert.New(t)
d := daggo.New()
assert.Nil(d.AddEdge(V("a"), V("x"), 10))
assert.Nil(d.AddEdge(V("x"), V("b"), 10))
assert.Nil(d.AddEdge(V("a"), V("c"), 10))
assert.Nil(d.AddEdge(V("a"), V("d"), 10))
assert.Nil(d.AddEdge(V("a"), V("e"), 10))
assert.Nil(d.AddEdge(V("b"), V("d"), 10))
assert.Nil(d.AddEdge(V("c"), V("d"), 10))
assert.Nil(d.AddEdge(V("c"), V("e"), 10))
assert.Nil(d.AddEdge(V("d"), V("e"), 10))
assert.Nil(d.AddEdge(V("d"), V("y"), 10))
assert.Equal(daggo.Vertices{V("a"), V("e")}, d.Shortest(V("a"), V("e"), false))
assert.Equal(daggo.Vertices{V("a"), V("x"), V("b"), V("d"), V("e")}, d.Longest(V("a"), V("e"), false))
assert.Nil(d.AddEdge(V("a"), V("c"), 3))
assert.Nil(d.AddEdge(V("c"), V("e"), 3))
assert.Equal(daggo.Vertices{V("a"), V("c"), V("e")}, d.Shortest(V("a"), V("e"), true))
assert.Nil(d.AddEdge(V("c"), V("d"), 100))
assert.Equal(daggo.Vertices{V("a"), V("c"), V("d"), V("e")}, d.Longest(V("a"), V("e"), true))
})
t.Run("DAG.Iterate", func(t *testing.T) {
assert := assert.New(t)
d := daggo.New()
assert.Nil(d.AddEdge(V("a"), V("b"), 1))
assert.Nil(d.AddEdge(V("a"), V("c"), 1))
assert.Nil(d.AddEdge(V("a"), V("d"), 1))
assert.Nil(d.AddEdge(V("a"), V("e"), 1))
assert.Nil(d.AddEdge(V("b"), V("d"), 1))
assert.Nil(d.AddEdge(V("c"), V("d"), 1))
assert.Nil(d.AddEdge(V("c"), V("e"), 1))
assert.Nil(d.AddEdge(V("d"), V("e"), 1))
assert.Nil(d.AddEdge(V("x"), V("b"), 1))
assert.Nil(d.AddEdge(V("d"), V("y"), 1))
ws := 0
attrs := d.CloseDAG(V("a"), V("e")).
Iterate(V("a"), nil, func(v daggo.Vertice, w int, acc []interface{}) []interface{} {
ws += w
return append(acc, interface{}(v.ID()))
})
assert.Equal(10, ws)
assert.Equal([]interface{}{"a", "b", "d", "e", "a", "c", "d", "e", "a", "c", "e", "a", "d", "e", "a", "e"}, attrs)
})
t.Run("DAG.Merge", func(t *testing.T) {
assert := assert.New(t)
d := daggo.New()
assert.Nil(d.AddEdge(V("a"), V("b"), 1))
assert.Nil(d.AddEdge(V("a"), V("c"), 1))
assert.Nil(d.AddEdge(V("a"), V("d"), 1))
assert.Nil(d.AddEdge(V("a"), V("e"), 1))
assert.Nil(d.AddEdge(V("b"), V("d"), 1))
a := daggo.New()
assert.Nil(a.AddEdge(V("c"), V("d"), 1))
assert.Nil(a.AddEdge(V("c"), V("e"), 1))
assert.Nil(a.AddEdge(V("d"), V("e"), 1))
assert.Nil(a.AddEdge(V("x"), V("b"), 1))
assert.Nil(a.AddEdge(V("d"), V("y"), 1))
err := d.Merge(a)
assert.Nil(err)
ws := 0
attrs := d.CloseDAG(V("a"), V("e")).
Iterate(V("a"), nil, func(v daggo.Vertice, w int, acc []interface{}) []interface{} {
ws += w
return append(acc, interface{}(v.ID()))
})
assert.Equal(10, ws)
assert.Equal([]interface{}{"a", "b", "d", "e", "a", "c", "d", "e", "a", "c", "e", "a", "d", "e", "a", "e"}, attrs)
assert.Nil(a.AddEdge(V("e"), V("a"), 1))
err = d.Merge(a)
assert.NotNil(err)
})
t.Run("DAG.Clone", func(t *testing.T) {
assert := assert.New(t)
d := daggo.New()
assert.Nil(d.AddEdge(V("a"), V("b"), 1))
assert.Nil(d.AddEdge(V("a"), V("c"), 1))
assert.Nil(d.AddEdge(V("a"), V("d"), 1))
assert.Nil(d.AddEdge(V("a"), V("e"), 1))
assert.Nil(d.AddEdge(V("b"), V("d"), 1))
assert.Nil(d.AddEdge(V("c"), V("d"), 1))
assert.Nil(d.AddEdge(V("c"), V("e"), 1))
assert.Nil(d.AddEdge(V("d"), V("e"), 1))
assert.Nil(d.AddEdge(V("x"), V("b"), 1))
assert.Nil(d.AddEdge(V("d"), V("y"), 1))
a := d.Clone()
assert.True(d.Equal(a))
assert.Nil(a.AddEdge(V("d"), V("n"), 1))
assert.False(d.Equal(a))
})
t.Run("DAG.JSON", func(t *testing.T) {
assert := assert.New(t)
d := daggo.New()
assert.Nil(d.AddEdge(V("a"), V("b"), 1))
assert.Nil(d.AddEdge(V("a"), V("c"), 1))
assert.Nil(d.AddEdge(V("a"), V("d"), 1))
assert.Nil(d.AddEdge(V("a"), V("e"), 1))
assert.Nil(d.AddEdge(V("b"), V("d"), 1))
assert.Nil(d.AddEdge(V("c"), V("d"), 1))
assert.Nil(d.AddEdge(V("c"), V("e"), 1))
assert.Nil(d.AddEdge(V("d"), V("e"), 1))
assert.Nil(d.AddEdge(V("x"), V("b"), 1))
assert.Nil(d.AddEdge(V("d"), V("y"), 1))
j := d.JSON()
a := daggo.FromJSON(j)
assert.True(d.Equal(a))
j.Edges["none"] = make(map[string]int)
assert.Nil(daggo.FromJSON(j))
j = d.JSON()
v, ok := j.Edges["test:y"]
assert.True(ok)
v["test:a"] = 0
assert.Nil(daggo.FromJSON(j))
})
}