Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/shortest_paths/tests/test_unweighted.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 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 |