OLD | NEW |
1 // Copyright (c) 2015, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2015, 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 /// A library to work with graphs. It contains a couple algorithms, including | 5 /// A library to work with graphs. It contains a couple algorithms, including |
6 /// Tarjan's algorithm to compute strongly connected components in a graph and | 6 /// Tarjan's algorithm to compute strongly connected components in a graph and |
7 /// Cooper et al's dominator algorithm. | 7 /// Cooper et al's dominator algorithm. |
8 /// | 8 /// |
9 /// Portions of the code in this library was adapted from | 9 /// Portions of the code in this library was adapted from |
10 /// `package:analyzer/src/generated/collection_utilities.dart`. | 10 /// `package:analyzer/src/generated/collection_utilities.dart`. |
(...skipping 25 matching lines...) Expand all Loading... |
36 if (identical(node, target)) return true; | 36 if (identical(node, target)) return true; |
37 if (!seen.add(node)) return false; | 37 if (!seen.add(node)) return false; |
38 return targetsOf(node).any(helper); | 38 return targetsOf(node).any(helper); |
39 } | 39 } |
40 return helper(source); | 40 return helper(source); |
41 } | 41 } |
42 | 42 |
43 /// Returns all nodes reachable from [root] in post order. | 43 /// Returns all nodes reachable from [root] in post order. |
44 Iterable<N> postOrder(N root) sync* { | 44 Iterable<N> postOrder(N root) sync* { |
45 var seen = new Set<N>(); | 45 var seen = new Set<N>(); |
46 Iterable<N> helper(n) sync* { | 46 Iterable<N> helper(N n) sync* { |
47 if (!seen.add(n)) return; | 47 if (!seen.add(n)) return; |
48 for (var x in targetsOf(n)) { | 48 for (var x in targetsOf(n)) { |
49 yield* helper(x); | 49 yield* helper(x); |
50 } | 50 } |
51 yield n; | 51 yield n; |
52 } | 52 } |
53 yield* helper(root); | 53 yield* helper(root); |
54 } | 54 } |
55 | 55 |
56 /// Returns an iterable of all nodes reachable from [root] in preorder. | 56 /// Returns an iterable of all nodes reachable from [root] in preorder. |
(...skipping 233 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
290 var nodesInPostOrder = _graph.postOrder(root).toList(); | 290 var nodesInPostOrder = _graph.postOrder(root).toList(); |
291 for (var n in nodesInPostOrder) { | 291 for (var n in nodesInPostOrder) { |
292 postOrderId[n] = i++; | 292 postOrderId[n] = i++; |
293 } | 293 } |
294 var nodesInReversedPostOrder = nodesInPostOrder.reversed; | 294 var nodesInReversedPostOrder = nodesInPostOrder.reversed; |
295 while (changed) { | 295 while (changed) { |
296 changed = false; | 296 changed = false; |
297 for (var n in nodesInReversedPostOrder) { | 297 for (var n in nodesInReversedPostOrder) { |
298 if (n == root) continue; | 298 if (n == root) continue; |
299 bool first = true; | 299 bool first = true; |
300 var idom = null; | 300 N idom; |
301 for (var p in _graph.sourcesOf(n)) { | 301 for (var p in _graph.sourcesOf(n)) { |
302 if (immediateDominators[p] != null) { | 302 if (immediateDominators[p] != null) { |
303 if (first) { | 303 if (first) { |
304 idom = p; | 304 idom = p; |
305 first = false; | 305 first = false; |
306 } else { | 306 } else { |
307 idom = _intersect(p, idom); | 307 idom = _intersect(p, idom); |
308 } | 308 } |
309 } | 309 } |
310 } | 310 } |
(...skipping 12 matching lines...) Expand all Loading... |
323 while (postOrderId[finger1] < postOrderId[finger2]) { | 323 while (postOrderId[finger1] < postOrderId[finger2]) { |
324 finger1 = immediateDominators[finger1]; | 324 finger1 = immediateDominators[finger1]; |
325 } | 325 } |
326 while (postOrderId[finger2] < postOrderId[finger1]) { | 326 while (postOrderId[finger2] < postOrderId[finger1]) { |
327 finger2 = immediateDominators[finger2]; | 327 finger2 = immediateDominators[finger2]; |
328 } | 328 } |
329 } | 329 } |
330 return finger1; | 330 return finger1; |
331 } | 331 } |
332 } | 332 } |
OLD | NEW |