tests the digraph structure tests a basic dependency graph appa 0001 0002 0003 0004 appb 0001 0002 build graph test root migration case test branch b only test whole graph test reverse to b 0002 test roots and leaves build graph graph migrationgraph graph addnodeappa 0001 none graph addnodeappa 0002 none graph addnodeappa 0003 none graph addnodeappa 0004 none graph addnodeappb 0001 none graph addnodeappb 0002 none graph addnodeappc 0001 none graph addnodeappc 0002 none graph adddependencyappa 0004 appa 0004 appa 0003 graph adddependencyappa 0003 appa 0003 appa 0002 graph adddependencyappa 0002 appa 0002 appa 0001 graph adddependencyappa 0003 appa 0003 appb 0002 graph adddependencyappb 0002 appb 0002 appb 0001 graph adddependencyappa 0004 appa 0004 appc 0002 graph adddependencyappc 0002 appc 0002 appc 0001 graph adddependencyappc 0001 appc 0001 appb 0001 graph adddependencyappc 0002 appc 0002 appa 0002 test branch c only self assertequal graph forwardsplanappc 0002 appb 0001 appc 0001 appa 0001 appa 0002 appc 0002 test whole graph self assertequal graph forwardsplanappa 0004 appb 0001 appc 0001 appa 0001 appa 0002 appc 0002 appb 0002 appa 0003 appa 0004 test reverse to b 0001 self assertequal graph backwardsplanappb 0001 appa 0004 appc 0002 appc 0001 appa 0003 appb 0002 appb 0001 test roots and leaves self assertequal graph rootnodes appa 0001 appb 0001 appc 0001 self assertequal graph leafnodes appa 0004 appb 0002 appc 0002 def testcirculargraphself build graph graph migrationgraph graph addnodeappa 0001 none graph addnodeappa 0002 none graph addnodeappa 0003 none graph addnodeappb 0001 none graph addnodeappb 0002 none graph adddependencyappa 0003 appa 0003 appa 0002 graph adddependencyappa 0002 appa 0002 appa 0001 graph adddependencyappa 0001 appa 0001 appb 0002 graph adddependencyappb 0002 appb 0002 appb 0001 graph adddependencyappb 0001 appb 0001 appa 0003 test whole graph with self assertraisescirculardependencyerror graph ensurenotcyclic def testcirculargraph2self graph migrationgraph graph addnodea 0001 none graph addnodec 0001 none graph addnodeb 0001 none graph adddependencya 0001 a 0001 b 0001 graph adddependencyb 0001 b 0001 a 0001 graph adddependencyc 0001 c 0001 b 0001 with self assertraisescirculardependencyerror graph ensurenotcyclic def testiterativedfsself graph migrationgraph root appa 1 graph addnoderoot none expected root for i in range2 750 parent appa stri 1 child appa stri graph addnodechild none graph adddependencystri child parent expected appendchild leaf expected1 forwardsplan graph forwardsplanleaf self assertequalexpected forwardsplan backwardsplan graph backwardsplanroot self assertequalexpected 1 backwardsplan def testiterativedfscomplexityself n 50 graph migrationgraph for i in range1 n 1 graph addnodeappa stri none graph addnodeappb stri none graph addnodeappc stri none for i in range1 n graph adddependencynone appb stri appa stri graph adddependencynone appc stri appa stri graph adddependencynone appa stri 1 appb stri graph adddependencynone appa stri 1 appc stri plan graph forwardsplanappa strn expected app stri for i in range1 n for app in appa appc appb appa strn self assertequalplan expected def testplaninvalidnodeself graph migrationgraph message node appb 0001 not a valid node with self assertraisesmessagenodenotfounderror message graph forwardsplanappb 0001 with self assertraisesmessagenodenotfounderror message graph backwardsplanappb 0001 def testmissingparentnodesself build graph graph migrationgraph graph addnodeappa 0001 none graph addnodeappa 0002 none graph addnodeappa 0003 none graph addnodeappb 0001 none graph adddependencyappa 0003 appa 0003 appa 0002 graph adddependencyappa 0002 appa 0002 appa 0001 msg migration appa 0001 dependencies reference nonexistent parent node appb 0002 with self assertraisesmessagenodenotfounderror msg graph adddependencyappa 0001 appa 0001 appb 0002 def testmissingchildnodesself build graph graph migrationgraph graph addnodeappa 0001 none msg migration appa 0002 dependencies reference nonexistent child node appa 0002 with self assertraisesmessagenodenotfounderror msg graph adddependencyappa 0002 appa 0002 appa 0001 def testvalidateconsistencymissingparentself graph migrationgraph graph addnodeappa 0001 none graph adddependency appa 0001 appa 0001 appb 0002 skipvalidationtrue msg migration appa 0001 dependencies reference nonexistent parent node appb 0002 with self assertraisesmessagenodenotfounderror msg graph validateconsistency def testvalidateconsistencymissingchildself graph migrationgraph graph addnodeappb 0002 none graph adddependency appb 0002 appa 0001 appb 0002 skipvalidationtrue msg migration appb 0002 dependencies reference nonexistent child node appa 0001 with self assertraisesmessagenodenotfounderror msg graph validateconsistency def testvalidateconsistencynoerrorself graph migrationgraph graph addnodeappa 0001 none graph addnodeappb 0002 none graph adddependency appa 0001 appa 0001 appb 0002 skipvalidationtrue graph validateconsistency def testvalidateconsistencydummyself msg appa 0001 req d by appb 0002 is missing graph migrationgraph graph adddummynode keyappa 0001 originappb 0002 errormessagemsg with self assertraisesmessagenodenotfounderror msg graph validateconsistency def testremovereplacednodesself add some dummy nodes to be replaced graph migrationgraph graph adddummynode keyappa 0001 originappa 0002 errormessagebad graph adddummynode keyappa 0002 originappb 0001 errormessagebad graph adddependency appa 0002 appa 0002 appa 0001 skipvalidationtrue add some normal parent and child nodes to test dependency remapping graph addnodeappc 0001 none graph addnodeappb 0001 none graph adddependency appa 0001 appa 0001 appc 0001 skipvalidationtrue graph adddependency appb 0001 appb 0001 appa 0002 skipvalidationtrue try replacing before replacement node exists msg unable to find replacement node appa 0001squashed0002 it was either never added to the migration graph or has been removed with self assertraisesmessagenodenotfounderror msg graph removereplacednodes replacementappa 0001squashed0002 replacedappa 0001 appa 0002 graph addnodeappa 0001squashed0002 none ensure validateconsistency still raises an error at this stage with self assertraisesmessagenodenotfounderror bad graph validateconsistency remove the dummy nodes graph removereplacednodes replacementappa 0001squashed0002 replacedappa 0001 appa 0002 ensure graph is now consistent and dependencies have been remapped graph validateconsistency parentnode graph nodemapappc 0001 replacementnode graph nodemapappa 0001squashed0002 childnode graph nodemapappb 0001 self assertinparentnode replacementnode parents self assertinreplacementnode parentnode children self assertinchildnode replacementnode children self assertinreplacementnode childnode parents def testremovereplacementnodeself add some dummy nodes to be replaced graph migrationgraph graph addnodeappa 0001 none graph addnodeappa 0002 none graph adddependencyappa 0002 appa 0002 appa 0001 try removing replacement node before replacement node exists msg unable to remove replacement node appa 0001squashed0002 it was either never added to the migration graph or has been removed already with self assertraisesmessagenodenotfounderror msg graph removereplacementnode replacementappa 0001squashed0002 replacedappa 0001 appa 0002 graph addnodeappa 0001squashed0002 none add a child node to test dependency remapping graph addnodeappb 0001 none graph adddependency appb 0001 appb 0001 appa 0001squashed0002 remove the replacement node graph removereplacementnode replacementappa 0001squashed0002 replacedappa 0001 appa 0002 ensure graph is consistent and child dependency has been remapped graph validateconsistency replacednode graph nodemapappa 0002 childnode graph nodemapappb 0001 self assertinchildnode replacednode children self assertinreplacednode childnode parents child dependency hasn t also gotten remapped to the other replaced node otherreplacednode graph nodemapappa 0001 self assertnotinchildnode otherreplacednode children self assertnotinotherreplacednode childnode parents def testinfiniteloopself graph migrationgraph graph addnodeappa 0001 none graph addnodeappb 0001 none graph addnodeappb 0002 none graph addnodeappc 0001squashed0002 none graph adddependency appb 0001 appb 0001 appc 0001squashed0002 graph adddependencyappb 0002 appb 0002 appa 0001 graph adddependencyappb 0002 appb 0002 appb 0001 graph adddependency appc 0001squashed0002 appc 0001squashed0002 appb 0002 with self assertraisescirculardependencyerror graph ensurenotcyclic def teststringifyself graph migrationgraph self assertequalstrgraph graph 0 nodes 0 edges graph addnodeappa 0001 none graph addnodeappa 0002 none graph addnodeappa 0003 none graph addnodeappb 0001 none graph addnodeappb 0002 none graph adddependencyappa 0002 appa 0002 appa 0001 graph adddependencyappa 0003 appa 0003 appa 0002 graph adddependencyappa 0003 appa 0003 appb 0002 self assertequalstrgraph graph 5 nodes 3 edges self assertequalreprgraph migrationgraph nodes5 edges3 class nodetestssimpletestcase def testnodereprself node nodeappa 0001 self assertequalreprnode node appa 0001 def testnodestrself node nodeappa 0001 self assertequalstrnode appa 0001 def testdummynodereprself node dummynode keyappa 0001 originappa 0001 errormessagex is missing self assertequalreprnode dummynode appa 0001 tests the digraph structure tests a basic dependency graph app_a 0001 0002 0003 0004 app_b 0001 0002 build graph test root migration case test branch b only test whole graph test reverse to b 0002 test roots and leaves tests a complex dependency graph app_a 0001 0002 0003 0004 app_b 0001 0002 x app_c 0001 0002 build graph test branch c only test whole graph test reverse to b 0001 test roots and leaves tests a circular dependency graph build graph test whole graph in a graph with merge migrations iterative_dfs traverses each node only once even if there are multiple paths leading to it tests for forwards backwards_plan of nonexistent node tests for missing parent nodes build graph tests for missing child nodes build graph validate_consistency raises an error if there s an isolated dummy node replaced nodes are properly removed and dependencies remapped add some dummy nodes to be replaced add some normal parent and child nodes to test dependency remapping try replacing before replacement node exists ensure validate_consistency still raises an error at this stage remove the dummy nodes ensure graph is now consistent and dependencies have been remapped a replacement node is properly removed and child dependencies remapped we assume parent dependencies are already correct add some dummy nodes to be replaced try removing replacement node before replacement node exists add a child node to test dependency remapping remove the replacement node ensure graph is consistent and child dependency has been remapped child dependency hasn t also gotten remapped to the other replaced node tests a complex dependency graph app_a 0001 app_b 0001 x 0002 app_c 0001 x 0002 and apply squashing on app_c
from django.db.migrations.exceptions import CircularDependencyError, NodeNotFoundError
from django.db.migrations.graph import DummyNode, MigrationGraph, Node
from django.test import SimpleTestCase


