Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / 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 non-empty 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 non-dags 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 non-empty 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 one-pair 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 one-pair function works on identity."""
302
        G = nx.DiGraph()
303
        G.add_node(3)
304
        assert_equal(nx.lowest_common_ancestor(G, 3, 3), 3)