### comparison env/lib/python3.9/site-packages/networkx/algorithms/traversal/tests/test_edgebfs.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal 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)
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()
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()
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()
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_