Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/approximation/tests/test_dominating_set.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 import networkx as nx | |
2 from networkx.algorithms.approximation import min_weighted_dominating_set | |
3 from networkx.algorithms.approximation import min_edge_dominating_set | |
4 | |
5 | |
6 class TestMinWeightDominatingSet: | |
7 def test_min_weighted_dominating_set(self): | |
8 graph = nx.Graph() | |
9 graph.add_edge(1, 2) | |
10 graph.add_edge(1, 5) | |
11 graph.add_edge(2, 3) | |
12 graph.add_edge(2, 5) | |
13 graph.add_edge(3, 4) | |
14 graph.add_edge(3, 6) | |
15 graph.add_edge(5, 6) | |
16 | |
17 vertices = {1, 2, 3, 4, 5, 6} | |
18 # due to ties, this might be hard to test tight bounds | |
19 dom_set = min_weighted_dominating_set(graph) | |
20 for vertex in vertices - dom_set: | |
21 neighbors = set(graph.neighbors(vertex)) | |
22 assert len(neighbors & dom_set) > 0, "Non dominating set found!" | |
23 | |
24 def test_star_graph(self): | |
25 """Tests that an approximate dominating set for the star graph, | |
26 even when the center node does not have the smallest integer | |
27 label, gives just the center node. | |
28 | |
29 For more information, see #1527. | |
30 | |
31 """ | |
32 # Create a star graph in which the center node has the highest | |
33 # label instead of the lowest. | |
34 G = nx.star_graph(10) | |
35 G = nx.relabel_nodes(G, {0: 9, 9: 0}) | |
36 assert min_weighted_dominating_set(G) == {9} | |
37 | |
38 def test_min_edge_dominating_set(self): | |
39 graph = nx.path_graph(5) | |
40 dom_set = min_edge_dominating_set(graph) | |
41 | |
42 # this is a crappy way to test, but good enough for now. | |
43 for edge in graph.edges(): | |
44 if edge in dom_set: | |
45 continue | |
46 else: | |
47 u, v = edge | |
48 found = False | |
49 for dom_edge in dom_set: | |
50 found |= u == dom_edge[0] or u == dom_edge[1] | |
51 assert found, "Non adjacent edge found!" | |
52 | |
53 graph = nx.complete_graph(10) | |
54 dom_set = min_edge_dominating_set(graph) | |
55 | |
56 # this is a crappy way to test, but good enough for now. | |
57 for edge in graph.edges(): | |
58 if edge in dom_set: | |
59 continue | |
60 else: | |
61 u, v = edge | |
62 found = False | |
63 for dom_edge in dom_set: | |
64 found |= u == dom_edge[0] or u == dom_edge[1] | |
65 assert found, "Non adjacent edge found!" |