Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/algorithms/dag.py @ 1:56ad4e20f292 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
author guerler
date Fri, 31 Jul 2020 00:32:28 -0400
parents
children
comparison
equal deleted inserted replaced
0:d30785e31577 1:56ad4e20f292
1 # -*- coding: utf-8 -*-
2 # Copyright (C) 2006-2019 by
3 # Aric Hagberg <hagberg@lanl.gov>
4 # Dan Schult <dschult@colgate.edu>
5 # Pieter Swart <swart@lanl.gov>
6 # All rights reserved.
7 # BSD license.
8 #
9 # Authors:
10 # Aric Hagberg <aric.hagberg@gmail.com>
11 # Dan Schult <dschult@colgate.edu>
12 # Ben Edwards <bedwards@cs.unm.edu>
13 # Neil Girdhar <neil.girdhar@mcgill.ca>
14 #
15 """Algorithms for directed acyclic graphs (DAGs).
16
17 Note that most of these functions are only guaranteed to work for DAGs.
18 In general, these functions do not check for acyclic-ness, so it is up
19 to the user to check for that.
20 """
21
22 from collections import defaultdict, deque
23 from math import gcd
24 from functools import partial
25 from itertools import chain
26 from itertools import product
27 from itertools import starmap
28 import heapq
29
30 import networkx as nx
31 from networkx.algorithms.traversal.breadth_first_search import \
32 descendants_at_distance
33 from networkx.generators.trees import NIL
34 from networkx.utils import arbitrary_element
35 from networkx.utils import consume
36 from networkx.utils import pairwise
37 from networkx.utils import not_implemented_for
38
39 __all__ = ['descendants',
40 'ancestors',
41 'topological_sort',
42 'lexicographical_topological_sort',
43 'all_topological_sorts',
44 'is_directed_acyclic_graph',
45 'is_aperiodic',
46 'transitive_closure',
47 'transitive_closure_dag',
48 'transitive_reduction',
49 'antichains',
50 'dag_longest_path',
51 'dag_longest_path_length',
52 'dag_to_branching']
53
54 chaini = chain.from_iterable
55
56
57 def descendants(G, source):
58 """Returns all nodes reachable from `source` in `G`.
59
60 Parameters
61 ----------
62 G : NetworkX DiGraph
63 A directed acyclic graph (DAG)
64 source : node in `G`
65
66 Returns
67 -------
68 set()
69 The descendants of `source` in `G`
70 """
71 if not G.has_node(source):
72 raise nx.NetworkXError("The node %s is not in the graph." % source)
73 des = set(n for n, d in nx.shortest_path_length(G, source=source).items())
74 return des - {source}
75
76
77 def ancestors(G, source):
78 """Returns all nodes having a path to `source` in `G`.
79
80 Parameters
81 ----------
82 G : NetworkX DiGraph
83 A directed acyclic graph (DAG)
84 source : node in `G`
85
86 Returns
87 -------
88 set()
89 The ancestors of source in G
90 """
91 if not G.has_node(source):
92 raise nx.NetworkXError("The node %s is not in the graph." % source)
93 anc = set(n for n, d in nx.shortest_path_length(G, target=source).items())
94 return anc - {source}
95
96
97 def has_cycle(G):
98 """Decides whether the directed graph has a cycle."""
99 try:
100 consume(topological_sort(G))
101 except nx.NetworkXUnfeasible:
102 return True
103 else:
104 return False
105
106
107 def is_directed_acyclic_graph(G):
108 """Returns True if the graph `G` is a directed acyclic graph (DAG) or
109 False if not.
110
111 Parameters
112 ----------
113 G : NetworkX graph
114
115 Returns
116 -------
117 bool
118 True if `G` is a DAG, False otherwise
119 """
120 return G.is_directed() and not has_cycle(G)
121
122
123 def topological_sort(G):
124 """Returns a generator of nodes in topologically sorted order.
125
126 A topological sort is a nonunique permutation of the nodes such that an
127 edge from u to v implies that u appears before v in the topological sort
128 order.
129
130 Parameters
131 ----------
132 G : NetworkX digraph
133 A directed acyclic graph (DAG)
134
135 Returns
136 -------
137 iterable
138 An iterable of node names in topological sorted order.
139
140 Raises
141 ------
142 NetworkXError
143 Topological sort is defined for directed graphs only. If the graph `G`
144 is undirected, a :exc:`NetworkXError` is raised.
145
146 NetworkXUnfeasible
147 If `G` is not a directed acyclic graph (DAG) no topological sort exists
148 and a :exc:`NetworkXUnfeasible` exception is raised. This can also be
149 raised if `G` is changed while the returned iterator is being processed
150
151 RuntimeError
152 If `G` is changed while the returned iterator is being processed.
153
154 Examples
155 --------
156 To get the reverse order of the topological sort:
157
158 >>> DG = nx.DiGraph([(1, 2), (2, 3)])
159 >>> list(reversed(list(nx.topological_sort(DG))))
160 [3, 2, 1]
161
162 If your DiGraph naturally has the edges representing tasks/inputs
163 and nodes representing people/processes that initiate tasks, then
164 topological_sort is not quite what you need. You will have to change
165 the tasks to nodes with dependence reflected by edges. The result is
166 a kind of topological sort of the edges. This can be done
167 with :func:`networkx.line_graph` as follows:
168
169 >>> list(nx.topological_sort(nx.line_graph(DG)))
170 [(1, 2), (2, 3)]
171
172 Notes
173 -----
174 This algorithm is based on a description and proof in
175 "Introduction to Algorithms: A Creative Approach" [1]_ .
176
177 See also
178 --------
179 is_directed_acyclic_graph, lexicographical_topological_sort
180
181 References
182 ----------
183 .. [1] Manber, U. (1989).
184 *Introduction to Algorithms - A Creative Approach.* Addison-Wesley.
185 """
186 if not G.is_directed():
187 raise nx.NetworkXError(
188 "Topological sort not defined on undirected graphs.")
189
190 indegree_map = {v: d for v, d in G.in_degree() if d > 0}
191 # These nodes have zero indegree and ready to be returned.
192 zero_indegree = [v for v, d in G.in_degree() if d == 0]
193
194 while zero_indegree:
195 node = zero_indegree.pop()
196 if node not in G:
197 raise RuntimeError("Graph changed during iteration")
198 for _, child in G.edges(node):
199 try:
200 indegree_map[child] -= 1
201 except KeyError:
202 raise RuntimeError("Graph changed during iteration")
203 if indegree_map[child] == 0:
204 zero_indegree.append(child)
205 del indegree_map[child]
206
207 yield node
208
209 if indegree_map:
210 raise nx.NetworkXUnfeasible("Graph contains a cycle or graph changed "
211 "during iteration")
212
213
214 def lexicographical_topological_sort(G, key=None):
215 """Returns a generator of nodes in lexicographically topologically sorted
216 order.
217
218 A topological sort is a nonunique permutation of the nodes such that an
219 edge from u to v implies that u appears before v in the topological sort
220 order.
221
222 Parameters
223 ----------
224 G : NetworkX digraph
225 A directed acyclic graph (DAG)
226
227 key : function, optional
228 This function maps nodes to keys with which to resolve ambiguities in
229 the sort order. Defaults to the identity function.
230
231 Returns
232 -------
233 iterable
234 An iterable of node names in lexicographical topological sort order.
235
236 Raises
237 ------
238 NetworkXError
239 Topological sort is defined for directed graphs only. If the graph `G`
240 is undirected, a :exc:`NetworkXError` is raised.
241
242 NetworkXUnfeasible
243 If `G` is not a directed acyclic graph (DAG) no topological sort exists
244 and a :exc:`NetworkXUnfeasible` exception is raised. This can also be
245 raised if `G` is changed while the returned iterator is being processed
246
247 RuntimeError
248 If `G` is changed while the returned iterator is being processed.
249
250 Notes
251 -----
252 This algorithm is based on a description and proof in
253 "Introduction to Algorithms: A Creative Approach" [1]_ .
254
255 See also
256 --------
257 topological_sort
258
259 References
260 ----------
261 .. [1] Manber, U. (1989).
262 *Introduction to Algorithms - A Creative Approach.* Addison-Wesley.
263 """
264 if not G.is_directed():
265 msg = "Topological sort not defined on undirected graphs."
266 raise nx.NetworkXError(msg)
267
268 if key is None:
269 def key(node):
270 return node
271
272 nodeid_map = {n: i for i, n in enumerate(G)}
273
274 def create_tuple(node):
275 return key(node), nodeid_map[node], node
276
277 indegree_map = {v: d for v, d in G.in_degree() if d > 0}
278 # These nodes have zero indegree and ready to be returned.
279 zero_indegree = [create_tuple(v) for v, d in G.in_degree() if d == 0]
280 heapq.heapify(zero_indegree)
281
282 while zero_indegree:
283 _, _, node = heapq.heappop(zero_indegree)
284
285 if node not in G:
286 raise RuntimeError("Graph changed during iteration")
287 for _, child in G.edges(node):
288 try:
289 indegree_map[child] -= 1
290 except KeyError:
291 raise RuntimeError("Graph changed during iteration")
292 if indegree_map[child] == 0:
293 heapq.heappush(zero_indegree, create_tuple(child))
294 del indegree_map[child]
295
296 yield node
297
298 if indegree_map:
299 msg = "Graph contains a cycle or graph changed during iteration"
300 raise nx.NetworkXUnfeasible(msg)
301
302
303 @not_implemented_for('undirected')
304 def all_topological_sorts(G):
305 """Returns a generator of _all_ topological sorts of the directed graph G.
306
307 A topological sort is a nonunique permutation of the nodes such that an
308 edge from u to v implies that u appears before v in the topological sort
309 order.
310
311 Parameters
312 ----------
313 G : NetworkX DiGraph
314 A directed graph
315
316 Returns
317 -------
318 generator
319 All topological sorts of the digraph G
320
321 Raises
322 ------
323 NetworkXNotImplemented
324 If `G` is not directed
325 NetworkXUnfeasible
326 If `G` is not acyclic
327
328 Examples
329 --------
330 To enumerate all topological sorts of directed graph:
331
332 >>> DG = nx.DiGraph([(1, 2), (2, 3), (2, 4)])
333 >>> list(nx.all_topological_sorts(DG))
334 [[1, 2, 4, 3], [1, 2, 3, 4]]
335
336 Notes
337 -----
338 Implements an iterative version of the algorithm given in [1].
339
340 References
341 ----------
342 .. [1] Knuth, Donald E., Szwarcfiter, Jayme L. (1974).
343 "A Structured Program to Generate All Topological Sorting Arrangements"
344 Information Processing Letters, Volume 2, Issue 6, 1974, Pages 153-157,
345 ISSN 0020-0190,
346 https://doi.org/10.1016/0020-0190(74)90001-5.
347 Elsevier (North-Holland), Amsterdam
348 """
349 if not G.is_directed():
350 raise nx.NetworkXError(
351 "Topological sort not defined on undirected graphs.")
352
353 # the names of count and D are chosen to match the global variables in [1]
354 # number of edges originating in a vertex v
355 count = dict(G.in_degree())
356 # vertices with indegree 0
357 D = deque([v for v, d in G.in_degree() if d == 0])
358 # stack of first value chosen at a position k in the topological sort
359 bases = []
360 current_sort = []
361
362 # do-while construct
363 while True:
364 assert all([count[v] == 0 for v in D])
365
366 if len(current_sort) == len(G):
367 yield list(current_sort)
368
369 # clean-up stack
370 while len(current_sort) > 0:
371 assert len(bases) == len(current_sort)
372 q = current_sort.pop()
373
374 # "restores" all edges (q, x)
375 # NOTE: it is important to iterate over edges instead
376 # of successors, so count is updated correctly in multigraphs
377 for _, j in G.out_edges(q):
378 count[j] += 1
379 assert count[j] >= 0
380 # remove entries from D
381 while len(D) > 0 and count[D[-1]] > 0:
382 D.pop()
383
384 # corresponds to a circular shift of the values in D
385 # if the first value chosen (the base) is in the first
386 # position of D again, we are done and need to consider the
387 # previous condition
388 D.appendleft(q)
389 if D[-1] == bases[-1]:
390 # all possible values have been chosen at current position
391 # remove corresponding marker
392 bases.pop()
393 else:
394 # there are still elements that have not been fixed
395 # at the current position in the topological sort
396 # stop removing elements, escape inner loop
397 break
398
399 else:
400 if len(D) == 0:
401 raise nx.NetworkXUnfeasible("Graph contains a cycle.")
402
403 # choose next node
404 q = D.pop()
405 # "erase" all edges (q, x)
406 # NOTE: it is important to iterate over edges instead
407 # of successors, so count is updated correctly in multigraphs
408 for _, j in G.out_edges(q):
409 count[j] -= 1
410 assert count[j] >= 0
411 if count[j] == 0:
412 D.append(j)
413 current_sort.append(q)
414
415 # base for current position might _not_ be fixed yet
416 if len(bases) < len(current_sort):
417 bases.append(q)
418
419 if len(bases) == 0:
420 break
421
422
423 def is_aperiodic(G):
424 """Returns True if `G` is aperiodic.
425
426 A directed graph is aperiodic if there is no integer k > 1 that
427 divides the length of every cycle in the graph.
428
429 Parameters
430 ----------
431 G : NetworkX DiGraph
432 A directed graph
433
434 Returns
435 -------
436 bool
437 True if the graph is aperiodic False otherwise
438
439 Raises
440 ------
441 NetworkXError
442 If `G` is not directed
443
444 Notes
445 -----
446 This uses the method outlined in [1]_, which runs in $O(m)$ time
447 given $m$ edges in `G`. Note that a graph is not aperiodic if it is
448 acyclic as every integer trivial divides length 0 cycles.
449
450 References
451 ----------
452 .. [1] Jarvis, J. P.; Shier, D. R. (1996),
453 "Graph-theoretic analysis of finite Markov chains,"
454 in Shier, D. R.; Wallenius, K. T., Applied Mathematical Modeling:
455 A Multidisciplinary Approach, CRC Press.
456 """
457 if not G.is_directed():
458 raise nx.NetworkXError(
459 "is_aperiodic not defined for undirected graphs")
460
461 s = arbitrary_element(G)
462 levels = {s: 0}
463 this_level = [s]
464 g = 0
465 lev = 1
466 while this_level:
467 next_level = []
468 for u in this_level:
469 for v in G[u]:
470 if v in levels: # Non-Tree Edge
471 g = gcd(g, levels[u] - levels[v] + 1)
472 else: # Tree Edge
473 next_level.append(v)
474 levels[v] = lev
475 this_level = next_level
476 lev += 1
477 if len(levels) == len(G): # All nodes in tree
478 return g == 1
479 else:
480 return g == 1 and nx.is_aperiodic(G.subgraph(set(G) - set(levels)))
481
482
483 @not_implemented_for('undirected')
484 def transitive_closure(G, reflexive=False):
485 """ Returns transitive closure of a directed graph
486
487 The transitive closure of G = (V,E) is a graph G+ = (V,E+) such that
488 for all v, w in V there is an edge (v, w) in E+ if and only if there
489 is a path from v to w in G.
490
491 Handling of paths from v to v has some flexibility within this definition.
492 A reflexive transitive closure creates a self-loop for the path
493 from v to v of length 0. The usual transitive closure creates a
494 self-loop only if a cycle exists (a path from v to v with length > 0).
495 We also allow an option for no self-loops.
496
497 Parameters
498 ----------
499 G : NetworkX DiGraph
500 A directed graph
501 reflexive : Bool or None, optional (default: False)
502 Determines when cycles create self-loops in the Transitive Closure.
503 If True, trivial cycles (length 0) create self-loops. The result
504 is a reflexive tranistive closure of G.
505 If False (the default) non-trivial cycles create self-loops.
506 If None, self-loops are not created.
507
508 Returns
509 -------
510 NetworkX DiGraph
511 The transitive closure of `G`
512
513 Raises
514 ------
515 NetworkXNotImplemented
516 If `G` is not directed
517
518 References
519 ----------
520 .. [1] http://www.ics.uci.edu/~eppstein/PADS/PartialOrder.py
521
522 TODO this function applies to all directed graphs and is probably misplaced
523 here in dag.py
524 """
525 if reflexive is None:
526 TC = G.copy()
527 for v in G:
528 edges = ((v, u) for u in nx.dfs_preorder_nodes(G, v) if v != u)
529 TC.add_edges_from(edges)
530 return TC
531 if reflexive is True:
532 TC = G.copy()
533 for v in G:
534 edges = ((v, u) for u in nx.dfs_preorder_nodes(G, v))
535 TC.add_edges_from(edges)
536 return TC
537 # reflexive is False
538 TC = G.copy()
539 for v in G:
540 edges = ((v, w) for u, w in nx.edge_dfs(G, v))
541 TC.add_edges_from(edges)
542 return TC
543
544
545 @not_implemented_for('undirected')
546 def transitive_closure_dag(G, topo_order=None):
547 """ Returns the transitive closure of a directed acyclic graph.
548
549 This function is faster than the function `transitive_closure`, but fails
550 if the graph has a cycle.
551
552 The transitive closure of G = (V,E) is a graph G+ = (V,E+) such that
553 for all v, w in V there is an edge (v, w) in E+ if and only if there
554 is a non-null path from v to w in G.
555
556 Parameters
557 ----------
558 G : NetworkX DiGraph
559 A directed acyclic graph (DAG)
560
561 topo_order: list or tuple, optional
562 A topological order for G (if None, the function will compute one)
563
564 Returns
565 -------
566 NetworkX DiGraph
567 The transitive closure of `G`
568
569 Raises
570 ------
571 NetworkXNotImplemented
572 If `G` is not directed
573 NetworkXUnfeasible
574 If `G` has a cycle
575
576 Notes
577 -----
578 This algorithm is probably simple enough to be well-known but I didn't find
579 a mention in the literature.
580 """
581 if topo_order is None:
582 topo_order = list(topological_sort(G))
583
584 TC = G.copy()
585
586 # idea: traverse vertices following a reverse topological order, connecting
587 # each vertex to its descendants at distance 2 as we go
588 for v in reversed(topo_order):
589 TC.add_edges_from((v, u) for u in descendants_at_distance(TC, v, 2))
590
591 return TC
592
593
594 @not_implemented_for('undirected')
595 def transitive_reduction(G):
596 """ Returns transitive reduction of a directed graph
597
598 The transitive reduction of G = (V,E) is a graph G- = (V,E-) such that
599 for all v,w in V there is an edge (v,w) in E- if and only if (v,w) is
600 in E and there is no path from v to w in G with length greater than 1.
601
602 Parameters
603 ----------
604 G : NetworkX DiGraph
605 A directed acyclic graph (DAG)
606
607 Returns
608 -------
609 NetworkX DiGraph
610 The transitive reduction of `G`
611
612 Raises
613 ------
614 NetworkXError
615 If `G` is not a directed acyclic graph (DAG) transitive reduction is
616 not uniquely defined and a :exc:`NetworkXError` exception is raised.
617
618 References
619 ----------
620 https://en.wikipedia.org/wiki/Transitive_reduction
621
622 """
623 if not is_directed_acyclic_graph(G):
624 msg = "Directed Acyclic Graph required for transitive_reduction"
625 raise nx.NetworkXError(msg)
626 TR = nx.DiGraph()
627 TR.add_nodes_from(G.nodes())
628 descendants = {}
629 # count before removing set stored in descendants
630 check_count = dict(G.in_degree)
631 for u in G:
632 u_nbrs = set(G[u])
633 for v in G[u]:
634 if v in u_nbrs:
635 if v not in descendants:
636 descendants[v] = {y for x, y in nx.dfs_edges(G, v)}
637 u_nbrs -= descendants[v]
638 check_count[v] -= 1
639 if check_count[v] == 0:
640 del descendants[v]
641 TR.add_edges_from((u, v) for v in u_nbrs)
642 return TR
643
644
645 @not_implemented_for('undirected')
646 def antichains(G, topo_order=None):
647 """Generates antichains from a directed acyclic graph (DAG).
648
649 An antichain is a subset of a partially ordered set such that any
650 two elements in the subset are incomparable.
651
652 Parameters
653 ----------
654 G : NetworkX DiGraph
655 A directed acyclic graph (DAG)
656
657 topo_order: list or tuple, optional
658 A topological order for G (if None, the function will compute one)
659
660 Returns
661 -------
662 generator object
663
664 Raises
665 ------
666 NetworkXNotImplemented
667 If `G` is not directed
668
669 NetworkXUnfeasible
670 If `G` contains a cycle
671
672 Notes
673 -----
674 This function was originally developed by Peter Jipsen and Franco Saliola
675 for the SAGE project. It's included in NetworkX with permission from the
676 authors. Original SAGE code at:
677
678 https://github.com/sagemath/sage/blob/master/src/sage/combinat/posets/hasse_diagram.py
679
680 References
681 ----------
682 .. [1] Free Lattices, by R. Freese, J. Jezek and J. B. Nation,
683 AMS, Vol 42, 1995, p. 226.
684 """
685 if topo_order is None:
686 topo_order = list(nx.topological_sort(G))
687
688 TC = nx.transitive_closure_dag(G, topo_order)
689 antichains_stacks = [([], list(reversed(topo_order)))]
690
691 while antichains_stacks:
692 (antichain, stack) = antichains_stacks.pop()
693 # Invariant:
694 # - the elements of antichain are independent
695 # - the elements of stack are independent from those of antichain
696 yield antichain
697 while stack:
698 x = stack.pop()
699 new_antichain = antichain + [x]
700 new_stack = [
701 t for t in stack if not ((t in TC[x]) or (x in TC[t]))]
702 antichains_stacks.append((new_antichain, new_stack))
703
704
705 @not_implemented_for('undirected')
706 def dag_longest_path(G, weight='weight', default_weight=1, topo_order=None):
707 """Returns the longest path in a directed acyclic graph (DAG).
708
709 If `G` has edges with `weight` attribute the edge data are used as
710 weight values.
711
712 Parameters
713 ----------
714 G : NetworkX DiGraph
715 A directed acyclic graph (DAG)
716
717 weight : str, optional
718 Edge data key to use for weight
719
720 default_weight : int, optional
721 The weight of edges that do not have a weight attribute
722
723 topo_order: list or tuple, optional
724 A topological order for G (if None, the function will compute one)
725
726 Returns
727 -------
728 list
729 Longest path
730
731 Raises
732 ------
733 NetworkXNotImplemented
734 If `G` is not directed
735
736 See also
737 --------
738 dag_longest_path_length
739
740 """
741 if not G:
742 return []
743
744 if topo_order is None:
745 topo_order = nx.topological_sort(G)
746
747 dist = {} # stores {v : (length, u)}
748 for v in topo_order:
749 us = [(dist[u][0] + data.get(weight, default_weight), u)
750 for u, data in G.pred[v].items()]
751
752 # Use the best predecessor if there is one and its distance is
753 # non-negative, otherwise terminate.
754 maxu = max(us, key=lambda x: x[0]) if us else (0, v)
755 dist[v] = maxu if maxu[0] >= 0 else (0, v)
756
757 u = None
758 v = max(dist, key=lambda x: dist[x][0])
759 path = []
760 while u != v:
761 path.append(v)
762 u = v
763 v = dist[v][1]
764
765 path.reverse()
766 return path
767
768
769 @not_implemented_for('undirected')
770 def dag_longest_path_length(G, weight='weight', default_weight=1):
771 """Returns the longest path length in a DAG
772
773 Parameters
774 ----------
775 G : NetworkX DiGraph
776 A directed acyclic graph (DAG)
777
778 weight : string, optional
779 Edge data key to use for weight
780
781 default_weight : int, optional
782 The weight of edges that do not have a weight attribute
783
784 Returns
785 -------
786 int
787 Longest path length
788
789 Raises
790 ------
791 NetworkXNotImplemented
792 If `G` is not directed
793
794 See also
795 --------
796 dag_longest_path
797 """
798 path = nx.dag_longest_path(G, weight, default_weight)
799 path_length = 0
800 for (u, v) in pairwise(path):
801 path_length += G[u][v].get(weight, default_weight)
802
803 return path_length
804
805
806 def root_to_leaf_paths(G):
807 """Yields root-to-leaf paths in a directed acyclic graph.
808
809 `G` must be a directed acyclic graph. If not, the behavior of this
810 function is undefined. A "root" in this graph is a node of in-degree
811 zero and a "leaf" a node of out-degree zero.
812
813 When invoked, this function iterates over each path from any root to
814 any leaf. A path is a list of nodes.
815
816 """
817 roots = (v for v, d in G.in_degree() if d == 0)
818 leaves = (v for v, d in G.out_degree() if d == 0)
819 all_paths = partial(nx.all_simple_paths, G)
820 # TODO In Python 3, this would be better as `yield from ...`.
821 return chaini(starmap(all_paths, product(roots, leaves)))
822
823
824 @not_implemented_for('multigraph')
825 @not_implemented_for('undirected')
826 def dag_to_branching(G):
827 """Returns a branching representing all (overlapping) paths from
828 root nodes to leaf nodes in the given directed acyclic graph.
829
830 As described in :mod:`networkx.algorithms.tree.recognition`, a
831 *branching* is a directed forest in which each node has at most one
832 parent. In other words, a branching is a disjoint union of
833 *arborescences*. For this function, each node of in-degree zero in
834 `G` becomes a root of one of the arborescences, and there will be
835 one leaf node for each distinct path from that root to a leaf node
836 in `G`.
837
838 Each node `v` in `G` with *k* parents becomes *k* distinct nodes in
839 the returned branching, one for each parent, and the sub-DAG rooted
840 at `v` is duplicated for each copy. The algorithm then recurses on
841 the children of each copy of `v`.
842
843 Parameters
844 ----------
845 G : NetworkX graph
846 A directed acyclic graph.
847
848 Returns
849 -------
850 DiGraph
851 The branching in which there is a bijection between root-to-leaf
852 paths in `G` (in which multiple paths may share the same leaf)
853 and root-to-leaf paths in the branching (in which there is a
854 unique path from a root to a leaf).
855
856 Each node has an attribute 'source' whose value is the original
857 node to which this node corresponds. No other graph, node, or
858 edge attributes are copied into this new graph.
859
860 Raises
861 ------
862 NetworkXNotImplemented
863 If `G` is not directed, or if `G` is a multigraph.
864
865 HasACycle
866 If `G` is not acyclic.
867
868 Examples
869 --------
870 To examine which nodes in the returned branching were produced by
871 which original node in the directed acyclic graph, we can collect
872 the mapping from source node to new nodes into a dictionary. For
873 example, consider the directed diamond graph::
874
875 >>> from collections import defaultdict
876 >>> from operator import itemgetter
877 >>>
878 >>> G = nx.DiGraph(nx.utils.pairwise('abd'))
879 >>> G.add_edges_from(nx.utils.pairwise('acd'))
880 >>> B = nx.dag_to_branching(G)
881 >>>
882 >>> sources = defaultdict(set)
883 >>> for v, source in B.nodes(data='source'):
884 ... sources[source].add(v)
885 >>> len(sources['a'])
886 1
887 >>> len(sources['d'])
888 2
889
890 To copy node attributes from the original graph to the new graph,
891 you can use a dictionary like the one constructed in the above
892 example::
893
894 >>> for source, nodes in sources.items():
895 ... for v in nodes:
896 ... B.nodes[v].update(G.nodes[source])
897
898 Notes
899 -----
900 This function is not idempotent in the sense that the node labels in
901 the returned branching may be uniquely generated each time the
902 function is invoked. In fact, the node labels may not be integers;
903 in order to relabel the nodes to be more readable, you can use the
904 :func:`networkx.convert_node_labels_to_integers` function.
905
906 The current implementation of this function uses
907 :func:`networkx.prefix_tree`, so it is subject to the limitations of
908 that function.
909
910 """
911 if has_cycle(G):
912 msg = 'dag_to_branching is only defined for acyclic graphs'
913 raise nx.HasACycle(msg)
914 paths = root_to_leaf_paths(G)
915 B, root = nx.prefix_tree(paths)
916 # Remove the synthetic `root` and `NIL` nodes in the prefix tree.
917 B.remove_node(root)
918 B.remove_node(NIL)
919 return B