Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / 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 non-acyclic 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())