Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/traversal/tests/test_dfs.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 class TestDFS: | |
5 @classmethod | |
6 def setup_class(cls): | |
7 # simple graph | |
8 G = nx.Graph() | |
9 G.add_edges_from([(0, 1), (1, 2), (1, 3), (2, 4), (3, 4)]) | |
10 cls.G = G | |
11 # simple graph, disconnected | |
12 D = nx.Graph() | |
13 D.add_edges_from([(0, 1), (2, 3)]) | |
14 cls.D = D | |
15 | |
16 def test_preorder_nodes(self): | |
17 assert list(nx.dfs_preorder_nodes(self.G, source=0)) == [0, 1, 2, 4, 3] | |
18 assert list(nx.dfs_preorder_nodes(self.D)) == [0, 1, 2, 3] | |
19 | |
20 def test_postorder_nodes(self): | |
21 assert list(nx.dfs_postorder_nodes(self.G, source=0)) == [3, 4, 2, 1, 0] | |
22 assert list(nx.dfs_postorder_nodes(self.D)) == [1, 0, 3, 2] | |
23 | |
24 def test_successor(self): | |
25 assert nx.dfs_successors(self.G, source=0) == {0: [1], 1: [2], 2: [4], 4: [3]} | |
26 assert nx.dfs_successors(self.D) == {0: [1], 2: [3]} | |
27 | |
28 def test_predecessor(self): | |
29 assert nx.dfs_predecessors(self.G, source=0) == {1: 0, 2: 1, 3: 4, 4: 2} | |
30 assert nx.dfs_predecessors(self.D) == {1: 0, 3: 2} | |
31 | |
32 def test_dfs_tree(self): | |
33 exp_nodes = sorted(self.G.nodes()) | |
34 exp_edges = [(0, 1), (1, 2), (2, 4), (4, 3)] | |
35 # Search from first node | |
36 T = nx.dfs_tree(self.G, source=0) | |
37 assert sorted(T.nodes()) == exp_nodes | |
38 assert sorted(T.edges()) == exp_edges | |
39 # Check source=None | |
40 T = nx.dfs_tree(self.G, source=None) | |
41 assert sorted(T.nodes()) == exp_nodes | |
42 assert sorted(T.edges()) == exp_edges | |
43 # Check source=None is the default | |
44 T = nx.dfs_tree(self.G) | |
45 assert sorted(T.nodes()) == exp_nodes | |
46 assert sorted(T.edges()) == exp_edges | |
47 | |
48 def test_dfs_edges(self): | |
49 edges = nx.dfs_edges(self.G, source=0) | |
50 assert list(edges) == [(0, 1), (1, 2), (2, 4), (4, 3)] | |
51 edges = nx.dfs_edges(self.D) | |
52 assert list(edges) == [(0, 1), (2, 3)] | |
53 | |
54 def test_dfs_labeled_edges(self): | |
55 edges = list(nx.dfs_labeled_edges(self.G, source=0)) | |
56 forward = [(u, v) for (u, v, d) in edges if d == "forward"] | |
57 assert forward == [(0, 0), (0, 1), (1, 2), (2, 4), (4, 3)] | |
58 | |
59 def test_dfs_labeled_disconnected_edges(self): | |
60 edges = list(nx.dfs_labeled_edges(self.D)) | |
61 forward = [(u, v) for (u, v, d) in edges if d == "forward"] | |
62 assert forward == [(0, 0), (0, 1), (2, 2), (2, 3)] | |
63 | |
64 def test_dfs_tree_isolates(self): | |
65 G = nx.Graph() | |
66 G.add_node(1) | |
67 G.add_node(2) | |
68 T = nx.dfs_tree(G, source=1) | |
69 assert sorted(T.nodes()) == [1] | |
70 assert sorted(T.edges()) == [] | |
71 T = nx.dfs_tree(G, source=None) | |
72 assert sorted(T.nodes()) == [1, 2] | |
73 assert sorted(T.edges()) == [] | |
74 | |
75 | |
76 class TestDepthLimitedSearch: | |
77 @classmethod | |
78 def setup_class(cls): | |
79 # a tree | |
80 G = nx.Graph() | |
81 nx.add_path(G, [0, 1, 2, 3, 4, 5, 6]) | |
82 nx.add_path(G, [2, 7, 8, 9, 10]) | |
83 cls.G = G | |
84 # a disconnected graph | |
85 D = nx.Graph() | |
86 D.add_edges_from([(0, 1), (2, 3)]) | |
87 nx.add_path(D, [2, 7, 8, 9, 10]) | |
88 cls.D = D | |
89 | |
90 def test_dls_preorder_nodes(self): | |
91 assert list(nx.dfs_preorder_nodes(self.G, source=0, depth_limit=2)) == [0, 1, 2] | |
92 assert list(nx.dfs_preorder_nodes(self.D, source=1, depth_limit=2)) == ([1, 0]) | |
93 | |
94 def test_dls_postorder_nodes(self): | |
95 assert list(nx.dfs_postorder_nodes(self.G, source=3, depth_limit=3)) == [ | |
96 1, | |
97 7, | |
98 2, | |
99 5, | |
100 4, | |
101 3, | |
102 ] | |
103 assert list(nx.dfs_postorder_nodes(self.D, source=2, depth_limit=2)) == ( | |
104 [3, 7, 2] | |
105 ) | |
106 | |
107 def test_dls_successor(self): | |
108 result = nx.dfs_successors(self.G, source=4, depth_limit=3) | |
109 assert {n: set(v) for n, v in result.items()} == { | |
110 2: {1, 7}, | |
111 3: {2}, | |
112 4: {3, 5}, | |
113 5: {6}, | |
114 } | |
115 result = nx.dfs_successors(self.D, source=7, depth_limit=2) | |
116 assert {n: set(v) for n, v in result.items()} == {8: {9}, 2: {3}, 7: {8, 2}} | |
117 | |
118 def test_dls_predecessor(self): | |
119 assert nx.dfs_predecessors(self.G, source=0, depth_limit=3) == { | |
120 1: 0, | |
121 2: 1, | |
122 3: 2, | |
123 7: 2, | |
124 } | |
125 assert nx.dfs_predecessors(self.D, source=2, depth_limit=3) == { | |
126 8: 7, | |
127 9: 8, | |
128 3: 2, | |
129 7: 2, | |
130 } | |
131 | |
132 def test_dls_tree(self): | |
133 T = nx.dfs_tree(self.G, source=3, depth_limit=1) | |
134 assert sorted(T.edges()) == [(3, 2), (3, 4)] | |
135 | |
136 def test_dls_edges(self): | |
137 edges = nx.dfs_edges(self.G, source=9, depth_limit=4) | |
138 assert list(edges) == [(9, 8), (8, 7), (7, 2), (2, 1), (2, 3), (9, 10)] | |
139 | |
140 def test_dls_labeled_edges(self): | |
141 edges = list(nx.dfs_labeled_edges(self.G, source=5, depth_limit=1)) | |
142 forward = [(u, v) for (u, v, d) in edges if d == "forward"] | |
143 assert forward == [(5, 5), (5, 4), (5, 6)] | |
144 | |
145 def test_dls_labeled_disconnected_edges(self): | |
146 edges = list(nx.dfs_labeled_edges(self.G, source=6, depth_limit=2)) | |
147 forward = [(u, v) for (u, v, d) in edges if d == "forward"] | |
148 assert forward == [(6, 6), (6, 5), (5, 4)] |