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 import 'dart:collection'; | |
7 | |
5 import 'utils.dart'; | 8 import 'utils.dart'; |
6 | 9 |
7 // TODO(nweiz): When sdk#26488 is fixed, use overloads to ensure that if [key] | 10 // 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. | 11 // or [value] isn't passed, `K2`/`V2` defaults to `K1`/`V1`, respectively. |
9 /// Creates a new map from [map] with new keys and values. | 12 /// Creates a new map from [map] with new keys and values. |
10 /// | 13 /// |
11 /// The return values of [key] are used as the keys and the return values of | 14 /// 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. | 15 /// [value] are used as the values for the new map. |
13 Map/*<K2, V2>*/ mapMap/*<K1, V1, K2, V2>*/(Map/*<K1, V1>*/ map, | 16 Map/*<K2, V2>*/ mapMap/*<K1, V1, K2, V2>*/(Map/*<K1, V1>*/ map, |
14 {/*=K2*/ key(/*=K1*/ key, /*=V1*/ value), | 17 {/*=K2*/ key(/*=K1*/ key, /*=V1*/ value), |
(...skipping 78 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
93 for (var element in values) { | 96 for (var element in values) { |
94 var elementOrderBy = orderBy(element); | 97 var elementOrderBy = orderBy(element); |
95 if (maxOrderBy == null || compare(elementOrderBy, maxOrderBy) > 0) { | 98 if (maxOrderBy == null || compare(elementOrderBy, maxOrderBy) > 0) { |
96 maxValue = element; | 99 maxValue = element; |
97 maxOrderBy = elementOrderBy; | 100 maxOrderBy = elementOrderBy; |
98 } | 101 } |
99 } | 102 } |
100 return maxValue; | 103 return maxValue; |
101 } | 104 } |
102 | 105 |
103 /// Returns the [transitive closure][] of [graph]. | 106 /// Returns the [transitive closure][] of [graph]. |
Lasse Reichstein Nielsen
2016/06/23 14:44:02
Consider changing "Returns" to "Computes".
The lin
nweiz
2016/06/23 20:52:58
I think the fact that "transitive closure" is a li
| |
104 /// | 107 /// |
105 /// [transitive closure]: https://en.wikipedia.org/wiki/Transitive_closure | 108 /// [transitive closure]: https://en.wikipedia.org/wiki/Transitive_closure |
106 /// | 109 /// |
107 /// This interprets [graph] as a directed graph with a vertex for each key and | 110 /// Interprets [graph] as a directed graph with a vertex for each key and edges |
108 /// edges from each key to the values associated with that key. | 111 /// from each key to the values that the key maps to. |
Lasse Reichstein Nielsen
2016/06/23 14:44:02
Maybe even:
with a vertex for each key and edge
nweiz
2016/06/23 20:52:57
I think that's less clear; it's still kind of mixi
| |
109 /// | 112 /// |
110 /// Assumes that every vertex in the graph has a key to represent it, even if | 113 /// Assumes that every vertex in the graph has a key to represent it, even if |
111 /// that vertex has no outgoing edges. For example, `{"a": ["b"]}` is not valid, | 114 /// that vertex has no outgoing edges. This isn't checked, but if it's not |
112 /// but `{"a": ["b"], "b": []}` is. | 115 /// satisfied, the function may crash or provide unexpected output. For example, |
116 /// `{"a": ["b"]}` is not valid, but `{"a": ["b"], "b": []}` is. | |
113 Map<dynamic/*=T*/, Set/*<T>*/> transitiveClosure/*<T>*/( | 117 Map<dynamic/*=T*/, Set/*<T>*/> transitiveClosure/*<T>*/( |
114 Map<dynamic/*=T*/, Iterable/*<T>*/> graph) { | 118 Map<dynamic/*=T*/, Iterable/*<T>*/> graph) { |
115 // This uses [Warshall's algorithm][], modified not to add a vertex from each | 119 // This uses [Warshall's algorithm][], modified not to add a vertex from each |
116 // node to itself. | 120 // node to itself. |
117 // | 121 // |
118 // [Warshall's algorithm]: https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshal l_algorithm#Applications_and_generalizations. | 122 // [Warshall's algorithm]: https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshal l_algorithm#Applications_and_generalizations. |
119 var result = /*<T, Set>*/{}; | 123 var result = /*<T, Set>*/{}; |
120 graph.forEach((vertex, edges) { | 124 graph.forEach((vertex, edges) { |
121 result[vertex] = new Set/*<T>*/.from(edges); | 125 result[vertex] = new Set/*<T>*/.from(edges); |
122 }); | 126 }); |
123 | 127 |
124 // Lists are faster to iterate than maps, so we create a list since we're | 128 // Lists are faster to iterate than maps, so we create a list since we're |
125 // iterating repeatedly. | 129 // iterating repeatedly. |
126 var keys = graph.keys.toList(); | 130 var keys = graph.keys.toList(); |
127 for (var vertex1 in keys) { | 131 for (var vertex1 in keys) { |
128 for (var vertex2 in keys) { | 132 for (var vertex2 in keys) { |
129 for (var vertex3 in keys) { | 133 for (var vertex3 in keys) { |
130 if (result[vertex2].contains(vertex1) && | 134 if (result[vertex2].contains(vertex1) && |
131 result[vertex1].contains(vertex3)) { | 135 result[vertex1].contains(vertex3)) { |
132 result[vertex2].add(vertex3); | 136 result[vertex2].add(vertex3); |
133 } | 137 } |
134 } | 138 } |
135 } | 139 } |
136 } | 140 } |
137 | 141 |
138 return result; | 142 return result; |
139 } | 143 } |
144 | |
145 /// Returns the [strongly connected components][] of [graph], in topological | |
Lasse Reichstein Nielsen
2016/06/23 14:44:02
Also consider Returns -> Computes.
(Because I jus
nweiz
2016/06/23 20:52:57
It's not explicitly mandated, but the documentatio
| |
146 /// order. | |
147 /// | |
148 /// [strongly connected components]: https://en.wikipedia.org/wiki/Strongly_conn ected_component | |
149 /// | |
150 /// Interprets [graph] as a directed graph with a vertex for each key and edges | |
151 /// from each key to the values that the key maps to. | |
Lasse Reichstein Nielsen
2016/06/23 14:44:03
Whatever you do above, do the same here.
nweiz
2016/06/23 20:52:57
Acknowledged.
| |
152 /// | |
Lasse Reichstein Nielsen
2016/06/23 14:44:02
Maybe add a comment saying that the graph modulo i
nweiz
2016/06/23 20:52:57
I think that's more complex than most users would
| |
153 /// Assumes that every vertex in the graph has a key to represent it, even if | |
154 /// that vertex has no outgoing edges. This isn't checked, but if it's not | |
155 /// satisfied, the function may crash or provide unexpected output. For example, | |
156 /// `{"a": ["b"]}` is not valid, but `{"a": ["b"], "b": []}` is. | |
157 List<Set/*<T>*/> stronglyConnectedComponents/*<T>*/( | |
158 Map<dynamic/*=T*/, Iterable/*<T>*/> graph) { | |
159 // This uses [Tarjan's algorithm][]. | |
160 // | |
161 // [Tarjan's algorithm]: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_con nected_components_algorithm | |
162 var index = 0; | |
163 var stack = /*<T>*/[]; | |
164 var result = /*<Set<T>>*/[]; | |
165 | |
166 // The order of these doesn't matter, so we use un-linked implementations to | |
167 // avoid unnecessary overhead. | |
168 var indices = new HashMap/*<T, int>*/(); | |
169 var lowLinks = new HashMap/*<T, int>*/(); | |
170 var onStack = new HashSet/*<T>*/(); | |
171 | |
172 strongConnect(/*=T*/ vertex) { | |
173 indices[vertex] = index; | |
174 lowLinks[vertex] = index; | |
175 index++; | |
176 | |
177 stack.add(vertex); | |
178 onStack.add(vertex); | |
179 | |
180 for (var successor in graph[vertex]) { | |
181 if (!indices.containsKey(successor)) { | |
182 strongConnect(successor); | |
183 lowLinks[vertex] = math.min(lowLinks[vertex], lowLinks[successor]); | |
184 } else if (onStack.contains(successor)) { | |
185 lowLinks[vertex] = math.min(lowLinks[vertex], lowLinks[successor]); | |
186 } | |
187 } | |
188 | |
189 if (lowLinks[vertex] == indices[vertex]) { | |
190 var component = new Set/*<T>*/(); | |
191 var/*=T*/ neighbor; | |
192 do { | |
193 neighbor = stack.removeLast(); | |
194 onStack.remove(neighbor); | |
195 component.add(neighbor); | |
196 } while (neighbor != vertex); | |
197 result.add(component); | |
198 } | |
199 } | |
200 | |
201 for (var vertex in graph.keys) { | |
202 if (!indices.containsKey(vertex)) strongConnect(vertex); | |
203 } | |
204 | |
205 // Tarjan's algorithm produces a reverse-topological sort, so we reverse it to | |
206 // get a normal topological sort. | |
207 return result.reversed.toList(); | |
208 } | |
OLD | NEW |