view env/lib/python3.9/site-packages/networkx/algorithms/components/tests/test_strongly_connected.py @ 0:4f3585e2f14b draft default tip

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

import pytest
import networkx as nx
from networkx import NetworkXNotImplemented


class TestStronglyConnected:
    @classmethod
    def setup_class(cls):
        cls.gc = []
        G = nx.DiGraph()
        G.add_edges_from(
            [
                (1, 2),
                (2, 3),
                (2, 8),
                (3, 4),
                (3, 7),
                (4, 5),
                (5, 3),
                (5, 6),
                (7, 4),
                (7, 6),
                (8, 1),
                (8, 7),
            ]
        )
        C = {frozenset([3, 4, 5, 7]), frozenset([1, 2, 8]), frozenset([6])}
        cls.gc.append((G, C))

        G = nx.DiGraph()
        G.add_edges_from([(1, 2), (1, 3), (1, 4), (4, 2), (3, 4), (2, 3)])
        C = {frozenset([2, 3, 4]), frozenset([1])}
        cls.gc.append((G, C))

        G = nx.DiGraph()
        G.add_edges_from([(1, 2), (2, 3), (3, 2), (2, 1)])
        C = {frozenset([1, 2, 3])}
        cls.gc.append((G, C))

        # Eppstein's tests
        G = nx.DiGraph({0: [1], 1: [2, 3], 2: [4, 5], 3: [4, 5], 4: [6], 5: [], 6: []})
        C = {
            frozenset([0]),
            frozenset([1]),
            frozenset([2]),
            frozenset([3]),
            frozenset([4]),
            frozenset([5]),
            frozenset([6]),
        }
        cls.gc.append((G, C))

        G = nx.DiGraph({0: [1], 1: [2, 3, 4], 2: [0, 3], 3: [4], 4: [3]})
        C = {frozenset([0, 1, 2]), frozenset([3, 4])}
        cls.gc.append((G, C))

    def test_tarjan(self):
        scc = nx.strongly_connected_components
        for G, C in self.gc:
            assert {frozenset(g) for g in scc(G)} == C

    def test_tarjan_recursive(self):
        scc = nx.strongly_connected_components_recursive
        for G, C in self.gc:
            assert {frozenset(g) for g in scc(G)} == C

    def test_kosaraju(self):
        scc = nx.kosaraju_strongly_connected_components
        for G, C in self.gc:
            assert {frozenset(g) for g in scc(G)} == C

    def test_number_strongly_connected_components(self):
        ncc = nx.number_strongly_connected_components
        for G, C in self.gc:
            assert ncc(G) == len(C)

    def test_is_strongly_connected(self):
        for G, C in self.gc:
            if len(C) == 1:
                assert nx.is_strongly_connected(G)
            else:
                assert not nx.is_strongly_connected(G)

    def test_contract_scc1(self):
        G = nx.DiGraph()
        G.add_edges_from(
            [
                (1, 2),
                (2, 3),
                (2, 11),
                (2, 12),
                (3, 4),
                (4, 3),
                (4, 5),
                (5, 6),
                (6, 5),
                (6, 7),
                (7, 8),
                (7, 9),
                (7, 10),
                (8, 9),
                (9, 7),
                (10, 6),
                (11, 2),
                (11, 4),
                (11, 6),
                (12, 6),
                (12, 11),
            ]
        )
        scc = list(nx.strongly_connected_components(G))
        cG = nx.condensation(G, scc)
        # DAG
        assert nx.is_directed_acyclic_graph(cG)
        # nodes
        assert sorted(cG.nodes()) == [0, 1, 2, 3]
        # edges
        mapping = {}
        for i, component in enumerate(scc):
            for n in component:
                mapping[n] = i
        edge = (mapping[2], mapping[3])
        assert cG.has_edge(*edge)
        edge = (mapping[2], mapping[5])
        assert cG.has_edge(*edge)
        edge = (mapping[3], mapping[5])
        assert cG.has_edge(*edge)

    def test_contract_scc_isolate(self):
        # Bug found and fixed in [1687].
        G = nx.DiGraph()
        G.add_edge(1, 2)
        G.add_edge(2, 1)
        scc = list(nx.strongly_connected_components(G))
        cG = nx.condensation(G, scc)
        assert list(cG.nodes()) == [0]
        assert list(cG.edges()) == []

    def test_contract_scc_edge(self):
        G = nx.DiGraph()
        G.add_edge(1, 2)
        G.add_edge(2, 1)
        G.add_edge(2, 3)
        G.add_edge(3, 4)
        G.add_edge(4, 3)
        scc = list(nx.strongly_connected_components(G))
        cG = nx.condensation(G, scc)
        assert sorted(cG.nodes()) == [0, 1]
        if 1 in scc[0]:
            edge = (0, 1)
        else:
            edge = (1, 0)
        assert list(cG.edges()) == [edge]

    def test_condensation_mapping_and_members(self):
        G, C = self.gc[1]
        C = sorted(C, key=len, reverse=True)
        cG = nx.condensation(G)
        mapping = cG.graph["mapping"]
        assert all(n in G for n in mapping)
        assert all(0 == cN for n, cN in mapping.items() if n in C[0])
        assert all(1 == cN for n, cN in mapping.items() if n in C[1])
        for n, d in cG.nodes(data=True):
            assert set(C[n]) == cG.nodes[n]["members"]

    def test_null_graph(self):
        G = nx.DiGraph()
        assert list(nx.strongly_connected_components(G)) == []
        assert list(nx.kosaraju_strongly_connected_components(G)) == []
        assert list(nx.strongly_connected_components_recursive(G)) == []
        assert len(nx.condensation(G)) == 0
        pytest.raises(
            nx.NetworkXPointlessConcept, nx.is_strongly_connected, nx.DiGraph()
        )

    def test_connected_raise(self):
        G = nx.Graph()
        pytest.raises(NetworkXNotImplemented, nx.strongly_connected_components, G)
        pytest.raises(
            NetworkXNotImplemented, nx.kosaraju_strongly_connected_components, G
        )
        pytest.raises(
            NetworkXNotImplemented, nx.strongly_connected_components_recursive, G
        )
        pytest.raises(NetworkXNotImplemented, nx.is_strongly_connected, G)
        pytest.raises(
            nx.NetworkXPointlessConcept, nx.is_strongly_connected, nx.DiGraph()
        )
        pytest.raises(NetworkXNotImplemented, nx.condensation, G)


#    Commented out due to variability on Travis-CI hardware/operating systems
#    def test_linear_time(self):
#        # See Issue #2831
#        count = 100  # base case
#        dg = nx.DiGraph()
#        dg.add_nodes_from([0, 1])
#        for i in range(2, count):
#            dg.add_node(i)
#            dg.add_edge(i, 1)
#            dg.add_edge(0, i)
#        t = time.time()
#        ret = tuple(nx.strongly_connected_components(dg))
#        dt = time.time() - t
#
#        count = 200
#        dg = nx.DiGraph()
#        dg.add_nodes_from([0, 1])
#        for i in range(2, count):
#            dg.add_node(i)
#            dg.add_edge(i, 1)
#            dg.add_edge(0, i)
#        t = time.time()
#        ret = tuple(nx.strongly_connected_components(dg))
#        dt2 = time.time() - t
#        assert_less(dt2, dt * 2.3)  # should be 2 times longer for this graph