Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/traversal/tests/test_edgedfs.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 | |
3 import networkx as nx | |
4 | |
5 edge_dfs = nx.algorithms.edge_dfs | |
6 | |
7 FORWARD = nx.algorithms.edgedfs.FORWARD | |
8 REVERSE = nx.algorithms.edgedfs.REVERSE | |
9 | |
10 # These tests can fail with hash randomization. The easiest and clearest way | |
11 # to write these unit tests is for the edges to be output in an expected total | |
12 # order, but we cannot guarantee the order amongst outgoing edges from a node, | |
13 # unless each class uses an ordered data structure for neighbors. This is | |
14 # painful to do with the current API. The alternative is that the tests are | |
15 # written (IMO confusingly) so that there is not a total order over the edges, | |
16 # but only a partial order. Due to the small size of the graphs, hopefully | |
17 # failures due to hash randomization will not occur. For an example of how | |
18 # this can fail, see TestEdgeDFS.test_multigraph. | |
19 | |
20 | |
21 class TestEdgeDFS: | |
22 @classmethod | |
23 def setup_class(cls): | |
24 cls.nodes = [0, 1, 2, 3] | |
25 cls.edges = [(0, 1), (1, 0), (1, 0), (2, 1), (3, 1)] | |
26 | |
27 def test_empty(self): | |
28 G = nx.Graph() | |
29 edges = list(edge_dfs(G)) | |
30 assert edges == [] | |
31 | |
32 def test_graph(self): | |
33 G = nx.Graph(self.edges) | |
34 x = list(edge_dfs(G, self.nodes)) | |
35 x_ = [(0, 1), (1, 2), (1, 3)] | |
36 assert x == x_ | |
37 | |
38 def test_digraph(self): | |
39 G = nx.DiGraph(self.edges) | |
40 x = list(edge_dfs(G, self.nodes)) | |
41 x_ = [(0, 1), (1, 0), (2, 1), (3, 1)] | |
42 assert x == x_ | |
43 | |
44 def test_digraph_orientation_invalid(self): | |
45 G = nx.DiGraph(self.edges) | |
46 edge_iterator = edge_dfs(G, self.nodes, orientation="hello") | |
47 pytest.raises(nx.NetworkXError, list, edge_iterator) | |
48 | |
49 def test_digraph_orientation_none(self): | |
50 G = nx.DiGraph(self.edges) | |
51 x = list(edge_dfs(G, self.nodes, orientation=None)) | |
52 x_ = [(0, 1), (1, 0), (2, 1), (3, 1)] | |
53 assert x == x_ | |
54 | |
55 def test_digraph_orientation_original(self): | |
56 G = nx.DiGraph(self.edges) | |
57 x = list(edge_dfs(G, self.nodes, orientation="original")) | |
58 x_ = [(0, 1, FORWARD), (1, 0, FORWARD), (2, 1, FORWARD), (3, 1, FORWARD)] | |
59 assert x == x_ | |
60 | |
61 def test_digraph2(self): | |
62 G = nx.DiGraph() | |
63 nx.add_path(G, range(4)) | |
64 x = list(edge_dfs(G, [0])) | |
65 x_ = [(0, 1), (1, 2), (2, 3)] | |
66 assert x == x_ | |
67 | |
68 def test_digraph_rev(self): | |
69 G = nx.DiGraph(self.edges) | |
70 x = list(edge_dfs(G, self.nodes, orientation="reverse")) | |
71 x_ = [(1, 0, REVERSE), (0, 1, REVERSE), (2, 1, REVERSE), (3, 1, REVERSE)] | |
72 assert x == x_ | |
73 | |
74 def test_digraph_rev2(self): | |
75 G = nx.DiGraph() | |
76 nx.add_path(G, range(4)) | |
77 x = list(edge_dfs(G, [3], orientation="reverse")) | |
78 x_ = [(2, 3, REVERSE), (1, 2, REVERSE), (0, 1, REVERSE)] | |
79 assert x == x_ | |
80 | |
81 def test_multigraph(self): | |
82 G = nx.MultiGraph(self.edges) | |
83 x = list(edge_dfs(G, self.nodes)) | |
84 x_ = [(0, 1, 0), (1, 0, 1), (0, 1, 2), (1, 2, 0), (1, 3, 0)] | |
85 # This is an example of where hash randomization can break. | |
86 # There are 3! * 2 alternative outputs, such as: | |
87 # [(0, 1, 1), (1, 0, 0), (0, 1, 2), (1, 3, 0), (1, 2, 0)] | |
88 # But note, the edges (1,2,0) and (1,3,0) always follow the (0,1,k) | |
89 # edges. So the algorithm only guarantees a partial order. A total | |
90 # order is guaranteed only if the graph data structures are ordered. | |
91 assert x == x_ | |
92 | |
93 def test_multidigraph(self): | |
94 G = nx.MultiDiGraph(self.edges) | |
95 x = list(edge_dfs(G, self.nodes)) | |
96 x_ = [(0, 1, 0), (1, 0, 0), (1, 0, 1), (2, 1, 0), (3, 1, 0)] | |
97 assert x == x_ | |
98 | |
99 def test_multidigraph_rev(self): | |
100 G = nx.MultiDiGraph(self.edges) | |
101 x = list(edge_dfs(G, self.nodes, orientation="reverse")) | |
102 x_ = [ | |
103 (1, 0, 0, REVERSE), | |
104 (0, 1, 0, REVERSE), | |
105 (1, 0, 1, REVERSE), | |
106 (2, 1, 0, REVERSE), | |
107 (3, 1, 0, REVERSE), | |
108 ] | |
109 assert x == x_ | |
110 | |
111 def test_digraph_ignore(self): | |
112 G = nx.DiGraph(self.edges) | |
113 x = list(edge_dfs(G, self.nodes, orientation="ignore")) | |
114 x_ = [(0, 1, FORWARD), (1, 0, FORWARD), (2, 1, REVERSE), (3, 1, REVERSE)] | |
115 assert x == x_ | |
116 | |
117 def test_digraph_ignore2(self): | |
118 G = nx.DiGraph() | |
119 nx.add_path(G, range(4)) | |
120 x = list(edge_dfs(G, [0], orientation="ignore")) | |
121 x_ = [(0, 1, FORWARD), (1, 2, FORWARD), (2, 3, FORWARD)] | |
122 assert x == x_ | |
123 | |
124 def test_multidigraph_ignore(self): | |
125 G = nx.MultiDiGraph(self.edges) | |
126 x = list(edge_dfs(G, self.nodes, orientation="ignore")) | |
127 x_ = [ | |
128 (0, 1, 0, FORWARD), | |
129 (1, 0, 0, FORWARD), | |
130 (1, 0, 1, REVERSE), | |
131 (2, 1, 0, REVERSE), | |
132 (3, 1, 0, REVERSE), | |
133 ] | |
134 assert x == x_ |