Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_chordal.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 pytest | |
2 import networkx as nx | |
3 | |
4 | |
5 class TestMCS: | |
6 @classmethod | |
7 def setup_class(cls): | |
8 # simple graph | |
9 connected_chordal_G = nx.Graph() | |
10 connected_chordal_G.add_edges_from( | |
11 [ | |
12 (1, 2), | |
13 (1, 3), | |
14 (2, 3), | |
15 (2, 4), | |
16 (3, 4), | |
17 (3, 5), | |
18 (3, 6), | |
19 (4, 5), | |
20 (4, 6), | |
21 (5, 6), | |
22 ] | |
23 ) | |
24 cls.connected_chordal_G = connected_chordal_G | |
25 | |
26 chordal_G = nx.Graph() | |
27 chordal_G.add_edges_from( | |
28 [ | |
29 (1, 2), | |
30 (1, 3), | |
31 (2, 3), | |
32 (2, 4), | |
33 (3, 4), | |
34 (3, 5), | |
35 (3, 6), | |
36 (4, 5), | |
37 (4, 6), | |
38 (5, 6), | |
39 (7, 8), | |
40 ] | |
41 ) | |
42 chordal_G.add_node(9) | |
43 cls.chordal_G = chordal_G | |
44 | |
45 non_chordal_G = nx.Graph() | |
46 non_chordal_G.add_edges_from([(1, 2), (1, 3), (2, 4), (2, 5), (3, 4), (3, 5)]) | |
47 cls.non_chordal_G = non_chordal_G | |
48 | |
49 def test_is_chordal(self): | |
50 assert not nx.is_chordal(self.non_chordal_G) | |
51 assert nx.is_chordal(self.chordal_G) | |
52 assert nx.is_chordal(self.connected_chordal_G) | |
53 assert nx.is_chordal(nx.complete_graph(3)) | |
54 assert nx.is_chordal(nx.cycle_graph(3)) | |
55 assert not nx.is_chordal(nx.cycle_graph(5)) | |
56 | |
57 def test_induced_nodes(self): | |
58 G = nx.generators.classic.path_graph(10) | |
59 Induced_nodes = nx.find_induced_nodes(G, 1, 9, 2) | |
60 assert Induced_nodes == {1, 2, 3, 4, 5, 6, 7, 8, 9} | |
61 pytest.raises( | |
62 nx.NetworkXTreewidthBoundExceeded, nx.find_induced_nodes, G, 1, 9, 1 | |
63 ) | |
64 Induced_nodes = nx.find_induced_nodes(self.chordal_G, 1, 6) | |
65 assert Induced_nodes == {1, 2, 4, 6} | |
66 pytest.raises(nx.NetworkXError, nx.find_induced_nodes, self.non_chordal_G, 1, 5) | |
67 | |
68 def test_chordal_find_cliques(self): | |
69 cliques = { | |
70 frozenset([9]), | |
71 frozenset([7, 8]), | |
72 frozenset([1, 2, 3]), | |
73 frozenset([2, 3, 4]), | |
74 frozenset([3, 4, 5, 6]), | |
75 } | |
76 assert nx.chordal_graph_cliques(self.chordal_G) == cliques | |
77 | |
78 def test_chordal_find_cliques_path(self): | |
79 G = nx.path_graph(10) | |
80 cliqueset = nx.chordal_graph_cliques(G) | |
81 for (u, v) in G.edges(): | |
82 assert frozenset([u, v]) in cliqueset or frozenset([v, u]) in cliqueset | |
83 | |
84 def test_chordal_find_cliquesCC(self): | |
85 cliques = {frozenset([1, 2, 3]), frozenset([2, 3, 4]), frozenset([3, 4, 5, 6])} | |
86 cgc = nx.chordal_graph_cliques | |
87 assert cgc(self.connected_chordal_G) == cliques | |
88 | |
89 def test_complete_to_chordal_graph(self): | |
90 fgrg = nx.fast_gnp_random_graph | |
91 test_graphs = [ | |
92 nx.barbell_graph(6, 2), | |
93 nx.cycle_graph(15), | |
94 nx.wheel_graph(20), | |
95 nx.grid_graph([10, 4]), | |
96 nx.ladder_graph(15), | |
97 nx.star_graph(5), | |
98 nx.bull_graph(), | |
99 fgrg(20, 0.3, seed=1), | |
100 ] | |
101 for G in test_graphs: | |
102 H, a = nx.complete_to_chordal_graph(G) | |
103 assert nx.is_chordal(H) | |
104 assert len(a) == H.number_of_nodes() | |
105 if nx.is_chordal(G): | |
106 assert G.number_of_edges() == H.number_of_edges() | |
107 assert set(a.values()) == {0} | |
108 else: | |
109 assert len(set(a.values())) == H.number_of_nodes() |