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"""
2Text-based visual representations of graphs
3"""
5import sys
6from collections import defaultdict
8import networkx as nx
9from networkx.utils import open_file
11__all__ = ["generate_network_text", "write_network_text"]
14class BaseGlyphs:
15 @classmethod
16 def as_dict(cls):
17 return {
18 a: getattr(cls, a)
19 for a in dir(cls)
20 if not a.startswith("_") and a != "as_dict"
21 }
24class AsciiBaseGlyphs(BaseGlyphs):
25 empty: str = "+"
26 newtree_last: str = "+-- "
27 newtree_mid: str = "+-- "
28 endof_forest: str = " "
29 within_forest: str = ": "
30 within_tree: str = "| "
33class AsciiDirectedGlyphs(AsciiBaseGlyphs):
34 last: str = "L-> "
35 mid: str = "|-> "
36 backedge: str = "<-"
37 vertical_edge: str = "!"
40class AsciiUndirectedGlyphs(AsciiBaseGlyphs):
41 last: str = "L-- "
42 mid: str = "|-- "
43 backedge: str = "-"
44 vertical_edge: str = "|"
47class UtfBaseGlyphs(BaseGlyphs):
48 # Notes on available box and arrow characters
49 # https://en.wikipedia.org/wiki/Box-drawing_character
50 # https://stackoverflow.com/questions/2701192/triangle-arrow
51 empty: str = "╙"
52 newtree_last: str = "╙── "
53 newtree_mid: str = "╟── "
54 endof_forest: str = " "
55 within_forest: str = "╎ "
56 within_tree: str = "│ "
59class UtfDirectedGlyphs(UtfBaseGlyphs):
60 last: str = "└─╼ "
61 mid: str = "├─╼ "
62 backedge: str = "╾"
63 vertical_edge: str = "╽"
66class UtfUndirectedGlyphs(UtfBaseGlyphs):
67 last: str = "└── "
68 mid: str = "├── "
69 backedge: str = "─"
70 vertical_edge: str = "│"
73def generate_network_text(
74 graph,
75 with_labels=True,
76 sources=None,
77 max_depth=None,
78 ascii_only=False,
79 vertical_chains=False,
80):
81 """Generate lines in the "network text" format
83 This works via a depth-first traversal of the graph and writing a line for
84 each unique node encountered. Non-tree edges are written to the right of
85 each node, and connection to a non-tree edge is indicated with an ellipsis.
86 This representation works best when the input graph is a forest, but any
87 graph can be represented.
89 This notation is original to networkx, although it is simple enough that it
90 may be known in existing literature. See #5602 for details. The procedure
91 is summarized as follows:
93 1. Given a set of source nodes (which can be specified, or automatically
94 discovered via finding the (strongly) connected components and choosing one
95 node with minimum degree from each), we traverse the graph in depth first
96 order.
98 2. Each reachable node will be printed exactly once on it's own line.
100 3. Edges are indicated in one of four ways:
102 a. a parent "L-style" connection on the upper left. This corresponds to
103 a traversal in the directed DFS tree.
105 b. a backref "<-style" connection shown directly on the right. For
106 directed graphs, these are drawn for any incoming edges to a node that
107 is not a parent edge. For undirected graphs, these are drawn for only
108 the non-parent edges that have already been represented (The edges that
109 have not been represented will be handled in the recursive case).
111 c. a child "L-style" connection on the lower right. Drawing of the
112 children are handled recursively.
114 d. if ``vertical_chains`` is true, and a parent node only has one child
115 a "vertical-style" edge is drawn between them.
117 4. The children of each node (wrt the directed DFS tree) are drawn
118 underneath and to the right of it. In the case that a child node has already
119 been drawn the connection is replaced with an ellipsis ("...") to indicate
120 that there is one or more connections represented elsewhere.
122 5. If a maximum depth is specified, an edge to nodes past this maximum
123 depth will be represented by an ellipsis.
125 6. If a node has a truthy "collapse" value, then we do not traverse past
126 that node.
128 Parameters
129 ----------
130 graph : nx.DiGraph | nx.Graph
131 Graph to represent
133 with_labels : bool | str
134 If True will use the "label" attribute of a node to display if it
135 exists otherwise it will use the node value itself. If given as a
136 string, then that attribute name will be used instead of "label".
137 Defaults to True.
139 sources : List
140 Specifies which nodes to start traversal from. Note: nodes that are not
141 reachable from one of these sources may not be shown. If unspecified,
142 the minimal set of nodes needed to reach all others will be used.
144 max_depth : int | None
145 The maximum depth to traverse before stopping. Defaults to None.
147 ascii_only : Boolean
148 If True only ASCII characters are used to construct the visualization
150 vertical_chains : Boolean
151 If True, chains of nodes will be drawn vertically when possible.
153 Yields
154 ------
155 str : a line of generated text
157 Examples
158 --------
159 >>> graph = nx.path_graph(10)
160 >>> graph.add_node("A")
161 >>> graph.add_node("B")
162 >>> graph.add_node("C")
163 >>> graph.add_node("D")
164 >>> graph.add_edge(9, "A")
165 >>> graph.add_edge(9, "B")
166 >>> graph.add_edge(9, "C")
167 >>> graph.add_edge("C", "D")
168 >>> graph.add_edge("C", "E")
169 >>> graph.add_edge("C", "F")
170 >>> nx.write_network_text(graph)
171 ╙── 0
172 └── 1
173 └── 2
174 └── 3
175 └── 4
176 └── 5
177 └── 6
178 └── 7
179 └── 8
180 └── 9
181 ├── A
182 ├── B
183 └── C
184 ├── D
185 ├── E
186 └── F
187 >>> nx.write_network_text(graph, vertical_chains=True)
188 ╙── 0
189 │
190 1
191 │
192 2
193 │
194 3
195 │
196 4
197 │
198 5
199 │
200 6
201 │
202 7
203 │
204 8
205 │
206 9
207 ├── A
208 ├── B
209 └── C
210 ├── D
211 ├── E
212 └── F
213 """
214 from typing import Any, NamedTuple
216 class StackFrame(NamedTuple):
217 parent: Any
218 node: Any
219 indents: list
220 this_islast: bool
221 this_vertical: bool
223 collapse_attr = "collapse"
225 is_directed = graph.is_directed()
227 if is_directed:
228 glyphs = AsciiDirectedGlyphs if ascii_only else UtfDirectedGlyphs
229 succ = graph.succ
230 pred = graph.pred
231 else:
232 glyphs = AsciiUndirectedGlyphs if ascii_only else UtfUndirectedGlyphs
233 succ = graph.adj
234 pred = graph.adj
236 if isinstance(with_labels, str):
237 label_attr = with_labels
238 elif with_labels:
239 label_attr = "label"
240 else:
241 label_attr = None
243 if max_depth == 0:
244 yield glyphs.empty + " ..."
245 elif len(graph.nodes) == 0:
246 yield glyphs.empty
247 else:
248 # If the nodes to traverse are unspecified, find the minimal set of
249 # nodes that will reach the entire graph
250 if sources is None:
251 sources = _find_sources(graph)
253 # Populate the stack with each:
254 # 1. parent node in the DFS tree (or None for root nodes),
255 # 2. the current node in the DFS tree
256 # 2. a list of indentations indicating depth
257 # 3. a flag indicating if the node is the final one to be written.
258 # Reverse the stack so sources are popped in the correct order.
259 last_idx = len(sources) - 1
260 stack = [
261 StackFrame(None, node, [], (idx == last_idx), False)
262 for idx, node in enumerate(sources)
263 ][::-1]
265 num_skipped_children = defaultdict(lambda: 0)
266 seen_nodes = set()
267 while stack:
268 parent, node, indents, this_islast, this_vertical = stack.pop()
270 if node is not Ellipsis:
271 skip = node in seen_nodes
272 if skip:
273 # Mark that we skipped a parent's child
274 num_skipped_children[parent] += 1
276 if this_islast:
277 # If we reached the last child of a parent, and we skipped
278 # any of that parents children, then we should emit an
279 # ellipsis at the end after this.
280 if num_skipped_children[parent] and parent is not None:
281 # Append the ellipsis to be emitted last
282 next_islast = True
283 try_frame = StackFrame(
284 node, Ellipsis, indents, next_islast, False
285 )
286 stack.append(try_frame)
288 # Redo this frame, but not as a last object
289 next_islast = False
290 try_frame = StackFrame(
291 parent, node, indents, next_islast, this_vertical
292 )
293 stack.append(try_frame)
294 continue
296 if skip:
297 continue
298 seen_nodes.add(node)
300 if not indents:
301 # Top level items (i.e. trees in the forest) get different
302 # glyphs to indicate they are not actually connected
303 if this_islast:
304 this_vertical = False
305 this_prefix = indents + [glyphs.newtree_last]
306 next_prefix = indents + [glyphs.endof_forest]
307 else:
308 this_prefix = indents + [glyphs.newtree_mid]
309 next_prefix = indents + [glyphs.within_forest]
311 else:
312 # Non-top-level items
313 if this_vertical:
314 this_prefix = indents
315 next_prefix = indents
316 else:
317 if this_islast:
318 this_prefix = indents + [glyphs.last]
319 next_prefix = indents + [glyphs.endof_forest]
320 else:
321 this_prefix = indents + [glyphs.mid]
322 next_prefix = indents + [glyphs.within_tree]
324 if node is Ellipsis:
325 label = " ..."
326 suffix = ""
327 children = []
328 else:
329 if label_attr is not None:
330 label = str(graph.nodes[node].get(label_attr, node))
331 else:
332 label = str(node)
334 # Determine if we want to show the children of this node.
335 if collapse_attr is not None:
336 collapse = graph.nodes[node].get(collapse_attr, False)
337 else:
338 collapse = False
340 # Determine:
341 # (1) children to traverse into after showing this node.
342 # (2) parents to immediately show to the right of this node.
343 if is_directed:
344 # In the directed case we must show every successor node
345 # note: it may be skipped later, but we don't have that
346 # information here.
347 children = list(succ[node])
348 # In the directed case we must show every predecessor
349 # except for parent we directly traversed from.
350 handled_parents = {parent}
351 else:
352 # Showing only the unseen children results in a more
353 # concise representation for the undirected case.
354 children = [
355 child for child in succ[node] if child not in seen_nodes
356 ]
358 # In the undirected case, parents are also children, so we
359 # only need to immediately show the ones we can no longer
360 # traverse
361 handled_parents = {*children, parent}
363 if max_depth is not None and len(indents) == max_depth - 1:
364 # Use ellipsis to indicate we have reached maximum depth
365 if children:
366 children = [Ellipsis]
367 handled_parents = {parent}
369 if collapse:
370 # Collapsing a node is the same as reaching maximum depth
371 if children:
372 children = [Ellipsis]
373 handled_parents = {parent}
375 # The other parents are other predecessors of this node that
376 # are not handled elsewhere.
377 other_parents = [p for p in pred[node] if p not in handled_parents]
378 if other_parents:
379 if label_attr is not None:
380 other_parents_labels = ", ".join(
381 [
382 str(graph.nodes[p].get(label_attr, p))
383 for p in other_parents
384 ]
385 )
386 else:
387 other_parents_labels = ", ".join(
388 [str(p) for p in other_parents]
389 )
390 suffix = " ".join(["", glyphs.backedge, other_parents_labels])
391 else:
392 suffix = ""
394 # Emit the line for this node, this will be called for each node
395 # exactly once.
396 if this_vertical:
397 yield "".join(this_prefix + [glyphs.vertical_edge])
399 yield "".join(this_prefix + [label, suffix])
401 if vertical_chains:
402 if is_directed:
403 num_children = len(set(children))
404 else:
405 num_children = len(set(children) - {parent})
406 # The next node can be drawn vertically if it is the only
407 # remaining child of this node.
408 next_is_vertical = num_children == 1
409 else:
410 next_is_vertical = False
412 # Push children on the stack in reverse order so they are popped in
413 # the original order.
414 for idx, child in enumerate(children[::-1]):
415 next_islast = idx == 0
416 try_frame = StackFrame(
417 node, child, next_prefix, next_islast, next_is_vertical
418 )
419 stack.append(try_frame)
422@open_file(1, "w")
423def write_network_text(
424 graph,
425 path=None,
426 with_labels=True,
427 sources=None,
428 max_depth=None,
429 ascii_only=False,
430 end="\n",
431 vertical_chains=False,
432):
433 """Creates a nice text representation of a graph
435 This works via a depth-first traversal of the graph and writing a line for
436 each unique node encountered. Non-tree edges are written to the right of
437 each node, and connection to a non-tree edge is indicated with an ellipsis.
438 This representation works best when the input graph is a forest, but any
439 graph can be represented.
441 Parameters
442 ----------
443 graph : nx.DiGraph | nx.Graph
444 Graph to represent
446 path : string or file or callable or None
447 Filename or file handle for data output.
448 if a function, then it will be called for each generated line.
449 if None, this will default to "sys.stdout.write"
451 with_labels : bool | str
452 If True will use the "label" attribute of a node to display if it
453 exists otherwise it will use the node value itself. If given as a
454 string, then that attribute name will be used instead of "label".
455 Defaults to True.
457 sources : List
458 Specifies which nodes to start traversal from. Note: nodes that are not
459 reachable from one of these sources may not be shown. If unspecified,
460 the minimal set of nodes needed to reach all others will be used.
462 max_depth : int | None
463 The maximum depth to traverse before stopping. Defaults to None.
465 ascii_only : Boolean
466 If True only ASCII characters are used to construct the visualization
468 end : string
469 The line ending character
471 vertical_chains : Boolean
472 If True, chains of nodes will be drawn vertically when possible.
474 Examples
475 --------
476 >>> graph = nx.balanced_tree(r=2, h=2, create_using=nx.DiGraph)
477 >>> nx.write_network_text(graph)
478 ╙── 0
479 ├─╼ 1
480 │ ├─╼ 3
481 │ └─╼ 4
482 └─╼ 2
483 ├─╼ 5
484 └─╼ 6
486 >>> # A near tree with one non-tree edge
487 >>> graph.add_edge(5, 1)
488 >>> nx.write_network_text(graph)
489 ╙── 0
490 ├─╼ 1 ╾ 5
491 │ ├─╼ 3
492 │ └─╼ 4
493 └─╼ 2
494 ├─╼ 5
495 │ └─╼ ...
496 └─╼ 6
498 >>> graph = nx.cycle_graph(5)
499 >>> nx.write_network_text(graph)
500 ╙── 0
501 ├── 1
502 │ └── 2
503 │ └── 3
504 │ └── 4 ─ 0
505 └── ...
507 >>> graph = nx.cycle_graph(5, nx.DiGraph)
508 >>> nx.write_network_text(graph, vertical_chains=True)
509 ╙── 0 ╾ 4
510 ╽
511 1
512 ╽
513 2
514 ╽
515 3
516 ╽
517 4
518 └─╼ ...
520 >>> nx.write_network_text(graph, vertical_chains=True, ascii_only=True)
521 +-- 0 <- 4
522 !
523 1
524 !
525 2
526 !
527 3
528 !
529 4
530 L-> ...
532 >>> graph = nx.generators.barbell_graph(4, 2)
533 >>> nx.write_network_text(graph, vertical_chains=False)
534 ╙── 4
535 ├── 5
536 │ └── 6
537 │ ├── 7
538 │ │ ├── 8 ─ 6
539 │ │ │ └── 9 ─ 6, 7
540 │ │ └── ...
541 │ └── ...
542 └── 3
543 ├── 0
544 │ ├── 1 ─ 3
545 │ │ └── 2 ─ 0, 3
546 │ └── ...
547 └── ...
548 >>> nx.write_network_text(graph, vertical_chains=True)
549 ╙── 4
550 ├── 5
551 │ │
552 │ 6
553 │ ├── 7
554 │ │ ├── 8 ─ 6
555 │ │ │ │
556 │ │ │ 9 ─ 6, 7
557 │ │ └── ...
558 │ └── ...
559 └── 3
560 ├── 0
561 │ ├── 1 ─ 3
562 │ │ │
563 │ │ 2 ─ 0, 3
564 │ └── ...
565 └── ...
567 >>> graph = nx.complete_graph(5, create_using=nx.Graph)
568 >>> nx.write_network_text(graph)
569 ╙── 0
570 ├── 1
571 │ ├── 2 ─ 0
572 │ │ ├── 3 ─ 0, 1
573 │ │ │ └── 4 ─ 0, 1, 2
574 │ │ └── ...
575 │ └── ...
576 └── ...
578 >>> graph = nx.complete_graph(3, create_using=nx.DiGraph)
579 >>> nx.write_network_text(graph)
580 ╙── 0 ╾ 1, 2
581 ├─╼ 1 ╾ 2
582 │ ├─╼ 2 ╾ 0
583 │ │ └─╼ ...
584 │ └─╼ ...
585 └─╼ ...
586 """
587 if path is None:
588 # The path is unspecified, write to stdout
589 _write = sys.stdout.write
590 elif hasattr(path, "write"):
591 # The path is already an open file
592 _write = path.write
593 elif callable(path):
594 # The path is a custom callable
595 _write = path
596 else:
597 raise TypeError(type(path))
599 for line in generate_network_text(
600 graph,
601 with_labels=with_labels,
602 sources=sources,
603 max_depth=max_depth,
604 ascii_only=ascii_only,
605 vertical_chains=vertical_chains,
606 ):
607 _write(line + end)
610def _find_sources(graph):
611 """
612 Determine a minimal set of nodes such that the entire graph is reachable
613 """
614 # For each connected part of the graph, choose at least
615 # one node as a starting point, preferably without a parent
616 if graph.is_directed():
617 # Choose one node from each SCC with minimum in_degree
618 sccs = list(nx.strongly_connected_components(graph))
619 # condensing the SCCs forms a dag, the nodes in this graph with
620 # 0 in-degree correspond to the SCCs from which the minimum set
621 # of nodes from which all other nodes can be reached.
622 scc_graph = nx.condensation(graph, sccs)
623 supernode_to_nodes = {sn: [] for sn in scc_graph.nodes()}
624 # Note: the order of mapping differs between pypy and cpython
625 # so we have to loop over graph nodes for consistency
626 mapping = scc_graph.graph["mapping"]
627 for n in graph.nodes:
628 sn = mapping[n]
629 supernode_to_nodes[sn].append(n)
630 sources = []
631 for sn in scc_graph.nodes():
632 if scc_graph.in_degree[sn] == 0:
633 scc = supernode_to_nodes[sn]
634 node = min(scc, key=lambda n: graph.in_degree[n])
635 sources.append(node)
636 else:
637 # For undirected graph, the entire graph will be reachable as
638 # long as we consider one node from every connected component
639 sources = [
640 min(cc, key=lambda n: graph.degree[n])
641 for cc in nx.connected_components(graph)
642 ]
643 sources = sorted(sources, key=lambda n: graph.degree[n])
644 return sources
647def _parse_network_text(lines):
648 """Reconstructs a graph from a network text representation.
650 This is mainly used for testing. Network text is for display, not
651 serialization, as such this cannot parse all network text representations
652 because node labels can be ambiguous with the glyphs and indentation used
653 to represent edge structure. Additionally, there is no way to determine if
654 disconnected graphs were originally directed or undirected.
656 Parameters
657 ----------
658 lines : list or iterator of strings
659 Input data in network text format
661 Returns
662 -------
663 G: NetworkX graph
664 The graph corresponding to the lines in network text format.
665 """
666 from itertools import chain
667 from typing import Any, NamedTuple
669 class ParseStackFrame(NamedTuple):
670 node: Any
671 indent: int
672 has_vertical_child: int | None
674 initial_line_iter = iter(lines)
676 is_ascii = None
677 is_directed = None
679 ##############
680 # Initial Pass
681 ##############
683 # Do an initial pass over the lines to determine what type of graph it is.
684 # Remember what these lines were, so we can reiterate over them in the
685 # parsing pass.
686 initial_lines = []
687 try:
688 first_line = next(initial_line_iter)
689 except StopIteration:
690 ...
691 else:
692 initial_lines.append(first_line)
693 # The first character indicates if it is an ASCII or UTF graph
694 first_char = first_line[0]
695 if first_char in {
696 UtfBaseGlyphs.empty,
697 UtfBaseGlyphs.newtree_mid[0],
698 UtfBaseGlyphs.newtree_last[0],
699 }:
700 is_ascii = False
701 elif first_char in {
702 AsciiBaseGlyphs.empty,
703 AsciiBaseGlyphs.newtree_mid[0],
704 AsciiBaseGlyphs.newtree_last[0],
705 }:
706 is_ascii = True
707 else:
708 raise AssertionError(f"Unexpected first character: {first_char}")
710 if is_ascii:
711 directed_glyphs = AsciiDirectedGlyphs.as_dict()
712 undirected_glyphs = AsciiUndirectedGlyphs.as_dict()
713 else:
714 directed_glyphs = UtfDirectedGlyphs.as_dict()
715 undirected_glyphs = UtfUndirectedGlyphs.as_dict()
717 # For both directed / undirected glyphs, determine which glyphs never
718 # appear as substrings in the other undirected / directed glyphs. Glyphs
719 # with this property unambiguously indicates if a graph is directed /
720 # undirected.
721 directed_items = set(directed_glyphs.values())
722 undirected_items = set(undirected_glyphs.values())
723 unambiguous_directed_items = []
724 for item in directed_items:
725 other_items = undirected_items
726 other_supersets = [other for other in other_items if item in other]
727 if not other_supersets:
728 unambiguous_directed_items.append(item)
729 unambiguous_undirected_items = []
730 for item in undirected_items:
731 other_items = directed_items
732 other_supersets = [other for other in other_items if item in other]
733 if not other_supersets:
734 unambiguous_undirected_items.append(item)
736 for line in initial_line_iter:
737 initial_lines.append(line)
738 if any(item in line for item in unambiguous_undirected_items):
739 is_directed = False
740 break
741 elif any(item in line for item in unambiguous_directed_items):
742 is_directed = True
743 break
745 if is_directed is None:
746 # Not enough information to determine, choose undirected by default
747 is_directed = False
749 glyphs = directed_glyphs if is_directed else undirected_glyphs
751 # the backedge symbol by itself can be ambiguous, but with spaces around it
752 # becomes unambiguous.
753 backedge_symbol = " " + glyphs["backedge"] + " "
755 # Reconstruct an iterator over all of the lines.
756 parsing_line_iter = chain(initial_lines, initial_line_iter)
758 ##############
759 # Parsing Pass
760 ##############
762 edges = []
763 nodes = []
764 is_empty = None
766 noparent = object() # sentinel value
768 # keep a stack of previous nodes that could be parents of subsequent nodes
769 stack = [ParseStackFrame(noparent, -1, None)]
771 for line in parsing_line_iter:
772 if line == glyphs["empty"]:
773 # If the line is the empty glyph, we are done.
774 # There shouldn't be anything else after this.
775 is_empty = True
776 continue
778 if backedge_symbol in line:
779 # This line has one or more backedges, separate those out
780 node_part, backedge_part = line.split(backedge_symbol)
781 backedge_nodes = [u.strip() for u in backedge_part.split(", ")]
782 # Now the node can be parsed
783 node_part = node_part.rstrip()
784 prefix, node = node_part.rsplit(" ", 1)
785 node = node.strip()
786 # Add the backedges to the edge list
787 edges.extend([(u, node) for u in backedge_nodes])
788 else:
789 # No backedge, the tail of this line is the node
790 prefix, node = line.rsplit(" ", 1)
791 node = node.strip()
793 prev = stack.pop()
795 if node in glyphs["vertical_edge"]:
796 # Previous node is still the previous node, but we know it will
797 # have exactly one child, which will need to have its nesting level
798 # adjusted.
799 modified_prev = ParseStackFrame(
800 prev.node,
801 prev.indent,
802 True,
803 )
804 stack.append(modified_prev)
805 continue
807 # The length of the string before the node characters give us a hint
808 # about our nesting level. The only case where this doesn't work is
809 # when there are vertical chains, which is handled explicitly.
810 indent = len(prefix)
811 curr = ParseStackFrame(node, indent, None)
813 if prev.has_vertical_child:
814 # In this case we know prev must be the parent of our current line,
815 # so we don't have to search the stack. (which is good because the
816 # indentation check wouldn't work in this case).
817 ...
818 else:
819 # If the previous node nesting-level is greater than the current
820 # nodes nesting-level than the previous node was the end of a path,
821 # and is not our parent. We can safely pop nodes off the stack
822 # until we find one with a comparable nesting-level, which is our
823 # parent.
824 while curr.indent <= prev.indent:
825 prev = stack.pop()
827 if node == "...":
828 # The current previous node is no longer a valid parent,
829 # keep it popped from the stack.
830 stack.append(prev)
831 else:
832 # The previous and current nodes may still be parents, so add them
833 # back onto the stack.
834 stack.append(prev)
835 stack.append(curr)
837 # Add the node and the edge to its parent to the node / edge lists.
838 nodes.append(curr.node)
839 if prev.node is not noparent:
840 edges.append((prev.node, curr.node))
842 if is_empty:
843 # Sanity check
844 assert len(nodes) == 0
846 # Reconstruct the graph
847 cls = nx.DiGraph if is_directed else nx.Graph
848 new = cls()
849 new.add_nodes_from(nodes)
850 new.add_edges_from(edges)
851 return new