ioftools / networkxMiCe / networkxmaster / networkx / algorithms / tests / test_lowest_common_ancestors.py @ 5cef0f13
History  View  Annotate  Download (11.2 KB)
1 
from nose.tools import * 

2 
from itertools import chain, combinations, product 
3  
4 
import networkx as nx 
5  
6 
tree_all_pairs_lca = nx.tree_all_pairs_lowest_common_ancestor 
7 
all_pairs_lca = nx.all_pairs_lowest_common_ancestor 
8  
9  
10 
def get_pair(dictionary, n1, n2): 
11 
if (n1, n2) in dictionary: 
12 
return dictionary[n1, n2]

13 
else:

14 
return dictionary[n2, n1]

15  
16  
17 
class TestTreeLCA(object): 
18 
def setUp(self): 
19 
self.DG = nx.DiGraph()

20 
edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)] 
21 
self.DG.add_edges_from(edges)

22 
self.ans = dict(tree_all_pairs_lca(self.DG, 0)) 
23 
gold = dict([((n, n), n) for n in self.DG]) 
24 
gold.update(dict(((0, i), 0) for i in range(1, 7))) 
25 
gold.update({(1, 2): 0, 
26 
(1, 3): 1, 
27 
(1, 4): 1, 
28 
(1, 5): 0, 
29 
(1, 6): 0, 
30 
(2, 3): 0, 
31 
(2, 4): 0, 
32 
(2, 5): 2, 
33 
(2, 6): 2, 
34 
(3, 4): 1, 
35 
(3, 5): 0, 
36 
(3, 6): 0, 
37 
(4, 5): 0, 
38 
(4, 6): 0, 
39 
(5, 6): 2}) 
40  
41 
self.gold = gold

42  
43 
@staticmethod

44 
def assert_has_same_pairs(d1, d2): 
45 
for (a, b) in ((min(pair), max(pair)) for pair in chain(d1, d2)): 
46 
assert_equal(get_pair(d1, a, b), get_pair(d2, a, b)) 
47  
48 
def test_tree_all_pairs_lowest_common_ancestor1(self): 
49 
"""Specifying the root is optional."""

50 
assert_equal(dict(tree_all_pairs_lca(self.DG)), self.ans) 
51  
52 
def test_tree_all_pairs_lowest_common_ancestor2(self): 
53 
"""Specifying only some pairs gives only those pairs."""

54 
test_pairs = [(0, 1), (0, 1), (1, 0)] 
55 
ans = dict(tree_all_pairs_lca(self.DG, 0, test_pairs)) 
56 
assert_true((0, 1) in ans and (1, 0) in ans) 
57 
assert_equal(len(ans), 2) 
58  
59 
def test_tree_all_pairs_lowest_common_ancestor3(self): 
60 
"""Specifying no pairs same as specifying all."""

61 
all_pairs = chain(combinations(self.DG, 2), 
62 
((node, node) for node in self.DG)) 
63  
64 
ans = dict(tree_all_pairs_lca(self.DG, 0, all_pairs)) 
65 
self.assert_has_same_pairs(ans, self.ans) 
66  
67 
def test_tree_all_pairs_lowest_common_ancestor4(self): 
68 
"""Gives the right answer."""

69 
ans = dict(tree_all_pairs_lca(self.DG)) 
70 
self.assert_has_same_pairs(self.gold, ans) 
71  
72 
def test_tree_all_pairs_lowest_common_ancestor5(self): 
73 
"""Handles invalid input correctly."""

74 
empty_digraph = tree_all_pairs_lca(nx.DiGraph()) 
75 
assert_raises(nx.NetworkXPointlessConcept, list, empty_digraph)

76  
77 
bad_pairs_digraph = tree_all_pairs_lca(self.DG, pairs=[(1, 2)]) 
78 
assert_raises(nx.NodeNotFound, list, bad_pairs_digraph)

79  
80 
def test_tree_all_pairs_lowest_common_ancestor6(self): 
81 
"""Works on subtrees."""

82 
ans = dict(tree_all_pairs_lca(self.DG, 1)) 
83 
gold = dict((pair, lca) for (pair, lca) in self.gold.items() 
84 
if all(n in (1, 3, 4) for n in pair)) 
85 
self.assert_has_same_pairs(gold, ans)

86  
87 
def test_tree_all_pairs_lowest_common_ancestor7(self): 
88 
"""Works on disconnected nodes."""

89 
G = nx.DiGraph() 
90 
G.add_node(1)

91 
assert_equal({(1, 1): 1}, dict(tree_all_pairs_lca(G))) 
92  
93 
G.add_node(0)

94 
assert_equal({(1, 1): 1}, dict(tree_all_pairs_lca(G, 1))) 
95 
assert_equal({(0, 0): 0}, dict(tree_all_pairs_lca(G, 0))) 
96  
97 
assert_raises(nx.NetworkXError, list, tree_all_pairs_lca(G))

98  
99 
def test_tree_all_pairs_lowest_common_ancestor8(self): 
100 
"""Raises right errors if not a tree."""

101 
# Cycle

