--- a/taskcluster/taskgraph/graph.py
+++ b/taskcluster/taskgraph/graph.py
@@ -73,39 +73,49 @@ class Graph(object):
             add_edges = set((left, right, name)
                             for (left, right, name) in self.edges
                             if (right if reverse else left) in nodes)
             add_nodes = set((left if reverse else right) for (left, right, _) in add_edges)
             new_nodes = nodes | add_nodes
             new_edges = edges | add_edges
         return Graph(new_nodes, new_edges)
 
-    def visit_postorder(self):
-        """
-        Generate a sequence of nodes in postorder, such that every node is
-        visited *after* any nodes it links to.
-
-        Behavior is undefined (read: it will hang) if the graph contains a
-        cycle.
-        """
+    def _visit(self, reverse):
         queue = collections.deque(sorted(self.nodes))
-        links_by_node = self.links_dict()
+        links_by_node = self.reverse_links_dict() if reverse else self.links_dict()
         seen = set()
         while queue:
             node = queue.popleft()
             if node in seen:
                 continue
             links = links_by_node[node]
             if all((n in seen) for n in links):
                 seen.add(node)
                 yield node
             else:
                 queue.extend(n for n in links if n not in seen)
                 queue.append(node)
 
+    def visit_postorder(self):
+        """
+        Generate a sequence of nodes in postorder, such that every node is
+        visited *after* any nodes it links to.
+
+        Behavior is undefined (read: it will hang) if the graph contains a
+        cycle.
+        """
+        return self._visit(False)
+
+    def visit_preorder(self):
+        """
+        Like visit_postorder, but in reverse: evrey node is visited *before*
+        any nodes it links to.
+        """
+        return self._visit(True)
+
     def links_dict(self):
         """
         Return a dictionary mapping each node to a set of the nodes it links to
         (omitting edge names)
         """
         links = collections.defaultdict(set)
         for left, right, _ in self.edges:
             links[left].add(right)

--- a/taskcluster/taskgraph/test/test_graph.py
+++ b/taskcluster/taskgraph/test/test_graph.py
@@ -124,16 +124,41 @@ class TestGraph(unittest.TestCase):
     def test_visit_postorder_multi_edges(self):
         "postorder visit of a graph with duplicate edges satisfies invariant"
         self.assert_postorder(self.multi_edges.visit_postorder(), self.multi_edges.nodes)
 
     def test_visit_postorder_disjoint(self):
         "postorder visit of a disjoint graph satisfies invariant"
         self.assert_postorder(self.disjoint.visit_postorder(), self.disjoint.nodes)
 
+    def assert_preorder(self, seq, all_nodes):
+        seen = set()
+        for e in seq:
+            for l, r, n in self.tree.edges:
+                if r == e:
+                    self.failUnless(l in seen)
+            seen.add(e)
+        self.assertEqual(seen, all_nodes)
+
+    def test_visit_preorder_tree(self):
+        "preorder visit of a tree satisfies invariant"
+        self.assert_preorder(self.tree.visit_preorder(), self.tree.nodes)
+
+    def test_visit_preorder_diamonds(self):
+        "preorder visit of a graph full of diamonds satisfies invariant"
+        self.assert_preorder(self.diamonds.visit_preorder(), self.diamonds.nodes)
+
+    def test_visit_preorder_multi_edges(self):
+        "preorder visit of a graph with duplicate edges satisfies invariant"
+        self.assert_preorder(self.multi_edges.visit_preorder(), self.multi_edges.nodes)
+
+    def test_visit_preorder_disjoint(self):
+        "preorder visit of a disjoint graph satisfies invariant"
+        self.assert_preorder(self.disjoint.visit_preorder(), self.disjoint.nodes)
+
     def test_links_dict(self):
         "link dict for a graph with multiple edges is correct"
         self.assertEqual(self.multi_edges.links_dict(), {
             '2': set(['1']),
             '3': set(['1', '2']),
             '4': set(['3']),
         })