ioftools / networkxMiCe / networkxmaster / 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!")
