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 82 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
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]. |
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. |
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 |
| 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. |
| 152 /// |
| 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 |