diff --git a/tests/unit/test_model.py b/tests/unit/test_model.py
index 04d1473..ee7c6ab 100644
--- a/tests/unit/test_model.py
+++ b/tests/unit/test_model.py
@@ -225,7 +225,7 @@
         self.assertFalse(python27diablo.changeMatches(change))
         self.assertFalse(python27essex.changeMatches(change))
 
-        item.freezeJobTree()
+        item.freezeJobGraph()
         self.assertEqual(len(item.getJobs()), 1)
         job = item.getJobs()[0]
         self.assertEqual(job.name, 'python27')
@@ -253,7 +253,7 @@
         self.assertTrue(python27diablo.changeMatches(change))
         self.assertFalse(python27essex.changeMatches(change))
 
-        item.freezeJobTree()
+        item.freezeJobGraph()
         self.assertEqual(len(item.getJobs()), 1)
         job = item.getJobs()[0]
         self.assertEqual(job.name, 'python27')
@@ -282,7 +282,7 @@
         self.assertFalse(python27diablo.changeMatches(change))
         self.assertTrue(python27essex.changeMatches(change))
 
-        item.freezeJobTree()
+        item.freezeJobGraph()
         self.assertEqual(len(item.getJobs()), 1)
         job = item.getJobs()[0]
         self.assertEqual(job.name, 'python27')
@@ -439,7 +439,7 @@
         self.assertTrue(python27.changeMatches(change))
         self.assertFalse(python27diablo.changeMatches(change))
 
-        item.freezeJobTree()
+        item.freezeJobGraph()
         self.assertEqual(len(item.getJobs()), 1)
         job = item.getJobs()[0]
         self.assertEqual(job.name, 'python27')
@@ -453,7 +453,7 @@
         self.assertTrue(python27.changeMatches(change))
         self.assertTrue(python27diablo.changeMatches(change))
 
-        item.freezeJobTree()
+        item.freezeJobGraph()
         self.assertEqual(len(item.getJobs()), 1)
         job = item.getJobs()[0]
         self.assertEqual(job.name, 'python27')
@@ -506,7 +506,7 @@
         self.assertTrue(base.changeMatches(change))
         self.assertFalse(python27.changeMatches(change))
 
-        item.freezeJobTree()
+        item.freezeJobGraph()
         self.assertEqual([], item.getJobs())
 
     def test_job_source_project(self):
@@ -609,3 +609,56 @@
         for x in range(10):
             self.db.update('job-name', 100, 'SUCCESS')
         self.assertEqual(self.db.getEstimatedTime('job-name'), 100)
+
+
+class TestGraph(BaseTestCase):
+    def test_job_graph_disallows_multiple_jobs_with_same_name(self):
+        graph = model.JobGraph()
+        job1 = model.Job('job')
+        job2 = model.Job('job')
+        graph.addJob(job1)
+        with testtools.ExpectedException(Exception,
+                                         "Job job already added"):
+            graph.addJob(job2)
+
+    def test_job_graph_disallows_circular_dependencies(self):
+        graph = model.JobGraph()
+        jobs = [model.Job('job%d' % i) for i in range(0, 10)]
+        prevjob = None
+        for j in jobs[:3]:
+            if prevjob:
+                j.dependencies = frozenset([prevjob.name])
+            graph.addJob(j)
+            prevjob = j
+        # 0 triggers 1 triggers 2 triggers 3...
+
+        # Cannot depend on itself
+        with testtools.ExpectedException(
+                Exception,
+                "Dependency cycle detected in job jobX"):
+            j = model.Job('jobX')
+            j.dependencies = frozenset([j.name])
+            graph.addJob(j)
+
+        # Disallow circular dependencies
+        with testtools.ExpectedException(
+                Exception,
+                "Dependency cycle detected in job job3"):
+            jobs[4].dependencies = frozenset([jobs[3].name])
+            graph.addJob(jobs[4])
+            jobs[3].dependencies = frozenset([jobs[4].name])
+            graph.addJob(jobs[3])
+
+        jobs[5].dependencies = frozenset([jobs[4].name])
+        graph.addJob(jobs[5])
+
+        with testtools.ExpectedException(
+                Exception,
+                "Dependency cycle detected in job job3"):
+            jobs[3].dependencies = frozenset([jobs[5].name])
+            graph.addJob(jobs[3])
+
+        jobs[3].dependencies = frozenset([jobs[2].name])
+        graph.addJob(jobs[3])
+        jobs[6].dependencies = frozenset([jobs[2].name])
+        graph.addJob(jobs[6])
diff --git a/tests/unit/test_scheduler.py b/tests/unit/test_scheduler.py
index e32e41b..a923ff1 100755
--- a/tests/unit/test_scheduler.py
+++ b/tests/unit/test_scheduler.py
@@ -4478,6 +4478,117 @@
         self.assertIn('project-test2 : SKIPPED', A.messages[1])
 
 
