### comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_dag.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal inserted replaced
-1:000000000000 0:4f3585e2f14b
1 from itertools import combinations, permutations
2
3 import pytest
4
5 import networkx as nx
6 from networkx.testing.utils import assert_edges_equal
7 from networkx.utils import consume
8 from networkx.utils import pairwise
9
10
11 class TestDagLongestPath:
12 """Unit tests computing the longest path in a directed acyclic graph."""
13
14 def test_empty(self):
15 G = nx.DiGraph()
16 assert nx.dag_longest_path(G) == []
17
18 def test_unweighted1(self):
19 edges = [(1, 2), (2, 3), (2, 4), (3, 5), (5, 6), (3, 7)]
20 G = nx.DiGraph(edges)
21 assert nx.dag_longest_path(G) == [1, 2, 3, 5, 6]
22
23 def test_unweighted2(self):
24 edges = [(1, 2), (2, 3), (3, 4), (4, 5), (1, 3), (1, 5), (3, 5)]
25 G = nx.DiGraph(edges)
26 assert nx.dag_longest_path(G) == [1, 2, 3, 4, 5]
27
28 def test_weighted(self):
29 G = nx.DiGraph()
30 edges = [(1, 2, -5), (2, 3, 1), (3, 4, 1), (4, 5, 0), (3, 5, 4), (1, 6, 2)]
32 assert nx.dag_longest_path(G) == [2, 3, 5]
33
34 def test_undirected_not_implemented(self):
35 G = nx.Graph()
36 pytest.raises(nx.NetworkXNotImplemented, nx.dag_longest_path, G)
37
38 def test_unorderable_nodes(self):
39 """Tests that computing the longest path does not depend on
40 nodes being orderable.
41
43
44 """
45 # Create the directed path graph on four nodes in a diamond shape,
46 # with nodes represented as (unorderable) Python objects.
47 nodes = [object() for n in range(4)]
48 G = nx.DiGraph()
53
54 # this will raise NotImplementedError when nodes need to be ordered
55 nx.dag_longest_path(G)
56
57
58 class TestDagLongestPathLength:
59 """Unit tests for computing the length of a longest path in a
60 directed acyclic graph.
61
62 """
63
64 def test_unweighted(self):
65 edges = [(1, 2), (2, 3), (2, 4), (3, 5), (5, 6), (5, 7)]
66 G = nx.DiGraph(edges)
67 assert nx.dag_longest_path_length(G) == 4
68
69 edges = [(1, 2), (2, 3), (3, 4), (4, 5), (1, 3), (1, 5), (3, 5)]
70 G = nx.DiGraph(edges)
71 assert nx.dag_longest_path_length(G) == 4
72
73 # test degenerate graphs
74 G = nx.DiGraph()
76 assert nx.dag_longest_path_length(G) == 0
77
78 def test_undirected_not_implemented(self):
79 G = nx.Graph()
80 pytest.raises(nx.NetworkXNotImplemented, nx.dag_longest_path_length, G)
81
82 def test_weighted(self):
83 edges = [(1, 2, -5), (2, 3, 1), (3, 4, 1), (4, 5, 0), (3, 5, 4), (1, 6, 2)]
84 G = nx.DiGraph()
86 assert nx.dag_longest_path_length(G) == 5
87
88
89 class TestDAG:
90 @classmethod
91 def setup_class(cls):
92 pass
93
94 def test_topological_sort1(self):
95 DG = nx.DiGraph([(1, 2), (1, 3), (2, 3)])
96
97 for algorithm in [nx.topological_sort, nx.lexicographical_topological_sort]:
98 assert tuple(algorithm(DG)) == (1, 2, 3)
99
101
102 for algorithm in [nx.topological_sort, nx.lexicographical_topological_sort]:
103 pytest.raises(nx.NetworkXUnfeasible, consume, algorithm(DG))
104
105 DG.remove_edge(2, 3)
106
107 for algorithm in [nx.topological_sort, nx.lexicographical_topological_sort]:
108 assert tuple(algorithm(DG)) == (1, 3, 2)
109
110 DG.remove_edge(3, 2)
111
112 assert tuple(nx.topological_sort(DG)) in {(1, 2, 3), (1, 3, 2)}
113 assert tuple(nx.lexicographical_topological_sort(DG)) == (1, 2, 3)
114
115 def test_is_directed_acyclic_graph(self):
116 G = nx.generators.complete_graph(2)
117 assert not nx.is_directed_acyclic_graph(G)
118 assert not nx.is_directed_acyclic_graph(G.to_directed())
119 assert not nx.is_directed_acyclic_graph(nx.Graph([(3, 4), (4, 5)]))
120 assert nx.is_directed_acyclic_graph(nx.DiGraph([(3, 4), (4, 5)]))
121
122 def test_topological_sort2(self):
123 DG = nx.DiGraph(
124 {
125 1: [2],
126 2: [3],
127 3: [4],
128 4: [5],
129 5: [1],
130 11: [12],
131 12: [13],
132 13: [14],
133 14: [15],
134 }
135 )
136 pytest.raises(nx.NetworkXUnfeasible, consume, nx.topological_sort(DG))
137
138 assert not nx.is_directed_acyclic_graph(DG)
139
140 DG.remove_edge(1, 2)
141 consume(nx.topological_sort(DG))
142 assert nx.is_directed_acyclic_graph(DG)
143
144 def test_topological_sort3(self):
145 DG = nx.DiGraph()
146 DG.add_edges_from([(1, i) for i in range(2, 5)])
147 DG.add_edges_from([(2, i) for i in range(5, 9)])
148 DG.add_edges_from([(6, i) for i in range(9, 12)])
149 DG.add_edges_from([(4, i) for i in range(12, 15)])
150
151 def validate(order):
152 assert isinstance(order, list)
153 assert set(order) == set(DG)
154 for u, v in combinations(order, 2):
155 assert not nx.has_path(DG, v, u)
156
157 validate(list(nx.topological_sort(DG)))
158
160 pytest.raises(nx.NetworkXUnfeasible, consume, nx.topological_sort(DG))
161
162 def test_topological_sort4(self):
163 G = nx.Graph()
165 # Only directed graphs can be topologically sorted.
166 pytest.raises(nx.NetworkXError, consume, nx.topological_sort(G))
167
168 def test_topological_sort5(self):
169 G = nx.DiGraph()
171 assert list(nx.topological_sort(G)) == [0, 1]
172
173 def test_topological_sort6(self):
174 for algorithm in [nx.topological_sort, nx.lexicographical_topological_sort]:
175
176 def runtime_error():
177 DG = nx.DiGraph([(1, 2), (2, 3), (3, 4)])
178 first = True
179 for x in algorithm(DG):
180 if first:
181 first = False
183
184 def unfeasible_error():
185 DG = nx.DiGraph([(1, 2), (2, 3), (3, 4)])
186 first = True
187 for x in algorithm(DG):
188 if first:
189 first = False
190 DG.remove_node(4)
191
192 def runtime_error2():
193 DG = nx.DiGraph([(1, 2), (2, 3), (3, 4)])
194 first = True
195 for x in algorithm(DG):
196 if first:
197 first = False
198 DG.remove_node(2)
199
200 pytest.raises(RuntimeError, runtime_error)
201 pytest.raises(RuntimeError, runtime_error2)
202 pytest.raises(nx.NetworkXUnfeasible, unfeasible_error)
203
204 def test_all_topological_sorts_1(self):
205 DG = nx.DiGraph([(1, 2), (2, 3), (3, 4), (4, 5)])
206 assert list(nx.all_topological_sorts(DG)) == [[1, 2, 3, 4, 5]]
207
208 def test_all_topological_sorts_2(self):
209 DG = nx.DiGraph([(1, 3), (2, 1), (2, 4), (4, 3), (4, 5)])
210 assert sorted(nx.all_topological_sorts(DG)) == [
211 [2, 1, 4, 3, 5],
212 [2, 1, 4, 5, 3],
213 [2, 4, 1, 3, 5],
214 [2, 4, 1, 5, 3],
215 [2, 4, 5, 1, 3],
216 ]
217
218 def test_all_topological_sorts_3(self):
219 def unfeasible():
220 DG = nx.DiGraph([(1, 2), (2, 3), (3, 4), (4, 2), (4, 5)])
221 # convert to list to execute generator
222 list(nx.all_topological_sorts(DG))
223
224 def not_implemented():
225 G = nx.Graph([(1, 2), (2, 3)])
226 # convert to list to execute generator
227 list(nx.all_topological_sorts(G))
228
229 def not_implemted_2():
230 G = nx.MultiGraph([(1, 2), (1, 2), (2, 3)])
231 list(nx.all_topological_sorts(G))
232
233 pytest.raises(nx.NetworkXUnfeasible, unfeasible)
234 pytest.raises(nx.NetworkXNotImplemented, not_implemented)
235 pytest.raises(nx.NetworkXNotImplemented, not_implemted_2)
236
237 def test_all_topological_sorts_4(self):
238 DG = nx.DiGraph()
239 for i in range(7):
241 assert sorted(map(list, permutations(DG.nodes))) == sorted(
242 nx.all_topological_sorts(DG)
243 )
244
245 def test_all_topological_sorts_multigraph_1(self):
246 DG = nx.MultiDiGraph([(1, 2), (1, 2), (2, 3), (3, 4), (3, 5), (3, 5), (3, 5)])
247 assert sorted(nx.all_topological_sorts(DG)) == sorted(
248 [[1, 2, 3, 4, 5], [1, 2, 3, 5, 4]]
249 )
250
251 def test_all_topological_sorts_multigraph_2(self):
252 N = 9
253 edges = []
254 for i in range(1, N):
255 edges.extend([(i, i + 1)] * i)
256 DG = nx.MultiDiGraph(edges)
257 assert list(nx.all_topological_sorts(DG)) == [list(range(1, N + 1))]
258
259 def test_ancestors(self):
260 G = nx.DiGraph()
261 ancestors = nx.algorithms.dag.ancestors
262 G.add_edges_from([(1, 2), (1, 3), (4, 2), (4, 3), (4, 5), (2, 6), (5, 6)])
263 assert ancestors(G, 6) == {1, 2, 4, 5}
264 assert ancestors(G, 3) == {1, 4}
265 assert ancestors(G, 1) == set()
266 pytest.raises(nx.NetworkXError, ancestors, G, 8)
267
268 def test_descendants(self):
269 G = nx.DiGraph()
270 descendants = nx.algorithms.dag.descendants
271 G.add_edges_from([(1, 2), (1, 3), (4, 2), (4, 3), (4, 5), (2, 6), (5, 6)])
272 assert descendants(G, 1) == {2, 3, 6}
273 assert descendants(G, 4) == {2, 3, 5, 6}
274 assert descendants(G, 3) == set()
275 pytest.raises(nx.NetworkXError, descendants, G, 8)
276
277 def test_transitive_closure(self):
278 G = nx.DiGraph([(1, 2), (2, 3), (3, 4)])
279 solution = [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
280 assert_edges_equal(nx.transitive_closure(G).edges(), solution)
281 G = nx.DiGraph([(1, 2), (2, 3), (2, 4)])
282 solution = [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4)]
283 assert_edges_equal(nx.transitive_closure(G).edges(), solution)
284 G = nx.DiGraph([(1, 2), (2, 3), (3, 1)])
285 solution = [(1, 2), (2, 1), (2, 3), (3, 2), (1, 3), (3, 1)]
286 soln = sorted(solution + [(n, n) for n in G])
287 assert_edges_equal(sorted(nx.transitive_closure(G).edges()), soln)
288 G = nx.Graph([(1, 2), (2, 3), (3, 4)])
289 pytest.raises(nx.NetworkXNotImplemented, nx.transitive_closure, G)
290
291 # test if edge data is copied
292 G = nx.DiGraph([(1, 2, {"a": 3}), (2, 3, {"b": 0}), (3, 4)])
293 H = nx.transitive_closure(G)
294 for u, v in G.edges():
295 assert G.get_edge_data(u, v) == H.get_edge_data(u, v)
296
297 k = 10
298 G = nx.DiGraph((i, i + 1, {"f": "b", "weight": i}) for i in range(k))
299 H = nx.transitive_closure(G)
300 for u, v in G.edges():
301 assert G.get_edge_data(u, v) == H.get_edge_data(u, v)
302
303 def test_reflexive_transitive_closure(self):
304 G = nx.DiGraph([(1, 2), (2, 3), (3, 4)])
305 solution = [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
306 soln = sorted(solution + [(n, n) for n in G])
307 assert_edges_equal(nx.transitive_closure(G).edges(), solution)
308 assert_edges_equal(nx.transitive_closure(G, False).edges(), solution)
309 assert_edges_equal(nx.transitive_closure(G, True).edges(), soln)
310 assert_edges_equal(nx.transitive_closure(G, None).edges(), solution)
311
312 G = nx.DiGraph([(1, 2), (2, 3), (2, 4)])
313 solution = [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4)]
314 soln = sorted(solution + [(n, n) for n in G])
315 assert_edges_equal(nx.transitive_closure(G).edges(), solution)
316 assert_edges_equal(nx.transitive_closure(G, False).edges(), solution)
317 assert_edges_equal(nx.transitive_closure(G, True).edges(), soln)
318 assert_edges_equal(nx.transitive_closure(G, None).edges(), solution)
319
320 G = nx.DiGraph([(1, 2), (2, 3), (3, 1)])
321 solution = sorted([(1, 2), (2, 1), (2, 3), (3, 2), (1, 3), (3, 1)])
322 soln = sorted(solution + [(n, n) for n in G])
323 assert_edges_equal(sorted(nx.transitive_closure(G).edges()), soln)
324 assert_edges_equal(sorted(nx.transitive_closure(G, False).edges()), soln)
325 assert_edges_equal(sorted(nx.transitive_closure(G, None).edges()), solution)
326 assert_edges_equal(sorted(nx.transitive_closure(G, True).edges()), soln)
327
328 def test_transitive_closure_dag(self):
329 G = nx.DiGraph([(1, 2), (2, 3), (3, 4)])
330 transitive_closure = nx.algorithms.dag.transitive_closure_dag
331 solution = [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
332 assert_edges_equal(transitive_closure(G).edges(), solution)
333 G = nx.DiGraph([(1, 2), (2, 3), (2, 4)])
334 solution = [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4)]
335 assert_edges_equal(transitive_closure(G).edges(), solution)
336 G = nx.Graph([(1, 2), (2, 3), (3, 4)])
337 pytest.raises(nx.NetworkXNotImplemented, transitive_closure, G)
338
339 # test if edge data is copied
340 G = nx.DiGraph([(1, 2, {"a": 3}), (2, 3, {"b": 0}), (3, 4)])
341 H = transitive_closure(G)
342 for u, v in G.edges():
343 assert G.get_edge_data(u, v) == H.get_edge_data(u, v)
344
345 k = 10
346 G = nx.DiGraph((i, i + 1, {"foo": "bar", "weight": i}) for i in range(k))
347 H = transitive_closure(G)
348 for u, v in G.edges():
349 assert G.get_edge_data(u, v) == H.get_edge_data(u, v)
350
351 def test_transitive_reduction(self):
352 G = nx.DiGraph([(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)])
353 transitive_reduction = nx.algorithms.dag.transitive_reduction
354 solution = [(1, 2), (2, 3), (3, 4)]
355 assert_edges_equal(transitive_reduction(G).edges(), solution)
356 G = nx.DiGraph([(1, 2), (1, 3), (1, 4), (2, 3), (2, 4)])
357 transitive_reduction = nx.algorithms.dag.transitive_reduction
358 solution = [(1, 2), (2, 3), (2, 4)]
359 assert_edges_equal(transitive_reduction(G).edges(), solution)
360 G = nx.Graph([(1, 2), (2, 3), (3, 4)])
361 pytest.raises(nx.NetworkXNotImplemented, transitive_reduction, G)
362
363 def _check_antichains(self, solution, result):
364 sol = [frozenset(a) for a in solution]
365 res = [frozenset(a) for a in result]
366 assert set(sol) == set(res)
367
368 def test_antichains(self):
369 antichains = nx.algorithms.dag.antichains
370 G = nx.DiGraph([(1, 2), (2, 3), (3, 4)])
371 solution = [[], [4], [3], [2], [1]]
372 self._check_antichains(list(antichains(G)), solution)
373 G = nx.DiGraph([(1, 2), (2, 3), (2, 4), (3, 5), (5, 6), (5, 7)])
374 solution = [
375 [],
376 [4],
377 [7],
378 [7, 4],
379 [6],
380 [6, 4],
381 [6, 7],
382 [6, 7, 4],
383 [5],
384 [5, 4],
385 [3],
386 [3, 4],
387 [2],
388 [1],
389 ]
390 self._check_antichains(list(antichains(G)), solution)
391 G = nx.DiGraph([(1, 2), (1, 3), (3, 4), (3, 5), (5, 6)])
392 solution = [
393 [],
394 [6],
395 [5],
396 [4],
397 [4, 6],
398 [4, 5],
399 [3],
400 [2],
401 [2, 6],
402 [2, 5],
403 [2, 4],
404 [2, 4, 6],
405 [2, 4, 5],
406 [2, 3],
407 [1],
408 ]
409 self._check_antichains(list(antichains(G)), solution)
410 G = nx.DiGraph({0: [1, 2], 1: [4], 2: [3], 3: [4]})
411 solution = [[], [4], [3], [2], [1], [1, 3], [1, 2], [0]]
412 self._check_antichains(list(antichains(G)), solution)
413 G = nx.DiGraph()
414 self._check_antichains(list(antichains(G)), [[]])
415 G = nx.DiGraph()
417 solution = [[], [0], [1], [1, 0], [2], [2, 0], [2, 1], [2, 1, 0]]
418 self._check_antichains(list(antichains(G)), solution)
419
420 def f(x):
421 return list(antichains(x))
422
423 G = nx.Graph([(1, 2), (2, 3), (3, 4)])
424 pytest.raises(nx.NetworkXNotImplemented, f, G)
425 G = nx.DiGraph([(1, 2), (2, 3), (3, 1)])
426 pytest.raises(nx.NetworkXUnfeasible, f, G)
427
428 def test_lexicographical_topological_sort(self):
429 G = nx.DiGraph([(1, 2), (2, 3), (1, 4), (1, 5), (2, 6)])
430 assert list(nx.lexicographical_topological_sort(G)) == [1, 2, 3, 4, 5, 6]
431 assert list(nx.lexicographical_topological_sort(G, key=lambda x: x)) == [
432 1,
433 2,
434 3,
435 4,
436 5,
437 6,
438 ]
439 assert list(nx.lexicographical_topological_sort(G, key=lambda x: -x)) == [
440 1,
441 5,
442 4,
443 2,
444 6,
445 3,
446 ]
447
448 def test_lexicographical_topological_sort2(self):
449 """
450 Check the case of two or more nodes with same key value.
451 Want to avoid exception raised due to comparing nodes directly.
452 See Issue #3493
453 """
454
455 class Test_Node:
456 def __init__(self, n):
457 self.label = n
458 self.priority = 1
459
460 def __repr__(self):
461 return f"Node({self.label})"
462
463 def sorting_key(node):
464 return node.priority
465
466 test_nodes = [Test_Node(n) for n in range(4)]
467 G = nx.DiGraph()
468 edges = [(0, 1), (0, 2), (0, 3), (2, 3)]
469 G.add_edges_from((test_nodes[a], test_nodes[b]) for a, b in edges)
470
471 sorting = list(nx.lexicographical_topological_sort(G, key=sorting_key))
472 assert sorting == test_nodes
473
474
475 def test_is_aperiodic_cycle():
476 G = nx.DiGraph()
477 nx.add_cycle(G, [1, 2, 3, 4])
478 assert not nx.is_aperiodic(G)
479
480
481 def test_is_aperiodic_cycle2():
482 G = nx.DiGraph()
483 nx.add_cycle(G, [1, 2, 3, 4])
484 nx.add_cycle(G, [3, 4, 5, 6, 7])
485 assert nx.is_aperiodic(G)
486
487
488 def test_is_aperiodic_cycle3():
489 G = nx.DiGraph()
490 nx.add_cycle(G, [1, 2, 3, 4])
491 nx.add_cycle(G, [3, 4, 5, 6])
492 assert not nx.is_aperiodic(G)
493
494
495 def test_is_aperiodic_cycle4():
496 G = nx.DiGraph()
497 nx.add_cycle(G, [1, 2, 3, 4])
499 assert nx.is_aperiodic(G)
500
501
502 def test_is_aperiodic_selfloop():
503 G = nx.DiGraph()
504 nx.add_cycle(G, [1, 2, 3, 4])
506 assert nx.is_aperiodic(G)
507
508
509 def test_is_aperiodic_raise():
510 G = nx.Graph()
511 pytest.raises(nx.NetworkXError, nx.is_aperiodic, G)
512
513
514 def test_is_aperiodic_bipartite():
515 # Bipartite graph
516 G = nx.DiGraph(nx.davis_southern_women_graph())
517 assert not nx.is_aperiodic(G)
518
519
520 def test_is_aperiodic_rary_tree():
521 G = nx.full_rary_tree(3, 27, create_using=nx.DiGraph())
522 assert not nx.is_aperiodic(G)
523
524
525 def test_is_aperiodic_disconnected():
526 # disconnected graph
527 G = nx.DiGraph()
528 nx.add_cycle(G, [1, 2, 3, 4])
529 nx.add_cycle(G, [5, 6, 7, 8])
530 assert not nx.is_aperiodic(G)
533 assert nx.is_aperiodic(G)
534
535
536 def test_is_aperiodic_disconnected2():
537 G = nx.DiGraph()
540 assert not nx.is_aperiodic(G)
541
542
543 class TestDagToBranching:
544 """Unit tests for the :func:`networkx.dag_to_branching` function."""
545
546 def test_single_root(self):
547 """Tests that a directed acyclic graph with a single degree
548 zero node produces an arborescence.
549
550 """
551 G = nx.DiGraph([(0, 1), (0, 2), (1, 3), (2, 3)])
552 B = nx.dag_to_branching(G)
553 expected = nx.DiGraph([(0, 1), (1, 3), (0, 2), (2, 4)])
554 assert nx.is_arborescence(B)
555 assert nx.is_isomorphic(B, expected)
556
557 def test_multiple_roots(self):
558 """Tests that a directed acyclic graph with multiple degree zero
559 nodes creates an arborescence with multiple (weakly) connected
560 components.
561
562 """
563 G = nx.DiGraph([(0, 1), (0, 2), (1, 3), (2, 3), (5, 2)])
564 B = nx.dag_to_branching(G)
565 expected = nx.DiGraph([(0, 1), (1, 3), (0, 2), (2, 4), (5, 6), (6, 7)])
566 assert nx.is_branching(B)
567 assert not nx.is_arborescence(B)
568 assert nx.is_isomorphic(B, expected)
569
570 # # Attributes are not copied by this function. If they were, this would
571 # # be a good test to uncomment.
572 # def test_copy_attributes(self):
573 # """Tests that node attributes are copied in the branching."""
574 # G = nx.DiGraph([(0, 1), (0, 2), (1, 3), (2, 3)])
575 # for v in G:
576 # G.node[v]['label'] = str(v)
577 # B = nx.dag_to_branching(G)
578 # # Determine the root node of the branching.
579 # root = next(v for v, d in B.in_degree() if d == 0)
580 # assert_equal(B.node[root]['label'], '0')
581 # children = B[root]
582 # # Get the left and right children, nodes 1 and 2, respectively.
583 # left, right = sorted(children, key=lambda v: B.node[v]['label'])
584 # assert_equal(B.node[left]['label'], '1')
585 # assert_equal(B.node[right]['label'], '2')
586 # # Get the left grandchild.
587 # children = B[left]
588 # assert_equal(len(children), 1)
589 # left_grandchild = arbitrary_element(children)
590 # assert_equal(B.node[left_grandchild]['label'], '3')
591 # # Get the right grandchild.
592 # children = B[right]
593 # assert_equal(len(children), 1)
594 # right_grandchild = arbitrary_element(children)
595 # assert_equal(B.node[right_grandchild]['label'], '3')
596
598 """Tests that a directed acyclic graph that is already an
599 arborescence produces an isomorphic arborescence as output.
600
601 """
602 A = nx.balanced_tree(2, 2, create_using=nx.DiGraph())
603 B = nx.dag_to_branching(A)
604 assert nx.is_isomorphic(A, B)
605
607 """Tests that a directed acyclic graph that is already a
608 branching produces an isomorphic branching as output.
609
610 """
611 T1 = nx.balanced_tree(2, 2, create_using=nx.DiGraph())
612 T2 = nx.balanced_tree(2, 2, create_using=nx.DiGraph())
613 G = nx.disjoint_union(T1, T2)
614 B = nx.dag_to_branching(G)
615 assert nx.is_isomorphic(G, B)
616
617 def test_not_acyclic(self):
618 """Tests that a non-acyclic graph causes an exception."""
619 with pytest.raises(nx.HasACycle):
620 G = nx.DiGraph(pairwise("abc", cyclic=True))
621 nx.dag_to_branching(G)
622
623 def test_undirected(self):
624 with pytest.raises(nx.NetworkXNotImplemented):
625 nx.dag_to_branching(nx.Graph())
626
627 def test_multigraph(self):
628 with pytest.raises(nx.NetworkXNotImplemented):
629 nx.dag_to_branching(nx.MultiGraph())
630
631 def test_multidigraph(self):
632 with pytest.raises(nx.NetworkXNotImplemented):
633 nx.dag_to_branching(nx.MultiDiGraph())