class GraphTests(SimpleTestCase):
    

    def test_simple_graph(self):
        
        
        graph = MigrationGraph()
        graph.add_node(("app_a", "0001"), None)
        graph.add_node(("app_a", "0002"), None)
        graph.add_node(("app_a", "0003"), None)
        graph.add_node(("app_a", "0004"), None)
        graph.add_node(("app_b", "0001"), None)
        graph.add_node(("app_b", "0002"), None)
        graph.add_dependency("app_a.0004", ("app_a", "0004"), ("app_a", "0003"))
        graph.add_dependency("app_a.0003", ("app_a", "0003"), ("app_a", "0002"))
        graph.add_dependency("app_a.0002", ("app_a", "0002"), ("app_a", "0001"))
        graph.add_dependency("app_a.0003", ("app_a", "0003"), ("app_b", "0002"))
        graph.add_dependency("app_b.0002", ("app_b", "0002"), ("app_b", "0001"))
        
        self.assertEqual(
            graph.forwards_plan(("app_a", "0001")),
            [("app_a", "0001")],
        )
        
        self.assertEqual(
            graph.forwards_plan(("app_b", "0002")),
            [("app_b", "0001"), ("app_b", "0002")],
        )
        
        self.assertEqual(
            graph.forwards_plan(("app_a", "0004")),
            [
                ("app_b", "0001"),
                ("app_b", "0002"),
                ("app_a", "0001"),
                ("app_a", "0002"),
                ("app_a", "0003"),
                ("app_a", "0004"),
            ],
        )
        
        self.assertEqual(
            graph.backwards_plan(("app_b", "0002")),
            [("app_a", "0004"), ("app_a", "0003"), ("app_b", "0002")],
        )
        
        self.assertEqual(
            graph.root_nodes(),
            [("app_a", "0001"), ("app_b", "0001")],
        )
        self.assertEqual(
            graph.leaf_nodes(),
            [("app_a", "0004"), ("app_b", "0002")],
        )

    def test_complex_graph(self):
        r
        
        graph = MigrationGraph()
        graph.add_node(("app_a", "0001"), None)
        graph.add_node(("app_a", "0002"), None)
        graph.add_node(("app_a", "0003"), None)
        graph.add_node(("app_a", "0004"), None)
        graph.add_node(("app_b", "0001"), None)
        graph.add_node(("app_b", "0002"), None)
        graph.add_node(("app_c", "0001"), None)
        graph.add_node(("app_c", "0002"), None)
        graph.add_dependency("app_a.0004", ("app_a", "0004"), ("app_a", "0003"))
        graph.add_dependency("app_a.0003", ("app_a", "0003"), ("app_a", "0002"))
        graph.add_dependency("app_a.0002", ("app_a", "0002"), ("app_a", "0001"))
        graph.add_dependency("app_a.0003", ("app_a", "0003"), ("app_b", "0002"))
        graph.add_dependency("app_b.0002", ("app_b", "0002"), ("app_b", "0001"))
        graph.add_dependency("app_a.0004", ("app_a", "0004"), ("app_c", "0002"))
        graph.add_dependency("app_c.0002", ("app_c", "0002"), ("app_c", "0001"))
        graph.add_dependency("app_c.0001", ("app_c", "0001"), ("app_b", "0001"))
        graph.add_dependency("app_c.0002", ("app_c", "0002"), ("app_a", "0002"))
        
        self.assertEqual(
            graph.forwards_plan(("app_c", "0002")),
            [
                ("app_b", "0001"),
                ("app_c", "0001"),
                ("app_a", "0001"),
                ("app_a", "0002"),
                ("app_c", "0002"),
            ],
        )
        
        self.assertEqual(
            graph.forwards_plan(("app_a", "0004")),
            [
                ("app_b", "0001"),
                ("app_c", "0001"),
                ("app_a", "0001"),
                ("app_a", "0002"),
                ("app_c", "0002"),
                ("app_b", "0002"),
                ("app_a", "0003"),
                ("app_a", "0004"),
            ],
        )
        
        self.assertEqual(
            graph.backwards_plan(("app_b", "0001")),
            [
                ("app_a", "0004"),
                ("app_c", "0002"),
                ("app_c", "0001"),
                ("app_a", "0003"),
                ("app_b", "0002"),
                ("app_b", "0001"),
            ],
        )
        
        self.assertEqual(
            graph.root_nodes(),
            [("app_a", "0001"), ("app_b", "0001"), ("app_c", "0001")],
        )
        self.assertEqual(
            graph.leaf_nodes(),
            [("app_a", "0004"), ("app_b", "0002"), ("app_c", "0002")],
        )

    def test_circular_graph(self):
        
        
        graph = MigrationGraph()
        graph.add_node(("app_a", "0001"), None)
        graph.add_node(("app_a", "0002"), None)
        graph.add_node(("app_a", "0003"), None)
        graph.add_node(("app_b", "0001"), None)
        graph.add_node(("app_b", "0002"), None)
        graph.add_dependency("app_a.0003", ("app_a", "0003"), ("app_a", "0002"))
        graph.add_dependency("app_a.0002", ("app_a", "0002"), ("app_a", "0001"))
        graph.add_dependency("app_a.0001", ("app_a", "0001"), ("app_b", "0002"))
        graph.add_dependency("app_b.0002", ("app_b", "0002"), ("app_b", "0001"))
        graph.add_dependency("app_b.0001", ("app_b", "0001"), ("app_a", "0003"))
        
        with self.assertRaises(CircularDependencyError):
            graph.ensure_not_cyclic()

    def test_circular_graph_2(self):
        graph = MigrationGraph()
        graph.add_node(("A", "0001"), None)
        graph.add_node(("C", "0001"), None)
        graph.add_node(("B", "0001"), None)
        graph.add_dependency("A.0001", ("A", "0001"), ("B", "0001"))
        graph.add_dependency("B.0001", ("B", "0001"), ("A", "0001"))
        graph.add_dependency("C.0001", ("C", "0001"), ("B", "0001"))

        with self.assertRaises(CircularDependencyError):
            graph.ensure_not_cyclic()

    def test_iterative_dfs(self):
        graph = MigrationGraph()
        root = ("app_a", "1")
        graph.add_node(root, None)
        expected = [root]
        for i in range(2, 750):
            parent = ("app_a", str(i - 1))
            child = ("app_a", str(i))
            graph.add_node(child, None)
            graph.add_dependency(str(i), child, parent)
            expected.append(child)
        leaf = expected[-1]

        forwards_plan = graph.forwards_plan(leaf)
        self.assertEqual(expected, forwards_plan)

        backwards_plan = graph.backwards_plan(root)
        self.assertEqual(expected[::-1], backwards_plan)

    def test_iterative_dfs_complexity(self):
        
        n = 50
        graph = MigrationGraph()
        for i in range(1, n + 1):
            graph.add_node(("app_a", str(i)), None)
            graph.add_node(("app_b", str(i)), None)
            graph.add_node(("app_c", str(i)), None)
        for i in range(1, n):
            graph.add_dependency(None, ("app_b", str(i)), ("app_a", str(i)))
            graph.add_dependency(None, ("app_c", str(i)), ("app_a", str(i)))
            graph.add_dependency(None, ("app_a", str(i + 1)), ("app_b", str(i)))
            graph.add_dependency(None, ("app_a", str(i + 1)), ("app_c", str(i)))
        plan = graph.forwards_plan(("app_a", str(n)))
        expected = [
            (app, str(i)) for i in range(1, n) for app in ["app_a", "app_c", "app_b"]
        ] + [("app_a", str(n))]
        self.assertEqual(plan, expected)

    def test_plan_invalid_node(self):
        
        graph = MigrationGraph()
        message = "Node ('app_b', '0001') not a valid node"

        with self.assertRaisesMessage(NodeNotFoundError, message):
            graph.forwards_plan(("app_b", "0001"))

        with self.assertRaisesMessage(NodeNotFoundError, message):
            graph.backwards_plan(("app_b", "0001"))

    def test_missing_parent_nodes(self):
        
        
        graph = MigrationGraph()
        graph.add_node(("app_a", "0001"), None)
        graph.add_node(("app_a", "0002"), None)
        graph.add_node(("app_a", "0003"), None)
        graph.add_node(("app_b", "0001"), None)
        graph.add_dependency("app_a.0003", ("app_a", "0003"), ("app_a", "0002"))
        graph.add_dependency("app_a.0002", ("app_a", "0002"), ("app_a", "0001"))
        msg = (
            "Migration app_a.0001 dependencies reference nonexistent parent node "
            "('app_b', '0002')"
        )
        with self.assertRaisesMessage(NodeNotFoundError, msg):
            graph.add_dependency("app_a.0001", ("app_a", "0001"), ("app_b", "0002"))

    def test_missing_child_nodes(self):
        
        
        graph = MigrationGraph()
        graph.add_node(("app_a", "0001"), None)
        msg = (
            "Migration app_a.0002 dependencies reference nonexistent child node "
            "('app_a', '0002')"
        )
        with self.assertRaisesMessage(NodeNotFoundError, msg):
            graph.add_dependency("app_a.0002", ("app_a", "0002"), ("app_a", "0001"))

    def test_validate_consistency_missing_parent(self):
        graph = MigrationGraph()
        graph.add_node(("app_a", "0001"), None)
        graph.add_dependency(
            "app_a.0001", ("app_a", "0001"), ("app_b", "0002"), skip_validation=True
        )
        msg = (
            "Migration app_a.0001 dependencies reference nonexistent parent node "
            "('app_b', '0002')"
        )
        with self.assertRaisesMessage(NodeNotFoundError, msg):
            graph.validate_consistency()

    def test_validate_consistency_missing_child(self):
        graph = MigrationGraph()
        graph.add_node(("app_b", "0002"), None)
        graph.add_dependency(
            "app_b.0002", ("app_a", "0001"), ("app_b", "0002"), skip_validation=True
        )
        msg = (
            "Migration app_b.0002 dependencies reference nonexistent child node "
            "('app_a', '0001')"
        )
        with self.assertRaisesMessage(NodeNotFoundError, msg):
            graph.validate_consistency()

    def test_validate_consistency_no_error(self):
        graph = MigrationGraph()
        graph.add_node(("app_a", "0001"), None)
        graph.add_node(("app_b", "0002"), None)
        graph.add_dependency(
            "app_a.0001", ("app_a", "0001"), ("app_b", "0002"), skip_validation=True
        )
        graph.validate_consistency()

    def test_validate_consistency_dummy(self):
        
        msg = "app_a.0001 (req'd by app_b.0002) is missing!"
        graph = MigrationGraph()
        graph.add_dummy_node(
            key=("app_a", "0001"), origin="app_b.0002", error_message=msg
        )
        with self.assertRaisesMessage(NodeNotFoundError, msg):
            graph.validate_consistency()

    def test_remove_replaced_nodes(self):
        
        
        graph = MigrationGraph()
        graph.add_dummy_node(
            key=("app_a", "0001"), origin="app_a.0002", error_message="BAD!"
        )
        graph.add_dummy_node(
            key=("app_a", "0002"), origin="app_b.0001", error_message="BAD!"
        )
        graph.add_dependency(
            "app_a.0002", ("app_a", "0002"), ("app_a", "0001"), skip_validation=True
        )
        
        graph.add_node(("app_c", "0001"), None)
        graph.add_node(("app_b", "0001"), None)
        graph.add_dependency(
            "app_a.0001", ("app_a", "0001"), ("app_c", "0001"), skip_validation=True
        )
        graph.add_dependency(
            "app_b.0001", ("app_b", "0001"), ("app_a", "0002"), skip_validation=True
        )
        
        msg = (
            "Unable to find replacement node ('app_a', '0001_squashed_0002'). It was "
            "either never added to the migration graph, or has been removed."
        )
        with self.assertRaisesMessage(NodeNotFoundError, msg):
            graph.remove_replaced_nodes(
                replacement=("app_a", "0001_squashed_0002"),
                replaced=[("app_a", "0001"), ("app_a", "0002")],
            )
        graph.add_node(("app_a", "0001_squashed_0002"), None)
        
        with self.assertRaisesMessage(NodeNotFoundError, "BAD!"):
            graph.validate_consistency()
        
        graph.remove_replaced_nodes(
            replacement=("app_a", "0001_squashed_0002"),
            replaced=[("app_a", "0001"), ("app_a", "0002")],
        )
        
        graph.validate_consistency()
        parent_node = graph.node_map[("app_c", "0001")]
        replacement_node = graph.node_map[("app_a", "0001_squashed_0002")]
        child_node = graph.node_map[("app_b", "0001")]
        self.assertIn(parent_node, replacement_node.parents)
        self.assertIn(replacement_node, parent_node.children)
        self.assertIn(child_node, replacement_node.children)
        self.assertIn(replacement_node, child_node.parents)

    def test_remove_replacement_node(self):
        
        
        graph = MigrationGraph()
        graph.add_node(("app_a", "0001"), None)
        graph.add_node(("app_a", "0002"), None)
        graph.add_dependency("app_a.0002", ("app_a", "0002"), ("app_a", "0001"))
        
        msg = (
            "Unable to remove replacement node ('app_a', '0001_squashed_0002'). It was"
            " either never added to the migration graph, or has been removed already."
        )
        with self.assertRaisesMessage(NodeNotFoundError, msg):
            graph.remove_replacement_node(
                replacement=("app_a", "0001_squashed_0002"),
                replaced=[("app_a", "0001"), ("app_a", "0002")],
            )
        graph.add_node(("app_a", "0001_squashed_0002"), None)
        
        graph.add_node(("app_b", "0001"), None)
        graph.add_dependency(
            "app_b.0001", ("app_b", "0001"), ("app_a", "0001_squashed_0002")
        )
        
        graph.remove_replacement_node(
            replacement=("app_a", "0001_squashed_0002"),
            replaced=[("app_a", "0001"), ("app_a", "0002")],
        )
        
        graph.validate_consistency()
        replaced_node = graph.node_map[("app_a", "0002")]
        child_node = graph.node_map[("app_b", "0001")]
        self.assertIn(child_node, replaced_node.children)
        self.assertIn(replaced_node, child_node.parents)
        
        
        other_replaced_node = graph.node_map[("app_a", "0001")]
        self.assertNotIn(child_node, other_replaced_node.children)
        self.assertNotIn(other_replaced_node, child_node.parents)

    def test_infinite_loop(self):
        
        graph = MigrationGraph()

        graph.add_node(("app_a", "0001"), None)
        graph.add_node(("app_b", "0001"), None)
        graph.add_node(("app_b", "0002"), None)
        graph.add_node(("app_c", "0001_squashed_0002"), None)

        graph.add_dependency(
            "app_b.0001", ("app_b", "0001"), ("app_c", "0001_squashed_0002")
        )
        graph.add_dependency("app_b.0002", ("app_b", "0002"), ("app_a", "0001"))
        graph.add_dependency("app_b.0002", ("app_b", "0002"), ("app_b", "0001"))
        graph.add_dependency(
            "app_c.0001_squashed_0002",
            ("app_c", "0001_squashed_0002"),
            ("app_b", "0002"),
        )

        with self.assertRaises(CircularDependencyError):
            graph.ensure_not_cyclic()

    def test_stringify(self):
        graph = MigrationGraph()
        self.assertEqual(str(graph), "Graph: 0 nodes, 0 edges")

        graph.add_node(("app_a", "0001"), None)
        graph.add_node(("app_a", "0002"), None)
        graph.add_node(("app_a", "0003"), None)
        graph.add_node(("app_b", "0001"), None)
        graph.add_node(("app_b", "0002"), None)
        graph.add_dependency("app_a.0002", ("app_a", "0002"), ("app_a", "0001"))
        graph.add_dependency("app_a.0003", ("app_a", "0003"), ("app_a", "0002"))
        graph.add_dependency("app_a.0003", ("app_a", "0003"), ("app_b", "0002"))

        self.assertEqual(str(graph), "Graph: 5 nodes, 3 edges")
        self.assertEqual(repr(graph), "<MigrationGraph: nodes=5, edges=3>")


class NodeTests(SimpleTestCase):
    def test_node_repr(self):
        node = Node(("app_a", "0001"))
        self.assertEqual(repr(node), "<Node: ('app_a', '0001')>")

    def test_node_str(self):
        node = Node(("app_a", "0001"))
        self.assertEqual(str(node), "('app_a', '0001')")

    def test_dummynode_repr(self):
        node = DummyNode(
            key=("app_a", "0001"),
            origin="app_a.0001",
            error_message="x is missing",
        )
        self.assertEqual(repr(node), "<DummyNode: ('app_a', '0001')>")