| 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 strongest connected components in a graph and | 6 /// Tarjan's algorithm to compute strongest 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 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 47 helper(n) { | 47 helper(n) { |
| 48 if (!seen.add(n)) return; | 48 if (!seen.add(n)) return; |
| 49 targetsOf(n).forEach(helper); | 49 targetsOf(n).forEach(helper); |
| 50 result.add(n); | 50 result.add(n); |
| 51 } | 51 } |
| 52 helper(root); | 52 helper(root); |
| 53 return result; | 53 return result; |
| 54 } | 54 } |
| 55 | 55 |
| 56 /// Return a list of nodes that form a cycle containing the given node. If the | 56 /// Return a list of nodes that form a cycle containing the given node. If the |
| 57 /// node is not part of this graph, then a list containing only the node | 57 /// node is not part of a cycle in this graph, then a list containing only the |
| 58 /// itself will be returned. | 58 /// node itself will be returned. |
| 59 List<N> findCycleContaining(N node) { | 59 List<N> findCycleContaining(N node) { |
| 60 assert(node != null); | 60 assert(node != null); |
| 61 _SccFinder<N> finder = new _SccFinder<N>(this); | 61 _SccFinder<N> finder = new _SccFinder<N>(this); |
| 62 return finder._componentContaining(node); | 62 return finder._componentContaining(node); |
| 63 } | 63 } |
| 64 | 64 |
| 65 /// Returns a dominator tree starting from root. This is a new graph, with the |
| 66 /// same nodes as this graph, but where edges exist between a node and the |
| 67 /// nodes it immediately dominates. For example, this graph: |
| 68 /// |
| 69 /// root |
| 70 /// / \ |
| 71 /// a b |
| 72 /// | / \ |
| 73 /// c d e |
| 74 /// \ / \ / |
| 75 /// f g |
| 76 /// |
| 77 /// Produces this tree: |
| 78 /// |
| 79 /// root |
| 80 /// /| \ |
| 81 /// a | b |
| 82 /// | | /|\ |
| 83 /// c | d | e |
| 84 /// | | |
| 85 /// f g |
| 86 /// |
| 87 /// Internally we compute dominators using (Cooper, Harvey, and Kennedy's |
| 88 /// algorithm)[http://www.cs.rice.edu/~keith/EMBED/dom.pdf]. |
| 65 Graph<N> dominatorTree(N root) { | 89 Graph<N> dominatorTree(N root) { |
| 66 var iDom = (new _DominatorFinder(this)..run(root)).immediateDominators; | 90 var iDom = (new _DominatorFinder(this)..run(root)).immediateDominators; |
| 67 var graph = new EdgeListGraph<N>(); | 91 var graph = new EdgeListGraph<N>(); |
| 68 for (N node in iDom.keys) { | 92 for (N node in iDom.keys) { |
| 69 if (node != root) graph.addEdge(iDom[node], node); | 93 if (node != root) graph.addEdge(iDom[node], node); |
| 70 } | 94 } |
| 71 return graph; | 95 return graph; |
| 72 } | 96 } |
| 73 } | 97 } |
| 74 | 98 |
| (...skipping 208 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 283 while (postOrderId[finger1] < postOrderId[finger2]) { | 307 while (postOrderId[finger1] < postOrderId[finger2]) { |
| 284 finger1 = immediateDominators[finger1]; | 308 finger1 = immediateDominators[finger1]; |
| 285 } | 309 } |
| 286 while (postOrderId[finger2] < postOrderId[finger1]) { | 310 while (postOrderId[finger2] < postOrderId[finger1]) { |
| 287 finger2 = immediateDominators[finger2]; | 311 finger2 = immediateDominators[finger2]; |
| 288 } | 312 } |
| 289 } | 313 } |
| 290 return finger1; | 314 return finger1; |
| 291 } | 315 } |
| 292 } | 316 } |
| OLD | NEW |