ioftools / networkxMiCe / networkxmaster / networkx / algorithms / tests / test_dag.py @ 5cef0f13
History  View  Annotate  Download (20.5 KB)
1 
from itertools import combinations, permutations 

2  
3 
from nose.tools import assert_equal 
4 
from nose.tools import assert_false 
5 
from nose.tools import assert_in 
6 
from nose.tools import assert_raises 
7 
from nose.tools import assert_true 
8 
from nose.tools import raises 
9 
from nose.tools import ok_ 
10  
11 
import networkx as nx 
12 
from networkx.testing.utils import assert_edges_equal 
13 
from networkx.utils import arbitrary_element 
14 
from networkx.utils import consume 
15 
from networkx.utils import pairwise 
16  
17  
18 
class TestDagLongestPath(object): 
19 
"""Unit tests computing the longest path in a directed acyclic graph."""

20  
21 
def test_empty(self): 
22 
G = nx.DiGraph() 
23 
assert_equal(nx.dag_longest_path(G), []) 
24  
25 
def test_unweighted1(self): 
26 
edges = [(1, 2), (2, 3), (2, 4), (3, 5), (5, 6), (3, 7)] 
27 
G = nx.DiGraph(edges) 
28 
assert_equal(nx.dag_longest_path(G), [1, 2, 3, 5, 6]) 
29  
30 
def test_unweighted2(self): 
31 
edges = [(1, 2), (2, 3), (3, 4), (4, 5), (1, 3), (1, 5), (3, 5)] 
32 
G = nx.DiGraph(edges) 
33 
assert_equal(nx.dag_longest_path(G), [1, 2, 3, 4, 5]) 
34  
35 
def test_weighted(self): 
36 
G = nx.DiGraph() 
37 
edges = [(1, 2, 5), (2, 3, 1), (3, 4, 1), (4, 5, 0), (3, 5, 4), 
38 
(1, 6, 2)] 
39 
G.add_weighted_edges_from(edges) 
40 
assert_equal(nx.dag_longest_path(G), [2, 3, 5]) 
41  
42 
def test_undirected_not_implemented(self): 
43 
G = nx.Graph() 
44 
assert_raises(nx.NetworkXNotImplemented, nx.dag_longest_path, G) 
45  
46 
def test_unorderable_nodes(self): 
47 
"""Tests that computing the longest path does not depend on

48 
nodes being orderable.

49 

50 
For more information, see issue #1989.

51 

52 
"""

53 
# TODO In Python 3, instances of the `object` class are

54 
# unorderable by default, so we wouldn't need to define our own

55 
# class here, we could just instantiate an instance of the

56 
# `object` class. However, we still support Python 2; when

57 
# support for Python 2 is dropped, this test can be simplified

58 
# by replacing `Unorderable()` by `object()`.

59 
class Unorderable(object): 
60 
def __lt__(self, other): 
61 
error_msg = "< not supported between instances of {} and {}"

62 
types = (type(self).__name__, type(other).__name__) 
63 
raise TypeError(error_msg.format(types)) 
64  
65 
# Create the directed path graph on four nodes in a diamond shape,

66 
# with nodes represented as (unorderable) Python objects.

67 
nodes = [Unorderable() for n in range(4)] 
68 
G = nx.DiGraph() 
69 
G.add_edge(nodes[0], nodes[1]) 
70 
G.add_edge(nodes[0], nodes[2]) 
71 
G.add_edge(nodes[2], nodes[3]) 
72 
G.add_edge(nodes[1], nodes[3]) 
73  
74 
# this will raise NotImplementedError when nodes need to be ordered

75 
nx.dag_longest_path(G) 
76  
77  
78 
class TestDagLongestPathLength(object): 
79 
"""Unit tests for computing the length of a longest path in a

80 
directed acyclic graph.

81 

82 
"""

83  
84 
def test_unweighted(self): 
85 
edges = [(1, 2), (2, 3), (2, 4), (3, 5), (5, 6), (5, 7)] 
86 
G = nx.DiGraph(edges) 
87 
assert_equal(nx.dag_longest_path_length(G), 4)

