Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_mis.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """ | |
2 Tests for maximal (not maximum) independent sets. | |
3 | |
4 """ | |
5 | |
6 import pytest | |
7 import networkx as nx | |
8 import random | |
9 | |
10 | |
11 class TestMaximalIndependantSet: | |
12 def setup(self): | |
13 self.florentine = nx.Graph() | |
14 self.florentine.add_edge("Acciaiuoli", "Medici") | |
15 self.florentine.add_edge("Castellani", "Peruzzi") | |
16 self.florentine.add_edge("Castellani", "Strozzi") | |
17 self.florentine.add_edge("Castellani", "Barbadori") | |
18 self.florentine.add_edge("Medici", "Barbadori") | |
19 self.florentine.add_edge("Medici", "Ridolfi") | |
20 self.florentine.add_edge("Medici", "Tornabuoni") | |
21 self.florentine.add_edge("Medici", "Albizzi") | |
22 self.florentine.add_edge("Medici", "Salviati") | |
23 self.florentine.add_edge("Salviati", "Pazzi") | |
24 self.florentine.add_edge("Peruzzi", "Strozzi") | |
25 self.florentine.add_edge("Peruzzi", "Bischeri") | |
26 self.florentine.add_edge("Strozzi", "Ridolfi") | |
27 self.florentine.add_edge("Strozzi", "Bischeri") | |
28 self.florentine.add_edge("Ridolfi", "Tornabuoni") | |
29 self.florentine.add_edge("Tornabuoni", "Guadagni") | |
30 self.florentine.add_edge("Albizzi", "Ginori") | |
31 self.florentine.add_edge("Albizzi", "Guadagni") | |
32 self.florentine.add_edge("Bischeri", "Guadagni") | |
33 self.florentine.add_edge("Guadagni", "Lamberteschi") | |
34 | |
35 def test_random_seed(self): | |
36 G = nx.complete_graph(5) | |
37 for node in G: | |
38 assert nx.maximal_independent_set(G, [node], seed=1) == [node] | |
39 | |
40 def test_K5(self): | |
41 """Maximal independent set: K5""" | |
42 G = nx.complete_graph(5) | |
43 for node in G: | |
44 assert nx.maximal_independent_set(G, [node]) == [node] | |
45 | |
46 def test_K55(self): | |
47 """Maximal independent set: K55""" | |
48 G = nx.complete_graph(55) | |
49 for node in G: | |
50 assert nx.maximal_independent_set(G, [node]) == [node] | |
51 | |
52 def test_exception(self): | |
53 """Bad input should raise exception.""" | |
54 G = self.florentine | |
55 pytest.raises(nx.NetworkXUnfeasible, nx.maximal_independent_set, G, ["Smith"]) | |
56 pytest.raises( | |
57 nx.NetworkXUnfeasible, nx.maximal_independent_set, G, ["Salviati", "Pazzi"] | |
58 ) | |
59 | |
60 def test_digraph_exception(self): | |
61 G = nx.DiGraph([(1, 2), (3, 4)]) | |
62 pytest.raises(nx.NetworkXNotImplemented, nx.maximal_independent_set, G) | |
63 | |
64 def test_florentine_family(self): | |
65 G = self.florentine | |
66 indep = nx.maximal_independent_set(G, ["Medici", "Bischeri"]) | |
67 assert sorted(indep) == sorted( | |
68 ["Medici", "Bischeri", "Castellani", "Pazzi", "Ginori", "Lamberteschi"] | |
69 ) | |
70 | |
71 def test_bipartite(self): | |
72 G = nx.complete_bipartite_graph(12, 34) | |
73 indep = nx.maximal_independent_set(G, [4, 5, 9, 10]) | |
74 assert sorted(indep) == list(range(12)) | |
75 | |
76 def test_random_graphs(self): | |
77 """Generate 50 random graphs of different types and sizes and | |
78 make sure that all sets are independent and maximal.""" | |
79 for i in range(0, 50, 10): | |
80 G = nx.random_graphs.erdos_renyi_graph(i * 10 + 1, random.random()) | |
81 IS = nx.maximal_independent_set(G) | |
82 assert not list(G.subgraph(IS).edges()) | |
83 neighbors_of_MIS = set.union(*(set(G.neighbors(v)) for v in IS)) | |
84 for v in set(G.nodes()).difference(IS): | |
85 assert v in neighbors_of_MIS |