+class TestDependencyGraph(ZuulTestCase):
+    tenant_config_file = 'config/dependency-graph/main.yaml'
+
+    def test_dependeny_graph_dispatch_jobs_once(self):
+        "Test a job in a dependency graph is queued only once"
+        # Job dependencies, starting with A
+        #     A
+        #    / \
+        #   B   C
+        #  / \ / \
+        # D   F   E
+        #     |
+        #     G
+
+        self.executor_server.hold_jobs_in_build = True
+        change = self.fake_gerrit.addFakeChange(
+            'org/project', 'master', 'change')
+        change.addApproval('code-review', 2)
+        self.fake_gerrit.addEvent(change.addApproval('approved', 1))
+
+        self.waitUntilSettled()
+        self.assertEqual([b.name for b in self.builds], ['A'])
+
+        self.executor_server.release('A')
+        self.waitUntilSettled()
+        self.assertEqual(sorted(b.name for b in self.builds), ['B', 'C'])
+
+        self.executor_server.release('B')
+        self.waitUntilSettled()
+        self.assertEqual(sorted(b.name for b in self.builds), ['C', 'D'])
+
+        self.executor_server.release('D')
+        self.waitUntilSettled()
+        self.assertEqual([b.name for b in self.builds], ['C'])
+
+        self.executor_server.release('C')
+        self.waitUntilSettled()
+        self.assertEqual(sorted(b.name for b in self.builds), ['E', 'F'])
+
+        self.executor_server.release('F')
+        self.waitUntilSettled()
+        self.assertEqual(sorted(b.name for b in self.builds), ['E', 'G'])
+
+        self.executor_server.release('G')
+        self.waitUntilSettled()
+        self.assertEqual([b.name for b in self.builds], ['E'])
+
+        self.executor_server.release('E')
+        self.waitUntilSettled()
+        self.assertEqual(len(self.builds), 0)
+
+        self.executor_server.hold_jobs_in_build = False
+        self.executor_server.release()
+        self.waitUntilSettled()
+
+        self.assertEqual(len(self.builds), 0)
+        self.assertEqual(len(self.history), 7)
+
+        self.assertEqual(change.data['status'], 'MERGED')
+        self.assertEqual(change.reported, 2)
+
+    def test_jobs_launched_only_if_all_dependencies_are_successful(self):
+        "Test that a job waits till all dependencies are successful"
+        # Job dependencies, starting with A
+        #     A
+        #    / \
+        #   B   C*
+        #  / \ / \
+        # D   F   E
+        #     |
+        #     G
+
+        self.executor_server.hold_jobs_in_build = True
+        change = self.fake_gerrit.addFakeChange(
+            'org/project', 'master', 'change')
+        change.addApproval('code-review', 2)
+
+        self.executor_server.failJob('C', change)
+
+        self.fake_gerrit.addEvent(change.addApproval('approved', 1))
+
+        self.waitUntilSettled()
+        self.assertEqual([b.name for b in self.builds], ['A'])
+
+        self.executor_server.release('A')
+        self.waitUntilSettled()
+        self.assertEqual(sorted(b.name for b in self.builds), ['B', 'C'])
+
+        self.executor_server.release('B')
+        self.waitUntilSettled()
+        self.assertEqual(sorted(b.name for b in self.builds), ['C', 'D'])
+
+        self.executor_server.release('D')
+        self.waitUntilSettled()
+        self.assertEqual([b.name for b in self.builds], ['C'])
+
+        self.executor_server.release('C')
+        self.waitUntilSettled()
+        self.assertEqual(len(self.builds), 0)
+
+        self.executor_server.hold_jobs_in_build = False
+        self.executor_server.release()
+        self.waitUntilSettled()
+
+        self.assertEqual(len(self.builds), 0)
+        self.assertEqual(len(self.history), 4)
+
+        self.assertEqual(change.data['status'], 'NEW')
+        self.assertEqual(change.reported, 2)
+
+
 class TestDuplicatePipeline(ZuulTestCase):
     tenant_config_file = 'config/duplicate-pipeline/main.yaml'