88  
89 
edges = [(1, 2), (2, 3), (3, 4), (4, 5), (1, 3), (1, 5), (3, 5)] 
90 
G = nx.DiGraph(edges) 
91 
assert_equal(nx.dag_longest_path_length(G), 4)

92  
93 
# test degenerate graphs

94 
G = nx.DiGraph() 
95 
G.add_node(1)

96 
assert_equal(nx.dag_longest_path_length(G), 0)

97  
98 
def test_undirected_not_implemented(self): 
99 
G = nx.Graph() 
100 
assert_raises(nx.NetworkXNotImplemented, nx.dag_longest_path_length, G) 
101  
102 
def test_weighted(self): 
103 
edges = [(1, 2, 5), (2, 3, 1), (3, 4, 1), (4, 5, 0), (3, 5, 4), 
104 
(1, 6, 2)] 
105 
G = nx.DiGraph() 
106 
G.add_weighted_edges_from(edges) 
107 
assert_equal(nx.dag_longest_path_length(G), 5)

108  
109  
110 
class TestDAG: 
111  
112 
def setUp(self): 
113 
pass

114  
115 
def test_topological_sort1(self): 
116 
DG = nx.DiGraph([(1, 2), (1, 3), (2, 3)]) 
117  
118 
for algorithm in [nx.topological_sort, 
119 
nx.lexicographical_topological_sort]: 
120 
assert_equal(tuple(algorithm(DG)), (1, 2, 3)) 
121  
122 
DG.add_edge(3, 2) 
123  
124 
for algorithm in [nx.topological_sort, 
125 
nx.lexicographical_topological_sort]: 
126 
assert_raises(nx.NetworkXUnfeasible, consume, algorithm(DG)) 
127  
128 
DG.remove_edge(2, 3) 
129  
130 
for algorithm in [nx.topological_sort, 
131 
nx.lexicographical_topological_sort]: 
132 
assert_equal(tuple(algorithm(DG)), (1, 3, 2)) 
133  
134 
DG.remove_edge(3, 2) 
135  
136 
assert_in(tuple(nx.topological_sort(DG)), {(1, 2, 3), (1, 3, 2)}) 
137 
assert_equal(tuple(nx.lexicographical_topological_sort(DG)), (1, 2, 3)) 
138  
139 
def test_is_directed_acyclic_graph(self): 
140 
G = nx.generators.complete_graph(2)

141 
assert_false(nx.is_directed_acyclic_graph(G)) 
142 
assert_false(nx.is_directed_acyclic_graph(G.to_directed())) 
143 
assert_false(nx.is_directed_acyclic_graph(nx.Graph([(3, 4), (4, 5)]))) 
144 
assert_true(nx.is_directed_acyclic_graph(nx.DiGraph([(3, 4), (4, 5)]))) 
145  
146 
def test_topological_sort2(self): 
147 
DG = nx.DiGraph({1: [2], 2: [3], 3: [4], 
148 
4: [5], 5: [1], 11: [12], 
149 
12: [13], 13: [14], 14: [15]}) 
150 
assert_raises(nx.NetworkXUnfeasible, consume, nx.topological_sort(DG)) 
151  
152 
assert_false(nx.is_directed_acyclic_graph(DG)) 
153  
154 
DG.remove_edge(1, 2) 
155 
consume(nx.topological_sort(DG)) 
156 
assert_true(nx.is_directed_acyclic_graph(DG)) 
157  
158 
def test_topological_sort3(self): 
159 
DG = nx.DiGraph() 
160 
DG.add_edges_from([(1, i) for i in range(2, 5)]) 
161 
DG.add_edges_from([(2, i) for i in range(5, 9)]) 
162 
DG.add_edges_from([(6, i) for i in range(9, 12)]) 
163 
DG.add_edges_from([(4, i) for i in range(12, 15)]) 
164  
165 
def validate(order): 
166 
ok_(isinstance(order, list)) 
167 
assert_equal(set(order), set(DG)) 
168 
for u, v in combinations(order, 2): 
169 
assert_false(nx.has_path(DG, v, u)) 
170 
validate(list(nx.topological_sort(DG)))

