pub fn sort_dag<T, P, C>(nodes: &mut [T], parents: P, children: C)Expand description
The same algorithm as sort, but for Directed Acyclic Graphs (DAGs),
encoded as trees with shared nodes.
WARNING: To avoid an infinite loop, one must be careful about the order of children.
E.g. if A has children C, B and B has child C, then the tree is not a DAG.
This is because the order of children is preserved after sorting.
Examples found in repository?
examples/dag.rs (line 41)
17fn main() {
18 let mut nodes: Vec<Node> = vec![
19 Node {
20 val: 0,
21 parents: vec![],
22 children: vec![2, 3],
23 },
24 // Shared between `1` and `2`.
25 Node {
26 val: 3,
27 parents: vec![2, 3],
28 children: vec![]
29 },
30 Node {
31 val: 1,
32 parents: vec![0],
33 children: vec![1],
34 },
35 Node {
36 val: 2,
37 parents: vec![0],
38 children: vec![1],
39 },
40 ];
41 sort_dag(&mut nodes, |n| &mut n.parents, |n| &mut n.children);
42 assert_eq!(
43 nodes,
44 vec![
45 Node { val: 0, parents: vec![], children: vec![1, 2] },
46 Node { val: 1, parents: vec![0], children: vec![3] },
47 Node { val: 2, parents: vec![0], children: vec![3] },
48 Node { val: 3, parents: vec![1, 2], children: vec![] }
49 ]
50 );
51
52 let mut nodes: Vec<Node> = vec![
53 Node {
54 val: 0,
55 parents: vec![],
56 children: vec![1, 3],
57 },
58 Node {
59 val: 1,
60 parents: vec![0],
61 children: vec![2],
62 },
63 Node {
64 val: 3,
65 parents: vec![1, 3],
66 children: vec![]
67 },
68 Node {
69 val: 2,
70 parents: vec![0],
71 children: vec![2],
72 },
73 ];
74 sort_dag(&mut nodes, |n| &mut n.parents, |n| &mut n.children);
75 assert_eq!(
76 nodes,
77 vec![
78 Node { val: 0, parents: vec![], children: vec![1, 2] },
79 Node { val: 1, parents: vec![0], children: vec![3] },
80 Node { val: 2, parents: vec![0], children: vec![3] },
81 Node { val: 3, parents: vec![1, 2], children: vec![] }
82 ]
83 );
84
85 let mut nodes: Vec<Node> = vec![
86 Node {
87 val: 0,
88 parents: vec![],
89 children: vec![3, 1],
90 },
91 Node {
92 val: 2,
93 parents: vec![0],
94 children: vec![2],
95 },
96 Node {
97 val: 3,
98 parents: vec![3, 1],
99 children: vec![]
100 },
101 Node {
102 val: 1,
103 parents: vec![0],
104 children: vec![2],
105 },
106 ];
107 sort_dag(&mut nodes, |n| &mut n.parents, |n| &mut n.children);
108 assert_eq!(
109 nodes,
110 vec![
111 Node { val: 0, parents: vec![], children: vec![1, 2] },
112 Node { val: 1, parents: vec![0], children: vec![3] },
113 Node { val: 2, parents: vec![0], children: vec![3] },
114 Node { val: 3, parents: vec![1, 2], children: vec![] }
115 ]
116 );
117
118 let mut nodes: Vec<Node> = vec![
119 Node {
120 val: 0,
121 parents: vec![],
122 children: vec![3, 1],
123 },
124 Node {
125 val: 2,
126 parents: vec![0],
127 children: vec![2],
128 },
129 Node {
130 val: 3,
131 parents: vec![3, 1],
132 children: vec![]
133 },
134 Node {
135 val: 1,
136 parents: vec![0],
137 children: vec![2],
138 },
139 ];
140 sort_dag(&mut nodes, |n| &mut n.parents, |n| &mut n.children);
141 assert_eq!(
142 nodes,
143 vec![
144 Node { val: 0, parents: vec![], children: vec![1, 2] },
145 Node { val: 1, parents: vec![0], children: vec![3] },
146 Node { val: 2, parents: vec![0], children: vec![3] },
147 Node { val: 3, parents: vec![1, 2], children: vec![] }
148 ]
149 );
150
151 let mut nodes: Vec<Node> = vec![
152 Node {
153 val: 0,
154 parents: vec![],
155 children: vec![3, 2],
156 },
157 Node {
158 val: 3,
159 parents: vec![3, 2],
160 children: vec![]
161 },
162 Node {
163 val: 2,
164 parents: vec![0],
165 children: vec![1],
166 },
167 Node {
168 val: 1,
169 parents: vec![0],
170 children: vec![1],
171 },
172 ];
173 sort_dag(&mut nodes, |n| &mut n.parents, |n| &mut n.children);
174 assert_eq!(
175 nodes,
176 vec![
177 Node { val: 0, parents: vec![], children: vec![1, 2] },
178 Node { val: 1, parents: vec![0], children: vec![3] },
179 Node { val: 2, parents: vec![0], children: vec![3] },
180 Node { val: 3, parents: vec![1, 2], children: vec![] }
181 ]
182 );
183
184 let mut nodes: Vec<Node> = vec![
185 Node {
186 val: 0,
187 parents: vec![],
188 children: vec![3, 2],
189 },
190 Node {
191 val: 3,
192 parents: vec![3, 2],
193 children: vec![]
194 },
195 Node {
196 val: 2,
197 parents: vec![0],
198 children: vec![1],
199 },
200 Node {
201 val: 1,
202 parents: vec![0],
203 // The sibling-as-child must become before shared children.
204 children: vec![2, 1],
205 },
206 ];
207 sort_dag(&mut nodes, |n| &mut n.parents, |n| &mut n.children);
208 assert_eq!(
209 nodes,
210 vec![
211 Node { val: 0, parents: vec![], children: vec![1, 2] },
212 Node { val: 1, parents: vec![0], children: vec![2, 3] },
213 Node { val: 2, parents: vec![0], children: vec![3] },
214 Node { val: 3, parents: vec![1, 2], children: vec![] }
215 ]
216 );
217}