Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / approximation / tests / test_dominating_set.py @ 5cef0f13

History | View | Annotate | Download (2.34 KB)

1
#!/usr/bin/env python
2
from nose.tools import ok_
3
from nose.tools import eq_
4
import networkx as nx
5
from networkx.algorithms.approximation import min_weighted_dominating_set
6
from networkx.algorithms.approximation import min_edge_dominating_set
7

    
8

    
9
class TestMinWeightDominatingSet:
10

    
11
    def test_min_weighted_dominating_set(self):
12
        graph = nx.Graph()
13
        graph.add_edge(1, 2)
14
        graph.add_edge(1, 5)
15
        graph.add_edge(2, 3)
16
        graph.add_edge(2, 5)
17
        graph.add_edge(3, 4)
18
        graph.add_edge(3, 6)
19
        graph.add_edge(5, 6)
20

    
21
        vertices = set([1, 2, 3, 4, 5, 6])
22
        # due to ties, this might be hard to test tight bounds
23
        dom_set = min_weighted_dominating_set(graph)
24
        for vertex in vertices - dom_set:
25
            neighbors = set(graph.neighbors(vertex))
26
            ok_(len(neighbors & dom_set) > 0, "Non dominating set found!")
27

    
28
    def test_star_graph(self):
29
        """Tests that an approximate dominating set for the star graph,
30
        even when the center node does not have the smallest integer
31
        label, gives just the center node.
32

33
        For more information, see #1527.
34

35
        """
36
        # Create a star graph in which the center node has the highest
37
        # label instead of the lowest.
38
        G = nx.star_graph(10)
39
        G = nx.relabel_nodes(G, {0: 9, 9: 0})
40
        eq_(min_weighted_dominating_set(G), {9})
41

    
42
    def test_min_edge_dominating_set(self):
43
        graph = nx.path_graph(5)
44
        dom_set = min_edge_dominating_set(graph)
45

    
46
        # this is a crappy way to test, but good enough for now.
47
        for edge in graph.edges():
48
            if edge in dom_set:
49
                continue
50
            else:
51
                u, v = edge
52
                found = False
53
                for dom_edge in dom_set:
54
                    found |= u == dom_edge[0] or u == dom_edge[1]
55
                ok_(found, "Non adjacent edge found!")
56

    
57
        graph = nx.complete_graph(10)
58
        dom_set = min_edge_dominating_set(graph)
59

    
60
        # this is a crappy way to test, but good enough for now.
61
        for edge in graph.edges():
62
            if edge in dom_set:
63
                continue
64
            else:
65
                u, v = edge
66
                found = False
67
                for dom_edge in dom_set:
68
                    found |= u == dom_edge[0] or u == dom_edge[1]
69
                ok_(found, "Non adjacent edge found!")