forked from hyoo-ru/mam_mol
-
Notifications
You must be signed in to change notification settings - Fork 0
/
graph.test.ts
113 lines (77 loc) · 3.08 KB
/
graph.test.ts
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
namespace $ {
$mol_test( {
'ordered links'() {
var graph = new $mol_graph< string , 'E' >()
graph.link( 'A' , 'B' , 'E' )
$mol_assert_equal( graph.edge_out( 'A' , 'B' ) , 'E' )
$mol_assert_equal( graph.edge_in( 'B' , 'A' ) , 'E' )
$mol_assert_equal( graph.edge_out( 'B' , 'A' ) , null )
$mol_assert_equal( graph.edge_in( 'A' , 'B' ) , null )
},
'nodes without edges'() {
var graph = new $mol_graph< string , {} >()
graph.nodes.add( 'A' )
graph.nodes.add( 'B' )
graph.nodes.add( 'C' )
graph.nodes.add( 'D' )
graph.acyclic( edge => 0 )
$mol_assert_equal( [ ... graph.sorted ].join( '' ) , 'ABCD' )
} ,
'partial ordering'() {
var graph = new $mol_graph< string , { priority : number } >()
graph.nodes.add( 'A' )
graph.nodes.add( 'B' )
graph.nodes.add( 'C' )
graph.nodes.add( 'D' )
graph.link( 'B' , 'C' , { priority : 0 } )
graph.acyclic( edge => edge.priority )
$mol_assert_equal( [ ... graph.sorted ].join( '' ) , 'ACBD' )
} ,
'sorting must cut cycles at low priority edges A'() {
var graph = new $mol_graph< string , { priority : number } >()
graph.link( 'A' , 'B' , { priority : 0 } )
graph.link( 'B' , 'C' , { priority : -2 } )
graph.link( 'C' , 'D' , { priority : 0 } )
graph.link( 'D' , 'A' , { priority : -1 } )
graph.acyclic( edge => edge.priority )
$mol_assert_equal( [ ... graph.sorted ].join( '' ) , 'BADC' )
} ,
'sorting must cut cycles at low priority edges B'() {
var graph = new $mol_graph< string , { priority : number } >()
graph.link( 'B' , 'C' , { priority : -2 } )
graph.link( 'C' , 'D' , { priority : 0 } )
graph.link( 'D' , 'A' , { priority : -1 } )
graph.link( 'A' , 'B' , { priority : 0 } )
graph.acyclic( edge => edge.priority )
$mol_assert_equal( [ ... graph.sorted ].join( '' ) , 'BADC' )
} ,
'sorting must cut cycles at low priority edges C'() {
var graph = new $mol_graph< string , { priority : number } >()
graph.link( 'C' , 'D' , { priority : 0 } )
graph.link( 'D' , 'A' , { priority : -1 } )
graph.link( 'A' , 'B' , { priority : 0 } )
graph.link( 'B' , 'C' , { priority : -2 } )
graph.acyclic( edge => edge.priority )
$mol_assert_equal( [ ... graph.sorted ].join( '' ) , 'BADC' )
} ,
'sorting must cut cycles at low priority edges D'() {
var graph = new $mol_graph< string , { priority : number } >()
graph.link( 'D' , 'A' , { priority : -1 } )
graph.link( 'A' , 'B' , { priority : 0 } )
graph.link( 'B' , 'C' , { priority : -2 } )
graph.link( 'C' , 'D' , { priority : 0 } )
graph.acyclic( edge => edge.priority )
$mol_assert_equal( [ ... graph.sorted ].join( '' ) , 'BADC' )
} ,
'sorting must group cutted cycles'() {
var graph = new $mol_graph< string , number >()
graph.link( 'A' , 'B' , 0 )
graph.link( 'B' , 'C' , 0 )
graph.link( 'C' , 'D' , -2 )
graph.link( 'D' , 'E' , 0 )
graph.link( 'E' , 'C' , 0 )
graph.acyclic( edge => edge )
$mol_assert_equal( [ ... graph.sorted ].join( '' ) , 'CEDBA' )
} ,
} )
}