102 
G = nx.DiGraph([(1, 2), (2, 1)]) 
103 
assert_raises(nx.NetworkXError, list, tree_all_pairs_lca(G))

104 
# DAG

105 
G = nx.DiGraph([(0, 2), (1, 2)]) 
106 
assert_raises(nx.NetworkXError, list, tree_all_pairs_lca(G))

107  
108 
def test_tree_all_pairs_lowest_common_ancestor9(self): 
109 
"""Test that pairs works correctly as a generator."""

110 
pairs = iter([(0, 1), (0, 1), (1, 0)]) 
111 
some_pairs = dict(tree_all_pairs_lca(self.DG, 0, pairs)) 
112 
assert_true((0, 1) in some_pairs and (1, 0) in some_pairs) 
113 
assert_equal(len(some_pairs), 2) 
114  
115 
def test_tree_all_pairs_lowest_common_ancestor10(self): 
116 
"""Test that pairs not in the graph raises error."""

117 
lca = tree_all_pairs_lca(self.DG, 0, [(1, 1)]) 
118 
assert_raises(nx.NodeNotFound, list, lca)

119  
120 
def test_tree_all_pairs_lowest_common_ancestor11(self): 
121 
"""Test that None as a node in the graph raises an error."""

122 
G = nx.DiGraph([(None, 3)]) 
123 
assert_raises(nx.NetworkXError, list, tree_all_pairs_lca(G))

124 
assert_raises(nx.NodeNotFound, list,

125 
tree_all_pairs_lca(self.DG, pairs=G.edges()))

126  
127 
def test_tree_all_pairs_lowest_common_ancestor12(self): 
128 
"""Test that tree routine bails on DAGs."""

129 
G = nx.DiGraph([(3, 4), (5, 4)]) 
130 
assert_raises(nx.NetworkXError, list, tree_all_pairs_lca(G))

131  
132 
def test_not_implemented_for(self): 
133 
NNI = nx.NetworkXNotImplemented 
134 
G = nx.Graph([(0, 1)]) 
135 
assert_raises(NNI, tree_all_pairs_lca, G) 
136 
assert_raises(NNI, all_pairs_lca, G) 
137 
assert_raises(NNI, nx.lowest_common_ancestor, G, 0, 1) 
138 
G = nx.MultiGraph([(0, 1)]) 
139 
assert_raises(NNI, tree_all_pairs_lca, G) 
140 
assert_raises(NNI, all_pairs_lca, G) 
141 
assert_raises(NNI, nx.lowest_common_ancestor, G, 0, 1) 
142 
G = nx.MultiDiGraph([(0, 1)]) 
143 
assert_raises(NNI, tree_all_pairs_lca, G) 
144 
assert_raises(NNI, all_pairs_lca, G) 
145 
assert_raises(NNI, nx.lowest_common_ancestor, G, 0, 1) 
146  
147 
def test_tree_all_pairs_lowest_common_ancestor13(self): 
148 
"""Test that it works on nonempty trees with no LCAs."""

149 
G = nx.DiGraph() 
150 
G.add_node(3)

151 
ans = list(tree_all_pairs_lca(G))

152 
assert_equal(ans, [((3, 3), 3)]) 
153  
154  
155 
class TestDAGLCA: 
156 
def setUp(self): 
157 
self.DG = nx.DiGraph()

158 
nx.add_path(self.DG, (0, 1, 2, 3)) 
159 
nx.add_path(self.DG, (0, 4, 3)) 
160 
nx.add_path(self.DG, (0, 5, 6, 8, 3)) 
161 
nx.add_path(self.DG, (5, 7, 8)) 
162 
self.DG.add_edge(6, 2) 
163 
self.DG.add_edge(7, 2) 
164  
165 
self.root_distance = nx.shortest_path_length(self.DG, source=0) 
166  
167 
self.gold = {(1, 1): 1, 
168 
(1, 2): 1, 
169 
(1, 3): 1, 
170 
(1, 4): 0, 
171 
(1, 5): 0, 
172 
(1, 6): 0, 
173 
(1, 7): 0, 
174 
(1, 8): 0, 
175 
(2, 2): 2, 
176 
(2, 3): 2, 
177 
(2, 4): 0, 
178 
(2, 5): 5, 
179 
(2, 6): 6, 
180 
(2, 7): 7, 
181 
(2, 8): 7, 
182 
(3, 3): 8, 
183 
(3, 4): 4, 
184 
(3, 5): 5, 
185 
(3, 6): 6, 
186 
(3, 7): 7, 
187 
(3, 8): 8, 
188 
(4, 4): 4, 
189 
(4, 5): 0, 
190 
(4, 6): 0, 
191 
(4, 7): 0, 
192 
(4, 8): 0, 
193 
(5, 5): 5, 
194 
(5, 6): 5, 
195 
(5, 7): 5, 
196 
(5, 8): 5, 
197 
(6, 6): 6, 
198 
(6, 7): 5, 
199 
(6, 8): 6, 
200 
(7, 7): 7, 
201 
(7, 8): 7, 
202 
(8, 8): 8} 
203 
self.gold.update(((0, n), 0) for n in self.DG) 
204  
205 
def assert_lca_dicts_same(self, d1, d2, G=None): 
206 
"""Checks if d1 and d2 contain the same pairs and

207 
have a node at the same distance from root for each.

208 
If G is None use self.DG."""

