File size: 1,228 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 |
import pytest
import networkx as nx
def test_dominating_set():
G = nx.gnp_random_graph(100, 0.1)
D = nx.dominating_set(G)
assert nx.is_dominating_set(G, D)
D = nx.dominating_set(G, start_with=0)
assert nx.is_dominating_set(G, D)
def test_complete():
"""In complete graphs each node is a dominating set.
Thus the dominating set has to be of cardinality 1.
"""
K4 = nx.complete_graph(4)
assert len(nx.dominating_set(K4)) == 1
K5 = nx.complete_graph(5)
assert len(nx.dominating_set(K5)) == 1
def test_raise_dominating_set():
with pytest.raises(nx.NetworkXError):
G = nx.path_graph(4)
D = nx.dominating_set(G, start_with=10)
def test_is_dominating_set():
G = nx.path_graph(4)
d = {1, 3}
assert nx.is_dominating_set(G, d)
d = {0, 2}
assert nx.is_dominating_set(G, d)
d = {1}
assert not nx.is_dominating_set(G, d)
def test_wikipedia_is_dominating_set():
"""Example from https://en.wikipedia.org/wiki/Dominating_set"""
G = nx.cycle_graph(4)
G.add_edges_from([(0, 4), (1, 4), (2, 5)])
assert nx.is_dominating_set(G, {4, 3, 5})
assert nx.is_dominating_set(G, {0, 2})
assert nx.is_dominating_set(G, {1, 2})
|