Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Algorithms for directed acyclic graphs (DAGs).
3Note that most of these functions are only guaranteed to work for DAGs.
4In general, these functions do not check for acyclic-ness, so it is up
5to the user to check for that.
6"""
8import heapq
9from collections import deque
10from itertools import combinations, product
11from math import gcd
13import networkx as nx
14from networkx.utils import arbitrary_element, not_implemented_for, pairwise
16__all__ = [
17 "descendants",
18 "ancestors",
19 "topological_sort",
20 "lexicographical_topological_sort",
21 "all_topological_sorts",
22 "topological_generations",
23 "is_directed_acyclic_graph",
24 "is_aperiodic",
25 "transitive_closure",
26 "transitive_closure_dag",
27 "transitive_reduction",
28 "antichains",
29 "dag_longest_path",
30 "dag_longest_path_length",
31 "dag_to_branching",
32]
35@nx._dispatchable
36def descendants(G, source):
37 """Returns all nodes reachable from `source` in `G`.
39 Parameters
40 ----------
41 G : NetworkX Graph
42 source : node in `G`
44 Returns
45 -------
46 set()
47 The descendants of `source` in `G`
49 Raises
50 ------
51 NetworkXError
52 If node `source` is not in `G`.
54 Examples
55 --------
56 >>> DG = nx.path_graph(5, create_using=nx.DiGraph)
57 >>> sorted(nx.descendants(DG, 2))
58 [3, 4]
60 The `source` node is not a descendant of itself, but can be included manually:
62 >>> sorted(nx.descendants(DG, 2) | {2})
63 [2, 3, 4]
65 See also
66 --------
67 ancestors
68 """
69 return {child for parent, child in nx.bfs_edges(G, source)}
72@nx._dispatchable
73def ancestors(G, source):
74 """Returns all nodes having a path to `source` in `G`.
76 Parameters
77 ----------
78 G : NetworkX Graph
79 source : node in `G`
81 Returns
82 -------
83 set()
84 The ancestors of `source` in `G`
86 Raises
87 ------
88 NetworkXError
89 If node `source` is not in `G`.
91 Examples
92 --------
93 >>> DG = nx.path_graph(5, create_using=nx.DiGraph)
94 >>> sorted(nx.ancestors(DG, 2))
95 [0, 1]
97 The `source` node is not an ancestor of itself, but can be included manually:
99 >>> sorted(nx.ancestors(DG, 2) | {2})
100 [0, 1, 2]
102 See also
103 --------
104 descendants
105 """
106 return {child for parent, child in nx.bfs_edges(G, source, reverse=True)}
109@nx._dispatchable
110def has_cycle(G):
111 """Decides whether the directed graph has a cycle."""
112 try:
113 # Feed the entire iterator into a zero-length deque.
114 deque(topological_sort(G), maxlen=0)
115 except nx.NetworkXUnfeasible:
116 return True
117 else:
118 return False
121@nx._dispatchable
122def is_directed_acyclic_graph(G):
123 """Returns True if the graph `G` is a directed acyclic graph (DAG) or
124 False if not.
126 Parameters
127 ----------
128 G : NetworkX graph
130 Returns
131 -------
132 bool
133 True if `G` is a DAG, False otherwise
135 Examples
136 --------
137 Undirected graph::
139 >>> G = nx.Graph([(1, 2), (2, 3)])
140 >>> nx.is_directed_acyclic_graph(G)
141 False
143 Directed graph with cycle::
145 >>> G = nx.DiGraph([(1, 2), (2, 3), (3, 1)])
146 >>> nx.is_directed_acyclic_graph(G)
147 False
149 Directed acyclic graph::
151 >>> G = nx.DiGraph([(1, 2), (2, 3)])
152 >>> nx.is_directed_acyclic_graph(G)
153 True
155 See also
156 --------
157 topological_sort
158 """
159 return G.is_directed() and not has_cycle(G)
162@nx._dispatchable
163def topological_generations(G):
164 """Stratifies a DAG into generations.
166 A topological generation is node collection in which ancestors of a node in each
167 generation are guaranteed to be in a previous generation, and any descendants of
168 a node are guaranteed to be in a following generation. Nodes are guaranteed to
169 be in the earliest possible generation that they can belong to.
171 Parameters
172 ----------
173 G : NetworkX digraph
174 A directed acyclic graph (DAG)
176 Yields
177 ------
178 sets of nodes
179 Yields sets of nodes representing each generation.
181 Raises
182 ------
183 NetworkXError
184 Generations are defined for directed graphs only. If the graph
185 `G` is undirected, a :exc:`NetworkXError` is raised.
187 NetworkXUnfeasible
188 If `G` is not a directed acyclic graph (DAG) no topological generations
189 exist and a :exc:`NetworkXUnfeasible` exception is raised. This can also
190 be raised if `G` is changed while the returned iterator is being processed
192 RuntimeError
193 If `G` is changed while the returned iterator is being processed.
195 Examples
196 --------
197 >>> DG = nx.DiGraph([(2, 1), (3, 1)])
198 >>> [sorted(generation) for generation in nx.topological_generations(DG)]
199 [[2, 3], [1]]
201 Notes
202 -----
203 The generation in which a node resides can also be determined by taking the
204 max-path-distance from the node to the farthest leaf node. That value can
205 be obtained with this function using `enumerate(topological_generations(G))`.
207 See also
208 --------
209 topological_sort
210 """
211 if not G.is_directed():
212 raise nx.NetworkXError("Topological sort not defined on undirected graphs.")
214 multigraph = G.is_multigraph()
215 indegree_map = {v: d for v, d in G.in_degree() if d > 0}
216 zero_indegree = [v for v, d in G.in_degree() if d == 0]
218 while zero_indegree:
219 this_generation = zero_indegree
220 zero_indegree = []
221 for node in this_generation:
222 if node not in G:
223 raise RuntimeError("Graph changed during iteration")
224 for child in G.neighbors(node):
225 try:
226 indegree_map[child] -= len(G[node][child]) if multigraph else 1
227 except KeyError as err:
228 raise RuntimeError("Graph changed during iteration") from err
229 if indegree_map[child] == 0:
230 zero_indegree.append(child)
231 del indegree_map[child]
232 yield this_generation
234 if indegree_map:
235 raise nx.NetworkXUnfeasible(
236 "Graph contains a cycle or graph changed during iteration"
237 )
240@nx._dispatchable
241def topological_sort(G):
242 """Returns a generator of nodes in topologically sorted order.
244 A topological sort is a nonunique permutation of the nodes of a
245 directed graph such that an edge from u to v implies that u
246 appears before v in the topological sort order. This ordering is
247 valid only if the graph has no directed cycles.
249 Parameters
250 ----------
251 G : NetworkX digraph
252 A directed acyclic graph (DAG)
254 Yields
255 ------
256 nodes
257 Yields the nodes in topological sorted order.
259 Raises
260 ------
261 NetworkXError
262 Topological sort is defined for directed graphs only. If the graph `G`
263 is undirected, a :exc:`NetworkXError` is raised.
265 NetworkXUnfeasible
266 If `G` is not a directed acyclic graph (DAG) no topological sort exists
267 and a :exc:`NetworkXUnfeasible` exception is raised. This can also be
268 raised if `G` is changed while the returned iterator is being processed
270 RuntimeError
271 If `G` is changed while the returned iterator is being processed.
273 Examples
274 --------
275 To get the reverse order of the topological sort:
277 >>> DG = nx.DiGraph([(1, 2), (2, 3)])
278 >>> list(reversed(list(nx.topological_sort(DG))))
279 [3, 2, 1]
281 If your DiGraph naturally has the edges representing tasks/inputs
282 and nodes representing people/processes that initiate tasks, then
283 topological_sort is not quite what you need. You will have to change
284 the tasks to nodes with dependence reflected by edges. The result is
285 a kind of topological sort of the edges. This can be done
286 with :func:`networkx.line_graph` as follows:
288 >>> list(nx.topological_sort(nx.line_graph(DG)))
289 [(1, 2), (2, 3)]
291 Notes
292 -----
293 This algorithm is based on a description and proof in
294 "Introduction to Algorithms: A Creative Approach" [1]_ .
296 See also
297 --------
298 is_directed_acyclic_graph, lexicographical_topological_sort
300 References
301 ----------
302 .. [1] Manber, U. (1989).
303 *Introduction to Algorithms - A Creative Approach.* Addison-Wesley.
304 """
305 for generation in nx.topological_generations(G):
306 yield from generation
309@nx._dispatchable
310def lexicographical_topological_sort(G, key=None):
311 """Generate the nodes in the unique lexicographical topological sort order.
313 Generates a unique ordering of nodes by first sorting topologically (for which there are often
314 multiple valid orderings) and then additionally by sorting lexicographically.
316 A topological sort arranges the nodes of a directed graph so that the
317 upstream node of each directed edge precedes the downstream node.
318 It is always possible to find a solution for directed graphs that have no cycles.
319 There may be more than one valid solution.
321 Lexicographical sorting is just sorting alphabetically. It is used here to break ties in the
322 topological sort and to determine a single, unique ordering. This can be useful in comparing
323 sort results.
325 The lexicographical order can be customized by providing a function to the `key=` parameter.
326 The definition of the key function is the same as used in python's built-in `sort()`.
327 The function takes a single argument and returns a key to use for sorting purposes.
329 Lexicographical sorting can fail if the node names are un-sortable. See the example below.
330 The solution is to provide a function to the `key=` argument that returns sortable keys.
333 Parameters
334 ----------
335 G : NetworkX digraph
336 A directed acyclic graph (DAG)
338 key : function, optional
339 A function of one argument that converts a node name to a comparison key.
340 It defines and resolves ambiguities in the sort order. Defaults to the identity function.
342 Yields
343 ------
344 nodes
345 Yields the nodes of G in lexicographical topological sort order.
347 Raises
348 ------
349 NetworkXError
350 Topological sort is defined for directed graphs only. If the graph `G`
351 is undirected, a :exc:`NetworkXError` is raised.
353 NetworkXUnfeasible
354 If `G` is not a directed acyclic graph (DAG) no topological sort exists
355 and a :exc:`NetworkXUnfeasible` exception is raised. This can also be
356 raised if `G` is changed while the returned iterator is being processed
358 RuntimeError
359 If `G` is changed while the returned iterator is being processed.
361 TypeError
362 Results from un-sortable node names.
363 Consider using `key=` parameter to resolve ambiguities in the sort order.
365 Examples
366 --------
367 >>> DG = nx.DiGraph([(2, 1), (2, 5), (1, 3), (1, 4), (5, 4)])
368 >>> list(nx.lexicographical_topological_sort(DG))
369 [2, 1, 3, 5, 4]
370 >>> list(nx.lexicographical_topological_sort(DG, key=lambda x: -x))
371 [2, 5, 1, 4, 3]
373 The sort will fail for any graph with integer and string nodes. Comparison of integer to strings
374 is not defined in python. Is 3 greater or less than 'red'?
376 >>> DG = nx.DiGraph([(1, "red"), (3, "red"), (1, "green"), (2, "blue")])
377 >>> list(nx.lexicographical_topological_sort(DG))
378 Traceback (most recent call last):
379 ...
380 TypeError: '<' not supported between instances of 'str' and 'int'
381 ...
383 Incomparable nodes can be resolved using a `key` function. This example function
384 allows comparison of integers and strings by returning a tuple where the first
385 element is True for `str`, False otherwise. The second element is the node name.
386 This groups the strings and integers separately so they can be compared only among themselves.
388 >>> key = lambda node: (isinstance(node, str), node)
389 >>> list(nx.lexicographical_topological_sort(DG, key=key))
390 [1, 2, 3, 'blue', 'green', 'red']
392 Notes
393 -----
394 This algorithm is based on a description and proof in
395 "Introduction to Algorithms: A Creative Approach" [1]_ .
397 See also
398 --------
399 topological_sort
401 References
402 ----------
403 .. [1] Manber, U. (1989).
404 *Introduction to Algorithms - A Creative Approach.* Addison-Wesley.
405 """
406 if not G.is_directed():
407 msg = "Topological sort not defined on undirected graphs."
408 raise nx.NetworkXError(msg)
410 if key is None:
412 def key(node):
413 return node
415 nodeid_map = {n: i for i, n in enumerate(G)}
417 def create_tuple(node):
418 return key(node), nodeid_map[node], node
420 indegree_map = {v: d for v, d in G.in_degree() if d > 0}
421 # These nodes have zero indegree and ready to be returned.
422 zero_indegree = [create_tuple(v) for v, d in G.in_degree() if d == 0]
423 heapq.heapify(zero_indegree)
425 while zero_indegree:
426 _, _, node = heapq.heappop(zero_indegree)
428 if node not in G:
429 raise RuntimeError("Graph changed during iteration")
430 for _, child in G.edges(node):
431 try:
432 indegree_map[child] -= 1
433 except KeyError as err:
434 raise RuntimeError("Graph changed during iteration") from err
435 if indegree_map[child] == 0:
436 try:
437 heapq.heappush(zero_indegree, create_tuple(child))
438 except TypeError as err:
439 raise TypeError(
440 f"{err}\nConsider using `key=` parameter to resolve ambiguities in the sort order."
441 )
442 del indegree_map[child]
444 yield node
446 if indegree_map:
447 msg = "Graph contains a cycle or graph changed during iteration"
448 raise nx.NetworkXUnfeasible(msg)
451@not_implemented_for("undirected")
452@nx._dispatchable
453def all_topological_sorts(G):
454 """Returns a generator of _all_ topological sorts of the directed graph G.
456 A topological sort is a nonunique permutation of the nodes such that an
457 edge from u to v implies that u appears before v in the topological sort
458 order.
460 Parameters
461 ----------
462 G : NetworkX DiGraph
463 A directed graph
465 Yields
466 ------
467 topological_sort_order : list
468 a list of nodes in `G`, representing one of the topological sort orders
470 Raises
471 ------
472 NetworkXNotImplemented
473 If `G` is not directed
474 NetworkXUnfeasible
475 If `G` is not acyclic
477 Examples
478 --------
479 To enumerate all topological sorts of directed graph:
481 >>> DG = nx.DiGraph([(1, 2), (2, 3), (2, 4)])
482 >>> list(nx.all_topological_sorts(DG))
483 [[1, 2, 4, 3], [1, 2, 3, 4]]
485 Notes
486 -----
487 Implements an iterative version of the algorithm given in [1].
489 References
490 ----------
491 .. [1] Knuth, Donald E., Szwarcfiter, Jayme L. (1974).
492 "A Structured Program to Generate All Topological Sorting Arrangements"
493 Information Processing Letters, Volume 2, Issue 6, 1974, Pages 153-157,
494 ISSN 0020-0190,
495 https://doi.org/10.1016/0020-0190(74)90001-5.
496 Elsevier (North-Holland), Amsterdam
497 """
498 if not G.is_directed():
499 raise nx.NetworkXError("Topological sort not defined on undirected graphs.")
501 # the names of count and D are chosen to match the global variables in [1]
502 # number of edges originating in a vertex v
503 count = dict(G.in_degree())
504 # vertices with indegree 0
505 D = deque([v for v, d in G.in_degree() if d == 0])
506 # stack of first value chosen at a position k in the topological sort
507 bases = []
508 current_sort = []
510 # do-while construct
511 while True:
512 assert all(count[v] == 0 for v in D)
514 if len(current_sort) == len(G):
515 yield list(current_sort)
517 # clean-up stack
518 while len(current_sort) > 0:
519 assert len(bases) == len(current_sort)
520 q = current_sort.pop()
522 # "restores" all edges (q, x)
523 # NOTE: it is important to iterate over edges instead
524 # of successors, so count is updated correctly in multigraphs
525 for _, j in G.out_edges(q):
526 count[j] += 1
527 assert count[j] >= 0
528 # remove entries from D
529 while len(D) > 0 and count[D[-1]] > 0:
530 D.pop()
532 # corresponds to a circular shift of the values in D
533 # if the first value chosen (the base) is in the first
534 # position of D again, we are done and need to consider the
535 # previous condition
536 D.appendleft(q)
537 if D[-1] == bases[-1]:
538 # all possible values have been chosen at current position
539 # remove corresponding marker
540 bases.pop()
541 else:
542 # there are still elements that have not been fixed
543 # at the current position in the topological sort
544 # stop removing elements, escape inner loop
545 break
547 else:
548 if len(D) == 0:
549 raise nx.NetworkXUnfeasible("Graph contains a cycle.")
551 # choose next node
552 q = D.pop()
553 # "erase" all edges (q, x)
554 # NOTE: it is important to iterate over edges instead
555 # of successors, so count is updated correctly in multigraphs
556 for _, j in G.out_edges(q):
557 count[j] -= 1
558 assert count[j] >= 0
559 if count[j] == 0:
560 D.append(j)
561 current_sort.append(q)
563 # base for current position might _not_ be fixed yet
564 if len(bases) < len(current_sort):
565 bases.append(q)
567 if len(bases) == 0:
568 break
571@not_implemented_for("undirected")
572@nx._dispatchable
573def is_aperiodic(G):
574 """Determine whether a directed graph is aperiodic.
576 A strongly connected directed graph is aperiodic if there is no integer ``k > 1``
577 that divides the length of every cycle in the graph.
579 This function requires the graph `G` to be strongly connected and will raise
580 an error if it's not. For graphs that are not strongly connected, you should
581 first identify their strongly connected components
582 (using :func:`~networkx.algorithms.components.strongly_connected_components`)
583 or attracting components
584 (using :func:`~networkx.algorithms.components.attracting_components`),
585 and then apply this function to those individual components.
587 Parameters
588 ----------
589 G : NetworkX graph
590 A directed graph.
592 Returns
593 -------
594 bool
595 Whether the graph is aperiodic.
597 Raises
598 ------
599 NetworkXNotImplemented
600 If `G` is not directed.
601 NetworkXError
602 If `G` is not strongly connected.
603 NetworkXPointlessConcept
604 If `G` has no nodes.
606 Examples
607 --------
608 A graph consisting of one cycle, the length of which is 2. Therefore ``k = 2``
609 divides the length of every cycle in the graph and thus the graph
610 is *not aperiodic*::
612 >>> DG = nx.DiGraph([(1, 2), (2, 1)])
613 >>> nx.is_aperiodic(DG)
614 False
616 A graph consisting of two cycles: one of length 2 and the other of length 3.
617 The cycle lengths are coprime, so there is no single value of k where ``k > 1``
618 that divides each cycle length and therefore the graph is *aperiodic*::
620 >>> DG = nx.DiGraph([(1, 2), (2, 3), (3, 1), (1, 4), (4, 1)])
621 >>> nx.is_aperiodic(DG)
622 True
624 A graph created from cycles of the same length can still be aperiodic since
625 the cycles can overlap and form new cycles of different lengths. For example,
626 the following graph contains a cycle ``[4, 2, 3, 1]`` of length 4, which is coprime
627 with the explicitly added cycles of length 3, so the graph is aperiodic::
629 >>> DG = nx.DiGraph()
630 >>> nx.add_cycle(DG, [1, 2, 3])
631 >>> nx.add_cycle(DG, [2, 1, 4])
632 >>> nx.is_aperiodic(DG)
633 True
635 A single-node graph's aperiodicity depends on whether it has a self-loop:
636 it is aperiodic if a self-loop exists, and periodic otherwise::
638 >>> G = nx.DiGraph()
639 >>> G.add_node(1)
640 >>> nx.is_aperiodic(G)
641 False
642 >>> G.add_edge(1, 1)
643 >>> nx.is_aperiodic(G)
644 True
646 A Markov chain can be modeled as a directed graph, with nodes representing
647 states and edges representing transitions with non-zero probability.
648 Aperiodicity is typically considered for irreducible Markov chains,
649 which are those that are *strongly connected* as graphs.
651 The following Markov chain is irreducible and aperiodic, and thus
652 ergodic. It is guaranteed to have a unique stationary distribution::
654 >>> G = nx.DiGraph()
655 >>> nx.add_cycle(G, [1, 2, 3, 4])
656 >>> G.add_edge(1, 3)
657 >>> nx.is_aperiodic(G)
658 True
660 Reducible Markov chains can sometimes have a unique stationary distribution.
661 This occurs if the chain has exactly one closed communicating class and
662 that class itself is aperiodic (see [1]_). You can use
663 :func:`~networkx.algorithms.components.attracting_components`
664 to find these closed communicating classes::
666 >>> G = nx.DiGraph([(1, 3), (2, 3)])
667 >>> nx.add_cycle(G, [3, 4, 5, 6])
668 >>> nx.add_cycle(G, [3, 5, 6])
669 >>> communicating_classes = list(nx.strongly_connected_components(G))
670 >>> len(communicating_classes)
671 3
672 >>> closed_communicating_classes = list(nx.attracting_components(G))
673 >>> len(closed_communicating_classes)
674 1
675 >>> nx.is_aperiodic(G.subgraph(closed_communicating_classes[0]))
676 True
678 Notes
679 -----
680 This uses the method outlined in [1]_, which runs in $O(m)$ time
681 given $m$ edges in `G`.
683 References
684 ----------
685 .. [1] Jarvis, J. P.; Shier, D. R. (1996),
686 "Graph-theoretic analysis of finite Markov chains,"
687 in Shier, D. R.; Wallenius, K. T., Applied Mathematical Modeling:
688 A Multidisciplinary Approach, CRC Press.
689 """
690 if len(G) == 0:
691 raise nx.NetworkXPointlessConcept("Graph has no nodes.")
692 if not nx.is_strongly_connected(G):
693 raise nx.NetworkXError("Graph is not strongly connected.")
695 s = nx.utils.arbitrary_element(G)
696 levels = {s: 0}
697 g = 0
698 # There are 3 relevant possible edge types in `dfs_labeled_edges`:
699 # "forward", "reverse", and "nontree".
700 for u, v, d in nx.dfs_labeled_edges(G, s):
701 if d == "forward":
702 # "forward" edges indicate a new node.
703 levels[v] = levels[u] + 1
704 elif d == "nontree" and (g := gcd(g, levels[u] - levels[v] + 1)) == 1:
705 # "nontree" edges indicate a previously explored node.
706 # Check whether this affects the common factor of cycle lengths.
707 return True
708 # "reverse" edges indicate backtracking in DFS and can be ignored.
709 return False
712@nx._dispatchable(preserve_all_attrs=True, returns_graph=True)
713def transitive_closure(G, reflexive=False):
714 """Returns transitive closure of a graph
716 The transitive closure of G = (V,E) is a graph G+ = (V,E+) such that
717 for all v, w in V there is an edge (v, w) in E+ if and only if there
718 is a path from v to w in G.
720 Handling of paths from v to v has some flexibility within this definition.
721 A reflexive transitive closure creates a self-loop for the path
722 from v to v of length 0. The usual transitive closure creates a
723 self-loop only if a cycle exists (a path from v to v with length > 0).
724 We also allow an option for no self-loops.
726 Parameters
727 ----------
728 G : NetworkX Graph
729 A directed/undirected graph/multigraph.
730 reflexive : Bool or None, optional (default: False)
731 Determines when cycles create self-loops in the Transitive Closure.
732 If True, trivial cycles (length 0) create self-loops. The result
733 is a reflexive transitive closure of G.
734 If False (the default) non-trivial cycles create self-loops.
735 If None, self-loops are not created.
737 Returns
738 -------
739 NetworkX graph
740 The transitive closure of `G`
742 Raises
743 ------
744 NetworkXError
745 If `reflexive` not in `{None, True, False}`
747 Examples
748 --------
749 The treatment of trivial (i.e. length 0) cycles is controlled by the
750 `reflexive` parameter.
752 Trivial (i.e. length 0) cycles do not create self-loops when
753 ``reflexive=False`` (the default)::
755 >>> DG = nx.DiGraph([(1, 2), (2, 3)])
756 >>> TC = nx.transitive_closure(DG, reflexive=False)
757 >>> TC.edges()
758 OutEdgeView([(1, 2), (1, 3), (2, 3)])
760 However, nontrivial (i.e. length greater than 0) cycles create self-loops
761 when ``reflexive=False`` (the default)::
763 >>> DG = nx.DiGraph([(1, 2), (2, 3), (3, 1)])
764 >>> TC = nx.transitive_closure(DG, reflexive=False)
765 >>> TC.edges()
766 OutEdgeView([(1, 2), (1, 3), (1, 1), (2, 3), (2, 1), (2, 2), (3, 1), (3, 2), (3, 3)])
768 Trivial cycles (length 0) create self-loops when ``reflexive=True``::
770 >>> DG = nx.DiGraph([(1, 2), (2, 3)])
771 >>> TC = nx.transitive_closure(DG, reflexive=True)
772 >>> TC.edges()
773 OutEdgeView([(1, 2), (1, 1), (1, 3), (2, 3), (2, 2), (3, 3)])
775 And the third option is not to create self-loops at all when ``reflexive=None``::
777 >>> DG = nx.DiGraph([(1, 2), (2, 3), (3, 1)])
778 >>> TC = nx.transitive_closure(DG, reflexive=None)
779 >>> TC.edges()
780 OutEdgeView([(1, 2), (1, 3), (2, 3), (2, 1), (3, 1), (3, 2)])
782 References
783 ----------
784 .. [1] https://www.ics.uci.edu/~eppstein/PADS/PartialOrder.py
785 """
786 TC = G.copy()
788 if reflexive not in {None, True, False}:
789 raise nx.NetworkXError("Incorrect value for the parameter `reflexive`")
791 for v in G:
792 if reflexive is None:
793 TC.add_edges_from((v, u) for u in nx.descendants(G, v) if u not in TC[v])
794 elif reflexive is True:
795 TC.add_edges_from(
796 (v, u) for u in nx.descendants(G, v) | {v} if u not in TC[v]
797 )
798 elif reflexive is False:
799 TC.add_edges_from((v, e[1]) for e in nx.edge_bfs(G, v) if e[1] not in TC[v])
801 return TC
804@not_implemented_for("undirected")
805@nx._dispatchable(preserve_all_attrs=True, returns_graph=True)
806def transitive_closure_dag(G, topo_order=None):
807 """Returns the transitive closure of a directed acyclic graph.
809 This function is faster than the function `transitive_closure`, but fails
810 if the graph has a cycle.
812 The transitive closure of G = (V,E) is a graph G+ = (V,E+) such that
813 for all v, w in V there is an edge (v, w) in E+ if and only if there
814 is a non-null path from v to w in G.
816 Parameters
817 ----------
818 G : NetworkX DiGraph
819 A directed acyclic graph (DAG)
821 topo_order: list or tuple, optional
822 A topological order for G (if None, the function will compute one)
824 Returns
825 -------
826 NetworkX DiGraph
827 The transitive closure of `G`
829 Raises
830 ------
831 NetworkXNotImplemented
832 If `G` is not directed
833 NetworkXUnfeasible
834 If `G` has a cycle
836 Examples
837 --------
838 >>> DG = nx.DiGraph([(1, 2), (2, 3)])
839 >>> TC = nx.transitive_closure_dag(DG)
840 >>> TC.edges()
841 OutEdgeView([(1, 2), (1, 3), (2, 3)])
843 Notes
844 -----
845 This algorithm is probably simple enough to be well-known but I didn't find
846 a mention in the literature.
847 """
848 if topo_order is None:
849 topo_order = list(topological_sort(G))
851 TC = G.copy()
853 # idea: traverse vertices following a reverse topological order, connecting
854 # each vertex to its descendants at distance 2 as we go
855 for v in reversed(topo_order):
856 TC.add_edges_from((v, u) for u in nx.descendants_at_distance(TC, v, 2))
858 return TC
861@not_implemented_for("undirected")
862@nx._dispatchable(returns_graph=True)
863def transitive_reduction(G):
864 """Returns transitive reduction of a directed graph
866 The transitive reduction of G = (V,E) is a graph G- = (V,E-) such that
867 for all v,w in V there is an edge (v,w) in E- if and only if (v,w) is
868 in E and there is no path from v to w in G with length greater than 1.
870 Parameters
871 ----------
872 G : NetworkX DiGraph
873 A directed acyclic graph (DAG)
875 Returns
876 -------
877 NetworkX DiGraph
878 The transitive reduction of `G`
880 Raises
881 ------
882 NetworkXError
883 If `G` is not a directed acyclic graph (DAG) transitive reduction is
884 not uniquely defined and a :exc:`NetworkXError` exception is raised.
886 Examples
887 --------
888 To perform transitive reduction on a DiGraph:
890 >>> DG = nx.DiGraph([(1, 2), (2, 3), (1, 3)])
891 >>> TR = nx.transitive_reduction(DG)
892 >>> list(TR.edges)
893 [(1, 2), (2, 3)]
895 To avoid unnecessary data copies, this implementation does not return a
896 DiGraph with node/edge data.
897 To perform transitive reduction on a DiGraph and transfer node/edge data:
899 >>> DG = nx.DiGraph()
900 >>> DG.add_edges_from([(1, 2), (2, 3), (1, 3)], color="red")
901 >>> TR = nx.transitive_reduction(DG)
902 >>> TR.add_nodes_from(DG.nodes(data=True))
903 >>> TR.add_edges_from((u, v, DG.edges[u, v]) for u, v in TR.edges)
904 >>> list(TR.edges(data=True))
905 [(1, 2, {'color': 'red'}), (2, 3, {'color': 'red'})]
907 References
908 ----------
909 https://en.wikipedia.org/wiki/Transitive_reduction
911 """
912 if not is_directed_acyclic_graph(G):
913 msg = "Directed Acyclic Graph required for transitive_reduction"
914 raise nx.NetworkXError(msg)
915 TR = nx.DiGraph()
916 TR.add_nodes_from(G.nodes())
917 descendants = {}
918 # count before removing set stored in descendants
919 check_count = dict(G.in_degree)
920 for u in G:
921 u_nbrs = set(G[u])
922 for v in G[u]:
923 if v in u_nbrs:
924 if v not in descendants:
925 descendants[v] = {y for x, y in nx.dfs_edges(G, v)}
926 u_nbrs -= descendants[v]
927 check_count[v] -= 1
928 if check_count[v] == 0:
929 del descendants[v]
930 TR.add_edges_from((u, v) for v in u_nbrs)
931 return TR
934@not_implemented_for("undirected")
935@nx._dispatchable
936def antichains(G, topo_order=None):
937 """Generates antichains from a directed acyclic graph (DAG).
939 An antichain is a subset of a partially ordered set such that any
940 two elements in the subset are incomparable.
942 Parameters
943 ----------
944 G : NetworkX DiGraph
945 A directed acyclic graph (DAG)
947 topo_order: list or tuple, optional
948 A topological order for G (if None, the function will compute one)
950 Yields
951 ------
952 antichain : list
953 a list of nodes in `G` representing an antichain
955 Raises
956 ------
957 NetworkXNotImplemented
958 If `G` is not directed
960 NetworkXUnfeasible
961 If `G` contains a cycle
963 Examples
964 --------
965 >>> DG = nx.DiGraph([(1, 2), (1, 3)])
966 >>> list(nx.antichains(DG))
967 [[], [3], [2], [2, 3], [1]]
969 Notes
970 -----
971 This function was originally developed by Peter Jipsen and Franco Saliola
972 for the SAGE project. It's included in NetworkX with permission from the
973 authors. Original SAGE code at:
975 https://github.com/sagemath/sage/blob/master/src/sage/combinat/posets/hasse_diagram.py
977 References
978 ----------
979 .. [1] Free Lattices, by R. Freese, J. Jezek and J. B. Nation,
980 AMS, Vol 42, 1995, p. 226.
981 """
982 if topo_order is None:
983 topo_order = list(nx.topological_sort(G))
985 TC = nx.transitive_closure_dag(G, topo_order)
986 antichains_stacks = [([], list(reversed(topo_order)))]
988 while antichains_stacks:
989 (antichain, stack) = antichains_stacks.pop()
990 # Invariant:
991 # - the elements of antichain are independent
992 # - the elements of stack are independent from those of antichain
993 yield antichain
994 while stack:
995 x = stack.pop()
996 new_antichain = antichain + [x]
997 new_stack = [t for t in stack if not ((t in TC[x]) or (x in TC[t]))]
998 antichains_stacks.append((new_antichain, new_stack))
1001@not_implemented_for("undirected")
1002@nx._dispatchable(edge_attrs={"weight": "default_weight"})
1003def dag_longest_path(G, weight="weight", default_weight=1, topo_order=None):
1004 """Returns the longest path in a directed acyclic graph (DAG).
1006 If `G` has edges with `weight` attribute the edge data are used as
1007 weight values.
1009 Parameters
1010 ----------
1011 G : NetworkX DiGraph
1012 A directed acyclic graph (DAG)
1014 weight : str, optional
1015 Edge data key to use for weight
1017 default_weight : int, optional
1018 The weight of edges that do not have a weight attribute
1020 topo_order: list or tuple, optional
1021 A topological order for `G` (if None, the function will compute one)
1023 Returns
1024 -------
1025 list
1026 Longest path
1028 Raises
1029 ------
1030 NetworkXNotImplemented
1031 If `G` is not directed
1033 Examples
1034 --------
1035 >>> DG = nx.DiGraph(
1036 ... [(0, 1, {"cost": 1}), (1, 2, {"cost": 1}), (0, 2, {"cost": 42})]
1037 ... )
1038 >>> list(nx.all_simple_paths(DG, 0, 2))
1039 [[0, 1, 2], [0, 2]]
1040 >>> nx.dag_longest_path(DG)
1041 [0, 1, 2]
1042 >>> nx.dag_longest_path(DG, weight="cost")
1043 [0, 2]
1045 In the case where multiple valid topological orderings exist, `topo_order`
1046 can be used to specify a specific ordering:
1048 >>> DG = nx.DiGraph([(0, 1), (0, 2)])
1049 >>> sorted(nx.all_topological_sorts(DG)) # Valid topological orderings
1050 [[0, 1, 2], [0, 2, 1]]
1051 >>> nx.dag_longest_path(DG, topo_order=[0, 1, 2])
1052 [0, 1]
1053 >>> nx.dag_longest_path(DG, topo_order=[0, 2, 1])
1054 [0, 2]
1056 See also
1057 --------
1058 dag_longest_path_length
1060 """
1061 if not G:
1062 return []
1064 if topo_order is None:
1065 topo_order = nx.topological_sort(G)
1067 dist = {} # stores {v : (length, u)}
1068 for v in topo_order:
1069 us = [
1070 (
1071 dist[u][0]
1072 + (
1073 max(data.values(), key=lambda x: x.get(weight, default_weight))
1074 if G.is_multigraph()
1075 else data
1076 ).get(weight, default_weight),
1077 u,
1078 )
1079 for u, data in G.pred[v].items()
1080 ]
1082 # Use the best predecessor if there is one and its distance is
1083 # non-negative, otherwise terminate.
1084 maxu = max(us, key=lambda x: x[0]) if us else (0, v)
1085 dist[v] = maxu if maxu[0] >= 0 else (0, v)
1087 u = None
1088 v = max(dist, key=lambda x: dist[x][0])
1089 path = []
1090 while u != v:
1091 path.append(v)
1092 u = v
1093 v = dist[v][1]
1095 path.reverse()
1096 return path
1099@not_implemented_for("undirected")
1100@nx._dispatchable(edge_attrs={"weight": "default_weight"})
1101def dag_longest_path_length(G, weight="weight", default_weight=1):
1102 """Returns the longest path length in a DAG
1104 Parameters
1105 ----------
1106 G : NetworkX DiGraph
1107 A directed acyclic graph (DAG)
1109 weight : string, optional
1110 Edge data key to use for weight
1112 default_weight : int, optional
1113 The weight of edges that do not have a weight attribute
1115 Returns
1116 -------
1117 int
1118 Longest path length
1120 Raises
1121 ------
1122 NetworkXNotImplemented
1123 If `G` is not directed
1125 Examples
1126 --------
1127 >>> DG = nx.DiGraph(
1128 ... [(0, 1, {"cost": 1}), (1, 2, {"cost": 1}), (0, 2, {"cost": 42})]
1129 ... )
1130 >>> list(nx.all_simple_paths(DG, 0, 2))
1131 [[0, 1, 2], [0, 2]]
1132 >>> nx.dag_longest_path_length(DG)
1133 2
1134 >>> nx.dag_longest_path_length(DG, weight="cost")
1135 42
1137 See also
1138 --------
1139 dag_longest_path
1140 """
1141 path = nx.dag_longest_path(G, weight, default_weight)
1142 path_length = 0
1143 if G.is_multigraph():
1144 for u, v in pairwise(path):
1145 i = max(G[u][v], key=lambda x: G[u][v][x].get(weight, default_weight))
1146 path_length += G[u][v][i].get(weight, default_weight)
1147 else:
1148 for u, v in pairwise(path):
1149 path_length += G[u][v].get(weight, default_weight)
1151 return path_length
1154@nx._dispatchable
1155def root_to_leaf_paths(G):
1156 """Yields root-to-leaf paths in a directed acyclic graph.
1158 `G` must be a directed acyclic graph. If not, the behavior of this
1159 function is undefined. A "root" in this graph is a node of in-degree
1160 zero and a "leaf" a node of out-degree zero.
1162 When invoked, this function iterates over each path from any root to
1163 any leaf. A path is a list of nodes.
1165 """
1166 roots = (v for v, d in G.in_degree() if d == 0)
1167 leaves = (v for v, d in G.out_degree() if d == 0)
1169 for root, leaf in product(roots, leaves):
1170 yield from nx.all_simple_paths(G, root, leaf)
1173@not_implemented_for("multigraph")
1174@not_implemented_for("undirected")
1175@nx._dispatchable(returns_graph=True)
1176def dag_to_branching(G):
1177 """Returns a branching representing all (overlapping) paths from
1178 root nodes to leaf nodes in the given directed acyclic graph.
1180 As described in :mod:`networkx.algorithms.tree.recognition`, a
1181 *branching* is a directed forest in which each node has at most one
1182 parent. In other words, a branching is a disjoint union of
1183 *arborescences*. For this function, each node of in-degree zero in
1184 `G` becomes a root of one of the arborescences, and there will be
1185 one leaf node for each distinct path from that root to a leaf node
1186 in `G`.
1188 Each node `v` in `G` with *k* parents becomes *k* distinct nodes in
1189 the returned branching, one for each parent, and the sub-DAG rooted
1190 at `v` is duplicated for each copy. The algorithm then recurses on
1191 the children of each copy of `v`.
1193 Parameters
1194 ----------
1195 G : NetworkX graph
1196 A directed acyclic graph.
1198 Returns
1199 -------
1200 DiGraph
1201 The branching in which there is a bijection between root-to-leaf
1202 paths in `G` (in which multiple paths may share the same leaf)
1203 and root-to-leaf paths in the branching (in which there is a
1204 unique path from a root to a leaf).
1206 Each node has an attribute 'source' whose value is the original
1207 node to which this node corresponds. No other graph, node, or
1208 edge attributes are copied into this new graph.
1210 Raises
1211 ------
1212 NetworkXNotImplemented
1213 If `G` is not directed, or if `G` is a multigraph.
1215 HasACycle
1216 If `G` is not acyclic.
1218 Examples
1219 --------
1220 To examine which nodes in the returned branching were produced by
1221 which original node in the directed acyclic graph, we can collect
1222 the mapping from source node to new nodes into a dictionary. For
1223 example, consider the directed diamond graph::
1225 >>> from collections import defaultdict
1226 >>> from operator import itemgetter
1227 >>>
1228 >>> G = nx.DiGraph(nx.utils.pairwise("abd"))
1229 >>> G.add_edges_from(nx.utils.pairwise("acd"))
1230 >>> B = nx.dag_to_branching(G)
1231 >>>
1232 >>> sources = defaultdict(set)
1233 >>> for v, source in B.nodes(data="source"):
1234 ... sources[source].add(v)
1235 >>> len(sources["a"])
1236 1
1237 >>> len(sources["d"])
1238 2
1240 To copy node attributes from the original graph to the new graph,
1241 you can use a dictionary like the one constructed in the above
1242 example::
1244 >>> for source, nodes in sources.items():
1245 ... for v in nodes:
1246 ... B.nodes[v].update(G.nodes[source])
1248 Notes
1249 -----
1250 This function is not idempotent in the sense that the node labels in
1251 the returned branching may be uniquely generated each time the
1252 function is invoked. In fact, the node labels may not be integers;
1253 in order to relabel the nodes to be more readable, you can use the
1254 :func:`networkx.convert_node_labels_to_integers` function.
1256 The current implementation of this function uses
1257 :func:`networkx.prefix_tree`, so it is subject to the limitations of
1258 that function.
1260 """
1261 if has_cycle(G):
1262 msg = "dag_to_branching is only defined for acyclic graphs"
1263 raise nx.HasACycle(msg)
1264 paths = root_to_leaf_paths(G)
1265 B = nx.prefix_tree(paths)
1266 # Remove the synthetic `root`(0) and `NIL`(-1) nodes from the tree
1267 B.remove_node(0)
1268 B.remove_node(-1)
1269 return B
1272@not_implemented_for("undirected")
1273@nx._dispatchable
1274def v_structures(G):
1275 """Yields 3-node tuples that represent the v-structures in `G`.
1277 Colliders are triples in the directed acyclic graph (DAG) where two parent nodes
1278 point to the same child node. V-structures are colliders where the two parent
1279 nodes are not adjacent. In a causal graph setting, the parents do not directly
1280 depend on each other, but conditioning on the child node provides an association.
1282 Parameters
1283 ----------
1284 G : graph
1285 A networkx `~networkx.DiGraph`.
1287 Yields
1288 ------
1289 A 3-tuple representation of a v-structure
1290 Each v-structure is a 3-tuple with the parent, collider, and other parent.
1292 Raises
1293 ------
1294 NetworkXNotImplemented
1295 If `G` is an undirected graph.
1297 Examples
1298 --------
1299 >>> G = nx.DiGraph([(1, 2), (0, 4), (3, 1), (2, 4), (0, 5), (4, 5), (1, 5)])
1300 >>> nx.is_directed_acyclic_graph(G)
1301 True
1302 >>> list(nx.dag.v_structures(G))
1303 [(0, 4, 2), (0, 5, 1), (4, 5, 1)]
1305 See Also
1306 --------
1307 colliders
1309 Notes
1310 -----
1311 This function was written to be used on DAGs, however it works on cyclic graphs
1312 too. Since colliders are referred to in the cyclic causal graph literature
1313 [2]_ we allow cyclic graphs in this function. It is suggested that you test if
1314 your input graph is acyclic as in the example if you want that property.
1316 References
1317 ----------
1318 .. [1] `Pearl's PRIMER <https://bayes.cs.ucla.edu/PRIMER/primer-ch2.pdf>`_
1319 Ch-2 page 50: v-structures def.
1320 .. [2] A Hyttinen, P.O. Hoyer, F. Eberhardt, M J ̈arvisalo, (2013)
1321 "Discovering cyclic causal models with latent variables:
1322 a general SAT-based procedure", UAI'13: Proceedings of the Twenty-Ninth
1323 Conference on Uncertainty in Artificial Intelligence, pg 301–310,
1324 `doi:10.5555/3023638.3023669 <https://dl.acm.org/doi/10.5555/3023638.3023669>`_
1325 """
1326 for p1, c, p2 in colliders(G):
1327 if not (G.has_edge(p1, p2) or G.has_edge(p2, p1)):
1328 yield (p1, c, p2)
1331@not_implemented_for("undirected")
1332@nx._dispatchable
1333def colliders(G):
1334 """Yields 3-node tuples that represent the colliders in `G`.
1336 In a Directed Acyclic Graph (DAG), if you have three nodes A, B, and C, and
1337 there are edges from A to C and from B to C, then C is a collider [1]_ . In
1338 a causal graph setting, this means that both events A and B are "causing" C,
1339 and conditioning on C provide an association between A and B even if
1340 no direct causal relationship exists between A and B.
1342 Parameters
1343 ----------
1344 G : graph
1345 A networkx `~networkx.DiGraph`.
1347 Yields
1348 ------
1349 A 3-tuple representation of a collider
1350 Each collider is a 3-tuple with the parent, collider, and other parent.
1352 Raises
1353 ------
1354 NetworkXNotImplemented
1355 If `G` is an undirected graph.
1357 Examples
1358 --------
1359 >>> G = nx.DiGraph([(1, 2), (0, 4), (3, 1), (2, 4), (0, 5), (4, 5), (1, 5)])
1360 >>> nx.is_directed_acyclic_graph(G)
1361 True
1362 >>> list(nx.dag.colliders(G))
1363 [(0, 4, 2), (0, 5, 4), (0, 5, 1), (4, 5, 1)]
1365 See Also
1366 --------
1367 v_structures
1369 Notes
1370 -----
1371 This function was written to be used on DAGs, however it works on cyclic graphs
1372 too. Since colliders are referred to in the cyclic causal graph literature
1373 [2]_ we allow cyclic graphs in this function. It is suggested that you test if
1374 your input graph is acyclic as in the example if you want that property.
1376 References
1377 ----------
1378 .. [1] `Wikipedia: Collider in causal graphs <https://en.wikipedia.org/wiki/Collider_(statistics)>`_
1379 .. [2] A Hyttinen, P.O. Hoyer, F. Eberhardt, M J ̈arvisalo, (2013)
1380 "Discovering cyclic causal models with latent variables:
1381 a general SAT-based procedure", UAI'13: Proceedings of the Twenty-Ninth
1382 Conference on Uncertainty in Artificial Intelligence, pg 301–310,
1383 `doi:10.5555/3023638.3023669 <https://dl.acm.org/doi/10.5555/3023638.3023669>`_
1384 """
1385 for node in G.nodes:
1386 for p1, p2 in combinations(G.predecessors(node), 2):
1387 yield (p1, node, p2)