Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/traversal/tests/test_edgebfs.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_bfs = nx.edge_bfs | |
6 | |
7 FORWARD = nx.algorithms.edgedfs.FORWARD | |
8 REVERSE = nx.algorithms.edgedfs.REVERSE | |
9 | |
10 | |
11 class TestEdgeBFS: | |
12 @classmethod | |
13 def setup_class(cls): | |
14 cls.nodes = [0, 1, 2, 3] | |
15 cls.edges = [(0, 1), (1, 0), (1, 0), (2, 0), (2, 1), (3, 1)] | |
16 | |
17 def test_empty(self): | |
18 G = nx.Graph() | |
19 edges = list(edge_bfs(G)) | |
20 assert edges == [] | |
21 | |
22 def test_graph_single_source(self): | |
23 G = nx.Graph(self.edges) | |
24 G.add_edge(4, 5) | |
25 x = list(edge_bfs(G, [0])) | |
26 x_ = [(0, 1), (0, 2), (1, 2), (1, 3)] | |
27 assert x == x_ | |
28 | |
29 def test_graph(self): | |
30 G = nx.Graph(self.edges) | |
31 x = list(edge_bfs(G, self.nodes)) | |
32 x_ = [(0, 1), (0, 2), (1, 2), (1, 3)] | |
33 assert x == x_ | |
34 | |
35 def test_digraph(self): | |
36 G = nx.DiGraph(self.edges) | |
37 x = list(edge_bfs(G, self.nodes)) | |
38 x_ = [(0, 1), (1, 0), (2, 0), (2, 1), (3, 1)] | |
39 assert x == x_ | |
40 | |
41 def test_digraph_orientation_invalid(self): | |
42 G = nx.DiGraph(self.edges) | |
43 edge_iterator = edge_bfs(G, self.nodes, orientation="hello") | |
44 pytest.raises(nx.NetworkXError, list, edge_iterator) | |
45 | |
46 def test_digraph_orientation_none(self): | |
47 G = nx.DiGraph(self.edges) | |
48 x = list(edge_bfs(G, self.nodes, orientation=None)) | |
49 x_ = [(0, 1), (1, 0), (2, 0), (2, 1), (3, 1)] | |
50 assert x == x_ | |
51 | |
52 def test_digraph_orientation_original(self): | |
53 G = nx.DiGraph(self.edges) | |
54 x = list(edge_bfs(G, self.nodes, orientation="original")) | |
55 x_ = [ | |
56 (0, 1, FORWARD), | |
57 (1, 0, FORWARD), | |
58 (2, 0, FORWARD), | |
59 (2, 1, FORWARD), | |
60 (3, 1, FORWARD), | |
61 ] | |
62 assert x == x_ | |
63 | |
64 def test_digraph2(self): | |
65 G = nx.DiGraph() | |
66 nx.add_path(G, range(4)) | |
67 x = list(edge_bfs(G, [0])) | |
68 x_ = [(0, 1), (1, 2), (2, 3)] | |
69 assert x == x_ | |
70 | |
71 def test_digraph_rev(self): | |
72 G = nx.DiGraph(self.edges) | |
73 x = list(edge_bfs(G, self.nodes, orientation="reverse")) | |
74 x_ = [ | |
75 (1, 0, REVERSE), | |
76 (2, 0, REVERSE), | |
77 (0, 1, REVERSE), | |
78 (2, 1, REVERSE), | |
79 (3, 1, REVERSE), | |
80 ] | |
81 assert x == x_ | |
82 | |
83 def test_digraph_rev2(self): | |
84 G = nx.DiGraph() | |
85 nx.add_path(G, range(4)) | |
86 x = list(edge_bfs(G, [3], orientation="reverse")) | |
87 x_ = [(2, 3, REVERSE), (1, 2, REVERSE), (0, 1, REVERSE)] | |
88 assert x == x_ | |
89 | |
90 def test_multigraph(self): | |
91 G = nx.MultiGraph(self.edges) | |
92 x = list(edge_bfs(G, self.nodes)) | |
93 x_ = [(0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 2, 0), (1, 2, 0), (1, 3, 0)] | |
94 # This is an example of where hash randomization can break. | |
95 # There are 3! * 2 alternative outputs, such as: | |
96 # [(0, 1, 1), (1, 0, 0), (0, 1, 2), (1, 3, 0), (1, 2, 0)] | |
97 # But note, the edges (1,2,0) and (1,3,0) always follow the (0,1,k) | |
98 # edges. So the algorithm only guarantees a partial order. A total | |
99 # order is guaranteed only if the graph data structures are ordered. | |
100 assert x == x_ | |
101 | |
102 def test_multidigraph(self): | |
103 G = nx.MultiDiGraph(self.edges) | |
104 x = list(edge_bfs(G, self.nodes)) | |
105 x_ = [(0, 1, 0), (1, 0, 0), (1, 0, 1), (2, 0, 0), (2, 1, 0), (3, 1, 0)] | |
106 assert x == x_ | |
107 | |
108 def test_multidigraph_rev(self): | |
109 G = nx.MultiDiGraph(self.edges) | |
110 x = list(edge_bfs(G, self.nodes, orientation="reverse")) | |
111 x_ = [ | |
112 (1, 0, 0, REVERSE), | |
113 (1, 0, 1, REVERSE), | |
114 (2, 0, 0, REVERSE), | |
115 (0, 1, 0, REVERSE), | |
116 (2, 1, 0, REVERSE), | |
117 (3, 1, 0, REVERSE), | |
118 ] | |
119 assert x == x_ | |
120 | |
121 def test_digraph_ignore(self): | |
122 G = nx.DiGraph(self.edges) | |
123 x = list(edge_bfs(G, self.nodes, orientation="ignore")) | |
124 x_ = [ | |
125 (0, 1, FORWARD), | |
126 (1, 0, REVERSE), | |
127 (2, 0, REVERSE), | |
128 (2, 1, REVERSE), | |
129 (3, 1, REVERSE), | |
130 ] | |
131 assert x == x_ | |
132 | |
133 def test_digraph_ignore2(self): | |
134 G = nx.DiGraph() | |
135 nx.add_path(G, range(4)) | |
136 x = list(edge_bfs(G, [0], orientation="ignore")) | |
137 x_ = [(0, 1, FORWARD), (1, 2, FORWARD), (2, 3, FORWARD)] | |
138 assert x == x_ | |
139 | |
140 def test_multidigraph_ignore(self): | |
141 G = nx.MultiDiGraph(self.edges) | |
142 x = list(edge_bfs(G, self.nodes, orientation="ignore")) | |
143 x_ = [ | |
144 (0, 1, 0, FORWARD), | |
145 (1, 0, 0, REVERSE), | |
146 (1, 0, 1, REVERSE), | |
147 (2, 0, 0, REVERSE), | |
148 (2, 1, 0, REVERSE), | |
149 (3, 1, 0, REVERSE), | |
150 ] | |
151 assert x == x_ |