OLD | NEW |
---|---|
1 // Copyright (c) 2016, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2016, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 import 'dart:math' as math; | |
6 | |
5 import 'utils.dart'; | 7 import 'utils.dart'; |
6 | 8 |
7 // TODO(nweiz): When sdk#26488 is fixed, use overloads to ensure that if [key] | 9 // TODO(nweiz): When sdk#26488 is fixed, use overloads to ensure that if [key] |
8 // or [value] isn't passed, `K2`/`V2` defaults to `K1`/`V1`, respectively. | 10 // or [value] isn't passed, `K2`/`V2` defaults to `K1`/`V1`, respectively. |
9 /// Creates a new map from [map] with new keys and values. | 11 /// Creates a new map from [map] with new keys and values. |
10 /// | 12 /// |
11 /// The return values of [key] are used as the keys and the return values of | 13 /// The return values of [key] are used as the keys and the return values of |
12 /// [value] are used as the values for the new map. | 14 /// [value] are used as the values for the new map. |
13 Map/*<K2, V2>*/ mapMap/*<K1, V1, K2, V2>*/(Map/*<K1, V1>*/ map, | 15 Map/*<K2, V2>*/ mapMap/*<K1, V1, K2, V2>*/(Map/*<K1, V1>*/ map, |
14 {/*=K2*/ key(/*=K1*/ key, /*=V1*/ value), | 16 {/*=K2*/ key(/*=K1*/ key, /*=V1*/ value), |
(...skipping 115 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
130 if (result[vertex2].contains(vertex1) && | 132 if (result[vertex2].contains(vertex1) && |
131 result[vertex1].contains(vertex3)) { | 133 result[vertex1].contains(vertex3)) { |
132 result[vertex2].add(vertex3); | 134 result[vertex2].add(vertex3); |
133 } | 135 } |
134 } | 136 } |
135 } | 137 } |
136 } | 138 } |
137 | 139 |
138 return result; | 140 return result; |
139 } | 141 } |
142 | |
143 /// Returns the [strongly connected components][] of [graph], in topological | |
144 /// order. | |
145 /// | |
146 /// [strongly connected components]: https://en.wikipedia.org/wiki/Strongly_conn ected_component | |
147 /// | |
148 /// This interprets [graph] as a directed graph with a vertex for each key and | |
149 /// edges from each key to the values associated with that key. | |
Lasse Reichstein Nielsen
2016/06/16 08:21:33
associated with that key -> that the key maps to.
nweiz
2016/06/20 21:19:38
Done.
| |
150 /// | |
151 /// Assumes that every vertex in the graph has a key to represent it, even if | |
152 /// that vertex has no outgoing edges. For example, `{"a": ["b"]}` is not valid, | |
153 /// but `{"a": ["b"], "b": []}` is. | |
Lasse Reichstein Nielsen
2016/06/16 08:21:33
Emphasize that this isn't checked, but if it fails
nweiz
2016/06/20 21:19:38
Done.
| |
154 List<Set/*<T>*/> stronglyConnectedComponents/*<T>*/( | |
155 Map<dynamic/*=T*/, Iterable/*<T>*/> graph) { | |
156 // This uses [Tarjan's algorithm][]. | |
157 // | |
158 // [Tarjan's algorithm]: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_con nected_components_algorithm | |
159 var index = 0; | |
160 var stack = /*<T>*/[]; | |
161 var indices = /*<T, int>*/{}; | |
162 var lowLinks = /*<T, int>*/{}; | |
163 var onStack = new Set/*<T>*/(); | |
Lasse Reichstein Nielsen
2016/06/16 08:21:33
You are using linked-hash-maps and -sets. The orde
nweiz
2016/06/20 21:19:38
Done.
| |
164 var result = /*<Set<T>>*/[]; | |
165 | |
166 strongConnect(/*=T*/ vertex) { | |
167 indices[vertex] = index; | |
168 lowLinks[vertex] = index; | |
169 index++; | |
170 | |
171 stack.add(vertex); | |
172 onStack.add(vertex); | |
173 | |
174 for (var successor in graph[vertex]) { | |
175 if (!indices.containsKey(successor)) { | |
176 strongConnect(successor); | |
177 lowLinks[vertex] = math.min(lowLinks[vertex], lowLinks[successor]); | |
178 } else if (onStack.contains(successor)) { | |
179 lowLinks[vertex] = math.min(lowLinks[vertex], lowLinks[successor]); | |
Lasse Reichstein Nielsen
2016/06/16 08:21:33
It annoys me to have two identical lines in separa
| |
180 } | |
181 } | |
182 | |
183 if (lowLinks[vertex] == indices[vertex]) { | |
184 var component = new Set/*<T>*/(); | |
185 var/*=T*/ neighbor; | |
186 do { | |
187 neighbor = stack.removeLast(); | |
188 onStack.remove(neighbor); | |
189 component.add(neighbor); | |
190 } while (neighbor != vertex); | |
191 result.add(component); | |
192 } | |
193 } | |
194 | |
195 for (var vertex in graph.keys) { | |
196 if (!indices.containsKey(vertex)) strongConnect(vertex); | |
197 } | |
198 | |
199 // Tarjan's algorithm produces a reverse-topological sort, so we reverse it to | |
200 // get a normal topological sort. | |
201 return result.reversed.toList(); | |
202 } | |
OLD | NEW |