two version of R2R are hereHEADmaster

1 files changed, 535 insertions, 0 deletions

diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/tests/test_planarity.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/tests/test_planarity.py
new file mode 100644
index 00000000..99bcff41
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/tests/test_planarity.py
@@ -0,0 +1,535 @@
+import pytest
+
+import networkx as nx
+from networkx.algorithms.planarity import (
+    check_planarity_recursive,
+    get_counterexample,
+    get_counterexample_recursive,
+)
+
+
+class TestLRPlanarity:
+    """Nose Unit tests for the :mod:`networkx.algorithms.planarity` module.
+
+    Tests three things:
+    1. Check that the result is correct
+        (returns planar if and only if the graph is actually planar)
+    2. In case a counter example is returned: Check if it is correct
+    3. In case an embedding is returned: Check if its actually an embedding
+    """
+
+    @staticmethod
+    def check_graph(G, is_planar=None):
+        """Raises an exception if the lr_planarity check returns a wrong result
+
+        Parameters
+        ----------
+        G : NetworkX graph
+        is_planar : bool
+            The expected result of the planarity check.
+            If set to None only counter example or embedding are verified.
+
+        """
+
+        # obtain results of planarity check
+        is_planar_lr, result = nx.check_planarity(G, True)
+        is_planar_lr_rec, result_rec = check_planarity_recursive(G, True)
+
+        if is_planar is not None:
+            # set a message for the assert
+            if is_planar:
+                msg = "Wrong planarity check result. Should be planar."
+            else:
+                msg = "Wrong planarity check result. Should be non-planar."
+
+            # check if the result is as expected
+            assert is_planar == is_planar_lr, msg
+            assert is_planar == is_planar_lr_rec, msg
+
+        if is_planar_lr:
+            # check embedding
+            check_embedding(G, result)
+            check_embedding(G, result_rec)
+        else:
+            # check counter example
+            check_counterexample(G, result)
+            check_counterexample(G, result_rec)
+
+    def test_simple_planar_graph(self):
+        e = [
+            (1, 2),
+            (2, 3),
+            (3, 4),
+            (4, 6),
+            (6, 7),
+            (7, 1),
+            (1, 5),
+            (5, 2),
+            (2, 4),
+            (4, 5),
+            (5, 7),
+        ]
+        self.check_graph(nx.Graph(e), is_planar=True)
+
+    def test_planar_with_selfloop(self):
+        e = [
+            (1, 1),
+            (2, 2),
+            (3, 3),
+            (4, 4),
+            (5, 5),
+            (1, 2),
+            (1, 3),
+            (1, 5),
+            (2, 5),
+            (2, 4),
+            (3, 4),
+            (3, 5),
+            (4, 5),
+        ]
+        self.check_graph(nx.Graph(e), is_planar=True)
+
+    def test_k3_3(self):
+        self.check_graph(nx.complete_bipartite_graph(3, 3), is_planar=False)
+
+    def test_k5(self):
+        self.check_graph(nx.complete_graph(5), is_planar=False)
+
+    def test_multiple_components_planar(self):
+        e = [(1, 2), (2, 3), (3, 1), (4, 5), (5, 6), (6, 4)]
+        self.check_graph(nx.Graph(e), is_planar=True)
+
+    def test_multiple_components_non_planar(self):
+        G = nx.complete_graph(5)
+        # add another planar component to the non planar component
+        # G stays non planar
+        G.add_edges_from([(6, 7), (7, 8), (8, 6)])
+        self.check_graph(G, is_planar=False)
+
+    def test_non_planar_with_selfloop(self):
+        G = nx.complete_graph(5)
+        # add self loops
+        for i in range(5):
+            G.add_edge(i, i)
+        self.check_graph(G, is_planar=False)
+
+    def test_non_planar1(self):
+        # tests a graph that has no subgraph directly isomorph to K5 or K3_3
+        e = [
+            (1, 5),
+            (1, 6),
+            (1, 7),
+            (2, 6),
+            (2, 3),
+            (3, 5),
+            (3, 7),
+            (4, 5),
+            (4, 6),
+            (4, 7),
+        ]
+        self.check_graph(nx.Graph(e), is_planar=False)
+
+    def test_loop(self):
+        # test a graph with a selfloop
+        e = [(1, 2), (2, 2)]
+        G = nx.Graph(e)
+        self.check_graph(G, is_planar=True)
+
+    def test_comp(self):
+        # test multiple component graph
+        e = [(1, 2), (3, 4)]
+        G = nx.Graph(e)
+        G.remove_edge(1, 2)
+        self.check_graph(G, is_planar=True)
+
+    def test_goldner_harary(self):
+        # test goldner-harary graph (a maximal planar graph)
+        e = [
+            (1, 2),
+            (1, 3),
+            (1, 4),
+            (1, 5),
+            (1, 7),
+            (1, 8),
+            (1, 10),
+            (1, 11),
+            (2, 3),
+            (2, 4),
+            (2, 6),
+            (2, 7),
+            (2, 9),
+            (2, 10),
+            (2, 11),
+            (3, 4),
+            (4, 5),
+            (4, 6),
+            (4, 7),
+            (5, 7),
+            (6, 7),
+            (7, 8),
+            (7, 9),
+            (7, 10),
+            (8, 10),
+            (9, 10),
+            (10, 11),
+        ]
+        G = nx.Graph(e)
+        self.check_graph(G, is_planar=True)
+
+    def test_planar_multigraph(self):
+        G = nx.MultiGraph([(1, 2), (1, 2), (1, 2), (1, 2), (2, 3), (3, 1)])
+        self.check_graph(G, is_planar=True)
+
+    def test_non_planar_multigraph(self):
+        G = nx.MultiGraph(nx.complete_graph(5))
+        G.add_edges_from([(1, 2)] * 5)
+        self.check_graph(G, is_planar=False)
+
+    def test_planar_digraph(self):
+        G = nx.DiGraph([(1, 2), (2, 3), (2, 4), (4, 1), (4, 2), (1, 4), (3, 2)])
+        self.check_graph(G, is_planar=True)
+
+    def test_non_planar_digraph(self):
+        G = nx.DiGraph(nx.complete_graph(5))
+        G.remove_edge(1, 2)
+        G.remove_edge(4, 1)
+        self.check_graph(G, is_planar=False)
+
+    def test_single_component(self):
+        # Test a graph with only a single node
+        G = nx.Graph()
+        G.add_node(1)
+        self.check_graph(G, is_planar=True)
+
+    def test_graph1(self):
+        G = nx.Graph(
+            [
+                (3, 10),
+                (2, 13),
+                (1, 13),
+                (7, 11),
+                (0, 8),
+                (8, 13),
+                (0, 2),
+                (0, 7),
+                (0, 10),
+                (1, 7),
+            ]
+        )
+        self.check_graph(G, is_planar=True)
+
+    def test_graph2(self):
+        G = nx.Graph(
+            [
+                (1, 2),
+                (4, 13),
+                (0, 13),
+                (4, 5),
+                (7, 10),
+                (1, 7),
+                (0, 3),
+                (2, 6),
+                (5, 6),
+                (7, 13),
+                (4, 8),
+                (0, 8),
+                (0, 9),
+                (2, 13),
+                (6, 7),
+                (3, 6),
+                (2, 8),
+            ]
+        )
+        self.check_graph(G, is_planar=False)
+
+    def test_graph3(self):
+        G = nx.Graph(
+            [
+                (0, 7),
+                (3, 11),
+                (3, 4),
+                (8, 9),
+                (4, 11),
+                (1, 7),
+                (1, 13),
+                (1, 11),
+                (3, 5),
+                (5, 7),
+                (1, 3),
+                (0, 4),
+                (5, 11),
+                (5, 13),
+            ]
+        )
+        self.check_graph(G, is_planar=False)
+
+    def test_counterexample_planar(self):
+        with pytest.raises(nx.NetworkXException):
+            # Try to get a counterexample of a planar graph
+            G = nx.Graph()
+            G.add_node(1)
+            get_counterexample(G)
+
+    def test_counterexample_planar_recursive(self):
+        with pytest.raises(nx.NetworkXException):
+            # Try to get a counterexample of a planar graph
+            G = nx.Graph()
+            G.add_node(1)
+            get_counterexample_recursive(G)
+
+    def test_edge_removal_from_planar_embedding(self):
+        # PlanarEmbedding.check_structure() must succeed after edge removal
+        edges = ((0, 1), (1, 2), (2, 3), (3, 4), (4, 0), (0, 2), (0, 3))
+        G = nx.Graph(edges)
+        cert, P = nx.check_planarity(G)
+        assert cert is True
+        P.remove_edge(0, 2)
+        self.check_graph(P, is_planar=True)
+        P.add_half_edge_ccw(1, 3, 2)
+        P.add_half_edge_cw(3, 1, 2)
+        self.check_graph(P, is_planar=True)
+        P.remove_edges_from(((0, 3), (1, 3)))
+        self.check_graph(P, is_planar=True)
+
+
+def check_embedding(G, embedding):
+    """Raises an exception if the combinatorial embedding is not correct
+
+    Parameters
+    ----------
+    G : NetworkX graph
+    embedding : a dict mapping nodes to a list of edges
+        This specifies the ordering of the outgoing edges from a node for
+        a combinatorial embedding
+
+    Notes
+    -----
+    Checks the following things:
+        - The type of the embedding is correct
+        - The nodes and edges match the original graph
+        - Every half edge has its matching opposite half edge
+        - No intersections of edges (checked by Euler's formula)
+    """
+
+    if not isinstance(embedding, nx.PlanarEmbedding):
+        raise nx.NetworkXException("Bad embedding. Not of type nx.PlanarEmbedding")
+
+    # Check structure
+    embedding.check_structure()
+
+    # Check that graphs are equivalent
+
+    assert set(G.nodes) == set(
+        embedding.nodes
+    ), "Bad embedding. Nodes don't match the original graph."
+
+    # Check that the edges are equal
+    g_edges = set()
+    for edge in G.edges:
+        if edge[0] != edge[1]:
+            g_edges.add((edge[0], edge[1]))
+            g_edges.add((edge[1], edge[0]))
+    assert g_edges == set(
+        embedding.edges
+    ), "Bad embedding. Edges don't match the original graph."
+
+
+def check_counterexample(G, sub_graph):
+    """Raises an exception if the counterexample is wrong.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+    subdivision_nodes : set
+        A set of nodes inducing a subgraph as a counterexample
+    """
+    # 1. Create the sub graph
+    sub_graph = nx.Graph(sub_graph)
+
+    # 2. Remove self loops
+    for u in sub_graph:
+        if sub_graph.has_edge(u, u):
+            sub_graph.remove_edge(u, u)
+
+    # keep track of nodes we might need to contract
+    contract = list(sub_graph)
+
+    # 3. Contract Edges
+    while len(contract) > 0:
+        contract_node = contract.pop()
+        if contract_node not in sub_graph:
+            # Node was already contracted
+            continue
+        degree = sub_graph.degree[contract_node]
+        # Check if we can remove the node
+        if degree == 2:
+            # Get the two neighbors
+            neighbors = iter(sub_graph[contract_node])
+            u = next(neighbors)
+            v = next(neighbors)
+            # Save nodes for later
+            contract.append(u)
+            contract.append(v)
+            # Contract edge
+            sub_graph.remove_node(contract_node)
+            sub_graph.add_edge(u, v)
+
+    # 4. Check for isomorphism with K5 or K3_3 graphs
+    if len(sub_graph) == 5:
+        if not nx.is_isomorphic(nx.complete_graph(5), sub_graph):
+            raise nx.NetworkXException("Bad counter example.")
+    elif len(sub_graph) == 6:
+        if not nx.is_isomorphic(nx.complete_bipartite_graph(3, 3), sub_graph):
+            raise nx.NetworkXException("Bad counter example.")
+    else:
+        raise nx.NetworkXException("Bad counter example.")
+
+
+class TestPlanarEmbeddingClass:
+    def test_add_half_edge(self):
+        embedding = nx.PlanarEmbedding()
+        embedding.add_half_edge(0, 1)
+        with pytest.raises(
+            nx.NetworkXException, match="Invalid clockwise reference node."
+        ):
+            embedding.add_half_edge(0, 2, cw=3)
+        with pytest.raises(
+            nx.NetworkXException, match="Invalid counterclockwise reference node."
+        ):
+            embedding.add_half_edge(0, 2, ccw=3)
+        with pytest.raises(
+            nx.NetworkXException, match="Only one of cw/ccw can be specified."
+        ):
+            embedding.add_half_edge(0, 2, cw=1, ccw=1)
+        with pytest.raises(
+            nx.NetworkXException,
+            match=(
+                r"Node already has out-half-edge\(s\), either"
+                " cw or ccw reference node required."
+            ),
+        ):
+            embedding.add_half_edge(0, 2)
+        # these should work
+        embedding.add_half_edge(0, 2, cw=1)
+        embedding.add_half_edge(0, 3, ccw=1)
+        assert sorted(embedding.edges(data=True)) == [
+            (0, 1, {"ccw": 2, "cw": 3}),
+            (0, 2, {"cw": 1, "ccw": 3}),
+            (0, 3, {"cw": 2, "ccw": 1}),
+        ]
+
+    def test_get_data(self):
+        embedding = self.get_star_embedding(4)
+        data = embedding.get_data()
+        data_cmp = {0: [3, 2, 1], 1: [0], 2: [0], 3: [0]}
+        assert data == data_cmp
+
+    def test_edge_removal(self):
+        embedding = nx.PlanarEmbedding()
+        embedding.set_data(
+            {
+                1: [2, 5, 7],
+                2: [1, 3, 4, 5],
+                3: [2, 4],
+                4: [3, 6, 5, 2],
+                5: [7, 1, 2, 4],
+                6: [4, 7],
+                7: [6, 1, 5],
+            }
+        )
+        # remove_edges_from() calls remove_edge(), so both are tested here
+        embedding.remove_edges_from(((5, 4), (1, 5)))
+        embedding.check_structure()
+        embedding_expected = nx.PlanarEmbedding()
+        embedding_expected.set_data(
+            {
+                1: [2, 7],
+                2: [1, 3, 4, 5],
+                3: [2, 4],
+                4: [3, 6, 2],
+                5: [7, 2],
+                6: [4, 7],
+                7: [6, 1, 5],
+            }
+        )
+        assert nx.utils.graphs_equal(embedding, embedding_expected)
+
+    def test_missing_edge_orientation(self):
+        embedding = nx.PlanarEmbedding({1: {2: {}}, 2: {1: {}}})
+        with pytest.raises(nx.NetworkXException):
+            # Invalid structure because the orientation of the edge was not set
+            embedding.check_structure()
+
+    def test_invalid_edge_orientation(self):
+        embedding = nx.PlanarEmbedding(
+            {
+                1: {2: {"cw": 2, "ccw": 2}},
+                2: {1: {"cw": 1, "ccw": 1}},
+                1: {3: {}},
+                3: {1: {}},
+            }
+        )
+        with pytest.raises(nx.NetworkXException):
+            embedding.check_structure()
+
+    def test_missing_half_edge(self):
+        embedding = nx.PlanarEmbedding()
+        embedding.add_half_edge(1, 2)
+        with pytest.raises(nx.NetworkXException):
+            # Invalid structure because other half edge is missing
+            embedding.check_structure()
+
+    def test_not_fulfilling_euler_formula(self):
+        embedding = nx.PlanarEmbedding()
+        for i in range(5):
+            ref = None
+            for j in range(5):
+                if i != j:
+                    embedding.add_half_edge(i, j, cw=ref)
+                    ref = j
+        with pytest.raises(nx.NetworkXException):
+            embedding.check_structure()
+
+    def test_missing_reference(self):
+        embedding = nx.PlanarEmbedding()
+        with pytest.raises(nx.NetworkXException, match="Invalid reference node."):
+            embedding.add_half_edge(1, 2, ccw=3)
+
+    def test_connect_components(self):
+        embedding = nx.PlanarEmbedding()
+        embedding.connect_components(1, 2)
+
+    def test_successful_face_traversal(self):
+        embedding = nx.PlanarEmbedding()
+        embedding.add_half_edge(1, 2)
+        embedding.add_half_edge(2, 1)
+        face = embedding.traverse_face(1, 2)
+        assert face == [1, 2]
+
+    def test_unsuccessful_face_traversal(self):
+        embedding = nx.PlanarEmbedding(
+            {1: {2: {"cw": 3, "ccw": 2}}, 2: {1: {"cw": 3, "ccw": 1}}}
+        )
+        with pytest.raises(nx.NetworkXException):
+            embedding.traverse_face(1, 2)
+
+    def test_forbidden_methods(self):
+        embedding = nx.PlanarEmbedding()
+        embedding.add_node(42)  # no exception
+        embedding.add_nodes_from([(23, 24)])  # no exception
+        with pytest.raises(NotImplementedError):
+            embedding.add_edge(1, 3)
+        with pytest.raises(NotImplementedError):
+            embedding.add_edges_from([(0, 2), (1, 4)])
+        with pytest.raises(NotImplementedError):
+            embedding.add_weighted_edges_from([(0, 2, 350), (1, 4, 125)])
+
+    @staticmethod
+    def get_star_embedding(n):
+        embedding = nx.PlanarEmbedding()
+        ref = None
+        for i in range(1, n):
+            embedding.add_half_edge(0, i, cw=ref)
+            ref = i
+            embedding.add_half_edge(i, 0)
+        return embedding