171  
172 
DG.add_edge(14, 1) 
173 
assert_raises(nx.NetworkXUnfeasible, consume, nx.topological_sort(DG)) 
174  
175 
def test_topological_sort4(self): 
176 
G = nx.Graph() 
177 
G.add_edge(1, 2) 
178 
# Only directed graphs can be topologically sorted.

179 
assert_raises(nx.NetworkXError, consume, nx.topological_sort(G)) 
180  
181 
def test_topological_sort5(self): 
182 
G = nx.DiGraph() 
183 
G.add_edge(0, 1) 
184 
assert_equal(list(nx.topological_sort(G)), [0, 1]) 
185  
186 
def test_topological_sort6(self): 
187 
for algorithm in [nx.topological_sort, 
188 
nx.lexicographical_topological_sort]: 
189 
def runtime_error(): 
190 
DG = nx.DiGraph([(1, 2), (2, 3), (3, 4)]) 
191 
first = True

192 
for x in algorithm(DG): 
193 
if first:

194 
first = False

195 
DG.add_edge(5  x, 5) 
196  
197 
def unfeasible_error(): 
198 
DG = nx.DiGraph([(1, 2), (2, 3), (3, 4)]) 
199 
first = True

200 
for x in algorithm(DG): 
201 
if first:

202 
first = False

203 
DG.remove_node(4)

204  
205 
def runtime_error2(): 
206 
DG = nx.DiGraph([(1, 2), (2, 3), (3, 4)]) 
207 
first = True

208 
for x in algorithm(DG): 
209 
if first:

210 
first = False

211 
DG.remove_node(2)

212  
213 
assert_raises(RuntimeError, runtime_error)

214 
assert_raises(RuntimeError, runtime_error2)

215 
assert_raises(nx.NetworkXUnfeasible, unfeasible_error) 
216  
217 
def test_all_topological_sorts_1(self): 
218 
DG = nx.DiGraph([(1, 2), (2, 3), (3, 4), (4, 5)]) 
219 
assert_equal(list(nx.all_topological_sorts(DG)), [[1, 2, 3, 4, 5]]) 
220  
221 
def test_all_topological_sorts_2(self): 
222 
DG = nx.DiGraph([(1, 3), (2, 1), (2, 4), (4, 3), (4, 5)]) 
223 
assert_equal(sorted(nx.all_topological_sorts(DG)),

224 
[[2, 1, 4, 3, 5], 
225 
[2, 1, 4, 5, 3], 
226 
[2, 4, 1, 3, 5], 
227 
[2, 4, 1, 5, 3], 
228 
[2, 4, 5, 1, 3]]) 
229  
230 
def test_all_topological_sorts_3(self): 
231 
def unfeasible(): 
232 
DG = nx.DiGraph([(1, 2), (2, 3), (3, 4), (4, 2), (4, 5)]) 
233 
# convert to list to execute generator

234 
list(nx.all_topological_sorts(DG))

235  
236 
def not_implemented(): 
237 
G = nx.Graph([(1, 2), (2, 3)]) 
238 
# convert to list to execute generator

239 
list(nx.all_topological_sorts(G))

240  
241 
def not_implemted_2(): 
242 
G = nx.MultiGraph([(1, 2), (1, 2), (2, 3)]) 
243 
list(nx.all_topological_sorts(G))

244 
assert_raises(nx.NetworkXUnfeasible, unfeasible) 
245 
assert_raises(nx.NetworkXNotImplemented, not_implemented) 
246 
assert_raises(nx.NetworkXNotImplemented, not_implemted_2) 
247  
248 
def test_all_topological_sorts_4(self): 
249 
DG = nx.DiGraph() 
250 
for i in range(7): 
251 
DG.add_node(i) 
252 
assert_equal(sorted(map(list, permutations(DG.nodes))), 
253 
sorted(nx.all_topological_sorts(DG)))

