ioftools / networkxMiCe / networkxmaster / networkx / algorithms / tests / test_dominating.py @ 5cef0f13
History  View  Annotate  Download (1.32 KB)
1 
from nose.tools import assert_equal, assert_true, assert_false, raises 

2 
import networkx as nx 
3  
4  
5 
def test_dominating_set(): 
6 
G = nx.gnp_random_graph(100, 0.1) 
7 
D = nx.dominating_set(G) 
8 
assert_true(nx.is_dominating_set(G, D)) 
9 
D = nx.dominating_set(G, start_with=0)

10 
assert_true(nx.is_dominating_set(G, D)) 
11  
12  
13 
def test_complete(): 
14 
""" In complete graphs each node is a dominating set.

15 
Thus the dominating set has to be of cardinality 1.

16 
"""

17 
K4 = nx.complete_graph(4)

18 
assert_equal(len(nx.dominating_set(K4)), 1) 
19 
K5 = nx.complete_graph(5)

20 
assert_equal(len(nx.dominating_set(K5)), 1) 
21  
22  
23 
@raises(nx.NetworkXError)

24 
def test_raise_dominating_set(): 
25 
G = nx.path_graph(4)

26 
D = nx.dominating_set(G, start_with=10)

27  
28  
29 
def test_is_dominating_set(): 
30 
G = nx.path_graph(4)

31 
d = set([1, 3]) 
32 
assert_true(nx.is_dominating_set(G, d)) 
33 
d = set([0, 2]) 
34 
assert_true(nx.is_dominating_set(G, d)) 
35 
d = set([1]) 
36 
assert_false(nx.is_dominating_set(G, d)) 
37  
38  
39 
def test_wikipedia_is_dominating_set(): 
40 
"""Example from https://en.wikipedia.org/wiki/Dominating_set

41 
"""

42 
G = nx.cycle_graph(4)

43 
G.add_edges_from([(0, 4), (1, 4), (2, 5)]) 
44 
assert_true(nx.is_dominating_set(G, set([4, 3, 5]))) 
45 
assert_true(nx.is_dominating_set(G, set([0, 2]))) 
46 
assert_true(nx.is_dominating_set(G, set([1, 2]))) 