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

Unified 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 side-by-side diff with in-line comments
Download patch
« no previous file with comments | « no previous file | no next file » | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: lib/src/graph.dart
diff --git a/lib/src/graph.dart b/lib/src/graph.dart
index 0c185e26ce85eab4d156ff0317411067a87ec5d2..12bbd8aa19ddc744fe616cdd809cdcfbd4fe1419 100644
--- a/lib/src/graph.dart
+++ b/lib/src/graph.dart
@@ -54,14 +54,38 @@ abstract class Graph<N> {
}
/// Return a list of nodes that form a cycle containing the given node. If the
- /// node is not part of this graph, then a list containing only the node
- /// itself will be returned.
+ /// node is not part of a cycle in this graph, then a list containing only the
+ /// node itself will be returned.
List<N> findCycleContaining(N node) {
assert(node != null);
_SccFinder<N> finder = new _SccFinder<N>(this);
return finder._componentContaining(node);
}
+ /// Returns a dominator tree starting from root. This is a new graph, with the
+ /// same nodes as this graph, but where edges exist between a node and the
+ /// nodes it immediately dominates. For example, this graph:
+ ///
+ /// root
+ /// / \
+ /// a b
+ /// | / \
+ /// c d e
+ /// \ / \ /
+ /// f g
+ ///
+ /// Produces this tree:
+ ///
+ /// root
+ /// /| \
+ /// a | b
+ /// | | /|\
+ /// c | d | e
+ /// | |
+ /// f g
+ ///
+ /// Internally we compute dominators using (Cooper, Harvey, and Kennedy's
+ /// algorithm)[http://www.cs.rice.edu/~keith/EMBED/dom.pdf].
Graph<N> dominatorTree(N root) {
var iDom = (new _DominatorFinder(this)..run(root)).immediateDominators;
var graph = new EdgeListGraph<N>();
« 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