254  
255 
def test_all_topological_sorts_multigraph_1(self): 
256 
DG = nx.MultiDiGraph([(1, 2), (1, 2), (2, 3), 
257 
(3, 4), (3, 5), (3, 5), (3, 5)]) 
258 
assert_equal(sorted(nx.all_topological_sorts(DG)),

259 
sorted([[1, 2, 3, 4, 5], 
260 
[1, 2, 3, 5, 4]])) 
261  
262 
def test_all_topological_sorts_multigraph_2(self): 
263 
N = 9

264 
edges = [] 
265 
for i in range(1, N): 
266 
edges.extend([(i, i+1)] * i)

267 
DG = nx.MultiDiGraph(edges) 
268 
assert_equal(list(nx.all_topological_sorts(DG)),

269 
[list(range(1, N+1))]) 
270  
271 
def test_ancestors(self): 
272 
G = nx.DiGraph() 
273 
ancestors = nx.algorithms.dag.ancestors 
274 
G.add_edges_from([ 
275 
(1, 2), (1, 3), (4, 2), (4, 3), (4, 5), (2, 6), (5, 6)]) 
276 
assert_equal(ancestors(G, 6), set([1, 2, 4, 5])) 
277 
assert_equal(ancestors(G, 3), set([1, 4])) 
278 
assert_equal(ancestors(G, 1), set()) 
279 
assert_raises(nx.NetworkXError, ancestors, G, 8)

280  
281 
def test_descendants(self): 
282 
G = nx.DiGraph() 
283 
descendants = nx.algorithms.dag.descendants 
284 
G.add_edges_from([ 
285 
(1, 2), (1, 3), (4, 2), (4, 3), (4, 5), (2, 6), (5, 6)]) 
286 
assert_equal(descendants(G, 1), set([2, 3, 6])) 
287 
assert_equal(descendants(G, 4), set([2, 3, 5, 6])) 
288 
assert_equal(descendants(G, 3), set()) 
289 
assert_raises(nx.NetworkXError, descendants, G, 8)

290  
291 
def test_transitive_closure(self): 
292 
G = nx.DiGraph([(1, 2), (2, 3), (3, 4)]) 
293 
transitive_closure = nx.algorithms.dag.transitive_closure 
294 
solution = [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)] 
295 
assert_edges_equal(transitive_closure(G).edges(), solution) 
296 
G = nx.DiGraph([(1, 2), (2, 3), (2, 4)]) 
297 
solution = [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4)] 
298 
assert_edges_equal(transitive_closure(G).edges(), solution) 
299 
G = nx.Graph([(1, 2), (2, 3), (3, 4)]) 
300 
assert_raises(nx.NetworkXNotImplemented, transitive_closure, G) 
301  
302 
# test if edge data is copied

303 
G = nx.DiGraph([(1, 2, {"a": 3}), (2, 3, {"b": 0}), (3, 4)]) 
304 
H = transitive_closure(G) 
305 
for u, v in G.edges(): 
306 
assert_equal(G.get_edge_data(u, v), H.get_edge_data(u, v)) 
307  
308 
k = 10

