exploration.graphs

  1"""
  2- Authors: Peter Mawhorter
  3- Consulted:
  4- Date: 2022-3-5
  5- Purpose: Low-level graph helpers & types.
  6
  7This file defines tools on top of the `networkx` package which are
  8lower-level than the key types used for most tasks (see `core.py` for
  9those).
 10"""
 11
 12from typing import (
 13    Optional, Hashable, Dict, Union, Iterable, Tuple, Any, NoReturn,
 14    Set, Sequence, cast, List, TypeVar, Generic, Callable
 15)
 16
 17import networkx as nx  # type: ignore[import]
 18
 19
 20Node = TypeVar('Node', bound=Hashable)
 21"Type variable for graph nodes."
 22
 23Edge = TypeVar('Edge', bound=Hashable)
 24"Type variable for graph edges."
 25
 26
 27class UniqueExitsGraph(nx.MultiDiGraph, Generic[Node, Edge]):
 28    """
 29    A `networkx.MultiDiGraph` which has unique-per-source-node names for
 30    each edge. On top of base functionality, this uses some extra memory
 31    to store per-edge outgoing (but not incoming) by-edge dictionaries,
 32    so that you can iterate over edges by their names rather than
 33    iterating over neighbor nodes. This helps in some circumstances where
 34    you know the edge name but not the name of the room it connects to.
 35
 36    This does NOT change the meaning of any of the built-in
 37    `networkx.MultiDiGraph` methods, but instead adds new methods for
 38    access to nodes or attributes by node -> edge name.
 39    """
 40    def __init__(self) -> None:
 41        super().__init__()
 42        # A dictionary that maps nodes to edge names, storing neighbor
 43        # nodes for each edge. Those neighbor nodes can be used to look
 44        # up edge attributes using the normal MultiDiGraph machinery.
 45        self._byEdge: Dict[Node, Dict[Edge, Node]] = {}
 46
 47    # Note: not hashable
 48
 49    def __eq__(self, other: Any) -> bool:
 50        """
 51        Compares two graphs for equality. Note that various kinds of
 52        graphs can be equal to a `UniqueExitsGraph` as long as the node
 53        names, edge names, and data attributes are all the same.
 54        """
 55        if not isinstance(other, nx.Graph):
 56            return False
 57        else:
 58            # Compare nodes
 59            myNodes = list(self)
 60            otherNodes = list(self)
 61            if len(myNodes) != len(otherNodes):
 62                return False
 63            myNodes.sort()
 64            otherNodes.sort()
 65            if myNodes != otherNodes:
 66                return False
 67
 68            # Compare edges
 69            myEdges = list(self.edges)
 70            otherEdges = list(other.edges)
 71            if len(myEdges) != len(otherEdges):
 72                return False
 73            if len(myEdges) > 0 and len(myEdges[0]) != len(otherEdges[0]):
 74                return False
 75            myEdges.sort()
 76            otherEdges.sort()
 77            if myEdges != otherEdges:
 78                return False
 79
 80            # Compare node data
 81            if any(
 82                self.nodes[node] != other.nodes[node]
 83                for node in myNodes
 84            ):
 85                return False
 86
 87            # Compare edge data
 88            if any(
 89                self.edges[edge] != other.edges[edge]
 90                for edge in myEdges
 91            ):
 92                return False
 93
 94            # Everything checks out...
 95            return True
 96
 97    def new_edge_key(self, u: Node, v: Node) -> NoReturn:
 98        """
 99        This method would normally be used to generate new edge keys. We
100        disable it, because we want to ensure that all edges are properly
101        labeled.
102        """
103        raise NotImplementedError(
104            "Attempted to add an edge without specifying a key!"
105        )
106
107    # TODO: Sort out networkx type annotations?
108    def add_node(self, node: Node, **attr: Any):  # type:ignore [override]
109        """
110        See `networkx.MultiDiGraph.add_node`.
111        """
112        super().add_node(node, **attr)
113        self._byEdge[node] = {}  # type Dict[Edge, Node]
114
115    def add_nodes_from(  # type:ignore [override]
116        self,
117        nodes: Union[
118            Iterable[Node],
119            Iterable[Tuple[Node, Dict[Any, Any]]]
120        ],
121        **attr: Any
122    ):
123        """
124        See `networkx.MultiDiGraph.add_nodes_from`.
125        """
126        super().add_nodes_from(nodes, **attr)
127        # Reassignment during tuple unpacking is not checkable...
128        n: Any
129        for n in nodes:
130            # Test for hashability & unpack tuple if not
131            try:
132                self._byEdge.get(n)
133            except TypeError:
134                n, _ = n  # mypy can't handle this properly
135            self._byEdge[n] = {}
136
137    def remove_node(self, node: Node):
138        """
139        See `networkx.MultiDiGraph.remove_node`.
140        """
141        # Handle deletion from inherited structures
142        super().remove_node(node)
143
144        # Ignore if not present
145        if node not in self._byEdge:
146            return
147
148        # Remove record of outgoing edges
149        del self._byEdge[node]
150
151        # Remove incoming edge records
152        for source, edgeMap in self._byEdge.items():
153            delete = []
154            # Find all edges which go to the deleted node
155            # (this is not terribly efficient)
156            for edgeName, dest in edgeMap.items():
157                if dest == node:
158                    delete.append(edgeName)
159            # Delete them in a separate loop, so that we don't
160            # modify-while-iterating (not efficient and maybe
161            # unnecessary?)
162            for d in delete:
163                del edgeMap[d]
164
165    def remove_nodes_from(self, nodes: Iterable[Node]):
166        """
167        See `networkx.MultiDiGraph.remove_nodes_from`.
168        """
169        # First use inherited method to remove from inherited structures
170        super().remove_nodes_from(nodes)
171        # remove our custom info
172        for n in nodes:
173            if n in self._byEdge:
174                del self._byEdge[n]
175
176            for source, edgeMap in self._byEdge.items():
177                delete = []
178                # Find all edges that go to any deleted node
179                for edgeName, dest in edgeMap.items():
180                    if dest in nodes:
181                        delete.append(edgeName)
182
183                # Remove edges in separate loop to avoid
184                # modifying-while-iterating (not efficient and maybe
185                # unnecessary?)
186                for d in delete:
187                    del edgeMap[d]
188
189    def add_edge( # type:ignore [override]
190        self,
191        u_of_edge: Node,
192        v_of_edge: Node,
193        key: Edge,
194        **attr: Any
195    ) -> Edge:
196        """
197        See `networkx.MultiDiGraph.add_edge`.
198
199        For a `UniqueExitsGraph`, an edge key must be supplied
200        explicitly. A `KeyError` will be raised if an edge using the
201        given key (i.e., name) already exists starting at the source node
202        (regardless of its destination!).
203
204        Returns the key it was given, to match the base `add_edge` API.
205        """
206        if u_of_edge in self._byEdge and key in self._byEdge[u_of_edge]:
207            raise KeyError(
208                f"Cannot add a second edge {key!r} starting at node"
209                f" {u_of_edge!r}."
210            )
211        super().add_edge(u_of_edge, v_of_edge, key, **attr)
212        # Note: the base add_edge function does NOT call our add_node
213        # function :(
214        if u_of_edge not in self._byEdge:
215            self._byEdge[u_of_edge] = {}
216        if v_of_edge not in self._byEdge:
217            self._byEdge[v_of_edge] = {}
218        # Add the edge to our by-edge-name structure
219        self._byEdge[u_of_edge][key] = v_of_edge
220
221        return key
222
223    def add_edges_from(
224        self,
225        ebunch_to_add: Any,
226        # Type should be this, but checker won't pass it:
227        # Union[
228        #     Iterable[Tuple[Node, Node, Edge]],
229        #     Iterable[Tuple[Node, Node, Edge, Dict[Any, Any]]]
230        # ],
231        **attr: Any
232    ):
233        """
234        See `networkx.MultiDiGraph.add_edges_from`. Tuples in the ebunch
235        must be 3- or 4-tuples that include a specific key (not just
236        data). Nodes will be created as necessary.
237
238        Raises a `KeyError` if adding an edge is impossible because it
239        re-uses the same edge name at a particular source node, but if an
240        attempt is made to add an existing edge with the same
241        destination, this will just update the relevant edge attributes.
242
243        Raises a `KeyError` instead of silently updating edge properties
244        if the existing edge was also added by an earlier entry in the
245        `ebunch_to_add` (i.e., if you are trying to add two edges at
246        once that go between the same pair of nodes and use the same
247        edge key).
248
249        >>> from exploration import graphs as eg
250        >>> g = eg.UniqueExitsGraph()
251        >>> g.add_edges_from([
252        ...     ('A', 'B', 'up'),
253        ...     ('A', 'B', 'up2'),
254        ...     ('B', 'A', 'down'),
255        ...     ('B', 'B', 'self'),
256        ...     ('B', 'C', 'next'),
257        ...     ('C', 'B', 'prev')
258        ... ])
259        >>> g.nodes
260        NodeView(('A', 'B', 'C'))
261        >>> for edge in g.edges:
262        ...    print(edge)
263        ('A', 'B', 'up')
264        ('A', 'B', 'up2')
265        ('B', 'A', 'down')
266        ('B', 'B', 'self')
267        ('B', 'C', 'next')
268        ('C', 'B', 'prev')
269        """
270        etuple: Any
271        for i, etuple in enumerate(ebunch_to_add):
272            if len(etuple) < 3:
273                raise ValueError(
274                    f"Edges to add must contain explicit keys for a"
275                    f" UniqueExitsGraph (edge #{i} had only 2 parts)."
276                )
277            try:
278                hash(etuple[2])
279            except TypeError:
280                raise ValueError(
281                    f"Edges to add must contain explicit keys for a"
282                    f" UniqueExitsGraph (edge #{i} had an unhashable 3rd"
283                    f" component)."
284                )
285
286            # Check edge name uniqueness
287            u, v, k = etuple[:3]
288            if u in self._byEdge and self._byEdge[u].get(k) != v:
289                raise KeyError(
290                    f"Cannot add or update an edge named '{k}' from node"
291                    f" '{u}' to node '{v}' because an edge by that name"
292                    f" already exists and goes to a different"
293                    f" destination."
294                )
295
296        # Add edges to inherited structures
297        super().add_edges_from(ebunch_to_add, **attr)
298
299        # Note base implementation calls add_edge, so we don't need to
300        # add edges to our extra structure
301
302    def remove_edge(  # type:ignore [override]
303        self,
304        u_of_edge: Node,
305        v_of_edge: Node,
306        key: Edge
307    ):
308        """
309        See `networkx.MultiDiGraph.remove_edge`. A key is required in
310        this version to specify which edge we're removing.
311
312        Raises a NetworkXError if the target edge does not exist.
313        """
314        super().remove_edge(u_of_edge, v_of_edge, key)
315        del self._byEdge[u_of_edge][key]
316
317    def remove_edges_from(
318        self,
319        ebunch: Union[  # type:ignore [override]
320            Iterable[Tuple[Node, Node, Edge]],
321            Iterable[Tuple[Node, Node, Edge, Dict[Any, Any]]]
322        ]
323    ):
324        """
325        See `networkx.MultiDiGraph.remove_edges_from`. Edge tuples in
326        the ebunch must be 3- or 4-tuples that include a key.
327
328        If an edge being removed is not present, it will be ignored.
329        """
330        if any(len(etuple) not in (3, 4) for etuple in ebunch):
331            raise ValueError(
332                "Edges to remove must be u, v, k 3-tuples or u, v, k, d"
333                " 4-tuples."
334            )
335        # TODO: Fix networkx MultiDiGraph type stubs
336        super().remove_edges_from(ebunch)  # type:ignore [arg-type]
337        # This calls self.remove_edge under the hood so we don't need
338        # extra cleanup steps for _byEdge.
339
340    def clear(self) -> None:
341        """
342        See `networkx.MultiDiGraph.clear`.
343        """
344        super().clear()
345        self._byEdge.clear()
346
347    def clear_edges(self) -> None:
348        """
349        See `networkx.MultiDiGraph.clear_edges`.
350        """
351        super().clear_edges()
352        for _, edgeMap in self._byEdge.items():
353            edgeMap.clear()
354
355    def reverse(self) -> NoReturn:  # type:ignore [override]
356        """
357        See `networkx.MultiDiGraph.reverse`.
358        """
359        raise NotImplementedError(
360            "Reversing a UniqueExitsGraph is not supported because"
361            " reversed edge names might not be unique."
362        )
363
364    def removeEdgeByKey(self, uOfEdge: Node, key: Edge):
365        """
366        Removes an edge sourced at a particular node that has a
367        particular key, without knowing what the destination is.
368
369        Raises a `KeyError` if the named edge does not exist.
370
371        ## Example
372
373        >>> g = UniqueExitsGraph()
374        >>> g.add_edges_from([
375        ...     ('A', 'B', 'up'),
376        ...     ('A', 'B', 'up2'),
377        ...     ('B', 'A', 'down'),
378        ...     ('B', 'B', 'self'),
379        ...     ('B', 'C', 'next'),
380        ...     ('C', 'B', 'prev')
381        ... ])
382        >>> g.getDestination('A', 'up')
383        'B'
384        >>> g.getDestination('A', 'up2')
385        'B'
386        >>> g.getDestination('B', 'self')
387        'B'
388        >>> g.removeEdgeByKey('A', 'up2')
389        >>> g.removeEdgeByKey('B', 'self')
390        >>> g.getDestination('A', 'up2') is None
391        True
392        >>> g.getDestination('B', 'self') is None
393        True
394        """
395        vOfEdge = self._byEdge[uOfEdge][key]
396        super().remove_edge(uOfEdge, vOfEdge, key)
397        del self._byEdge[uOfEdge][key]
398
399    def removeEdgesByKey(self, edgeIds: Iterable[Tuple[Node, Edge]]):
400        """
401        Removes multiple edges by source node and key, without needing
402        to know destination nodes. The `edgeIds` argument must be a list
403        of tuples containing source node, edge key pairs.
404
405        Silently ignores already-nonexistent edges.
406
407        ## Example
408
409        >>> g = UniqueExitsGraph()
410        >>> g.add_edges_from([
411        ...     ('A', 'B', 'up'),
412        ...     ('A', 'B', 'up2'),
413        ...     ('B', 'A', 'down'),
414        ...     ('B', 'B', 'self'),
415        ...     ('B', 'C', 'next'),
416        ...     ('C', 'B', 'prev')
417        ... ])
418        >>> g.getDestination('A', 'up')
419        'B'
420        >>> g.getDestination('A', 'up2')
421        'B'
422        >>> g.getDestination('B', 'self')
423        'B'
424        >>> g.removeEdgesByKey([('A', 'up2'), ('B', 'self')])
425        >>> g.getDestination('A', 'up2') is None
426        True
427        >>> g.getDestination('B', 'self') is None
428        True
429        """
430        for source, key in edgeIds:
431            if key in self._byEdge.get(source, {}):
432                self.removeEdgeByKey(source, key)
433            # Otherwise ignore this edge...
434
435    def connections(
436        self,
437        edgeFilter: Optional[
438            Callable[[Node, Edge, Node, 'UniqueExitsGraph'], bool]
439        ] = None
440    ) -> nx.Graph:
441        """
442        Returns an undirected graph with the same nodes IDs as the base
443        graph but none of the node or edge attributes. Nodes which have
444        any connection between them in either direction in the original
445        graph will be connected by a single edge in the connections
446        graph.
447
448        If an `edgeFilter` function is provided, it will be given a
449        source node, an edge, a destination node, and the entire graph as
450        arguments. It should return a boolean, and for edges where it
451        returns False, these won't be included in the final graph. Note
452        that because two nodes can be connected by multiple edges in
453        either direction, filtering out a single edge may not sever the
454        connection between two nodes in the final graph.
455        """
456        result: nx.Graph = nx.Graph()
457        result.add_nodes_from(self)
458        if edgeFilter is None:
459            result.add_edges_from(self.edges(keys=False, data=False))
460        else:
461            useEdges = []
462            for (src, dst, edge) in self.edges(keys=True):
463                if edgeFilter(src, edge, dst, self):
464                    result.add_edge(src, dst)
465        return result
466
467    def destinationsFrom(self, source: Node) -> Dict[Edge, Node]:
468        """
469        Given a source node, returns a dictionary mapping the keys of all
470        outgoing edges from that node to their destination nodes. Raises
471        a `KeyError` if the node is not present in the graph.
472
473        Editing the dictionary returned could cause serious problems, so
474        please don't; it will be updated live as the graph is changed.
475
476        ## Example
477
478        >>> g = UniqueExitsGraph()
479        >>> g.add_edges_from([
480        ...     ('A', 'B', 'up'),
481        ...     ('A', 'B', 'up2'),
482        ...     ('B', 'A', 'down'),
483        ...     ('B', 'B', 'self'),
484        ...     ('B', 'C', 'next'),
485        ...     ('C', 'B', 'prev')
486        ... ])
487        >>> g.destinationsFrom('A')
488        {'up': 'B', 'up2': 'B'}
489        >>> g.destinationsFrom('B')
490        {'down': 'A', 'self': 'B', 'next': 'C'}
491        >>> g.destinationsFrom('C')
492        {'prev': 'B'}
493        >>> g.destinationsFrom('D')
494        Traceback (most recent call last):
495        ...
496        KeyError...
497        """
498        return self._byEdge[source]
499
500    def destination(self, source: Node, edge: Edge) -> Node:
501        """
502        Given a source node and an edge key, looks up and returns the
503        destination node for that edge. Raises a `KeyError` if there is no
504        edge from the specified node with the specified name.
505
506        ## Example
507
508        >>> g = UniqueExitsGraph()
509        >>> g.add_edges_from([
510        ...     ('A', 'B', 'up'),
511        ...     ('A', 'B', 'up2'),
512        ...     ('B', 'A', 'down'),
513        ...     ('B', 'B', 'self'),
514        ...     ('B', 'C', 'next'),
515        ...     ('C', 'B', 'prev')
516        ... ])
517        >>> g.destination('A', 'up')
518        'B'
519        >>> g.destination('A', 'up2')
520        'B'
521        >>> g.destination('B', 'down')
522        'A'
523        >>> g.destination('A', 'nonexistent')
524        Traceback (most recent call last):
525        ...
526        KeyError...
527        >>> g.destination('D', 'any')
528        Traceback (most recent call last):
529        ...
530        KeyError...
531        """
532        return self._byEdge[source][edge]
533
534    def getDestination(
535        self,
536        source: Node,
537        edge: Edge,
538        default: Any = None
539    ) -> Optional[Node]:
540        """
541        Works like `destination`, but instead of raising a `KeyError` if
542        the node or edge is missing, it returns a default value (with a
543        default default of `None`).
544
545        ## Example
546
547        >>> g = UniqueExitsGraph()
548        >>> g.add_edges_from([
549        ...     ('A', 'B', 'up'),
550        ...     ('A', 'B', 'up2'),
551        ...     ('B', 'A', 'down'),
552        ...     ('B', 'B', 'self'),
553        ...     ('B', 'C', 'next'),
554        ...     ('C', 'B', 'prev')
555        ... ])
556        >>> g.getDestination('A', 'up')
557        'B'
558        >>> g.getDestination('A', 'up2')
559        'B'
560        >>> g.getDestination('B', 'down')
561        'A'
562        >>> g.getDestination('A', 'nonexistent') is None
563        True
564        >>> g.getDestination('A', 'nonexistent', 'default')
565        'default'
566        >>> g.getDestination('D', 'any') is None
567        True
568        """
569        return self._byEdge.get(source, {}).get(edge, default)
570
571    def allEdgesTo(
572        self,
573        destination: Node
574    ) -> List[Tuple[Node, Edge]]:
575        """
576        Searches the entire graph for edges whose destinations are the
577        specified destination, and returns a list of (node, edge) pairs
578        indicating the source node and edge name for each of those edges.
579        Self-edges are included in this list.
580
581        ## Example
582
583        >>> g = UniqueExitsGraph()
584        >>> g.add_edges_from([
585        ...     ('A', 'B', 'up'),
586        ...     ('A', 'B', 'up2'),
587        ...     ('B', 'A', 'down'),
588        ...     ('B', 'B', 'self'),
589        ...     ('B', 'C', 'next'),
590        ...     ('C', 'B', 'prev')
591        ... ])
592        >>> g.allEdgesTo('A')
593        [('B', 'down')]
594        >>> g.allEdgesTo('B')
595        [('A', 'up'), ('A', 'up2'), ('B', 'self'), ('C', 'prev')]
596        >>> g.allEdgesTo('C')
597        [('B', 'next')]
598        >>> g.allEdgesTo('D')
599        []
600        """
601        results = []
602        for node in self:
603            fromThere = self[node]
604            toHere = fromThere.get(destination, {})
605            for edgeKey in toHere:
606                results.append((node, edgeKey))
607
608        return results
609
610    def allEdges(self) -> List[Tuple[Node, Node, Edge]]:
611        """
612        Returns a list of tuples containing source node, destination
613        node, and then edge node, which includes each edge in the graph
614        once.
615        """
616        # TODO: Fix networkx type annotations
617        return self.edges(keys=True)  # type: ignore
618
619    def textMapObj(
620        self,
621        edgeSep: str = '::',
622        external: Optional[Set[Node]] = None,
623        explorationOrder: Optional[Tuple[Node, Sequence[Edge]]] = None,
624        edgeOrders: Union[
625            Dict[Node, Sequence[Edge]],
626            Dict[Node, Dict[Edge, Any]],
627            None
628        ] = None
629    ):
630        """
631        Returns a special object which is JSON-serializable and which
632        when serialized creates a semi-human-usable text-format map of
633        the graph.
634
635        The object consists of nested dictionaries, one per node, where
636        keys are node name + edge name strings (combined using the
637        `edgeSep` argument, default is '::'). The value for each key is
638        one of:
639
640        1. Another dictionary representing the node that edge leads
641            to, which can in turn have dictionary values...
642        2. A string naming a destination node that's already represented
643            elsewhere (or naming the current node for self-edges).
644
645        Any node present in the specified `external` set will be linked
646        to instead of listed out, even if it exists in the graph. The
647        `external` set **will be modified** by this function to include
648        all visited nodes in the graph.
649
650        If an `explorationOrder` is provided, it must be a tuple
651        specifying a start node followed by a sequence of edges that
652        indicates the path taken, and the edges will be visited
653        according to that order (this only matters in Python 3.7+ where
654        dictionaries have consistent order). A `ValueError` will be
655        raised if an invalid exploration order is provided. The path
656        list will be ignored if `edgeOrders` is provided explicitly.
657
658        TODO: What about unexplorable graphs (allow node names in place
659        of edge names in exploration order?)?!?
660
661        If `edgeOrders` is provided directly, it will override the
662        path part of the `explorationOrder` to determine the ordering of
663        edges at each node. If not and `explorationOrder` is provided, it
664        will be deduced from the `explorationOrder`. If neither is
665        present, ordering will follow whatever natural order is in the
666        graph, which in most cases should be order-of-creation.
667
668        Notes:
669        - For the format to avoid ambiguity, the `edgeSep` value must be
670            a string which does not appear in any node or edge names.
671        - Nodes and edge values will be converted to strings to build the
672            map.
673        - Node and edge properties are not represented in the resulting
674            object.
675        - For a variety of reasons, the result cannot be converted back
676            to a graph object. This is not intended for use as a JSON
677            serialization route (see the `networkx.readwrite.json_graph`
678            module for some built-in options).
679        - To get a string representation, one could do:
680            `json.dumps(graph.textMapObj())`
681
682        ## Examples
683
684        >>> from exploration import graphs as eg
685        >>> import json
686        >>> g = eg.UniqueExitsGraph()
687        >>> g.add_edges_from([
688        ...     ('A', 'B', 'up'),
689        ...     ('A', 'B', 'up2'),
690        ...     ('B', 'A', 'down'),
691        ...     ('B', 'B', 'self'),
692        ...     ('B', 'C', 'next'),
693        ...     ('C', 'B', 'prev')
694        ... ])
695        >>> print(json.dumps(g.textMapObj(), indent=2))
696        {
697          "A::up": {
698            "B::down": "A",
699            "B::self": "B",
700            "B::next": {
701              "C::prev": "B"
702            }
703          },
704          "A::up2": "B"
705        }
706        """
707        # We use `external` as our visited set
708        if external is None:
709            external = set()
710
711        if explorationOrder is not None:
712            here, path = explorationOrder
713        else:
714            # Find first non-external node as our starting node
715            for here in self.nodes:
716                if here not in external:
717                    break
718
719            # Path is empty
720            path = []
721
722        # Determine edge ordering for each node from exploration order
723        # or by natural ordering if no explorationOrder is available
724        if edgeOrders is None:
725            edgeOrders = cast(
726                Dict[Node, Dict[Edge, Any]],
727                {}
728            )
729            current = here
730            for i in range(len(path)):
731                edge = path[i]
732                # Add this edge next in the ordering for this node
733                orderHere: Dict[Edge, Any] = edgeOrders.setdefault(current, {})
734                # Note: we use a dictionary here because dictionaries do
735                # preserve insertion ordering (3.7+) and we need to both
736                # keep things in order AND do a bunch of lookups to
737                # avoid duplicates.
738                if edge not in orderHere:
739                    orderHere[edge] = True
740
741                # Move to next node
742                if edge not in self._byEdge[current]:
743                    raise ValueError(
744                        f"Invalid edge in exploration order path: at"
745                        f" step {i} we reached node {current} and were"
746                        f" supposed to take edge {edge} but that edge"
747                        f" does not exist."
748                    )
749                current = self._byEdge[current][edge]
750
751            # Add any unexplored nodes and/or edges in natural order
752            for node in self.nodes:
753                orderHere = edgeOrders.setdefault(node, {})
754                for edge in self._byEdge[node]:
755                    if edge not in orderHere:
756                        orderHere[edge] = True
757
758        result = {}
759        external.add(here)
760        # Now loop through keys of this node
761        for key in edgeOrders[here]:
762            combined = str(here) + edgeSep + str(key)
763            dest = self._byEdge[here][key]
764            if dest in external:
765                # links, including self-links
766                result[combined] = str(dest)
767            else:
768                # Recurse
769                result[combined] = self.textMapObj(
770                    edgeSep,
771                    external,
772                    (dest, []),  # empty path since we have edgeOrders
773                    edgeOrders
774                )
775
776        return result