Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/readwrite/text.py: 17%
291 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""
2Text-based visual representations of graphs
3"""
4import sys
5import warnings
6from collections import defaultdict
8import networkx as nx
9from networkx.utils import open_file
11__all__ = ["forest_str", "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 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 forest_str(graph, with_labels=True, sources=None, write=None, ascii_only=False):
648 """Creates a nice utf8 representation of a forest
650 This function has been superseded by
651 :func:`nx.readwrite.text.generate_network_text`, which should be used
652 instead.
654 Parameters
655 ----------
656 graph : nx.DiGraph | nx.Graph
657 Graph to represent (must be a tree, forest, or the empty graph)
659 with_labels : bool
660 If True will use the "label" attribute of a node to display if it
661 exists otherwise it will use the node value itself. Defaults to True.
663 sources : List
664 Mainly relevant for undirected forests, specifies which nodes to list
665 first. If unspecified the root nodes of each tree will be used for
666 directed forests; for undirected forests this defaults to the nodes
667 with the smallest degree.
669 write : callable
670 Function to use to write to, if None new lines are appended to
671 a list and returned. If set to the `print` function, lines will
672 be written to stdout as they are generated. If specified,
673 this function will return None. Defaults to None.
675 ascii_only : Boolean
676 If True only ASCII characters are used to construct the visualization
678 Returns
679 -------
680 str | None :
681 utf8 representation of the tree / forest
683 Examples
684 --------
685 >>> graph = nx.balanced_tree(r=2, h=3, create_using=nx.DiGraph)
686 >>> print(nx.forest_str(graph))
687 ╙── 0
688 ├─╼ 1
689 │ ├─╼ 3
690 │ │ ├─╼ 7
691 │ │ └─╼ 8
692 │ └─╼ 4
693 │ ├─╼ 9
694 │ └─╼ 10
695 └─╼ 2
696 ├─╼ 5
697 │ ├─╼ 11
698 │ └─╼ 12
699 └─╼ 6
700 ├─╼ 13
701 └─╼ 14
704 >>> graph = nx.balanced_tree(r=1, h=2, create_using=nx.Graph)
705 >>> print(nx.forest_str(graph))
706 ╙── 0
707 └── 1
708 └── 2
710 >>> print(nx.forest_str(graph, ascii_only=True))
711 +-- 0
712 L-- 1
713 L-- 2
714 """
715 msg = (
716 "\nforest_str is deprecated as of version 3.1 and will be removed "
717 "in version 3.3. Use generate_network_text or write_network_text "
718 "instead.\n"
719 )
720 warnings.warn(msg, DeprecationWarning)
722 if len(graph.nodes) > 0:
723 if not nx.is_forest(graph):
724 raise nx.NetworkXNotImplemented("input must be a forest or the empty graph")
726 printbuf = []
727 if write is None:
728 _write = printbuf.append
729 else:
730 _write = write
732 write_network_text(
733 graph,
734 _write,
735 with_labels=with_labels,
736 sources=sources,
737 ascii_only=ascii_only,
738 end="",
739 )
741 if write is None:
742 # Only return a string if the custom write function was not specified
743 return "\n".join(printbuf)
746def _parse_network_text(lines):
747 """Reconstructs a graph from a network text representation.
749 This is mainly used for testing. Network text is for display, not
750 serialization, as such this cannot parse all network text representations
751 because node labels can be ambiguous with the glyphs and indentation used
752 to represent edge structure. Additionally, there is no way to determine if
753 disconnected graphs were originally directed or undirected.
755 Parameters
756 ----------
757 lines : list or iterator of strings
758 Input data in network text format
760 Returns
761 -------
762 G: NetworkX graph
763 The graph corresponding to the lines in network text format.
764 """
765 from itertools import chain
766 from typing import Any, NamedTuple, Union
768 class ParseStackFrame(NamedTuple):
769 node: Any
770 indent: int
771 has_vertical_child: Union[int, None]
773 initial_line_iter = iter(lines)
775 is_ascii = None
776 is_directed = None
778 ##############
779 # Initial Pass
780 ##############
782 # Do an initial pass over the lines to determine what type of graph it is.
783 # Remember what these lines were, so we can reiterate over them in the
784 # parsing pass.
785 initial_lines = []
786 try:
787 first_line = next(initial_line_iter)
788 except StopIteration:
789 ...
790 else:
791 initial_lines.append(first_line)
792 # The first character indicates if it is an ASCII or UTF graph
793 first_char = first_line[0]
794 if first_char in {
795 UtfBaseGlyphs.empty,
796 UtfBaseGlyphs.newtree_mid[0],
797 UtfBaseGlyphs.newtree_last[0],
798 }:
799 is_ascii = False
800 elif first_char in {
801 AsciiBaseGlyphs.empty,
802 AsciiBaseGlyphs.newtree_mid[0],
803 AsciiBaseGlyphs.newtree_last[0],
804 }:
805 is_ascii = True
806 else:
807 raise AssertionError(f"Unexpected first character: {first_char}")
809 if is_ascii:
810 directed_glyphs = AsciiDirectedGlyphs.as_dict()
811 undirected_glyphs = AsciiUndirectedGlyphs.as_dict()
812 else:
813 directed_glyphs = UtfDirectedGlyphs.as_dict()
814 undirected_glyphs = UtfUndirectedGlyphs.as_dict()
816 # For both directed / undirected glyphs, determine which glyphs never
817 # appear as substrings in the other undirected / directed glyphs. Glyphs
818 # with this property unambiguously indicates if a graph is directed /
819 # undirected.
820 directed_items = set(directed_glyphs.values())
821 undirected_items = set(undirected_glyphs.values())
822 unambiguous_directed_items = []
823 for item in directed_items:
824 other_items = undirected_items
825 other_supersets = [other for other in other_items if item in other]
826 if not other_supersets:
827 unambiguous_directed_items.append(item)
828 unambiguous_undirected_items = []
829 for item in undirected_items:
830 other_items = directed_items
831 other_supersets = [other for other in other_items if item in other]
832 if not other_supersets:
833 unambiguous_undirected_items.append(item)
835 for line in initial_line_iter:
836 initial_lines.append(line)
837 if any(item in line for item in unambiguous_undirected_items):
838 is_directed = False
839 break
840 elif any(item in line for item in unambiguous_directed_items):
841 is_directed = True
842 break
844 if is_directed is None:
845 # Not enough information to determine, choose undirected by default
846 is_directed = False
848 glyphs = directed_glyphs if is_directed else undirected_glyphs
850 # the backedge symbol by itself can be ambiguous, but with spaces around it
851 # becomes unambiguous.
852 backedge_symbol = " " + glyphs["backedge"] + " "
854 # Reconstruct an iterator over all of the lines.
855 parsing_line_iter = chain(initial_lines, initial_line_iter)
857 ##############
858 # Parsing Pass
859 ##############
861 edges = []
862 nodes = []
863 is_empty = None
865 noparent = object() # sentinel value
867 # keep a stack of previous nodes that could be parents of subsequent nodes
868 stack = [ParseStackFrame(noparent, -1, None)]
870 for line in parsing_line_iter:
871 if line == glyphs["empty"]:
872 # If the line is the empty glyph, we are done.
873 # There shouldn't be anything else after this.
874 is_empty = True
875 continue
877 if backedge_symbol in line:
878 # This line has one or more backedges, separate those out
879 node_part, backedge_part = line.split(backedge_symbol)
880 backedge_nodes = [u.strip() for u in backedge_part.split(", ")]
881 # Now the node can be parsed
882 node_part = node_part.rstrip()
883 prefix, node = node_part.rsplit(" ", 1)
884 node = node.strip()
885 # Add the backedges to the edge list
886 edges.extend([(u, node) for u in backedge_nodes])
887 else:
888 # No backedge, the tail of this line is the node
889 prefix, node = line.rsplit(" ", 1)
890 node = node.strip()
892 prev = stack.pop()
894 if node in glyphs["vertical_edge"]:
895 # Previous node is still the previous node, but we know it will
896 # have exactly one child, which will need to have its nesting level
897 # adjusted.
898 modified_prev = ParseStackFrame(
899 prev.node,
900 prev.indent,
901 True,
902 )
903 stack.append(modified_prev)
904 continue
906 # The length of the string before the node characters give us a hint
907 # about our nesting level. The only case where this doesn't work is
908 # when there are vertical chains, which is handled explicitly.
909 indent = len(prefix)
910 curr = ParseStackFrame(node, indent, None)
912 if prev.has_vertical_child:
913 # In this case we know prev must be the parent of our current line,
914 # so we don't have to search the stack. (which is good because the
915 # indentation check wouldn't work in this case).
916 ...
917 else:
918 # If the previous node nesting-level is greater than the current
919 # nodes nesting-level than the previous node was the end of a path,
920 # and is not our parent. We can safely pop nodes off the stack
921 # until we find one with a comparable nesting-level, which is our
922 # parent.
923 while curr.indent <= prev.indent:
924 prev = stack.pop()
926 if node == "...":
927 # The current previous node is no longer a valid parent,
928 # keep it popped from the stack.
929 stack.append(prev)
930 else:
931 # The previous and current nodes may still be parents, so add them
932 # back onto the stack.
933 stack.append(prev)
934 stack.append(curr)
936 # Add the node and the edge to its parent to the node / edge lists.
937 nodes.append(curr.node)
938 if prev.node is not noparent:
939 edges.append((prev.node, curr.node))
941 if is_empty:
942 # Sanity check
943 assert len(nodes) == 0
945 # Reconstruct the graph
946 cls = nx.DiGraph if is_directed else nx.Graph
947 new = cls()
948 new.add_nodes_from(nodes)
949 new.add_edges_from(edges)
950 return new