309 
G = nx.DiGraph((i, i + 1, {"f": "b", "weight": i}) for i in range(k)) 
310 
H = transitive_closure(G) 
311 
for u, v in G.edges(): 
312 
assert_equal(G.get_edge_data(u, v), H.get_edge_data(u, v)) 
313  
314 
def test_transitive_reduction(self): 
315 
G = nx.DiGraph([(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]) 
316 
transitive_reduction = nx.algorithms.dag.transitive_reduction 
317 
solution = [(1, 2), (2, 3), (3, 4)] 
318 
assert_edges_equal(transitive_reduction(G).edges(), solution) 
319 
G = nx.DiGraph([(1, 2), (1, 3), (1, 4), (2, 3), (2, 4)]) 
320 
transitive_reduction = nx.algorithms.dag.transitive_reduction 
321 
solution = [(1, 2), (2, 3), (2, 4)] 
322 
assert_edges_equal(transitive_reduction(G).edges(), solution) 
323 
G = nx.Graph([(1, 2), (2, 3), (3, 4)]) 
324 
assert_raises(nx.NetworkXNotImplemented, transitive_reduction, G) 
325  
326 
def _check_antichains(self, solution, result): 
327 
sol = [frozenset(a) for a in solution] 
328 
res = [frozenset(a) for a in result] 
329 
assert_true(set(sol) == set(res)) 
330  
331 
def test_antichains(self): 
332 
antichains = nx.algorithms.dag.antichains 
333 
G = nx.DiGraph([(1, 2), (2, 3), (3, 4)]) 
334 
solution = [[], [4], [3], [2], [1]] 
335 
self._check_antichains(list(antichains(G)), solution) 
336 
G = nx.DiGraph([(1, 2), (2, 3), (2, 4), (3, 5), (5, 6), (5, 7)]) 
337 
solution = [[], [4], [7], [7, 4], [6], [6, 4], [6, 7], [6, 7, 4], 
338 
[5], [5, 4], [3], [3, 4], [2], [1]] 
339 
self._check_antichains(list(antichains(G)), solution) 
340 
G = nx.DiGraph([(1, 2), (1, 3), (3, 4), (3, 5), (5, 6)]) 
341 
solution = [[], [6], [5], [4], [4, 6], [4, 5], [3], [2], [2, 6], 
342 
[2, 5], [2, 4], [2, 4, 6], [2, 4, 5], [2, 3], [1]] 
343 
self._check_antichains(list(antichains(G)), solution) 
344 
G = nx.DiGraph({0: [1, 2], 1: [4], 2: [3], 3: [4]}) 
345 
solution = [[], [4], [3], [2], [1], [1, 3], [1, 2], [0]] 
346 
self._check_antichains(list(antichains(G)), solution) 
347 
G = nx.DiGraph() 
348 
self._check_antichains(list(antichains(G)), [[]]) 
349 
G = nx.DiGraph() 
350 
G.add_nodes_from([0, 1, 2]) 
351 
solution = [[], [0], [1], [1, 0], [2], [2, 0], [2, 1], [2, 1, 0]] 
352 
self._check_antichains(list(antichains(G)), solution) 
353  
354 
def f(x): return list(antichains(x)) 
355 
G = nx.Graph([(1, 2), (2, 3), (3, 4)]) 
356 
assert_raises(nx.NetworkXNotImplemented, f, G) 
357 
G = nx.DiGraph([(1, 2), (2, 3), (3, 1)]) 
358 
assert_raises(nx.NetworkXUnfeasible, f, G) 
359  
360 
def test_lexicographical_topological_sort(self): 
361 
G = nx.DiGraph([(1, 2), (2, 3), (1, 4), (1, 5), (2, 6)]) 
362 
assert_equal(list(nx.lexicographical_topological_sort(G)),

363 
[1, 2, 3, 4, 5, 6]) 
364 
assert_equal(list(nx.lexicographical_topological_sort(

365 
G, key=lambda x: x)),

366 
[1, 2, 3, 4, 5, 6]) 
367 
assert_equal(list(nx.lexicographical_topological_sort(

368 
G, key=lambda x: x)),

369 
[1, 5, 4, 2, 6, 3]) 
370  
371 
def test_lexicographical_topological_sort2(self): 
372 
'''

373 
Check the case of two or more nodes with same key value.

374 
Want to avoid exception raised due to comparing nodes directly.

375 
See Issue #3493

376 
'''

377 
class Test_Node: 
378 
def __init__(self, n): 
379 
self.label = n

380 
self.priority = 1 
381  
382 
def __repr__(self): 
383 
return 'Node({})'.format(self.label) 
384  
385 
def sorting_key(node): 
386 
return node.priority

387  
388 
test_nodes = [Test_Node(n) for n in range(4)] 
389 
G = nx.DiGraph() 
390 
edges = [(0, 1), (0, 2), (0, 3), (2, 3)] 
391 
G.add_edges_from((test_nodes[a], test_nodes[b]) for a, b in edges) 
392  
393 
sorting = list(nx.lexicographical_topological_sort(G, key=sorting_key))

394 
# order reported does depend on order of list(G) in python 3.5

395 
# and that is not deterministic due to dicts not being ordered until v3.6

396 
# after dropping NX support for 3.5 this can become:

397 
# assert_equal(sorting, test_nodes)

398 
assert_equal(set(sorting), set(test_nodes)) 
399  
400  
401 
def test_is_aperiodic_cycle(): 
402 
G = nx.DiGraph() 
403 
nx.add_cycle(G, [1, 2, 3, 4]) 
404 
assert_false(nx.is_aperiodic(G)) 
405  
406  
407 
def test_is_aperiodic_cycle2(): 
408 
G = nx.DiGraph() 
409 
nx.add_cycle(G, [1, 2, 3, 4]) 
410 
nx.add_cycle(G, [3, 4, 5, 6, 7]) 
411 
assert_true(nx.is_aperiodic(G)) 
412  
413  
414 
def test_is_aperiodic_cycle3(): 
415 
G = nx.DiGraph() 
416 
nx.add_cycle(G, [1, 2, 3, 4]) 
417 
nx.add_cycle(G, [3, 4, 5, 6]) 
418 
assert_false(nx.is_aperiodic(G)) 
419  
420  
421 
def test_is_aperiodic_cycle4(): 
422 
G = nx.DiGraph() 
423 
nx.add_cycle(G, [1, 2, 3, 4]) 
424 
G.add_edge(1, 3) 
425 
assert_true(nx.is_aperiodic(G)) 
426  
427  
428 
def test_is_aperiodic_selfloop(): 
429 
G = nx.DiGraph() 
430 
nx.add_cycle(G, [1, 2, 3, 4]) 
431 
G.add_edge(1, 1) 
432 
assert_true(nx.is_aperiodic(G)) 
433  
434  
435 
def test_is_aperiodic_raise(): 
436 
G = nx.Graph() 
437 
assert_raises(nx.NetworkXError, 
438 
nx.is_aperiodic, 
439 
G) 
440  
441  
442 
def test_is_aperiodic_bipartite(): 
443 
# Bipartite graph

444 
G = nx.DiGraph(nx.davis_southern_women_graph()) 
445 
assert_false(nx.is_aperiodic(G)) 
446  
447  
448 
def test_is_aperiodic_rary_tree(): 
449 
G = nx.full_rary_tree(3, 27, create_using=nx.DiGraph()) 
450 
assert_false(nx.is_aperiodic(G)) 
451  
452  
453 
def test_is_aperiodic_disconnected(): 
454 
# disconnected graph

455 
G = nx.DiGraph() 
456 
nx.add_cycle(G, [1, 2, 3, 4]) 
457 
nx.add_cycle(G, [5, 6, 7, 8]) 
458 
assert_false(nx.is_aperiodic(G)) 
459 
G.add_edge(1, 3) 
460 
G.add_edge(5, 7) 
461 
assert_true(nx.is_aperiodic(G)) 
462  
463  
464 
def test_is_aperiodic_disconnected2(): 
465 
G = nx.DiGraph() 
466 
nx.add_cycle(G, [0, 1, 2]) 
467 
G.add_edge(3, 3) 
468 
assert_false(nx.is_aperiodic(G)) 
469  
470  
471 
class TestDagToBranching(object): 
472 
"""Unit tests for the :func:`networkx.dag_to_branching` function."""

473  
474 
def test_single_root(self): 
475 
"""Tests that a directed acyclic graph with a single degree

476 
zero node produces an arborescence.

477 

478 
"""

479 
G = nx.DiGraph([(0, 1), (0, 2), (1, 3), (2, 3)]) 
480 
B = nx.dag_to_branching(G) 
481 
expected = nx.DiGraph([(0, 1), (1, 3), (0, 2), (2, 4)]) 
482 
assert_true(nx.is_arborescence(B)) 
483 
assert_true(nx.is_isomorphic(B, expected)) 
484  
485 
def test_multiple_roots(self): 
486 
"""Tests that a directed acyclic graph with multiple degree zero

487 
nodes creates an arborescence with multiple (weakly) connected

488 
components.

489 

490 
"""

491 
G = nx.DiGraph([(0, 1), (0, 2), (1, 3), (2, 3), (5, 2)]) 
492 
B = nx.dag_to_branching(G) 
493 
expected = nx.DiGraph([(0, 1), (1, 3), (0, 2), (2, 4), (5, 6), (6, 7)]) 
494 
assert_true(nx.is_branching(B)) 
495 
assert_false(nx.is_arborescence(B)) 
496 
assert_true(nx.is_isomorphic(B, expected)) 
497  
498 
# # Attributes are not copied by this function. If they were, this would

499 
# # be a good test to uncomment.

500 
# def test_copy_attributes(self):

501 
# """Tests that node attributes are copied in the branching."""

502 
# G = nx.DiGraph([(0, 1), (0, 2), (1, 3), (2, 3)])

503 
# for v in G:

504 
# G.node[v]['label'] = str(v)

505 
# B = nx.dag_to_branching(G)

506 
# # Determine the root node of the branching.

507 
# root = next(v for v, d in B.in_degree() if d == 0)

508 
# assert_equal(B.node[root]['label'], '0')

509 
# children = B[root]

510 
# # Get the left and right children, nodes 1 and 2, respectively.

511 
# left, right = sorted(children, key=lambda v: B.node[v]['label'])

512 
# assert_equal(B.node[left]['label'], '1')

513 
# assert_equal(B.node[right]['label'], '2')

514 
# # Get the left grandchild.

515 
# children = B[left]

516 
# assert_equal(len(children), 1)

517 
# left_grandchild = arbitrary_element(children)

518 
# assert_equal(B.node[left_grandchild]['label'], '3')

519 
# # Get the right grandchild.

520 
# children = B[right]

521 
# assert_equal(len(children), 1)

522 
# right_grandchild = arbitrary_element(children)

523 
# assert_equal(B.node[right_grandchild]['label'], '3')

524  
525 
def test_already_arborescence(self): 
526 
"""Tests that a directed acyclic graph that is already an

527 
arborescence produces an isomorphic arborescence as output.

528 

529 
"""

530 
A = nx.balanced_tree(2, 2, create_using=nx.DiGraph()) 
531 
B = nx.dag_to_branching(A) 
532 
assert_true(nx.is_isomorphic(A, B)) 
533  
534 
def test_already_branching(self): 
535 
"""Tests that a directed acyclic graph that is already a

536 
branching produces an isomorphic branching as output.

537 

538 
"""

539 
T1 = nx.balanced_tree(2, 2, create_using=nx.DiGraph()) 
540 
T2 = nx.balanced_tree(2, 2, create_using=nx.DiGraph()) 
541 
G = nx.disjoint_union(T1, T2) 
542 
B = nx.dag_to_branching(G) 
543 
assert_true(nx.is_isomorphic(G, B)) 
544  
545 
@raises(nx.HasACycle)

546 
def test_not_acyclic(self): 
547 
"""Tests that a nonacyclic graph causes an exception."""

548 
G = nx.DiGraph(pairwise('abc', cyclic=True)) 
549 
nx.dag_to_branching(G) 
550  
551 
@raises(nx.NetworkXNotImplemented)

552 
def test_undirected(self): 
553 
nx.dag_to_branching(nx.Graph()) 
554  
555 
@raises(nx.NetworkXNotImplemented)

556 
def test_multigraph(self): 
557 
nx.dag_to_branching(nx.MultiGraph()) 
558  
559 
@raises(nx.NetworkXNotImplemented)

560 
def test_multidigraph(self): 
561 
nx.dag_to_branching(nx.MultiDiGraph()) 