diff env/lib/python3.9/site-packages/networkx/algorithms/tests/test_mis.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_mis.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,85 @@
+"""
+Tests for maximal (not maximum) independent sets.
+
+"""
+
+import pytest
+import networkx as nx
+import random
+
+
+class TestMaximalIndependantSet:
+    def setup(self):
+        self.florentine = nx.Graph()
+        self.florentine.add_edge("Acciaiuoli", "Medici")
+        self.florentine.add_edge("Castellani", "Peruzzi")
+        self.florentine.add_edge("Castellani", "Strozzi")
+        self.florentine.add_edge("Castellani", "Barbadori")
+        self.florentine.add_edge("Medici", "Barbadori")
+        self.florentine.add_edge("Medici", "Ridolfi")
+        self.florentine.add_edge("Medici", "Tornabuoni")
+        self.florentine.add_edge("Medici", "Albizzi")
+        self.florentine.add_edge("Medici", "Salviati")
+        self.florentine.add_edge("Salviati", "Pazzi")
+        self.florentine.add_edge("Peruzzi", "Strozzi")
+        self.florentine.add_edge("Peruzzi", "Bischeri")
+        self.florentine.add_edge("Strozzi", "Ridolfi")
+        self.florentine.add_edge("Strozzi", "Bischeri")
+        self.florentine.add_edge("Ridolfi", "Tornabuoni")
+        self.florentine.add_edge("Tornabuoni", "Guadagni")
+        self.florentine.add_edge("Albizzi", "Ginori")
+        self.florentine.add_edge("Albizzi", "Guadagni")
+        self.florentine.add_edge("Bischeri", "Guadagni")
+        self.florentine.add_edge("Guadagni", "Lamberteschi")
+
+    def test_random_seed(self):
+        G = nx.complete_graph(5)
+        for node in G:
+            assert nx.maximal_independent_set(G, [node], seed=1) == [node]
+
+    def test_K5(self):
+        """Maximal independent set: K5"""
+        G = nx.complete_graph(5)
+        for node in G:
+            assert nx.maximal_independent_set(G, [node]) == [node]
+
+    def test_K55(self):
+        """Maximal independent set: K55"""
+        G = nx.complete_graph(55)
+        for node in G:
+            assert nx.maximal_independent_set(G, [node]) == [node]
+
+    def test_exception(self):
+        """Bad input should raise exception."""
+        G = self.florentine
+        pytest.raises(nx.NetworkXUnfeasible, nx.maximal_independent_set, G, ["Smith"])
+        pytest.raises(
+            nx.NetworkXUnfeasible, nx.maximal_independent_set, G, ["Salviati", "Pazzi"]
+        )
+
+    def test_digraph_exception(self):
+        G = nx.DiGraph([(1, 2), (3, 4)])
+        pytest.raises(nx.NetworkXNotImplemented, nx.maximal_independent_set, G)
+
+    def test_florentine_family(self):
+        G = self.florentine
+        indep = nx.maximal_independent_set(G, ["Medici", "Bischeri"])
+        assert sorted(indep) == sorted(
+            ["Medici", "Bischeri", "Castellani", "Pazzi", "Ginori", "Lamberteschi"]
+        )
+
+    def test_bipartite(self):
+        G = nx.complete_bipartite_graph(12, 34)
+        indep = nx.maximal_independent_set(G, [4, 5, 9, 10])
+        assert sorted(indep) == list(range(12))
+
+    def test_random_graphs(self):
+        """Generate 50 random graphs of different types and sizes and
+        make sure that all sets are independent and maximal."""
+        for i in range(0, 50, 10):
+            G = nx.random_graphs.erdos_renyi_graph(i * 10 + 1, random.random())
+            IS = nx.maximal_independent_set(G)
+            assert not list(G.subgraph(IS).edges())
+            neighbors_of_MIS = set.union(*(set(G.neighbors(v)) for v in IS))
+            for v in set(G.nodes()).difference(IS):
+                assert v in neighbors_of_MIS