Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / 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])))