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

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal inserted replaced
-1:000000000000 0:4f3585e2f14b
1 import networkx as nx
2
3
4 def validate_grid_path(r, c, s, t, p):
5 assert isinstance(p, list)
6 assert p[0] == s
7 assert p[-1] == t
8 s = ((s - 1) // c, (s - 1) % c)
9 t = ((t - 1) // c, (t - 1) % c)
10 assert len(p) == abs(t[0] - s[0]) + abs(t[1] - s[1]) + 1
11 p = [((u - 1) // c, (u - 1) % c) for u in p]
12 for u in p:
13 assert 0 <= u[0] < r
14 assert 0 <= u[1] < c
15 for u, v in zip(p[:-1], p[1:]):
16 assert (abs(v[0] - u[0]), abs(v[1] - u[1])) in [(0, 1), (1, 0)]
17
18
19 class TestUnweightedPath:
20 @classmethod
21 def setup_class(cls):
22 from networkx import convert_node_labels_to_integers as cnlti
23
24 cls.grid = cnlti(nx.grid_2d_graph(4, 4), first_label=1, ordering="sorted")
25 cls.cycle = nx.cycle_graph(7)
26 cls.directed_cycle = nx.cycle_graph(7, create_using=nx.DiGraph())
27
28 def test_bidirectional_shortest_path(self):
29 assert nx.bidirectional_shortest_path(self.cycle, 0, 3) == [0, 1, 2, 3]
30 assert nx.bidirectional_shortest_path(self.cycle, 0, 4) == [0, 6, 5, 4]
31 validate_grid_path(
32 4, 4, 1, 12, nx.bidirectional_shortest_path(self.grid, 1, 12)
33 )
34 assert nx.bidirectional_shortest_path(self.directed_cycle, 0, 3) == [0, 1, 2, 3]
35
36 def test_shortest_path_length(self):
37 assert nx.shortest_path_length(self.cycle, 0, 3) == 3
38 assert nx.shortest_path_length(self.grid, 1, 12) == 5
39 assert nx.shortest_path_length(self.directed_cycle, 0, 4) == 4
40 # now with weights
41 assert nx.shortest_path_length(self.cycle, 0, 3, weight=True) == 3
42 assert nx.shortest_path_length(self.grid, 1, 12, weight=True) == 5
43 assert nx.shortest_path_length(self.directed_cycle, 0, 4, weight=True) == 4
44
45 def test_single_source_shortest_path(self):
46 p = nx.single_source_shortest_path(self.directed_cycle, 3)
47 assert p[0] == [3, 4, 5, 6, 0]
48 p = nx.single_source_shortest_path(self.cycle, 0)
49 assert p[3] == [0, 1, 2, 3]
50 p = nx.single_source_shortest_path(self.cycle, 0, cutoff=0)
51 assert p == {0: [0]}
52
53 def test_single_source_shortest_path_length(self):
54 pl = nx.single_source_shortest_path_length
55 lengths = {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
56 assert dict(pl(self.cycle, 0)) == lengths
57 lengths = {0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6}
58 assert dict(pl(self.directed_cycle, 0)) == lengths
59
60 def test_single_target_shortest_path(self):
61 p = nx.single_target_shortest_path(self.directed_cycle, 0)
62 assert p[3] == [3, 4, 5, 6, 0]
63 p = nx.single_target_shortest_path(self.cycle, 0)
64 assert p[3] == [3, 2, 1, 0]
65 p = nx.single_target_shortest_path(self.cycle, 0, cutoff=0)
66 assert p == {0: [0]}
67
68 def test_single_target_shortest_path_length(self):
69 pl = nx.single_target_shortest_path_length
70 lengths = {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
71 assert dict(pl(self.cycle, 0)) == lengths
72 lengths = {0: 0, 1: 6, 2: 5, 3: 4, 4: 3, 5: 2, 6: 1}
73 assert dict(pl(self.directed_cycle, 0)) == lengths
74
75 def test_all_pairs_shortest_path(self):
76 p = dict(nx.all_pairs_shortest_path(self.cycle))
77 assert p[0][3] == [0, 1, 2, 3]
78 p = dict(nx.all_pairs_shortest_path(self.grid))
79 validate_grid_path(4, 4, 1, 12, p[1][12])
80
81 def test_all_pairs_shortest_path_length(self):
82 l = dict(nx.all_pairs_shortest_path_length(self.cycle))
83 assert l[0] == {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
84 l = dict(nx.all_pairs_shortest_path_length(self.grid))
85 assert l[1][16] == 6
86
87 def test_predecessor_path(self):
88 G = nx.path_graph(4)
89 assert nx.predecessor(G, 0) == {0: [], 1: [0], 2: [1], 3: [2]}
90 assert nx.predecessor(G, 0, 3) == [2]
91
92 def test_predecessor_cycle(self):
93 G = nx.cycle_graph(4)
94 pred = nx.predecessor(G, 0)
95 assert pred[0] == []
96 assert pred[1] == [0]
97 assert pred[2] in [[1, 3], [3, 1]]
98 assert pred[3] == [0]
99
100 def test_predecessor_cutoff(self):
101 G = nx.path_graph(4)
102 p = nx.predecessor(G, 0, 3)
103 assert 4 not in p
104
105 def test_predecessor_target(self):
106 G = nx.path_graph(4)
107 p = nx.predecessor(G, 0, 3)
108 assert p == [2]
109 p = nx.predecessor(G, 0, 3, cutoff=2)
110 assert p == []
111 p, s = nx.predecessor(G, 0, 3, return_seen=True)
112 assert p == [2]
113 assert s == 3
114 p, s = nx.predecessor(G, 0, 3, cutoff=2, return_seen=True)
115 assert p == []
116 assert s == -1