File size: 1,865 Bytes
57db94b |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
"""
Tests for maximal (not maximum) independent sets.
"""
import random
import pytest
import networkx as nx
def test_random_seed():
G = nx.empty_graph(5)
assert nx.maximal_independent_set(G, seed=1) == [1, 0, 3, 2, 4]
@pytest.mark.parametrize("graph", [nx.complete_graph(5), nx.complete_graph(55)])
def test_K5(graph):
"""Maximal independent set for complete graphs"""
assert all(nx.maximal_independent_set(graph, [n]) == [n] for n in graph)
def test_exceptions():
"""Bad input should raise exception."""
G = nx.florentine_families_graph()
pytest.raises(nx.NetworkXUnfeasible, nx.maximal_independent_set, G, ["Smith"])
pytest.raises(
nx.NetworkXUnfeasible, nx.maximal_independent_set, G, ["Salviati", "Pazzi"]
)
# MaximalIndependentSet is not implemented for directed graphs
pytest.raises(nx.NetworkXNotImplemented, nx.maximal_independent_set, nx.DiGraph(G))
def test_florentine_family():
G = nx.florentine_families_graph()
indep = nx.maximal_independent_set(G, ["Medici", "Bischeri"])
assert set(indep) == {
"Medici",
"Bischeri",
"Castellani",
"Pazzi",
"Ginori",
"Lamberteschi",
}
def test_bipartite():
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():
"""Generate 5 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.erdos_renyi_graph(i * 10 + 1, random.random())
IS = nx.maximal_independent_set(G)
assert G.subgraph(IS).number_of_edges() == 0
nbrs_of_MIS = set.union(*(set(G.neighbors(v)) for v in IS))
assert all(v in nbrs_of_MIS for v in set(G.nodes()).difference(IS))
|