diff env/lib/python3.9/site-packages/networkx/linalg/tests/test_algebraic_connectivity.py @ 0:4f3585e2f14b draft default tip

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/env/lib/python3.9/site-packages/networkx/linalg/tests/test_algebraic_connectivity.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,365 @@
+from math import sqrt
+
+import pytest
+
+numpy = pytest.importorskip("numpy")
+numpy.linalg = pytest.importorskip("numpy.linalg")
+scipy = pytest.importorskip("scipy")
+scipy.sparse = pytest.importorskip("scipy.sparse")
+
+
+import networkx as nx
+from networkx.testing import almost_equal
+
+try:
+    from scikits.sparse.cholmod import cholesky
+
+    _cholesky = cholesky
+except ImportError:
+    _cholesky = None
+
+if _cholesky is None:
+    methods = ("tracemin_pcg", "tracemin_lu", "lanczos", "lobpcg")
+else:
+    methods = ("tracemin_pcg", "tracemin_chol", "tracemin_lu", "lanczos", "lobpcg")
+
+
+def check_eigenvector(A, l, x):
+    nx = numpy.linalg.norm(x)
+    # Check zeroness.
+    assert not almost_equal(nx, 0)
+    y = A * x
+    ny = numpy.linalg.norm(y)
+    # Check collinearity.
+    assert almost_equal(numpy.dot(x, y), nx * ny)
+    # Check eigenvalue.
+    assert almost_equal(ny, l * nx)
+
+
+class TestAlgebraicConnectivity:
+    @pytest.mark.parametrize("method", methods)
+    def test_directed(self, method):
+        G = nx.DiGraph()
+        pytest.raises(
+            nx.NetworkXNotImplemented, nx.algebraic_connectivity, G, method=method
+        )
+        pytest.raises(nx.NetworkXNotImplemented, nx.fiedler_vector, G, method=method)
+
+    @pytest.mark.parametrize("method", methods)
+    def test_null_and_singleton(self, method):
+        G = nx.Graph()
+        pytest.raises(nx.NetworkXError, nx.algebraic_connectivity, G, method=method)
+        pytest.raises(nx.NetworkXError, nx.fiedler_vector, G, method=method)
+        G.add_edge(0, 0)
+        pytest.raises(nx.NetworkXError, nx.algebraic_connectivity, G, method=method)
+        pytest.raises(nx.NetworkXError, nx.fiedler_vector, G, method=method)
+
+    @pytest.mark.parametrize("method", methods)
+    def test_disconnected(self, method):
+        G = nx.Graph()
+        G.add_nodes_from(range(2))
+        assert nx.algebraic_connectivity(G) == 0
+        pytest.raises(nx.NetworkXError, nx.fiedler_vector, G, method=method)
+        G.add_edge(0, 1, weight=0)
+        assert nx.algebraic_connectivity(G) == 0
+        pytest.raises(nx.NetworkXError, nx.fiedler_vector, G, method=method)
+
+    def test_unrecognized_method(self):
+        G = nx.path_graph(4)
+        pytest.raises(nx.NetworkXError, nx.algebraic_connectivity, G, method="unknown")
+        pytest.raises(nx.NetworkXError, nx.fiedler_vector, G, method="unknown")
+
+    @pytest.mark.parametrize("method", methods)
+    def test_two_nodes(self, method):
+        G = nx.Graph()
+        G.add_edge(0, 1, weight=1)
+        A = nx.laplacian_matrix(G)
+        assert almost_equal(nx.algebraic_connectivity(G, tol=1e-12, method=method), 2)
+        x = nx.fiedler_vector(G, tol=1e-12, method=method)
+        check_eigenvector(A, 2, x)
+
+    @pytest.mark.parametrize("method", methods)
+    def test_two_nodes_multigraph(self, method):
+        G = nx.MultiGraph()
+        G.add_edge(0, 0, spam=1e8)
+        G.add_edge(0, 1, spam=1)
+        G.add_edge(0, 1, spam=-2)
+        A = -3 * nx.laplacian_matrix(G, weight="spam")
+        assert almost_equal(
+            nx.algebraic_connectivity(G, weight="spam", tol=1e-12, method=method), 6
+        )
+        x = nx.fiedler_vector(G, weight="spam", tol=1e-12, method=method)
+        check_eigenvector(A, 6, x)
+
+    def test_abbreviation_of_method(self):
+        G = nx.path_graph(8)
+        A = nx.laplacian_matrix(G)
+        sigma = 2 - sqrt(2 + sqrt(2))
+        ac = nx.algebraic_connectivity(G, tol=1e-12, method="tracemin")
+        assert almost_equal(ac, sigma)
+        x = nx.fiedler_vector(G, tol=1e-12, method="tracemin")
+        check_eigenvector(A, sigma, x)
+
+    @pytest.mark.parametrize("method", methods)
+    def test_path(self, method):
+        G = nx.path_graph(8)
+        A = nx.laplacian_matrix(G)
+        sigma = 2 - sqrt(2 + sqrt(2))
+        ac = nx.algebraic_connectivity(G, tol=1e-12, method=method)
+        assert almost_equal(ac, sigma)
+        x = nx.fiedler_vector(G, tol=1e-12, method=method)
+        check_eigenvector(A, sigma, x)
+
+    @pytest.mark.parametrize("method", methods)
+    def test_problematic_graph_issue_2381(self, method):
+        G = nx.path_graph(4)
+        G.add_edges_from([(4, 2), (5, 1)])
+        A = nx.laplacian_matrix(G)
+        sigma = 0.438447187191
+        ac = nx.algebraic_connectivity(G, tol=1e-12, method=method)
+        assert almost_equal(ac, sigma)
+        x = nx.fiedler_vector(G, tol=1e-12, method=method)
+        check_eigenvector(A, sigma, x)
+
+    @pytest.mark.parametrize("method", methods)
+    def test_cycle(self, method):
+        G = nx.cycle_graph(8)
+        A = nx.laplacian_matrix(G)
+        sigma = 2 - sqrt(2)
+        ac = nx.algebraic_connectivity(G, tol=1e-12, method=method)
+        assert almost_equal(ac, sigma)
+        x = nx.fiedler_vector(G, tol=1e-12, method=method)
+        check_eigenvector(A, sigma, x)
+
+    @pytest.mark.parametrize("method", methods)
+    def test_seed_argument(self, method):
+        G = nx.cycle_graph(8)
+        A = nx.laplacian_matrix(G)
+        sigma = 2 - sqrt(2)
+        ac = nx.algebraic_connectivity(G, tol=1e-12, method=method, seed=1)
+        assert almost_equal(ac, sigma)
+        x = nx.fiedler_vector(G, tol=1e-12, method=method, seed=1)
+        check_eigenvector(A, sigma, x)
+
+    @pytest.mark.parametrize(
+        ("normalized", "sigma", "laplacian_fn"),
+        (
+            (False, 0.2434017461399311, nx.laplacian_matrix),
+            (True, 0.08113391537997749, nx.normalized_laplacian_matrix),
+        ),
+    )
+    @pytest.mark.parametrize("method", methods)
+    def test_buckminsterfullerene(self, normalized, sigma, laplacian_fn, method):
+        G = nx.Graph(
+            [
+                (1, 10),
+                (1, 41),
+                (1, 59),
+                (2, 12),
+                (2, 42),
+                (2, 60),
+                (3, 6),
+                (3, 43),
+                (3, 57),
+                (4, 8),
+                (4, 44),
+                (4, 58),
+                (5, 13),
+                (5, 56),
+                (5, 57),
+                (6, 10),
+                (6, 31),
+                (7, 14),
+                (7, 56),
+                (7, 58),
+                (8, 12),
+                (8, 32),
+                (9, 23),
+                (9, 53),
+                (9, 59),
+                (10, 15),
+                (11, 24),
+                (11, 53),
+                (11, 60),
+                (12, 16),
+                (13, 14),
+                (13, 25),
+                (14, 26),
+                (15, 27),
+                (15, 49),
+                (16, 28),
+                (16, 50),
+                (17, 18),
+                (17, 19),
+                (17, 54),
+                (18, 20),
+                (18, 55),
+                (19, 23),
+                (19, 41),
+                (20, 24),
+                (20, 42),
+                (21, 31),
+                (21, 33),
+                (21, 57),
+                (22, 32),
+                (22, 34),
+                (22, 58),
+                (23, 24),
+                (25, 35),
+                (25, 43),
+                (26, 36),
+                (26, 44),
+                (27, 51),
+                (27, 59),
+                (28, 52),
+                (28, 60),
+                (29, 33),
+                (29, 34),
+                (29, 56),
+                (30, 51),
+                (30, 52),
+                (30, 53),
+                (31, 47),
+                (32, 48),
+                (33, 45),
+                (34, 46),
+                (35, 36),
+                (35, 37),
+                (36, 38),
+                (37, 39),
+                (37, 49),
+                (38, 40),
+                (38, 50),
+                (39, 40),
+                (39, 51),
+                (40, 52),
+                (41, 47),
+                (42, 48),
+                (43, 49),
+                (44, 50),
+                (45, 46),
+                (45, 54),
+                (46, 55),
+                (47, 54),
+                (48, 55),
+            ]
+        )
+        A = laplacian_fn(G)
+        try:
+            assert almost_equal(
+                nx.algebraic_connectivity(
+                    G, normalized=normalized, tol=1e-12, method=method
+                ),
+                sigma,
+            )
+            x = nx.fiedler_vector(G, normalized=normalized, tol=1e-12, method=method)
+            check_eigenvector(A, sigma, x)
+        except nx.NetworkXError as e:
+            if e.args not in (
+                ("Cholesky solver unavailable.",),
+                ("LU solver unavailable.",),
+            ):
+                raise
+
+
+class TestSpectralOrdering:
+    _graphs = (nx.Graph, nx.DiGraph, nx.MultiGraph, nx.MultiDiGraph)
+
+    @pytest.mark.parametrize("graph", _graphs)
+    def test_nullgraph(self, graph):
+        G = graph()
+        pytest.raises(nx.NetworkXError, nx.spectral_ordering, G)
+
+    @pytest.mark.parametrize("graph", _graphs)
+    def test_singleton(self, graph):
+        G = graph()
+        G.add_node("x")
+        assert nx.spectral_ordering(G) == ["x"]
+        G.add_edge("x", "x", weight=33)
+        G.add_edge("x", "x", weight=33)
+        assert nx.spectral_ordering(G) == ["x"]
+
+    def test_unrecognized_method(self):
+        G = nx.path_graph(4)
+        pytest.raises(nx.NetworkXError, nx.spectral_ordering, G, method="unknown")
+
+    @pytest.mark.parametrize("method", methods)
+    def test_three_nodes(self, method):
+        G = nx.Graph()
+        G.add_weighted_edges_from([(1, 2, 1), (1, 3, 2), (2, 3, 1)], weight="spam")
+        order = nx.spectral_ordering(G, weight="spam", method=method)
+        assert set(order) == set(G)
+        assert {1, 3} in (set(order[:-1]), set(order[1:]))
+
+    @pytest.mark.parametrize("method", methods)
+    def test_three_nodes_multigraph(self, method):
+        G = nx.MultiDiGraph()
+        G.add_weighted_edges_from([(1, 2, 1), (1, 3, 2), (2, 3, 1), (2, 3, 2)])
+        order = nx.spectral_ordering(G, method=method)
+        assert set(order) == set(G)
+        assert {2, 3} in (set(order[:-1]), set(order[1:]))
+
+    @pytest.mark.parametrize("method", methods)
+    def test_path(self, method):
+        # based on setup_class numpy is installed if we get here
+        from numpy.random import shuffle
+
+        path = list(range(10))
+        shuffle(path)
+        G = nx.Graph()
+        nx.add_path(G, path)
+        order = nx.spectral_ordering(G, method=method)
+        assert order in [path, list(reversed(path))]
+
+    @pytest.mark.parametrize("method", methods)
+    def test_seed_argument(self, method):
+        # based on setup_class numpy is installed if we get here
+        from numpy.random import shuffle
+
+        path = list(range(10))
+        shuffle(path)
+        G = nx.Graph()
+        nx.add_path(G, path)
+        order = nx.spectral_ordering(G, method=method, seed=1)
+        assert order in [path, list(reversed(path))]
+
+    @pytest.mark.parametrize("method", methods)
+    def test_disconnected(self, method):
+        G = nx.Graph()
+        nx.add_path(G, range(0, 10, 2))
+        nx.add_path(G, range(1, 10, 2))
+        order = nx.spectral_ordering(G, method=method)
+        assert set(order) == set(G)
+        seqs = [
+            list(range(0, 10, 2)),
+            list(range(8, -1, -2)),
+            list(range(1, 10, 2)),
+            list(range(9, -1, -2)),
+        ]
+        assert order[:5] in seqs
+        assert order[5:] in seqs
+
+    @pytest.mark.parametrize(
+        ("normalized", "expected_order"),
+        (
+            (False, [[1, 2, 0, 3, 4, 5, 6, 9, 7, 8], [8, 7, 9, 6, 5, 4, 3, 0, 2, 1]]),
+            (True, [[1, 2, 3, 0, 4, 5, 9, 6, 7, 8], [8, 7, 6, 9, 5, 4, 0, 3, 2, 1]]),
+        ),
+    )
+    @pytest.mark.parametrize("method", methods)
+    def test_cycle(self, normalized, expected_order, method):
+        path = list(range(10))
+        G = nx.Graph()
+        nx.add_path(G, path, weight=5)
+        G.add_edge(path[-1], path[0], weight=1)
+        A = nx.laplacian_matrix(G).todense()
+        try:
+            order = nx.spectral_ordering(G, normalized=normalized, method=method)
+        except nx.NetworkXError as e:
+            if e.args not in (
+                ("Cholesky solver unavailable.",),
+                ("LU solver unavailable.",),
+            ):
+                raise
+        else:
+            assert order in expected_order