include fields in verify_deps, refactor graph dfs

test/graph_test.dart

Index: test/graph_test.dart
diff --git a/test/graph_test.dart b/test/graph_test.dart
new file mode 100644
index 0000000000000000000000000000000000000000..4934adfeeb88124ad6cee45e25ca59e97f689494
--- /dev/null
+++ b/test/graph_test.dart
@@ -0,0 +1,73 @@
+// Copyright (c) 2015, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+import 'package:dart2js_info/src/graph.dart';
+import 'package:test/test.dart';
+
+main() {
+  var graph = makeTestGraph();
+
+  test('preorder traversal', () {
+    expect(graph.preOrder('A').toList(), equals(['A', 'E', 'D', 'C', 'B']));
+  });
+
+  test('postorder traversal', () {
+    expect(graph.postOrder('A').toList(), equals(['C', 'E', 'D', 'B', 'A']));
+  });
+
+  test('topological sort', () {
+    expect(
+        graph.computeTopologicalSort(),
+        equals([
+          ['C'],
+          ['E'],
+          ['D', 'B', 'A']
+        ]));
+  });
+
+  test('contains path', () {
+    expect(graph.containsPath('A', 'C'), isTrue);
+    expect(graph.containsPath('B', 'E'), isTrue);
+    expect(graph.containsPath('C', 'A'), isFalse);
+    expect(graph.containsPath('E', 'B'), isFalse);
+  });
+
+  test('dominator tree', () {
+    // A dominates all other nodes in the graph, the resulting tree looks like
+    //       A
+    //    / / | |
+    //    B C D E
+    var dom = graph.dominatorTree('A');
+    expect(dom.targetsOf('A').length, equals(4));
+  });
+
+  test('cycle finding', () {
+    expect(graph.findCycleContaining('B'), equals(['A', 'D', 'B']));
+    expect(graph.findCycleContaining('C'), equals(['C']));
+  });
+}
+
+/// Creates a simple test graph with the following structure:
+/// ```
+///      A -> E
+///     / ^   ^
+///    /  \  /
+///   v   v /
+///  B -> D
+///  \  /
+///  v v
+///   C
+/// ```
+Graph<String> makeTestGraph() {
+  var graph = new EdgeListGraph<String>();
+  graph.addEdge('A', 'B');
+  graph.addEdge('A', 'D');
+  graph.addEdge('A', 'E');
+  graph.addEdge('B', 'C');
+  graph.addEdge('B', 'D');
+  graph.addEdge('D', 'A');
+  graph.addEdge('D', 'C');
+  graph.addEdge('D', 'E');
+  return graph;
+}