| 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 |