Repository: piccolo-orm/piccolo
Issue: Migrations can fail if the chain of foreign keys is too long

### Discussed in https://github.com/piccolo-orm/piccolo/discussions/615

If you have tables like this, where each one has a foreign key to the next:

```python
from piccolo.columns import Varchar, ForeignKey
from piccolo.table import Table


class Manager(Table):
    name = Varchar()

class Manager2(Table):
    fk = ForeignKey(Manager)

class Manager3(Table):
    fk = ForeignKey(Manager2)

class Manager4(Table):
    fk = ForeignKey(Manager3)

class Manager5(Table):
    fk = ForeignKey(Manager4)
```

And you try and create them all in a single migration, then it can fail.

There's a bug in `sort_table_classes`, which sorts tables based on their foreign keys. It only happens if there are 5 or more tables, and if they have foreign keys to each other.

Changed files:
tests/apps/migrations/auto/test_migration_manager.py, tests/apps/migrations/auto/integration/test_migrations.py, piccolo/table.py

diff --git a/piccolo/table.py b/piccolo/table.py
index c0bcac28..8aeeee6f 100644
--- a/piccolo/table.py
+++ b/piccolo/table.py
@@ -1439,12 +1439,13 @@ def _get_graph(
 
             # We also recursively check the related tables to get a fuller
             # picture of the schema and relationships.
-            output.update(
-                _get_graph(
-                    [referenced_table],
-                    iterations=iterations + 1,
+            if referenced_table._meta.tablename not in output:
+                output.update(
+                    _get_graph(
+                        [referenced_table],
+                        iterations=iterations + 1,
+                    )
                 )
-            )
 
         output[table_class._meta.tablename] = dependents
 
diff --git a/tests/apps/migrations/auto/integration/test_migrations.py b/tests/apps/migrations/auto/integration/test_migrations.py
index d7261a07..bb16a4f0 100644
--- a/tests/apps/migrations/auto/integration/test_migrations.py
+++ b/tests/apps/migrations/auto/integration/test_migrations.py
@@ -182,10 +182,15 @@ class TestMigrations(MigrationTestCase):
     ###########################################################################
 
     def table(self, column: Column):
+        """
+        A utility for creating Piccolo tables with the given column.
+        """
         return create_table_class(
             class_name="MyTable", class_members={"my_column": column}
         )
 
+    ###########################################################################
+
     def test_varchar_column(self):
         self._test_migrations(
             table_snapshots=[
@@ -854,25 +859,56 @@ class TestM2MMigrations(MigrationTestCase):
 ###############################################################################
 
 
-class TableA(Table):
-    name = Varchar(unique=True)
+@postgres_only
+class TestForeignKeys(MigrationTestCase):
+    def setUp(self):
+        class TableA(Table):
+            pass
+
+        class TableB(Table):
+            fk = ForeignKey(TableA)
+
+        class TableC(Table):
+            fk = ForeignKey(TableB)
+
+        class TableD(Table):
+            fk = ForeignKey(TableC)
 
+        class TableE(Table):
+            fk = ForeignKey(TableD)
 
-class TableB(Table):
-    table_a = ForeignKey(TableA, target_column="name")
+        self.table_classes = [TableA, TableB, TableC, TableD, TableE]
 
+    def tearDown(self):
+        drop_db_tables_sync(Migration, *self.table_classes)
 
-class TableC(Table):
-    table_a = ForeignKey(TableA, target_column=TableA.name)
+    def test_foreign_keys(self):
+        """
+        Make sure that if we try creating tables with lots of foreign keys
+        to each other it runs successfully.
+
+        https://github.com/piccolo-orm/piccolo/issues/616
+
+        """
+
+        self._test_migrations(table_snapshots=[self.table_classes])
+        for table_class in self.table_classes:
+            self.assertTrue(table_class.table_exists().run_sync())
 
 
 @postgres_only
 class TestTargetColumn(MigrationTestCase):
     def setUp(self):
-        pass
+        class TableA(Table):
+            name = Varchar(unique=True)
+
+        class TableB(Table):
+            table_a = ForeignKey(TableA, target_column=TableA.name)
+
+        self.table_classes = [TableA, TableB]
 
     def tearDown(self):
-        drop_db_tables_sync(Migration, TableA, TableC)
+        drop_db_tables_sync(Migration, *self.table_classes)
 
     def test_target_column(self):
         """
@@ -880,14 +916,14 @@ class TestTargetColumn(MigrationTestCase):
         other than the primary key.
         """
         self._test_migrations(
-            table_snapshots=[[TableA, TableC]],
+            table_snapshots=[self.table_classes],
         )
 
-        for table_class in [TableA, TableC]:
+        for table_class in self.table_classes:
             self.assertTrue(table_class.table_exists().run_sync())
 
         # Make sure the constraint was created correctly.
-        response = TableA.raw(
+        response = self.run_sync(
             """
             SELECT EXISTS(
                 SELECT 1
@@ -895,22 +931,28 @@ class TestTargetColumn(MigrationTestCase):
                 JOIN INFORMATION_SCHEMA.TABLE_CONSTRAINTS TC ON
                     CCU.CONSTRAINT_NAME = TC.CONSTRAINT_NAME
                 WHERE CONSTRAINT_TYPE = 'FOREIGN KEY'
-                    AND TC.TABLE_NAME = 'table_c'
+                    AND TC.TABLE_NAME = 'table_b'
                     AND CCU.TABLE_NAME = 'table_a'
                     AND CCU.COLUMN_NAME = 'name'
             )
             """
-        ).run_sync()
+        )
         self.assertTrue(response[0]["exists"])
 
 
 @postgres_only
 class TestTargetColumnString(MigrationTestCase):
     def setUp(self):
-        pass
+        class TableA(Table):
+            name = Varchar(unique=True)
+
+        class TableB(Table):
+            table_a = ForeignKey(TableA, target_column="name")
+
+        self.table_classes = [TableA, TableB]
 
     def tearDown(self):
-        drop_db_tables_sync(Migration, TableA, TableB)
+        drop_db_tables_sync(Migration, *self.table_classes)
 
     def test_target_column(self):
         """
@@ -918,14 +960,14 @@ class TestTargetColumnString(MigrationTestCase):
         other than the primary key.
         """
         self._test_migrations(
-            table_snapshots=[[TableA, TableB]],
+            table_snapshots=[self.table_classes],
         )
 
-        for table_class in [TableA, TableB]:
+        for table_class in self.table_classes:
             self.assertTrue(table_class.table_exists().run_sync())
 
         # Make sure the constraint was created correctly.
-        response = TableA.raw(
+        response = self.run_sync(
             """
             SELECT EXISTS(
                 SELECT 1
@@ -938,5 +980,5 @@ class TestTargetColumnString(MigrationTestCase):
                     AND CCU.COLUMN_NAME = 'name'
             )
             """
-        ).run_sync()
+        )
         self.assertTrue(response[0]["exists"])
diff --git a/tests/apps/migrations/auto/test_migration_manager.py b/tests/apps/migrations/auto/test_migration_manager.py
index 4c5a08df..c416ae33 100644
--- a/tests/apps/migrations/auto/test_migration_manager.py
+++ b/tests/apps/migrations/auto/test_migration_manager.py
@@ -1,4 +1,5 @@
 import asyncio
+import random
 from io import StringIO
 from unittest import TestCase
 from unittest.mock import MagicMock, patch
@@ -19,8 +20,15 @@ asyncpg = LazyLoader("asyncpg", globals(), "asyncpg")
 
 class TestSortTableClasses(TestCase):
     def test_sort_table_classes(self):
-        self.assertEqual(sort_table_classes([Manager, Band]), [Manager, Band])
-        self.assertEqual(sort_table_classes([Band, Manager]), [Manager, Band])
+        """
+        Make sure simple use cases work correctly.
+        """
+        self.assertListEqual(
+            sort_table_classes([Manager, Band]), [Manager, Band]
+        )
+        self.assertListEqual(
+            sort_table_classes([Band, Manager]), [Manager, Band]
+        )
 
         sorted_tables = sort_table_classes([Manager, Venue, Concert, Band])
         self.assertTrue(
@@ -45,7 +53,7 @@ class TestSortTableClasses(TestCase):
         class TableB(Table):
             pass
 
-        self.assertEqual(
+        self.assertListEqual(
             sort_table_classes([TableA, TableB]), [TableA, TableB]
         )
 
@@ -54,7 +62,7 @@ class TestSortTableClasses(TestCase):
         Make sure that sorting a list with only a single table in it still
         works.
         """
-        self.assertEqual(sort_table_classes([Band]), [Band])
+        self.assertListEqual(sort_table_classes([Band]), [Band])
 
     def test_recursive_table(self):
         """
@@ -68,10 +76,40 @@ class TestSortTableClasses(TestCase):
         class TableB(Table):
             table_a = ForeignKey(TableA)
 
-        self.assertEqual(
+        self.assertListEqual(
             sort_table_classes([TableA, TableB]), [TableA, TableB]
         )
 
+    def test_long_chain(self):
+        """
+        Make sure sorting works when there are a lot of tables with foreign
+        keys to each other.
+
+        https://github.com/piccolo-orm/piccolo/issues/616
+
+        """
+
+        class TableA(Table):
+            pass
+
+        class TableB(Table):
+            fk = ForeignKey(TableA)
+
+        class TableC(Table):
+            fk = ForeignKey(TableB)
+
+        class TableD(Table):
+            fk = ForeignKey(TableC)
+
+        class TableE(Table):
+            fk = ForeignKey(TableD)
+
+        tables = [TableA, TableB, TableC, TableD, TableE]
+
+        shuffled_tables = random.sample(tables, len(tables))
+
+        self.assertListEqual(sort_table_classes(shuffled_tables), tables)
+
 
 class TestMigrationManager(DBTestCase):
     @postgres_only