Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(126)

Side by Side Diff: lib/src/graph.dart

Issue 1299843003: Fix comments (Closed) Base URL: git@github.com:dart-lang/dart2js_info.git@master
Patch Set: Created 5 years, 4 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « no previous file | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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 }
OLDNEW
« no previous file with comments | « no previous file | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698