209 
if G is None: 
210 
G = self.DG

211 
root_distance = self.root_distance

212 
else:

213 
roots = [n for n, deg in G.in_degree if deg == 0] 
214 
assert(len(roots) == 1) 
215 
root_distance = nx.shortest_path_length(G, source=roots[0])

216  
217 
for a, b in ((min(pair), max(pair)) for pair in chain(d1, d2)): 
218 
assert_equal(root_distance[get_pair(d1, a, b)], 
219 
root_distance[get_pair(d2, a, b)]) 
220  
221 
def test_all_pairs_lowest_common_ancestor1(self): 
222 
"""Produces the correct results."""

223 
self.assert_lca_dicts_same(dict(all_pairs_lca(self.DG)), self.gold) 
224  
225 
def test_all_pairs_lowest_common_ancestor2(self): 
226 
"""Produces the correct results when all pairs given."""

227 
all_pairs = list(product(self.DG.nodes(), self.DG.nodes())) 
228 
ans = all_pairs_lca(self.DG, pairs=all_pairs)

229 
self.assert_lca_dicts_same(dict(ans), self.gold) 
230  
231 
def test_all_pairs_lowest_common_ancestor3(self): 
232 
"""Produces the correct results when all pairs given as a generator."""

233 
all_pairs = product(self.DG.nodes(), self.DG.nodes()) 
234 
ans = all_pairs_lca(self.DG, pairs=all_pairs)

235 
self.assert_lca_dicts_same(dict(ans), self.gold) 
236  
237 
def test_all_pairs_lowest_common_ancestor4(self): 
238 
"""Graph with two roots."""

239 
G = self.DG.copy()

240 
G.add_edge(9, 10) 
241 
G.add_edge(9, 4) 
242 
gold = self.gold.copy()

243 
gold[9, 9] = 9 
244 
gold[9, 10] = 9 
245 
gold[9, 4] = 9 
246 
gold[9, 3] = 9 
247 
gold[10, 4] = 9 
248 
gold[10, 3] = 9 
249 
gold[10, 10] = 10 
250  
251 
testing = dict(all_pairs_lca(G))

252  
253 
G.add_edge(1, 9) 
254 
G.add_edge(1, 0) 
255 
self.assert_lca_dicts_same(testing, gold, G)

256  
257 
def test_all_pairs_lowest_common_ancestor5(self): 
258 
"""Test that pairs not in the graph raises error."""

259 
assert_raises(nx.NodeNotFound, all_pairs_lca, self.DG, [(1, 1)]) 
260  
261 
def test_all_pairs_lowest_common_ancestor6(self): 
262 
"""Test that pairs with no LCA specified emits nothing."""

263 
G = self.DG.copy()

264 
G.add_node(1)

265 
gen = all_pairs_lca(G, [(1, 1), (1, 0)]) 
266 
assert_equal(dict(gen), {(1, 1): 1}) 
267  
268 
def test_all_pairs_lowest_common_ancestor7(self): 
269 
"""Test that LCA on null graph bails."""

270 
assert_raises(nx.NetworkXPointlessConcept, 
271 
all_pairs_lca, 
272 
nx.DiGraph()) 
273  
274 
def test_all_pairs_lowest_common_ancestor8(self): 
275 
"""Test that LCA on nondags bails."""

276 
assert_raises(nx.NetworkXError, all_pairs_lca, 
277 
nx.DiGraph([(3, 4), (4, 3)])) 
278  
279 
def test_all_pairs_lowest_common_ancestor9(self): 
280 
"""Test that it works on nonempty graphs with no LCAs."""

281 
G = nx.DiGraph() 
282 
G.add_node(3)

283 
ans = list(all_pairs_lca(G))

284 
assert_equal(ans, [((3, 3), 3)]) 
285  
286 
def test_all_pairs_lowest_common_ancestor10(self): 
287 
"""Test that it bails on None as a node."""

288 
G = nx.DiGraph([(None, 3)]) 
289 
assert_raises(nx.NetworkXError, all_pairs_lca, G) 
290 
assert_raises(nx.NodeNotFound, all_pairs_lca, 
291 
self.DG, pairs=G.edges())

292  
293 
def test_lowest_common_ancestor1(self): 
294 
"""Test that the onepair function works on default."""

295 
G = nx.DiGraph([(0, 1), (2, 1)]) 
296 
sentinel = object()

297 
assert_is(nx.lowest_common_ancestor(G, 0, 2, default=sentinel), 
298 
sentinel) 
299  
300 
def test_lowest_common_ancestor2(self): 
301 
"""Test that the onepair function works on identity."""

302 
G = nx.DiGraph() 
303 
G.add_node(3)

304 
assert_equal(nx.lowest_common_ancestor(G, 3, 3), 3) 