diff env/lib/python3.9/site-packages/networkx/algorithms/tests/test_sparsifiers.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/algorithms/tests/test_sparsifiers.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,137 @@
+"""Unit tests for the sparsifier computation functions."""
+import pytest
+import networkx as nx
+from networkx.utils import py_random_state
+
+
+_seed = 2
+
+
+def _test_spanner(G, spanner, stretch, weight=None):
+    """Test whether a spanner is valid.
+
+    This function tests whether the given spanner is a subgraph of the
+    given graph G with the same node set. It also tests for all shortest
+    paths whether they adhere to the given stretch.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+        The original graph for which the spanner was constructed.
+
+    spanner : NetworkX graph
+        The spanner to be tested.
+
+    stretch : float
+        The proclaimed stretch of the spanner.
+
+    weight : object
+        The edge attribute to use as distance.
+    """
+    # check node set
+    assert set(G.nodes()) == set(spanner.nodes())
+
+    # check edge set and weights
+    for u, v in spanner.edges():
+        assert G.has_edge(u, v)
+        if weight:
+            assert spanner[u][v][weight] == G[u][v][weight]
+
+    # check connectivity and stretch
+    original_length = dict(nx.shortest_path_length(G, weight=weight))
+    spanner_length = dict(nx.shortest_path_length(spanner, weight=weight))
+    for u in G.nodes():
+        for v in G.nodes():
+            if u in original_length and v in original_length[u]:
+                assert spanner_length[u][v] <= stretch * original_length[u][v]
+
+
+@py_random_state(1)
+def _assign_random_weights(G, seed=None):
+    """Assigns random weights to the edges of a graph.
+
+    Parameters
+    ----------
+
+    G : NetworkX graph
+        The original graph for which the spanner was constructed.
+
+    seed : integer, random_state, or None (default)
+        Indicator of random number generation state.
+        See :ref:`Randomness<randomness>`.
+    """
+    for u, v in G.edges():
+        G[u][v]["weight"] = seed.random()
+
+
+def test_spanner_trivial():
+    """Test a trivial spanner with stretch 1."""
+    G = nx.complete_graph(20)
+    spanner = nx.spanner(G, 1, seed=_seed)
+
+    for u, v in G.edges:
+        assert spanner.has_edge(u, v)
+
+
+def test_spanner_unweighted_complete_graph():
+    """Test spanner construction on a complete unweighted graph."""
+    G = nx.complete_graph(20)
+
+    spanner = nx.spanner(G, 4, seed=_seed)
+    _test_spanner(G, spanner, 4)
+
+    spanner = nx.spanner(G, 10, seed=_seed)
+    _test_spanner(G, spanner, 10)
+
+
+def test_spanner_weighted_complete_graph():
+    """Test spanner construction on a complete weighted graph."""
+    G = nx.complete_graph(20)
+    _assign_random_weights(G, seed=_seed)
+
+    spanner = nx.spanner(G, 4, weight="weight", seed=_seed)
+    _test_spanner(G, spanner, 4, weight="weight")
+
+    spanner = nx.spanner(G, 10, weight="weight", seed=_seed)
+    _test_spanner(G, spanner, 10, weight="weight")
+
+
+def test_spanner_unweighted_gnp_graph():
+    """Test spanner construction on an unweighted gnp graph."""
+    G = nx.gnp_random_graph(20, 0.4, seed=_seed)
+
+    spanner = nx.spanner(G, 4, seed=_seed)
+    _test_spanner(G, spanner, 4)
+
+    spanner = nx.spanner(G, 10, seed=_seed)
+    _test_spanner(G, spanner, 10)
+
+
+def test_spanner_weighted_gnp_graph():
+    """Test spanner construction on an weighted gnp graph."""
+    G = nx.gnp_random_graph(20, 0.4, seed=_seed)
+    _assign_random_weights(G, seed=_seed)
+
+    spanner = nx.spanner(G, 4, weight="weight", seed=_seed)
+    _test_spanner(G, spanner, 4, weight="weight")
+
+    spanner = nx.spanner(G, 10, weight="weight", seed=_seed)
+    _test_spanner(G, spanner, 10, weight="weight")
+
+
+def test_spanner_unweighted_disconnected_graph():
+    """Test spanner construction on a disconnected graph."""
+    G = nx.disjoint_union(nx.complete_graph(10), nx.complete_graph(10))
+
+    spanner = nx.spanner(G, 4, seed=_seed)
+    _test_spanner(G, spanner, 4)
+
+    spanner = nx.spanner(G, 10, seed=_seed)
+    _test_spanner(G, spanner, 10)
+
+
+def test_spanner_invalid_stretch():
+    """Check whether an invalid stretch is caught."""
+    with pytest.raises(ValueError):
+        G = nx.empty_graph()
+        nx.spanner(G, 0)