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

History | View | Annotate | Download (2.34 KB)

1 | 5cef0f13 | tiamilani | ```
#!/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!")` |