Skip to main content
`Ctrl`+`K`

# Source code for networkx.utils.backends

    """
    Docs for backend users
    ~~~~~~~~~~~~~~~~~~~~~~
    NetworkX utilizes a plugin-dispatch architecture. A valid NetworkX backend
    specifies `entry points
    <https://packaging.python.org/en/latest/specifications/entry-points>`_, named
    ``networkx.backends`` and an optional ``networkx.backend_info`` when it is
    installed (not imported). This allows NetworkX to dispatch (redirect) function
    calls to the backend so the execution flows to the designated backend
    implementation. This design enhances flexibility and integration, making
    NetworkX more adaptable and efficient.

    NetworkX can dispatch to backends **explicitly** (this requires changing code)
    or **automatically** (this requires setting configuration or environment
    variables). The best way to use a backend depends on the backend, your use
    case, and whether you want to automatically convert to or from backend
    graphs. Automatic conversions of graphs is always opt-in.

    To explicitly dispatch to a backend, use the `backend=` keyword argument in a
    dispatchable function. This will convert (and cache by default) input NetworkX
    graphs to backend graphs and call the backend implementation. Another explicit
    way to use a backend is to create a backend graph directly--for example,
    perhaps the backend has its own functions for loading data and creating
    graphs--and pass that graph to a dispatchable function, which will then call
    the backend implementation without converting.

    Using automatic dispatch requires setting configuration options. Every NetworkX
    configuration may also be set from an environment variable and are processed at
    the time networkx is imported.  The following configuration variables are
    supported:

    * ``nx.config.backend_priority`` (``NETWORKX_BACKEND_PRIORITY`` env var), a
      list of backends, controls dispatchable functions that don't return graphs
      such as e.g. ``nx.pagerank``. When one of these functions is called with
      NetworkX graphs as input, the dispatcher iterates over the backends listed in
      this backend_priority config and will use the first backend that implements
      this function. The input NetworkX graphs are converted (and cached by
      default) to backend graphs. Using this configuration can allow you to use the
      full flexibility of NetworkX graphs and the performance of backend
      implementations, but possible downsides are that creating NetworkX graphs,
      converting to backend graphs, and caching backend graphs may all be
      expensive.

    * ``nx.config.backend_priority.algos`` (``NETWORKX_BACKEND_PRIORITY_ALGOS`` env
      var), can be used instead of ``nx.config.backend_priority``
      (``NETWORKX_BACKEND_PRIORITY`` env var) to emphasize that the setting only
      affects the dispatching of algorithm functions as described above.

    * ``nx.config.backend_priority.generators``
      (``NETWORKX_BACKEND_PRIORITY_GENERATORS`` env var), a list of backends,
      controls dispatchable functions that return graphs such as
      nx.from_pandas_edgelist and nx.empty_graph. When one of these functions is
      called, the first backend listed in this backend_priority config that
      implements this function will be used and will return a backend graph. When
      this backend graph is passed to other dispatchable NetworkX functions, it
      will use the backend implementation if it exists or raise by default unless
      nx.config.fallback_to_nx is True (default is False). Using this configuration
      avoids creating NetworkX graphs, which subsequently avoids the need to
      convert to and cache backend graphs as when using
      nx.config.backend_priority.algos, but possible downsides are that the backend
      graph may not behave the same as a NetworkX graph and the backend may not
      implement all algorithms that you use, which may break your workflow.

    * ``nx.config.fallback_to_nx`` (``NETWORKX_FALLBACK_TO_NX`` env var), a boolean
      (default False), controls what happens when a backend graph is passed to a
      dispatchable function that is not implemented by that backend. The default
      behavior when False is to raise. If True, then the backend graph will be
      converted (and cached by default) to a NetworkX graph and will run with the
      default NetworkX implementation. Enabling this configuration can allow
      workflows to complete if the backend does not implement all algorithms used
      by the workflow, but a possible downside is that it may require converting
      the input backend graph to a NetworkX graph, which may be expensive. If a
      backend graph is duck-type compatible as a NetworkX graph, then the backend
      may choose not to convert to a NetworkX graph and use the incoming graph
      as-is.

    * ``nx.config.cache_converted_graphs`` (``NETWORKX_CACHE_CONVERTED_GRAPHS`` env
      var), a boolean (default True), controls whether graph conversions are cached
      to G.__networkx_cache__ or not. Caching can improve performance by avoiding
      repeated conversions, but it uses more memory.

    .. note:: Backends *should* follow the NetworkX backend naming convention. For
       example, if a backend is named ``parallel`` and specified using
       ``backend=parallel`` or ``NETWORKX_BACKEND_PRIORITY=parallel``, the package
       installed is ``nx-parallel``, and we would use ``import nx_parallel`` if we
       were to import the backend package directly.

    Backends are encouraged to document how they recommend to be used and whether
    their graph types are duck-type compatible as NetworkX graphs. If backend
    graphs are NetworkX-compatible and you want your workflow to automatically
    "just work" with a backend--converting and caching if necessary--then use all
    of the above configurations. Automatically converting graphs is opt-in, and
    configuration gives the user control.

    Examples:
    ---------

    Use the ``cugraph`` backend for every algorithm function it supports. This will
    allow for fall back to the default NetworkX implementations for algorithm calls
    not supported by cugraph because graph generator functions are still returning
    NetworkX graphs.

    .. code-block:: bash

       bash> NETWORKX_BACKEND_PRIORITY=cugraph python my_networkx_script.py

    Explicitly use the ``parallel`` backend for a function call.

    .. code-block:: python

        nx.betweenness_centrality(G, k=10, backend="parallel")

    Explicitly use the ``parallel`` backend for a function call by passing an
    instance of the backend graph type to the function.

    .. code-block:: python

       H = nx_parallel.ParallelGraph(G)
       nx.betweenness_centrality(H, k=10)

    Explicitly use the ``parallel`` backend and pass additional backend-specific
    arguments. Here, ``get_chunks`` is an argument unique to the ``parallel``
    backend.

    .. code-block:: python

       nx.betweenness_centrality(G, k=10, backend="parallel", get_chunks=get_chunks)

    Automatically dispatch the ``cugraph`` backend for all NetworkX algorithms and
    generators, and allow the backend graph object returned from generators to be
    passed to NetworkX functions the backend does not support.

    .. code-block:: bash

       bash> NETWORKX_BACKEND_PRIORITY_ALGOS=cugraph \\
             NETWORKX_BACKEND_PRIORITY_GENERATORS=cugraph \\
             NETWORKX_FALLBACK_TO_NX=True \\
             python my_networkx_script.py

    How does this work?
    -------------------

    If you've looked at functions in the NetworkX codebase, you might have seen the
    ``@nx._dispatchable`` decorator on most of the functions. This decorator allows the NetworkX
    function to dispatch to the corresponding backend function if available. When the decorated
    function is called, it first checks for a backend to run the function, and if no appropriate
    backend is specified or available, it runs the NetworkX version of the function.

    Backend Keyword Argument
    ^^^^^^^^^^^^^^^^^^^^^^^^

    When a decorated function is called with the ``backend`` kwarg provided, it checks
    if the specified backend is installed, and loads it. Next it checks whether to convert
    input graphs by first resolving the backend of each input graph by looking
    for an attribute named ``__networkx_backend__`` that holds the backend name for that
    graph type. If all input graphs backend matches the ``backend`` kwarg, the backend's
    function is called with the original inputs. If any of the input graphs do not match
    the ``backend`` kwarg, they are converted to the backend graph type before calling.
    Exceptions are raised if any step is not possible, e.g. if the backend does not
    implement this function.

    Finding a Backend
    ^^^^^^^^^^^^^^^^^

    When a decorated function is called without a ``backend`` kwarg, it tries to find a
    dispatchable backend function.
    The backend type of each input graph parameter is resolved (using the
    ``__networkx_backend__`` attribute) and if they all agree, that backend's function
    is called if possible. Otherwise the backends listed in the config ``backend_priority``
    are considered one at a time in order. If that backend supports the function and
    can convert the input graphs to its backend type, that backend function is called.
    Otherwise the next backend is considered.

    During this process, the backends can provide helpful information to the dispatcher
    via helper methods in the backend's interface. Backend methods ``can_run`` and
    ``should_run`` are used by the dispatcher to determine whether to use the backend
    function. If the number of nodes is small, it might be faster to run the NetworkX
    version of the function. This is how backends can provide info about whether to run.

    Falling Back to NetworkX
    ^^^^^^^^^^^^^^^^^^^^^^^^

    If none of the backends are appropriate, we "fall back" to the NetworkX function.
    That means we resolve the backends of all input graphs and if all are NetworkX
    graphs we call the NetworkX function. If any are not NetworkX graphs, we raise
    an exception unless the `fallback_to_nx` config is set. If it is, we convert all
    graph types to NetworkX graph types before calling the NetworkX function.

    Functions that mutate the graph
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

    Any function decorated with the option that indicates it mutates the graph goes through
    a slightly different path to automatically find backends. These functions typically
    generate a graph, or add attributes or change the graph structure. The config
    `backend_priority.generators` holds a list of backend names similar to the config
    `backend_priority`. The process is similar for finding a matching backend. Once found,
    the backend function is called and a backend graph is returned (instead of a NetworkX
    graph). You can then use this backend graph in any function supported by the backend.
    And you can use it for functions not supported by the backend if you set the config
    `fallback_to_nx` to allow it to convert the backend graph to a NetworkX graph before
    calling the function.

    Optional keyword arguments
    ^^^^^^^^^^^^^^^^^^^^^^^^^^

    Backends can add optional keyword parameters to NetworkX functions to allow you to
    control aspects of the backend algorithm. Thus the function signatures can be extended
    beyond the NetworkX function signature. For example, the ``parallel`` backend might
    have a parameter to specify how many CPUs to use. These parameters are collected
    by the dispatchable decorator code at the start of the function call and used when
    calling the backend function.

    Existing Backends
    ^^^^^^^^^^^^^^^^^

    NetworkX does not know all the backends that have been created.  In fact, the
    NetworkX library does not need to know that a backend exists for it to work. As
    long as the backend package creates the ``entry_point``, and provides the
    correct interface, it will be called when the user requests it using one of the
    three approaches described above. Some backends have been working with the
    NetworkX developers to ensure smooth operation.

    Refer to the :doc:`/backends` section to see a list of available backends known
    to work with the current stable release of NetworkX.

    .. _introspect:

    Introspection and Logging
    -------------------------
    Introspection techniques aim to demystify dispatching and backend graph conversion behaviors.

    The primary way to see what the dispatch machinery is doing is by enabling logging.
    This can help you verify that the backend you specified is being used.
    You can enable NetworkX's backend logger to print to ``sys.stderr`` like this::

        import logging
        nxl = logging.getLogger("networkx")
        nxl.addHandler(logging.StreamHandler())
        nxl.setLevel(logging.DEBUG)

    And you can disable it by running this::

        nxl.setLevel(logging.CRITICAL)

    Refer to :external+python:mod:`logging` to learn more about the logging facilities in Python.

    By looking at the ``.backends`` attribute, you can get the set of all currently
    installed backends that implement a particular function. For example::

        >>> nx.betweenness_centrality.backends  # doctest: +SKIP
        {'parallel'}

    The function docstring will also show which installed backends support it
    along with any backend-specific notes and keyword arguments::

        >>> help(nx.betweenness_centrality)  # doctest: +SKIP
        ...
        Backends
        --------
        parallel : Parallel backend for NetworkX algorithms
          The parallel computation is implemented by dividing the nodes into chunks
          and computing betweenness centrality for each chunk concurrently.
        ...

    The NetworkX documentation website also includes info about trusted backends of NetworkX in function references.
    For example, see :func:`~networkx.algorithms.shortest_paths.weighted.all_pairs_bellman_ford_path_length`.

    Introspection capabilities are currently limited, but we are working to improve them.
    We plan to make it easier to answer questions such as:

    - What happened (and why)?
    - What *will* happen (and why)?
    - Where was time spent (including conversions)?
    - What is in the cache and how much memory is it using?

    Transparency is essential to allow for greater understanding, debug-ability,
    and customization. After all, NetworkX dispatching is extremely flexible and can
    support advanced workflows with multiple backends and fine-tuned configuration,
    but introspection can be helpful by describing *when* and *how* to evolve your workflow
    to meet your needs. If you have suggestions for how to improve introspection, please
    `let us know <https://github.com/networkx/networkx/issues/new>`_!

    Docs for backend developers
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~

    Creating a custom backend
    -------------------------

    1.  Defining a ``BackendInterface`` object:

        Note that the ``BackendInterface`` doesn't need to must be a class. It can be an
        instance of a class, or a module as well. You can define the following methods or
        functions in your backend's ``BackendInterface`` object.:

        1. ``convert_from_nx`` and ``convert_to_nx`` methods or functions are required for
           backend dispatching to work. The arguments to ``convert_from_nx`` are:

           - ``G`` : NetworkX Graph
           - ``edge_attrs`` : dict, optional
                Dictionary mapping edge attributes to default values if missing in ``G``.
                If None, then no edge attributes will be converted and default may be 1.
           - ``node_attrs``: dict, optional
                Dictionary mapping node attributes to default values if missing in ``G``.
                If None, then no node attributes will be converted.
           - ``preserve_edge_attrs`` : bool
                Whether to preserve all edge attributes.
           - ``preserve_node_attrs`` : bool
                Whether to preserve all node attributes.
           - ``preserve_graph_attrs`` : bool
                Whether to preserve all graph attributes.
           - ``preserve_all_attrs`` : bool
                Whether to preserve all graph, node, and edge attributes.
           - ``name`` : str
                The name of the algorithm.
           - ``graph_name`` : str
                The name of the graph argument being converted.

        2. ``can_run`` (Optional):
              If your backend only partially implements an algorithm, you can define
              a ``can_run(name, args, kwargs)`` function in your ``BackendInterface`` object that
              returns True or False indicating whether the backend can run the algorithm with
              the given arguments or not. Instead of a boolean you can also return a string
              message to inform the user why that algorithm can't be run.

        3. ``should_run`` (Optional):
              A backend may also define ``should_run(name, args, kwargs)``
              that is similar to ``can_run``, but answers whether the backend *should* be run.
              ``should_run`` is only run when performing backend graph conversions. Like
              ``can_run``, it receives the original arguments so it can decide whether it
              should be run by inspecting the arguments. ``can_run`` runs before
              ``should_run``, so ``should_run`` may assume ``can_run`` is True. If not
              implemented by the backend, ``can_run``and ``should_run`` are assumed to
              always return True if the backend implements the algorithm.

        4. ``on_start_tests`` (Optional):
              A special ``on_start_tests(items)`` function may be defined by the backend.
              It will be called with the list of NetworkX tests discovered. Each item
              is a test object that can be marked as xfail if the backend does not support
              the test using ``item.add_marker(pytest.mark.xfail(reason=...))``.

    2.  Adding entry points

        To be discoverable by NetworkX, your package must register an
        `entry-point <https://packaging.python.org/en/latest/specifications/entry-points>`_
        ``networkx.backends`` in the package's metadata, with a `key pointing to your
        dispatch object <https://packaging.python.org/en/latest/guides/creating-and-discovering-plugins/#using-package-metadata>`_ .
        For example, if you are using ``setuptools`` to manage your backend package,
        you can `add the following to your pyproject.toml file <https://setuptools.pypa.io/en/latest/userguide/entry_point.html>`_::

            [project.entry-points."networkx.backends"]
            backend_name = "your_backend_interface_object"

        You can also add the ``backend_info`` entry-point. It points towards the ``get_info``
        function that returns all the backend information, which is then used to build the
        "Additional Backend Implementation" box at the end of algorithm's documentation
        page. Note that the `get_info` function shouldn't import your backend package.::

            [project.entry-points."networkx.backend_info"]
            backend_name = "your_get_info_function"

        The ``get_info`` should return a dictionary with following key-value pairs:
            - ``backend_name`` : str or None
                It is the name passed in the ``backend`` kwarg.
            - ``project`` : str or None
                The name of your backend project.
            - ``package`` : str or None
                The name of your backend package.
            - ``url`` : str or None
                This is the url to either your backend's codebase or documentation, and
                will be displayed as a hyperlink to the ``backend_name``, in the
                "Additional backend implementations" section.
            - ``short_summary`` : str or None
                One line summary of your backend which will be displayed in the
                "Additional backend implementations" section.
            - ``default_config`` : dict
                A dictionary mapping the backend config parameter names to their default values.
                This is used to automatically initialize the default configs for all the
                installed backends at the time of networkx's import.

                .. seealso:: `~networkx.utils.configs.Config`

            - ``functions`` : dict or None
                A dictionary mapping function names to a dictionary of information
                about the function. The information can include the following keys:

                - ``url`` : str or None
                  The url to ``function``'s source code or documentation.
                - ``additional_docs`` : str or None
                  A short description or note about the backend function's
                  implementation.
                - ``additional_parameters`` : dict or None
                  A dictionary mapping additional parameters headers to their
                  short descriptions. For example::

                      "additional_parameters": {
                          'param1 : str, function (default = "chunks")' : "...",
                          'param2 : int' : "...",
                      }

                If any of these keys are not present, the corresponding information
                will not be displayed in the "Additional backend implementations"
                section on NetworkX docs website.

            Note that your backend's docs would only appear on the official NetworkX docs only
            if your backend is a trusted backend of NetworkX, and is present in the
            `.circleci/config.yml` and `.github/workflows/deploy-docs.yml` files in the
            NetworkX repository.

    3.  Defining a Backend Graph class

        The backend must create an object with an attribute ``__networkx_backend__`` that holds
        a string with the entry point name::

            class BackendGraph:
                __networkx_backend__ = "backend_name"
                ...

        A backend graph instance may have a ``G.__networkx_cache__`` dict to enable
        caching, and care should be taken to clear the cache when appropriate.

    Testing the Custom backend
    --------------------------

    To test your custom backend, you can run the NetworkX test suite on your backend.
    This also ensures that the custom backend is compatible with NetworkX's API.
    The following steps will help you run the tests:

    1. Setting Backend Environment Variables:
        - ``NETWORKX_TEST_BACKEND`` : Setting this to your backend's ``backend_name`` will
          let NetworkX's dispatch machinery to automatically convert a regular NetworkX
          ``Graph``, ``DiGraph``, ``MultiGraph``, etc. to their backend equivalents, using
          ``your_backend_interface_object.convert_from_nx(G, ...)`` function.
        - ``NETWORKX_FALLBACK_TO_NX`` (default=False) : Setting this variable to `True` will
          instruct tests to use a NetworkX ``Graph`` for algorithms not implemented by your
          custom backend. Setting this to `False` will only run the tests for algorithms
          implemented by your custom backend and tests for other algorithms will ``xfail``.

    2. Running Tests:
        You can invoke NetworkX tests for your custom backend with the following commands::

            NETWORKX_TEST_BACKEND=<backend_name>
            NETWORKX_FALLBACK_TO_NX=True # or False
            pytest --pyargs networkx

    How tests are run?
    ------------------

    1. While dispatching to the backend implementation the ``_convert_and_call`` function
       is used and while testing the ``_convert_and_call_for_tests`` function is used.
       Other than testing it also checks for functions that return numpy scalars, and
       for functions that return graphs it runs the backend implementation and the
       networkx implementation and then converts the backend graph into a NetworkX graph
       and then compares them, and returns the networkx graph. This can be regarded as
       (pragmatic) technical debt. We may replace these checks in the future.

    2. Conversions while running tests:
        - Convert NetworkX graphs using ``<your_backend_interface_object>.convert_from_nx(G, ...)`` into
          the backend graph.
        - Pass the backend graph objects to the backend implementation of the algorithm.
        - Convert the result back to a form expected by NetworkX tests using
          ``<your_backend_interface_object>.convert_to_nx(result, ...)``.
        - For nx_loopback, the graph is copied using the dispatchable metadata

    3. Dispatchable algorithms that are not implemented by the backend
       will cause a ``pytest.xfail``, when the ``NETWORKX_FALLBACK_TO_NX``
       environment variable is set to ``False``, giving some indication that
       not all tests are running, while avoiding causing an explicit failure.
    """

    import inspect
    import itertools
    import logging
    import os
    import warnings
    from functools import partial
    from importlib.metadata import entry_points

    import networkx as nx

    from .configs import BackendPriorities, Config, NetworkXConfig
    from .decorators import argmap

    __all__ = ["_dispatchable"]

    _logger = logging.getLogger(__name__)

    def _do_nothing():
        """This does nothing at all, yet it helps turn `_dispatchable` into functions."""

    def _get_backends(group, *, load_and_call=False):
        """
        Retrieve NetworkX ``backends`` and ``backend_info`` from the entry points.

        Parameters
        -----------
        group : str
            The entry_point to be retrieved.
        load_and_call : bool, optional
            If True, load and call the backend. Defaults to False.

        Returns
        --------
        dict
            A dictionary mapping backend names to their respective backend objects.

        Notes
        ------
        If a backend is defined more than once, a warning is issued.
        The `nx_loopback` backend is removed if it exists, as it is only available during testing.
        A warning is displayed if an error occurs while loading a backend.
        """
        items = entry_points(group=group)
        rv = {}
        for ep in items:
            if ep.name in rv:
                warnings.warn(
                    f"networkx backend defined more than once: {ep.name}",
                    RuntimeWarning,
                    stacklevel=2,
                )
            elif load_and_call:
                try:
                    rv[ep.name] = ep.load()()
                except Exception as exc:
                    warnings.warn(
                        f"Error encountered when loading info for backend {ep.name}: {exc}",
                        RuntimeWarning,
                        stacklevel=2,
                    )
            else:
                rv[ep.name] = ep
        rv.pop("nx_loopback", None)
        return rv

    # Note: "networkx" will be in `backend_info`, but not `backends` or `config.backends`.
    # It is valid to use "networkx"` as backend argument and in `config.backend_priority`.
    # We may make "networkx" a "proper" backend and have it in `backends` and `config.backends`.
    backends = _get_backends("networkx.backends")
    backend_info = {}  # fill backend_info after networkx is imported in __init__.py

    # Load and cache backends on-demand
    _loaded_backends = {}  # type: ignore[var-annotated]
    _registered_algorithms = {}

    # Get default configuration from environment variables at import time
    def _comma_sep_to_list(string):
        return [stripped for x in string.strip().split(",") if (stripped := x.strip())]

    def _set_configs_from_environment():
        """Initialize ``config.backend_priority``, load backend_info and config.

        This gets default values from environment variables (see ``nx.config`` for details).
        This function is run at the very end of importing networkx. It is run at this time
        to avoid loading backend_info before the rest of networkx is imported in case a
        backend uses networkx for its backend_info (e.g. subclassing the Config class.)
        """
        # backend_info is defined above as empty dict. Fill it after import finishes.
        backend_info.update(_get_backends("networkx.backend_info", load_and_call=True))
        backend_info.update(
            (backend, {}) for backend in backends.keys() - backend_info.keys()
        )

        # set up config based on backend_info and environment
        config = NetworkXConfig(
            backend_priority=BackendPriorities(
                algos=[],
                generators=[],
            ),
            backends=Config(
                **{
                    backend: (
                        cfg
                        if isinstance(cfg := info["default_config"], Config)
                        else Config(**cfg)
                    )
                    if "default_config" in info
                    else Config()
                    for backend, info in backend_info.items()
                }
            ),
            cache_converted_graphs=bool(
                os.environ.get("NETWORKX_CACHE_CONVERTED_GRAPHS", True)
            ),
            fallback_to_nx=bool(os.environ.get("NETWORKX_FALLBACK_TO_NX", False)),
            warnings_to_ignore={
                x.strip()
                for x in os.environ.get("NETWORKX_WARNINGS_TO_IGNORE", "").split(",")
                if x.strip()
            },
        )
        backend_info["networkx"] = {}
        type(config.backends).__doc__ = "All installed NetworkX backends and their configs."

        # NETWORKX_BACKEND_PRIORITY is the same as NETWORKX_BACKEND_PRIORITY_ALGOS
        priorities = {
            key[26:].lower(): val
            for key, val in os.environ.items()
            if key.startswith("NETWORKX_BACKEND_PRIORITY_")
        }
        backend_priority = config.backend_priority
        backend_priority.algos = (
            _comma_sep_to_list(priorities.pop("algos"))
            if "algos" in priorities
            else _comma_sep_to_list(
                os.environ.get(
                    "NETWORKX_BACKEND_PRIORITY",
                    os.environ.get("NETWORKX_AUTOMATIC_BACKENDS", ""),
                )
            )
        )
        backend_priority.generators = _comma_sep_to_list(priorities.pop("generators", ""))
        for key in sorted(priorities):
            backend_priority[key] = _comma_sep_to_list(priorities[key])

        return config

    def _always_run(name, args, kwargs):
        return True

    def _load_backend(backend_name):
        if backend_name in _loaded_backends:
            return _loaded_backends[backend_name]
        if backend_name not in backends:
            raise ImportError(f"'{backend_name}' backend is not installed")
        rv = _loaded_backends[backend_name] = backends[backend_name].load()
        if not hasattr(rv, "can_run"):
            rv.can_run = _always_run
        if not hasattr(rv, "should_run"):
            rv.should_run = _always_run
        return rv

    class _dispatchable:
        _is_testing = False

        class _fallback_to_nx:
            """Class property that returns ``nx.config.fallback_to_nx``."""

            def __get__(self, instance, owner=None):
                warnings.warn(
                    "`_dispatchable._fallback_to_nx` is deprecated and will be removed "
                    "in NetworkX v3.5. Use `nx.config.fallback_to_nx` instead.",
                    category=DeprecationWarning,
                    stacklevel=2,
                )
                return nx.config.fallback_to_nx

        # Note that chaining `@classmethod` and `@property` was removed in Python 3.13
        _fallback_to_nx = _fallback_to_nx()  # type: ignore[assignment,misc]

        def __new__(
            cls,
            func=None,
            *,
            name=None,
            graphs="G",
            edge_attrs=None,
            node_attrs=None,
            preserve_edge_attrs=False,
            preserve_node_attrs=False,
            preserve_graph_attrs=False,
            preserve_all_attrs=False,
            mutates_input=False,
            returns_graph=False,
        ):
            """A decorator function that is used to redirect the execution of ``func``
            function to its backend implementation.

            This decorator function dispatches to
            a different backend implementation based on the input graph types, and it also
            manages all the ``backend_kwargs``. Usage can be any of the following decorator
            forms:

            - ``@_dispatchable``
            - ``@_dispatchable()``
            - ``@_dispatchable(name="override_name")``
            - ``@_dispatchable(graphs="graph_var_name")``
            - ``@_dispatchable(edge_attrs="weight")``
            - ``@_dispatchable(graphs={"G": 0, "H": 1}, edge_attrs={"weight": "default"})``
                with 0 and 1 giving the position in the signature function for graph
                objects. When ``edge_attrs`` is a dict, keys are keyword names and values
                are defaults.

            Parameters
            ----------
            func : callable, optional
                The function to be decorated. If ``func`` is not provided, returns a
                partial object that can be used to decorate a function later. If ``func``
                is provided, returns a new callable object that dispatches to a backend
                algorithm based on input graph types.

            name : str, optional
                The name of the algorithm to use for dispatching. If not provided,
                the name of ``func`` will be used. ``name`` is useful to avoid name
                conflicts, as all dispatched algorithms live in a single namespace.
                For example, ``tournament.is_strongly_connected`` had a name conflict
                with the standard ``nx.is_strongly_connected``, so we used
                ``@_dispatchable(name="tournament_is_strongly_connected")``.

            graphs : str or dict or None, default "G"
                If a string, the parameter name of the graph, which must be the first
                argument of the wrapped function. If more than one graph is required
                for the algorithm (or if the graph is not the first argument), provide
                a dict keyed to argument names with argument position as values for each
                graph argument. For example, ``@_dispatchable(graphs={"G": 0, "auxiliary?": 4})``
                indicates the 0th parameter ``G`` of the function is a required graph,
                and the 4th parameter ``auxiliary?`` is an optional graph.
                To indicate that an argument is a list of graphs, do ``"[graphs]"``.
                Use ``graphs=None``, if *no* arguments are NetworkX graphs such as for
                graph generators, readers, and conversion functions.

            edge_attrs : str or dict, optional
                ``edge_attrs`` holds information about edge attribute arguments
                and default values for those edge attributes.
                If a string, ``edge_attrs`` holds the function argument name that
                indicates a single edge attribute to include in the converted graph.
                The default value for this attribute is 1. To indicate that an argument
                is a list of attributes (all with default value 1), use e.g. ``"[attrs]"``.
                If a dict, ``edge_attrs`` holds a dict keyed by argument names, with
                values that are either the default value or, if a string, the argument
                name that indicates the default value.

            node_attrs : str or dict, optional
                Like ``edge_attrs``, but for node attributes.

            preserve_edge_attrs : bool or str or dict, optional
                For bool, whether to preserve all edge attributes.
                For str, the parameter name that may indicate (with ``True`` or a
                callable argument) whether all edge attributes should be preserved
                when converting.
                For dict of ``{graph_name: {attr: default}}``, indicate pre-determined
                edge attributes (and defaults) to preserve for input graphs.

            preserve_node_attrs : bool or str or dict, optional
                Like ``preserve_edge_attrs``, but for node attributes.

            preserve_graph_attrs : bool or set
                For bool, whether to preserve all graph attributes.
                For set, which input graph arguments to preserve graph attributes.

            preserve_all_attrs : bool
                Whether to preserve all edge, node and graph attributes.
                This overrides all the other preserve_*_attrs.

            mutates_input : bool or dict, default False
                For bool, whether the function mutates an input graph argument.
                For dict of ``{arg_name: arg_pos}``, arguments that indicate whether an
                input graph will be mutated, and ``arg_name`` may begin with ``"not "``
                to negate the logic (for example, this is used by ``copy=`` arguments).
                By default, dispatching doesn't convert input graphs to a different
                backend for functions that mutate input graphs.

            returns_graph : bool, default False
                Whether the function can return or yield a graph object. By default,
                dispatching doesn't convert input graphs to a different backend for
                functions that return graphs.
            """
            if func is None:
                return partial(
                    _dispatchable,
                    name=name,
                    graphs=graphs,
                    edge_attrs=edge_attrs,
                    node_attrs=node_attrs,
                    preserve_edge_attrs=preserve_edge_attrs,
                    preserve_node_attrs=preserve_node_attrs,
                    preserve_graph_attrs=preserve_graph_attrs,
                    preserve_all_attrs=preserve_all_attrs,
                    mutates_input=mutates_input,
                    returns_graph=returns_graph,
                )
            if isinstance(func, str):
                raise TypeError("'name' and 'graphs' must be passed by keyword") from None
            # If name not provided, use the name of the function
            if name is None:
                name = func.__name__

            self = object.__new__(cls)

            # standard function-wrapping stuff
            # __annotations__ not used
            self.__name__ = func.__name__
            # self.__doc__ = func.__doc__  # __doc__ handled as cached property
            self.__defaults__ = func.__defaults__
            # We "magically" add `backend=` keyword argument to allow backend to be specified
            if func.__kwdefaults__:
                self.__kwdefaults__ = {**func.__kwdefaults__, "backend": None}
            else:
                self.__kwdefaults__ = {"backend": None}
            self.__module__ = func.__module__
            self.__qualname__ = func.__qualname__
            self.__dict__.update(func.__dict__)
            self.__wrapped__ = func

            # Supplement docstring with backend info; compute and cache when needed
            self._orig_doc = func.__doc__
            self._cached_doc = None

            self.orig_func = func
            self.name = name
            self.edge_attrs = edge_attrs
            self.node_attrs = node_attrs
            self.preserve_edge_attrs = preserve_edge_attrs or preserve_all_attrs
            self.preserve_node_attrs = preserve_node_attrs or preserve_all_attrs
            self.preserve_graph_attrs = preserve_graph_attrs or preserve_all_attrs
            self.mutates_input = mutates_input
            # Keep `returns_graph` private for now, b/c we may extend info on return types
            self._returns_graph = returns_graph

            if edge_attrs is not None and not isinstance(edge_attrs, str | dict):
                raise TypeError(
                    f"Bad type for edge_attrs: {type(edge_attrs)}. Expected str or dict."
                ) from None
            if node_attrs is not None and not isinstance(node_attrs, str | dict):
                raise TypeError(
                    f"Bad type for node_attrs: {type(node_attrs)}. Expected str or dict."
                ) from None
            if not isinstance(self.preserve_edge_attrs, bool | str | dict):
                raise TypeError(
                    f"Bad type for preserve_edge_attrs: {type(self.preserve_edge_attrs)}."
                    " Expected bool, str, or dict."
                ) from None
            if not isinstance(self.preserve_node_attrs, bool | str | dict):
                raise TypeError(
                    f"Bad type for preserve_node_attrs: {type(self.preserve_node_attrs)}."
                    " Expected bool, str, or dict."
                ) from None
            if not isinstance(self.preserve_graph_attrs, bool | set):
                raise TypeError(
                    f"Bad type for preserve_graph_attrs: {type(self.preserve_graph_attrs)}."
                    " Expected bool or set."
                ) from None
            if not isinstance(self.mutates_input, bool | dict):
                raise TypeError(
                    f"Bad type for mutates_input: {type(self.mutates_input)}."
                    " Expected bool or dict."
                ) from None
            if not isinstance(self._returns_graph, bool):
                raise TypeError(
                    f"Bad type for returns_graph: {type(self._returns_graph)}."
                    " Expected bool."
                ) from None

            if isinstance(graphs, str):
                graphs = {graphs: 0}
            elif graphs is None:
                pass
            elif not isinstance(graphs, dict):
                raise TypeError(
                    f"Bad type for graphs: {type(graphs)}. Expected str or dict."
                ) from None
            elif len(graphs) == 0:
                raise KeyError("'graphs' must contain at least one variable name") from None

            # This dict comprehension is complicated for better performance; equivalent shown below.
            self.optional_graphs = set()
            self.list_graphs = set()
            if graphs is None:
                self.graphs = {}
            else:
                self.graphs = {
                    self.optional_graphs.add(val := k[:-1]) or val
                    if (last := k[-1]) == "?"
                    else self.list_graphs.add(val := k[1:-1]) or val
                    if last == "]"
                    else k: v
                    for k, v in graphs.items()
                }
            # The above is equivalent to:
            # self.optional_graphs = {k[:-1] for k in graphs if k[-1] == "?"}
            # self.list_graphs = {k[1:-1] for k in graphs if k[-1] == "]"}
            # self.graphs = {k[:-1] if k[-1] == "?" else k: v for k, v in graphs.items()}

            # Compute and cache the signature on-demand
            self._sig = None

            # Which backends implement this function?
            self.backends = {
                backend
                for backend, info in backend_info.items()
                if "functions" in info and name in info["functions"]
            }

            if name in _registered_algorithms:
                raise KeyError(
                    f"Algorithm already exists in dispatch registry: {name}"
                ) from None
            # Use the magic of `argmap` to turn `self` into a function. This does result
            # in small additional overhead compared to calling `_dispatchable` directly,
            # but `argmap` has the magical property that it can stack with other `argmap`
            # decorators "for free". Being a function is better for REPRs and type-checkers.
            self = argmap(_do_nothing)(self)
            _registered_algorithms[name] = self
            return self

        @property
        def __doc__(self):
            """If the cached documentation exists, it is returned.
            Otherwise, the documentation is generated using _make_doc() method,
            cached, and then returned."""

            if (rv := self._cached_doc) is not None:
                return rv
            rv = self._cached_doc = self._make_doc()
            return rv

        @__doc__.setter
        def __doc__(self, val):
            """Sets the original documentation to the given value and resets the
            cached documentation."""

            self._orig_doc = val
            self._cached_doc = None

        @property
        def __signature__(self):
            """Return the signature of the original function, with the addition of
            the `backend` and `backend_kwargs` parameters."""

            if self._sig is None:
                sig = inspect.signature(self.orig_func)
                # `backend` is now a reserved argument used by dispatching.
                # assert "backend" not in sig.parameters
                if not any(
                    p.kind == inspect.Parameter.VAR_KEYWORD for p in sig.parameters.values()
                ):
                    sig = sig.replace(
                        parameters=[
                            *sig.parameters.values(),
                            inspect.Parameter(
                                "backend", inspect.Parameter.KEYWORD_ONLY, default=None
                            ),
                            inspect.Parameter(
                                "backend_kwargs", inspect.Parameter.VAR_KEYWORD
                            ),
                        ]
                    )
                else:
                    *parameters, var_keyword = sig.parameters.values()
                    sig = sig.replace(
                        parameters=[
                            *parameters,
                            inspect.Parameter(
                                "backend", inspect.Parameter.KEYWORD_ONLY, default=None
                            ),
                            var_keyword,
                        ]
                    )
                self._sig = sig
            return self._sig

        def __call__(self, /, *args, backend=None, **kwargs):
            """Returns the result of the original function, or the backend function if
            the backend is specified and that backend implements `func`."""

            if not backends:
                # Fast path if no backends are installed
                if backend is not None and backend != "networkx":
                    raise ImportError(f"'{backend}' backend is not installed")
                return self.orig_func(*args, **kwargs)

            # Use `backend_name` in this function instead of `backend`.
            # This is purely for aesthetics and to make it easier to search for this
            # variable since "backend" is used in many comments and log/error messages.
            backend_name = backend
            if backend_name is not None and backend_name not in backend_info:
                raise ImportError(f"'{backend_name}' backend is not installed")

            graphs_resolved = {}
            for gname, pos in self.graphs.items():
                if pos < len(args):
                    if gname in kwargs:
                        raise TypeError(f"{self.name}() got multiple values for {gname!r}")
                    graph = args[pos]
                elif gname in kwargs:
                    graph = kwargs[gname]
                elif gname not in self.optional_graphs:
                    raise TypeError(
                        f"{self.name}() missing required graph argument: {gname}"
                    )
                else:
                    continue
                if graph is None:
                    if gname not in self.optional_graphs:
                        raise TypeError(
                            f"{self.name}() required graph argument {gname!r} is None; must be a graph"
                        )
                else:
                    graphs_resolved[gname] = graph

            # Alternative to the above that does not check duplicated args or missing required graphs.
            # graphs_resolved = {
            #     gname: graph
            #     for gname, pos in self.graphs.items()
            #     if (graph := args[pos] if pos < len(args) else kwargs.get(gname)) is not None
            # }

            # Check if any graph comes from a backend
            if self.list_graphs:
                # Make sure we don't lose values by consuming an iterator
                args = list(args)
                for gname in self.list_graphs & graphs_resolved.keys():
                    list_of_graphs = list(graphs_resolved[gname])
                    graphs_resolved[gname] = list_of_graphs
                    if gname in kwargs:
                        kwargs[gname] = list_of_graphs
                    else:
                        args[self.graphs[gname]] = list_of_graphs

                graph_backend_names = {
                    getattr(g, "__networkx_backend__", None)
                    for gname, g in graphs_resolved.items()
                    if gname not in self.list_graphs
                }
                for gname in self.list_graphs & graphs_resolved.keys():
                    graph_backend_names.update(
                        getattr(g, "__networkx_backend__", None)
                        for g in graphs_resolved[gname]
                    )
            else:
                graph_backend_names = {
                    getattr(g, "__networkx_backend__", None)
                    for g in graphs_resolved.values()
                }

            backend_priority = nx.config.backend_priority.get(
                self.name,
                nx.config.backend_priority.generators
                if self._returns_graph
                else nx.config.backend_priority.algos,
            )
            if self._is_testing and backend_priority and backend_name is None:
                # Special path if we are running networkx tests with a backend.
                # This even runs for (and handles) functions that mutate input graphs.
                return self._convert_and_call_for_tests(
                    backend_priority[0],
                    args,
                    kwargs,
                    fallback_to_nx=nx.config.fallback_to_nx,
                )

            graph_backend_names.discard(None)
            if backend_name is not None:
                # Must run with the given backend.
                # `can_run` only used for better log and error messages.
                # Check `mutates_input` for logging, not behavior.
                blurb = (
                    "No other backends will be attempted, because the backend was "
                    f"specified with the `backend='{backend_name}'` keyword argument."
                )
                extra_message = (
                    f"'{backend_name}' backend raised NotImplementedError when calling "
                    f"`{self.name}'. {blurb}"
                )
                if not graph_backend_names or graph_backend_names == {backend_name}:
                    # All graphs are backend graphs--no need to convert!
                    if self._can_backend_run(backend_name, args, kwargs):
                        return self._call_with_backend(
                            backend_name, args, kwargs, extra_message=extra_message
                        )
                    if self._does_backend_have(backend_name):
                        extra = " for the given arguments"
                    else:
                        extra = ""
                    raise NotImplementedError(
                        f"`{self.name}' is not implemented by '{backend_name}' backend"
                        f"{extra}. {blurb}"
                    )
                if self._can_convert(backend_name, graph_backend_names):
                    if self._can_backend_run(backend_name, args, kwargs):
                        if self._will_call_mutate_input(args, kwargs):
                            _logger.debug(
                                "`%s' will mutate an input graph. This prevents automatic conversion "
                                "to, and use of, backends listed in `nx.config.backend_priority`. "
                                "Using backend specified by the "
                                "`backend='%s'` keyword argument. This may change behavior by not "
                                "mutating inputs.",
                                self.name,
                                backend_name,
                            )
                            mutations = []
                        else:
                            mutations = None
                        rv = self._convert_and_call(
                            backend_name,
                            graph_backend_names,
                            args,
                            kwargs,
                            extra_message=extra_message,
                            mutations=mutations,
                        )
                        if mutations:
                            for cache, key in mutations:
                                # If the call mutates inputs, then remove all inputs gotten
                                # from cache. We do this after all conversions (and call) so
                                # that a graph can be gotten from a cache multiple times.
                                cache.pop(key, None)
                        return rv
                    if self._does_backend_have(backend_name):
                        extra = " for the given arguments"
                    else:
                        extra = ""
                    raise NotImplementedError(
                        f"`{self.name}' is not implemented by '{backend_name}' backend"
                        f"{extra}. {blurb}"
                    )
                if len(graph_backend_names) == 1:
                    maybe_s = ""
                    graph_backend_names = f"'{next(iter(graph_backend_names))}'"
                else:
                    maybe_s = "s"
                raise TypeError(
                    f"`{self.name}' is unable to convert graph from backend{maybe_s} "
                    f"{graph_backend_names} to '{backend_name}' backend, which was "
                    f"specified with the `backend='{backend_name}'` keyword argument. "
                    f"{blurb}"
                )

            if self._will_call_mutate_input(args, kwargs):
                # The current behavior for functions that mutate input graphs:
                #
                # 1. If backend is specified by `backend=` keyword, use it (done above).
                # 2. If inputs are from one backend, try to use it.
                # 3. If all input graphs are instances of `nx.Graph`, then run with the
                #    default "networkx" implementation.
                #
                # Do not automatically convert if a call will mutate inputs, because doing
                # so would change behavior. Hence, we should fail if there are multiple input
                # backends or if the input backend does not implement the function. However,
                # we offer a way for backends to circumvent this if they do not implement
                # this function: we will fall back to the default "networkx" implementation
                # without using conversions if all input graphs are subclasses of `nx.Graph`.
                blurb = (
                    "conversions between backends (if configured) will not be attempted, "
                    "because this may change behavior. You may specify a backend to use "
                    "by passing e.g. `backend='networkx'` keyword, but this may also "
                    "change behavior by not mutating inputs."
                )
                fallback_blurb = (
                    "This call will mutate inputs, so fall back to 'networkx' "
                    "backend (without converting) since all input graphs are "
                    "instances of nx.Graph and are hopefully compatible.",
                )
                if len(graph_backend_names) == 1:
                    [backend_name] = graph_backend_names
                    msg_template = (
                        f"Backend '{backend_name}' does not implement `{self.name}'%s. "
                        f"This call will mutate an input, so automatic {blurb}"
                    )
                    # `can_run` is only used for better log and error messages
                    try:
                        if self._can_backend_run(backend_name, args, kwargs):
                            return self._call_with_backend(
                                backend_name,
                                args,
                                kwargs,
                                extra_message=msg_template % " with these arguments",
                            )
                    except NotImplementedError as exc:
                        if all(isinstance(g, nx.Graph) for g in graphs_resolved.values()):
                            _logger.debug(
                                "Backend '%s' raised when calling `%s': %s. %s",
                                backend_name,
                                self.name,
                                exc,
                                fallback_blurb,
                            )
                        else:
                            raise
                    else:
                        if nx.config.fallback_to_nx and all(
                            # Consider dropping the `isinstance` check here to allow
                            # duck-type graphs, but let's wait for a backend to ask us.
                            isinstance(g, nx.Graph)
                            for g in graphs_resolved.values()
                        ):
                            # Log that we are falling back to networkx
                            _logger.debug(
                                "Backend '%s' can't run `%s'. %s",
                                backend_name,
                                self.name,
                                fallback_blurb,
                            )
                        else:
                            if self._does_backend_have(backend_name):
                                extra = " with these arguments"
                            else:
                                extra = ""
                            raise NotImplementedError(msg_template % extra)
                elif nx.config.fallback_to_nx and all(
                    # Consider dropping the `isinstance` check here to allow
                    # duck-type graphs, but let's wait for a backend to ask us.
                    isinstance(g, nx.Graph)
                    for g in graphs_resolved.values()
                ):
                    # Log that we are falling back to networkx
                    _logger.debug(
                        "`%s' was called with inputs from multiple backends: %s. %s",
                        self.name,
                        graph_backend_names,
                        fallback_blurb,
                    )
                else:
                    raise RuntimeError(
                        f"`{self.name}' will mutate an input, but it was called with inputs "
                        f"from multiple backends: {graph_backend_names}. Automatic {blurb}"
                    )
                # At this point, no backends are available to handle the call with
                # the input graph types, but if the input graphs are compatible
                # nx.Graph instances, fall back to networkx without converting.
                return self.orig_func(*args, **kwargs)

            # We may generalize fallback configuration as e.g. `nx.config.backend_fallback`
            if nx.config.fallback_to_nx or not graph_backend_names:
                # Use "networkx" by default if there are no inputs from backends.
                # For example, graph generators should probably return NetworkX graphs
                # instead of raising NotImplementedError.
                backend_fallback = ["networkx"]
            else:
                backend_fallback = []

            # ##########################
            # # How this behaves today #
            # ##########################
            #
            # The prose below describes the implementation and a *possible* way to
            # generalize "networkx" as "just another backend". The code is structured
            # to perhaps someday support backend-to-backend conversions (including
            # simply passing objects from one backend directly to another backend;
            # the dispatch machinery does not necessarily need to perform conversions),
            # but since backend-to-backend matching is not yet supported, the following
            # code is merely a convenient way to implement dispatch behaviors that have
            # been carefully developed since NetworkX 3.0 and to include falling back
            # to the default NetworkX implementation.
            #
            # The current behavior for functions that don't mutate input graphs:
            #
            # 1. If backend is specified by `backend=` keyword, use it (done above).
            # 2. If input is from a backend other than "networkx", try to use it.
            #    - Note: if present, "networkx" graphs will be converted to the backend.
            # 3. If input is from "networkx" (or no backend), try to use backends from
            #    `backend_priority` before running with the default "networkx" implementation.
            # 4. If configured, "fall back" and run with the default "networkx" implementation.
            #
            # ################################################
            # # How this is implemented and may work someday #
            # ################################################
            #
            # Let's determine the order of backends we should try according
            # to `backend_priority`, `backend_fallback`, and input backends.
            # There are two† dimensions of priorities to consider:
            #   backend_priority > unspecified > backend_fallback
            # and
            #   backend of an input > not a backend of an input
            # These are combined to form five groups of priorities as such:
            #
            #                    input   ~input
            #                  +-------+-------+
            # backend_priority |   1   |   2   |
            #      unspecified |   3   |  N/A  | (if only 1)
            # backend_fallback |   4   |   5   |
            #                  +-------+-------+
            #
            # This matches the behaviors we developed in versions 3.0 to 3.2, it
            # ought to cover virtually all use cases we expect, and I (@eriknw) don't
            # think it can be done any simpler (although it can be generalized further
            # and made to be more complicated to capture 100% of *possible* use cases).
            # Some observations:
            #
            #   1. If an input is in `backend_priority`, it will be used before trying a
            #      backend that is higher priority in `backend_priority` and not an input.
            #   2. To prioritize converting from one backend to another even if both implement
            #      a function, list one in `backend_priority` and one in `backend_fallback`.
            #   3. To disable conversions, set `backend_priority` and `backend_fallback` to [].
            #
            # †: There is actually a third dimension of priorities:
            #        should_run == True > should_run == False
            #    Backends with `can_run == True` and `should_run == False` are tried last.
            #
            seen = set()
            group1 = []  # In backend_priority, and an input
            group2 = []  # In backend_priority, but not an input
            for name in backend_priority:
                if name in seen:
                    continue
                seen.add(name)
                if name in graph_backend_names:
                    group1.append(name)
                else:
                    group2.append(name)
            group4 = []  # In backend_fallback, and an input
            group5 = []  # In backend_fallback, but not an input
            for name in backend_fallback:
                if name in seen:
                    continue
                seen.add(name)
                if name in graph_backend_names:
                    group4.append(name)
                else:
                    group5.append(name)
            # An input, but not in backend_priority or backend_fallback.
            group3 = graph_backend_names - seen
            if len(group3) > 1:
                # `group3` backends are not configured for automatic conversion or fallback.
                # There are at least two issues if this group contains multiple backends:
                #
                #   1. How should we prioritize them? We have no good way to break ties.
                #      Although we could arbitrarily choose alphabetical or left-most,
                #      let's follow the Zen of Python and refuse the temptation to guess.
                #   2. We probably shouldn't automatically convert to these backends,
                #      because we are not configured to do so.
                #
                # (2) is important to allow disabling all conversions by setting both
                # `nx.config.backend_priority` and `nx.config.backend_fallback` to [].
                #
                # If there is a single backend in `group3`, then giving it priority over
                # the fallback backends is what is generally expected. For example, this
                # allows input graphs of `backend_fallback` backends (such as "networkx")
                # to be converted to, and run with, the unspecified backend.
                _logger.debug(
                    "Call to `%s' has inputs from multiple backends, %s, that "
                    "have no priority set in `nx.config.backend_priority`, "
                    "so automatic conversions to "
                    "these backends will not be attempted.",
                    self.name,
                    group3,
                )
                group3 = ()

            try_order = list(itertools.chain(group1, group2, group3, group4, group5))
            if len(try_order) > 1:
                # Should we consider adding an option for more verbose logging?
                # For example, we could explain the order of `try_order` in detail.
                _logger.debug(
                    "Call to `%s' has inputs from %s backends, and will try to use "
                    "backends in the following order: %s",
                    self.name,
                    graph_backend_names or "no",
                    try_order,
                )
            backends_to_try_again = []
            for is_not_first, backend_name in enumerate(try_order):
                if is_not_first:
                    _logger.debug("Trying next backend: '%s'", backend_name)
                try:
                    if not graph_backend_names or graph_backend_names == {backend_name}:
                        if self._can_backend_run(backend_name, args, kwargs):
                            return self._call_with_backend(backend_name, args, kwargs)
                    elif self._can_convert(
                        backend_name, graph_backend_names
                    ) and self._can_backend_run(backend_name, args, kwargs):
                        if self._should_backend_run(backend_name, args, kwargs):
                            rv = self._convert_and_call(
                                backend_name, graph_backend_names, args, kwargs
                            )
                            if (
                                self._returns_graph
                                and graph_backend_names
                                and backend_name not in graph_backend_names
                            ):
                                # If the function has graph inputs and graph output, we try
                                # to make it so the backend of the return type will match the
                                # backend of the input types. In case this is not possible,
                                # let's tell the user that the backend of the return graph
                                # has changed. Perhaps we could try to convert back, but
                                # "fallback" backends for graph generators should typically
                                # be compatible with NetworkX graphs.
                                _logger.debug(
                                    "Call to `%s' is returning a graph from a different "
                                    "backend! It has inputs from %s backends, but ran with "
                                    "'%s' backend and is returning graph from '%s' backend",
                                    self.name,
                                    graph_backend_names,
                                    backend_name,
                                    backend_name,
                                )
                            return rv
                        # `should_run` is False, but `can_run` is True, so try again later
                        backends_to_try_again.append(backend_name)
                except NotImplementedError as exc:
                    _logger.debug(
                        "Backend '%s' raised when calling `%s': %s",
                        backend_name,
                        self.name,
                        exc,
                    )

            # We are about to fail. Let's try backends with can_run=True and should_run=False.
            # This is unlikely to help today since we try to run with "networkx" before this.
            for backend_name in backends_to_try_again:
                _logger.debug(
                    "Trying backend: '%s' (ignoring `should_run=False`)", backend_name
                )
                try:
                    rv = self._convert_and_call(
                        backend_name, graph_backend_names, args, kwargs
                    )
                    if (
                        self._returns_graph
                        and graph_backend_names
                        and backend_name not in graph_backend_names
                    ):
                        _logger.debug(
                            "Call to `%s' is returning a graph from a different "
                            "backend! It has inputs from %s backends, but ran with "
                            "'%s' backend and is returning graph from '%s' backend",
                            self.name,
                            graph_backend_names,
                            backend_name,
                            backend_name,
                        )
                    return rv
                except NotImplementedError as exc:
                    _logger.debug(
                        "Backend '%s' raised when calling `%s': %s",
                        backend_name,
                        self.name,
                        exc,
                    )
            # As a final effort, we could try to convert and run with `group3` backends
            # that we discarded when `len(group3) > 1`, but let's not consider doing
            # so until there is a reasonable request for it.

            if len(unspecified_backends := graph_backend_names - seen) > 1:
                raise TypeError(
                    f"Unable to convert inputs from {graph_backend_names} backends and "
                    f"run `{self.name}'. NetworkX is configured to automatically convert "
                    f"to {try_order} backends. To remedy this, you may enable automatic "
                    f"conversion to {unspecified_backends} backends by adding them to "
                    "`nx.config.backend_priority`, or you "
                    "may specify a backend to use with the `backend=` keyword argument."
                )
            raise NotImplementedError(
                f"`{self.name}' is not implemented by {try_order} backends. To remedy "
                "this, you may enable automatic conversion to more backends (including "
                "'networkx') by adding them to `nx.config.backend_priority`, "
                "or you may specify a backend to use with "
                "the `backend=` keyword argument."
            )

        def _will_call_mutate_input(self, args, kwargs):
            return (mutates_input := self.mutates_input) and (
                mutates_input is True
                or any(
                    # If `mutates_input` begins with "not ", then assume the argument is bool,
                    # otherwise treat it as a node or edge attribute if it's not None.
                    not (
                        args[arg_pos]
                        if len(args) > arg_pos
                        # This assumes that e.g. `copy=True` is the default
                        else kwargs.get(arg_name[4:], True)
                    )
                    if arg_name.startswith("not ")
                    else (args[arg_pos] if len(args) > arg_pos else kwargs.get(arg_name))
                    is not None
                    for arg_name, arg_pos in mutates_input.items()
                )
            )

        def _can_convert(self, backend_name, graph_backend_names):
            # Backend-to-backend conversion not supported yet.
            # We can only convert to and from networkx.
            rv = backend_name == "networkx" or graph_backend_names.issubset(
                {"networkx", backend_name}
            )
            if not rv:
                _logger.debug(
                    "Unable to convert from %s backends to '%s' backend",
                    graph_backend_names,
                    backend_name,
                )
            return rv

        def _does_backend_have(self, backend_name):
            """Does the specified backend have this algorithm?"""
            if backend_name == "networkx":
                return True
            # Inspect the backend; don't trust metadata used to create `self.backends`
            backend = _load_backend(backend_name)
            return hasattr(backend, self.name)

        def _can_backend_run(self, backend_name, args, kwargs):
            """Can the specified backend run this algorithm with these arguments?"""
            if backend_name == "networkx":
                return True
            backend = _load_backend(backend_name)
            # `backend.can_run` and `backend.should_run` may return strings that describe
            # why they can't or shouldn't be run.
            if not hasattr(backend, self.name):
                _logger.debug(
                    "Backend '%s' does not implement `%s'", backend_name, self.name
                )
                return False
            can_run = backend.can_run(self.name, args, kwargs)
            if isinstance(can_run, str) or not can_run:
                reason = f", because: {can_run}" if isinstance(can_run, str) else ""
                _logger.debug(
                    "Backend '%s' can't run `%s` with arguments: %s%s",
                    backend_name,
                    self.name,
                    _LazyArgsRepr(self, args, kwargs),
                    reason,
                )
                return False
            return True

        def _should_backend_run(self, backend_name, args, kwargs):
            """Should the specified backend run this algorithm with these arguments?

            Note that this does not check ``backend.can_run``.
            """
            # `backend.can_run` and `backend.should_run` may return strings that describe
            # why they can't or shouldn't be run.
            if backend_name == "networkx":
                return True
            backend = _load_backend(backend_name)
            should_run = backend.should_run(self.name, args, kwargs)
            if isinstance(should_run, str) or not should_run:
                reason = f", because: {should_run}" if isinstance(should_run, str) else ""
                _logger.debug(
                    "Backend '%s' shouldn't run `%s` with arguments: %s%s",
                    backend_name,
                    self.name,
                    _LazyArgsRepr(self, args, kwargs),
                    reason,
                )
                return False
            return True

        def _convert_arguments(self, backend_name, args, kwargs, *, use_cache, mutations):
            """Convert graph arguments to the specified backend.

            Returns
            -------
            args tuple and kwargs dict
            """
            bound = self.__signature__.bind(*args, **kwargs)
            bound.apply_defaults()
            if not self.graphs:
                bound_kwargs = bound.kwargs
                del bound_kwargs["backend"]
                return bound.args, bound_kwargs
            if backend_name == "networkx":
                # `backend_interface.convert_from_nx` preserves everything
                preserve_edge_attrs = preserve_node_attrs = preserve_graph_attrs = True
            else:
                preserve_edge_attrs = self.preserve_edge_attrs
                preserve_node_attrs = self.preserve_node_attrs
                preserve_graph_attrs = self.preserve_graph_attrs
                edge_attrs = self.edge_attrs
                node_attrs = self.node_attrs
            # Convert graphs into backend graph-like object
            # Include the edge and/or node labels if provided to the algorithm
            if preserve_edge_attrs is False:
                # e.g. `preserve_edge_attrs=False`
                pass
            elif preserve_edge_attrs is True:
                # e.g. `preserve_edge_attrs=True`
                edge_attrs = None
            elif isinstance(preserve_edge_attrs, str):
                if bound.arguments[preserve_edge_attrs] is True or callable(
                    bound.arguments[preserve_edge_attrs]
                ):
                    # e.g. `preserve_edge_attrs="attr"` and `func(attr=True)`
                    # e.g. `preserve_edge_attrs="attr"` and `func(attr=myfunc)`
                    preserve_edge_attrs = True
                    edge_attrs = None
                elif bound.arguments[preserve_edge_attrs] is False and (
                    isinstance(edge_attrs, str)
                    and edge_attrs == preserve_edge_attrs
                    or isinstance(edge_attrs, dict)
                    and preserve_edge_attrs in edge_attrs
                ):
                    # e.g. `preserve_edge_attrs="attr"` and `func(attr=False)`
                    # Treat `False` argument as meaning "preserve_edge_data=False"
                    # and not `False` as the edge attribute to use.
                    preserve_edge_attrs = False
                    edge_attrs = None
                else:
                    # e.g. `preserve_edge_attrs="attr"` and `func(attr="weight")`
                    preserve_edge_attrs = False
            # Else: e.g. `preserve_edge_attrs={"G": {"weight": 1}}`

            if edge_attrs is None:
                # May have been set to None above b/c all attributes are preserved
                pass
            elif isinstance(edge_attrs, str):
                if edge_attrs[0] == "[":
                    # e.g. `edge_attrs="[edge_attributes]"` (argument of list of attributes)
                    # e.g. `func(edge_attributes=["foo", "bar"])`
                    edge_attrs = {
                        edge_attr: 1 for edge_attr in bound.arguments[edge_attrs[1:-1]]
                    }
                elif callable(bound.arguments[edge_attrs]):
                    # e.g. `edge_attrs="weight"` and `func(weight=myfunc)`
                    preserve_edge_attrs = True
                    edge_attrs = None
                elif bound.arguments[edge_attrs] is not None:
                    # e.g. `edge_attrs="weight"` and `func(weight="foo")` (default of 1)
                    edge_attrs = {bound.arguments[edge_attrs]: 1}
                elif self.name == "to_numpy_array" and hasattr(
                    bound.arguments["dtype"], "names"
                ):
                    # Custom handling: attributes may be obtained from `dtype`
                    edge_attrs = {
                        edge_attr: 1 for edge_attr in bound.arguments["dtype"].names
                    }
                else:
                    # e.g. `edge_attrs="weight"` and `func(weight=None)`
                    edge_attrs = None
            else:
                # e.g. `edge_attrs={"attr": "default"}` and `func(attr="foo", default=7)`
                # e.g. `edge_attrs={"attr": 0}` and `func(attr="foo")`
                edge_attrs = {
                    edge_attr: bound.arguments.get(val, 1) if isinstance(val, str) else val
                    for key, val in edge_attrs.items()
                    if (edge_attr := bound.arguments[key]) is not None
                }

            if preserve_node_attrs is False:
                # e.g. `preserve_node_attrs=False`
                pass
            elif preserve_node_attrs is True:
                # e.g. `preserve_node_attrs=True`
                node_attrs = None
            elif isinstance(preserve_node_attrs, str):
                if bound.arguments[preserve_node_attrs] is True or callable(
                    bound.arguments[preserve_node_attrs]
                ):
                    # e.g. `preserve_node_attrs="attr"` and `func(attr=True)`
                    # e.g. `preserve_node_attrs="attr"` and `func(attr=myfunc)`
                    preserve_node_attrs = True
                    node_attrs = None
                elif bound.arguments[preserve_node_attrs] is False and (
                    isinstance(node_attrs, str)
                    and node_attrs == preserve_node_attrs
                    or isinstance(node_attrs, dict)
                    and preserve_node_attrs in node_attrs
                ):
                    # e.g. `preserve_node_attrs="attr"` and `func(attr=False)`
                    # Treat `False` argument as meaning "preserve_node_data=False"
                    # and not `False` as the node attribute to use. Is this used?
                    preserve_node_attrs = False
                    node_attrs = None
                else:
                    # e.g. `preserve_node_attrs="attr"` and `func(attr="weight")`
                    preserve_node_attrs = False
            # Else: e.g. `preserve_node_attrs={"G": {"pos": None}}`

            if node_attrs is None:
                # May have been set to None above b/c all attributes are preserved
                pass
            elif isinstance(node_attrs, str):
                if node_attrs[0] == "[":
                    # e.g. `node_attrs="[node_attributes]"` (argument of list of attributes)
                    # e.g. `func(node_attributes=["foo", "bar"])`
                    node_attrs = {
                        node_attr: None for node_attr in bound.arguments[node_attrs[1:-1]]
                    }
                elif callable(bound.arguments[node_attrs]):
                    # e.g. `node_attrs="weight"` and `func(weight=myfunc)`
                    preserve_node_attrs = True
                    node_attrs = None
                elif bound.arguments[node_attrs] is not None:
                    # e.g. `node_attrs="weight"` and `func(weight="foo")`
                    node_attrs = {bound.arguments[node_attrs]: None}
                else:
                    # e.g. `node_attrs="weight"` and `func(weight=None)`
                    node_attrs = None
            else:
                # e.g. `node_attrs={"attr": "default"}` and `func(attr="foo", default=7)`
                # e.g. `node_attrs={"attr": 0}` and `func(attr="foo")`
                node_attrs = {
                    node_attr: bound.arguments.get(val) if isinstance(val, str) else val
                    for key, val in node_attrs.items()
                    if (node_attr := bound.arguments[key]) is not None
                }

            # It should be safe to assume that we either have networkx graphs or backend graphs.
            # Future work: allow conversions between backends.
            for gname in self.graphs:
                if gname in self.list_graphs:
                    bound.arguments[gname] = [
                        self._convert_graph(
                            backend_name,
                            g,
                            edge_attrs=edge_attrs,
                            node_attrs=node_attrs,
                            preserve_edge_attrs=preserve_edge_attrs,
                            preserve_node_attrs=preserve_node_attrs,
                            preserve_graph_attrs=preserve_graph_attrs,
                            graph_name=gname,
                            use_cache=use_cache,
                            mutations=mutations,
                        )
                        if getattr(g, "__networkx_backend__", "networkx") != backend_name
                        else g
                        for g in bound.arguments[gname]
                    ]
                else:
                    graph = bound.arguments[gname]
                    if graph is None:
                        if gname in self.optional_graphs:
                            continue
                        raise TypeError(
                            f"Missing required graph argument `{gname}` in {self.name} function"
                        )
                    if isinstance(preserve_edge_attrs, dict):
                        preserve_edges = False
                        edges = preserve_edge_attrs.get(gname, edge_attrs)
                    else:
                        preserve_edges = preserve_edge_attrs
                        edges = edge_attrs
                    if isinstance(preserve_node_attrs, dict):
                        preserve_nodes = False
                        nodes = preserve_node_attrs.get(gname, node_attrs)
                    else:
                        preserve_nodes = preserve_node_attrs
                        nodes = node_attrs
                    if isinstance(preserve_graph_attrs, set):
                        preserve_graph = gname in preserve_graph_attrs
                    else:
                        preserve_graph = preserve_graph_attrs
                    if getattr(graph, "__networkx_backend__", "networkx") != backend_name:
                        bound.arguments[gname] = self._convert_graph(
                            backend_name,
                            graph,
                            edge_attrs=edges,
                            node_attrs=nodes,
                            preserve_edge_attrs=preserve_edges,
                            preserve_node_attrs=preserve_nodes,
                            preserve_graph_attrs=preserve_graph,
                            graph_name=gname,
                            use_cache=use_cache,
                            mutations=mutations,
                        )
            bound_kwargs = bound.kwargs
            del bound_kwargs["backend"]
            return bound.args, bound_kwargs

        def _convert_graph(
            self,
            backend_name,
            graph,
            *,
            edge_attrs,
            node_attrs,
            preserve_edge_attrs,
            preserve_node_attrs,
            preserve_graph_attrs,
            graph_name,
            use_cache,
            mutations,
        ):
            if (
                use_cache
                and (nx_cache := getattr(graph, "__networkx_cache__", None)) is not None
            ):
                cache = nx_cache.setdefault("backends", {}).setdefault(backend_name, {})
                key = _get_cache_key(
                    edge_attrs=edge_attrs,
                    node_attrs=node_attrs,
                    preserve_edge_attrs=preserve_edge_attrs,
                    preserve_node_attrs=preserve_node_attrs,
                    preserve_graph_attrs=preserve_graph_attrs,
                )
                compat_key, rv = _get_from_cache(cache, key, mutations=mutations)
                if rv is not None:
                    if "cache" not in nx.config.warnings_to_ignore:
                        warnings.warn(
                            "Note: conversions to backend graphs are saved to cache "
                            "(`G.__networkx_cache__` on the original graph) by default."
                            "\n\nThis warning means the cached graph is being used "
                            f"for the {backend_name!r} backend in the "
                            f"call to {self.name}.\n\nFor the cache to be consistent "
                            "(i.e., correct), the input graph must not have been "
                            "manually mutated since the cached graph was created. "
                            "Examples of manually mutating the graph data structures "
                            "resulting in an inconsistent cache include:\n\n"
                            "    >>> G[u][v][key] = val\n\n"
                            "and\n\n"
                            "    >>> for u, v, d in G.edges(data=True):\n"
                            "    ...     d[key] = val\n\n"
                            "Using methods such as `G.add_edge(u, v, weight=val)` "
                            "will correctly clear the cache to keep it consistent. "
                            "You may also use `G.__networkx_cache__.clear()` to "
                            "manually clear the cache, or set `G.__networkx_cache__` "
                            "to None to disable caching for G. Enable or disable caching "
                            "globally via `nx.config.cache_converted_graphs` config.\n\n"
                            "To disable this warning:\n\n"
                            '    >>> nx.config.warnings_to_ignore.add("cache")\n'
                        )
                    _logger.debug(
                        "Using cached converted graph (from '%s' to '%s' backend) "
                        "in call to `%s' for '%s' argument",
                        getattr(graph, "__networkx_backend__", None),
                        backend_name,
                        self.name,
                        graph_name,
                    )
                    return rv

            if backend_name == "networkx":
                # Perhaps we should check that "__networkx_backend__" attribute exists
                # and return the original object if not.
                if not hasattr(graph, "__networkx_backend__"):
                    _logger.debug(
                        "Unable to convert input to 'networkx' backend in call to `%s' for "
                        "'%s argument, because it is not from a backend (i.e., it does not "
                        "have `G.__networkx_backend__` attribute). Using the original "
                        "object: %s",
                        self.name,
                        graph_name,
                        graph,
                    )
                    # This may fail, but let it fail in the networkx function
                    return graph
                backend = _load_backend(graph.__networkx_backend__)
                rv = backend.convert_to_nx(graph)
            else:
                backend = _load_backend(backend_name)
                rv = backend.convert_from_nx(
                    graph,
                    edge_attrs=edge_attrs,
                    node_attrs=node_attrs,
                    preserve_edge_attrs=preserve_edge_attrs,
                    preserve_node_attrs=preserve_node_attrs,
                    # Always preserve graph attrs when we are caching b/c this should be
                    # cheap and may help prevent extra (unnecessary) conversions. Because
                    # we do this, we don't need `preserve_graph_attrs` in the cache key.
                    preserve_graph_attrs=preserve_graph_attrs or use_cache,
                    name=self.name,
                    graph_name=graph_name,
                )
            if use_cache and nx_cache is not None and mutations is None:
                _set_to_cache(cache, key, rv)
                _logger.debug(
                    "Caching converted graph (from '%s' to '%s' backend) "
                    "in call to `%s' for '%s' argument",
                    getattr(graph, "__networkx_backend__", None),
                    backend_name,
                    self.name,
                    graph_name,
                )

            return rv

        def _call_with_backend(self, backend_name, args, kwargs, *, extra_message=None):
            """Call this dispatchable function with a backend without converting inputs."""
            if backend_name == "networkx":
                return self.orig_func(*args, **kwargs)
            backend = _load_backend(backend_name)
            _logger.debug(
                "Using backend '%s' for call to `%s' with arguments: %s",
                backend_name,
                self.name,
                _LazyArgsRepr(self, args, kwargs),
            )
            try:
                return getattr(backend, self.name)(*args, **kwargs)
            except NotImplementedError as exc:
                if extra_message is not None:
                    _logger.debug(
                        "Backend '%s' raised when calling `%s': %s",
                        backend_name,
                        self.name,
                        exc,
                    )
                    raise NotImplementedError(extra_message) from exc
                raise

        def _convert_and_call(
            self,
            backend_name,
            input_backend_names,
            args,
            kwargs,
            *,
            extra_message=None,
            mutations=None,
        ):
            """Call this dispatchable function with a backend after converting inputs.

            Parameters
            ----------
            backend_name : str
            input_backend_names : set[str]
            args : arguments tuple
            kwargs : keywords dict
            extra_message : str, optional
                Additional message to log if NotImplementedError is raised by backend.
            mutations : list, optional
                Used to clear objects gotten from cache if inputs will be mutated.
            """
            if backend_name == "networkx":
                func = self.orig_func
            else:
                backend = _load_backend(backend_name)
                func = getattr(backend, self.name)
            other_backend_names = input_backend_names - {backend_name}
            _logger.debug(
                "Converting input graphs from %s backend%s to '%s' backend for call to `%s'",
                other_backend_names
                if len(other_backend_names) > 1
                else f"'{next(iter(other_backend_names))}'",
                "s" if len(other_backend_names) > 1 else "",
                backend_name,
                self.name,
            )
            try:
                converted_args, converted_kwargs = self._convert_arguments(
                    backend_name,
                    args,
                    kwargs,
                    use_cache=nx.config.cache_converted_graphs,
                    mutations=mutations,
                )
            except NotImplementedError as exc:
                # Only log the exception if we are adding an extra message
                # because we don't want to lose any information.
                _logger.debug(
                    "Failed to convert graphs from %s to '%s' backend for call to `%s'"
                    + ("" if extra_message is None else ": %s"),
                    input_backend_names,
                    backend_name,
                    self.name,
                    *(() if extra_message is None else (exc,)),
                )
                if extra_message is not None:
                    raise NotImplementedError(extra_message) from exc
                raise
            if backend_name != "networkx":
                _logger.debug(
                    "Using backend '%s' for call to `%s' with arguments: %s",
                    backend_name,
                    self.name,
                    _LazyArgsRepr(self, converted_args, converted_kwargs),
                )
            try:
                return func(*converted_args, **converted_kwargs)
            except NotImplementedError as exc:
                if extra_message is not None:
                    _logger.debug(
                        "Backend '%s' raised when calling `%s': %s",
                        backend_name,
                        self.name,
                        exc,
                    )
                    raise NotImplementedError(extra_message) from exc
                raise

        def _convert_and_call_for_tests(
            self, backend_name, args, kwargs, *, fallback_to_nx=False
        ):
            """Call this dispatchable function with a backend; for use with testing."""
            backend = _load_backend(backend_name)
            if not self._can_backend_run(backend_name, args, kwargs):
                if fallback_to_nx or not self.graphs:
                    if fallback_to_nx:
                        _logger.debug(
                            "Falling back to use 'networkx' instead of '%s' backend "
                            "for call to `%s' with arguments: %s",
                            backend_name,
                            self.name,
                            _LazyArgsRepr(self, args, kwargs),
                        )
                    return self.orig_func(*args, **kwargs)

                import pytest

                msg = f"'{self.name}' not implemented by {backend_name}"
                if hasattr(backend, self.name):
                    msg += " with the given arguments"
                pytest.xfail(msg)

            from collections.abc import Iterable, Iterator, Mapping
            from copy import copy, deepcopy
            from io import BufferedReader, BytesIO, StringIO, TextIOWrapper
            from itertools import tee
            from random import Random

            import numpy as np
            from numpy.random import Generator, RandomState
            from scipy.sparse import sparray

            # We sometimes compare the backend result to the original result,
            # so we need two sets of arguments. We tee iterators and copy
            # random state so that they may be used twice.
            if not args:
                args1 = args2 = args
            else:
                args1, args2 = zip(
                    *(
                        (arg, deepcopy(arg))
                        if isinstance(arg, RandomState)
                        else (arg, copy(arg))
                        if isinstance(arg, BytesIO | StringIO | Random | Generator)
                        else tee(arg)
                        if isinstance(arg, Iterator)
                        and not isinstance(arg, BufferedReader | TextIOWrapper)
                        else (arg, arg)
                        for arg in args
                    )
                )
            if not kwargs:
                kwargs1 = kwargs2 = kwargs
            else:
                kwargs1, kwargs2 = zip(
                    *(
                        ((k, v), (k, deepcopy(v)))
                        if isinstance(v, RandomState)
                        else ((k, v), (k, copy(v)))
                        if isinstance(v, BytesIO | StringIO | Random | Generator)
                        else ((k, (teed := tee(v))[0]), (k, teed[1]))
                        if isinstance(v, Iterator)
                        and not isinstance(v, BufferedReader | TextIOWrapper)
                        else ((k, v), (k, v))
                        for k, v in kwargs.items()
                    )
                )
                kwargs1 = dict(kwargs1)
                kwargs2 = dict(kwargs2)
            try:
                converted_args, converted_kwargs = self._convert_arguments(
                    backend_name, args1, kwargs1, use_cache=False, mutations=None
                )
                _logger.debug(
                    "Using backend '%s' for call to `%s' with arguments: %s",
                    backend_name,
                    self.name,
                    _LazyArgsRepr(self, converted_args, converted_kwargs),
                )
                result = getattr(backend, self.name)(*converted_args, **converted_kwargs)
            except NotImplementedError as exc:
                if fallback_to_nx:
                    _logger.debug(
                        "Graph conversion failed; falling back to use 'networkx' instead "
                        "of '%s' backend for call to `%s'",
                        backend_name,
                        self.name,
                    )
                    return self.orig_func(*args2, **kwargs2)
                import pytest

                pytest.xfail(
                    exc.args[0] if exc.args else f"{self.name} raised {type(exc).__name__}"
                )
            # Verify that `self._returns_graph` is correct. This compares the return type
            # to the type expected from `self._returns_graph`. This handles tuple and list
            # return types, but *does not* catch functions that yield graphs.
            if (
                self._returns_graph
                != (
                    isinstance(result, nx.Graph)
                    or hasattr(result, "__networkx_backend__")
                    or isinstance(result, tuple | list)
                    and any(
                        isinstance(x, nx.Graph) or hasattr(x, "__networkx_backend__")
                        for x in result
                    )
                )
                and not (
                    # May return Graph or None
                    self.name in {"check_planarity", "check_planarity_recursive"}
                    and any(x is None for x in result)
                )
                and not (
                    # May return Graph or dict
                    self.name in {"held_karp_ascent"}
                    and any(isinstance(x, dict) for x in result)
                )
                and self.name
                not in {
                    # yields graphs
                    "all_triads",
                    "general_k_edge_subgraphs",
                    # yields graphs or arrays
                    "nonisomorphic_trees",
                }
            ):
                raise RuntimeError(f"`returns_graph` is incorrect for {self.name}")

            def check_result(val, depth=0):
                if isinstance(val, np.number):
                    raise RuntimeError(
                        f"{self.name} returned a numpy scalar {val} ({type(val)}, depth={depth})"
                    )
                if isinstance(val, np.ndarray | sparray):
                    return
                if isinstance(val, nx.Graph):
                    check_result(val._node, depth=depth + 1)
                    check_result(val._adj, depth=depth + 1)
                    return
                if isinstance(val, Iterator):
                    raise NotImplementedError
                if isinstance(val, Iterable) and not isinstance(val, str):
                    for x in val:
                        check_result(x, depth=depth + 1)
                if isinstance(val, Mapping):
                    for x in val.values():
                        check_result(x, depth=depth + 1)

            def check_iterator(it):
                for val in it:
                    try:
                        check_result(val)
                    except RuntimeError as exc:
                        raise RuntimeError(
                            f"{self.name} returned a numpy scalar {val} ({type(val)})"
                        ) from exc
                    yield val

            if self.name in {"from_edgelist"}:
                # numpy scalars are explicitly given as values in some tests
                pass
            elif isinstance(result, Iterator):
                result = check_iterator(result)
            else:
                try:
                    check_result(result)
                except RuntimeError as exc:
                    raise RuntimeError(
                        f"{self.name} returned a numpy scalar {result} ({type(result)})"
                    ) from exc
                check_result(result)

            if self.name in {
                "edmonds_karp",
                "barycenter",
                "contracted_edge",
                "contracted_nodes",
                "stochastic_graph",
                "relabel_nodes",
                "maximum_branching",
                "incremental_closeness_centrality",
                "minimal_branching",
                "minimum_spanning_arborescence",
                "recursive_simple_cycles",
                "connected_double_edge_swap",
            }:
                # Special-case algorithms that mutate input graphs
                bound = self.__signature__.bind(*converted_args, **converted_kwargs)
                bound.apply_defaults()
                bound2 = self.__signature__.bind(*args2, **kwargs2)
                bound2.apply_defaults()
                if self.name in {
                    "minimal_branching",
                    "minimum_spanning_arborescence",
                    "recursive_simple_cycles",
                    "connected_double_edge_swap",
                }:
                    G1 = backend.convert_to_nx(bound.arguments["G"])
                    G2 = bound2.arguments["G"]
                    G2._adj = G1._adj
                    if G2.is_directed():
                        G2._pred = G1._pred
                    nx._clear_cache(G2)
                elif self.name == "edmonds_karp":
                    R1 = backend.convert_to_nx(bound.arguments["residual"])
                    R2 = bound2.arguments["residual"]
                    if R1 is not None and R2 is not None:
                        for k, v in R1.edges.items():
                            R2.edges[k]["flow"] = v["flow"]
                        R2.graph.update(R1.graph)
                        nx._clear_cache(R2)
                elif self.name == "barycenter" and bound.arguments["attr"] is not None:
                    G1 = backend.convert_to_nx(bound.arguments["G"])
                    G2 = bound2.arguments["G"]
                    attr = bound.arguments["attr"]
                    for k, v in G1.nodes.items():
                        G2.nodes[k][attr] = v[attr]
                    nx._clear_cache(G2)
                elif (
                    self.name in {"contracted_nodes", "contracted_edge"}
                    and not bound.arguments["copy"]
                ):
                    # Edges and nodes changed; node "contraction" and edge "weight" attrs
                    G1 = backend.convert_to_nx(bound.arguments["G"])
                    G2 = bound2.arguments["G"]
                    G2.__dict__.update(G1.__dict__)
                    nx._clear_cache(G2)
                elif self.name == "stochastic_graph" and not bound.arguments["copy"]:
                    G1 = backend.convert_to_nx(bound.arguments["G"])
                    G2 = bound2.arguments["G"]
                    for k, v in G1.edges.items():
                        G2.edges[k]["weight"] = v["weight"]
                    nx._clear_cache(G2)
                elif (
                    self.name == "relabel_nodes"
                    and not bound.arguments["copy"]
                    or self.name in {"incremental_closeness_centrality"}
                ):
                    G1 = backend.convert_to_nx(bound.arguments["G"])
                    G2 = bound2.arguments["G"]
                    if G1 is G2:
                        return G2
                    G2._node.clear()
                    G2._node.update(G1._node)
                    G2._adj.clear()
                    G2._adj.update(G1._adj)
                    if hasattr(G1, "_pred") and hasattr(G2, "_pred"):
                        G2._pred.clear()
                        G2._pred.update(G1._pred)
                    if hasattr(G1, "_succ") and hasattr(G2, "_succ"):
                        G2._succ.clear()
                        G2._succ.update(G1._succ)
                    nx._clear_cache(G2)
                    if self.name == "relabel_nodes":
                        return G2
                return backend.convert_to_nx(result)

            converted_result = backend.convert_to_nx(result)
            if isinstance(converted_result, nx.Graph) and self.name not in {
                "boykov_kolmogorov",
                "preflow_push",
                "quotient_graph",
                "shortest_augmenting_path",
                "spectral_graph_forge",
                # We don't handle tempfile.NamedTemporaryFile arguments
                "read_gml",
                "read_graph6",
                "read_sparse6",
                # We don't handle io.BufferedReader or io.TextIOWrapper arguments
                "bipartite_read_edgelist",
                "read_adjlist",
                "read_edgelist",
                "read_graphml",
                "read_multiline_adjlist",
                "read_pajek",
                "from_pydot",
                "pydot_read_dot",
                "agraph_read_dot",
                # graph comparison fails b/c of nan values
                "read_gexf",
            }:
                # For graph return types (e.g. generators), we compare that results are
                # the same between the backend and networkx, then return the original
                # networkx result so the iteration order will be consistent in tests.
                G = self.orig_func(*args2, **kwargs2)
                if not nx.utils.graphs_equal(G, converted_result):
                    assert G.number_of_nodes() == converted_result.number_of_nodes()
                    assert G.number_of_edges() == converted_result.number_of_edges()
                    assert G.graph == converted_result.graph
                    assert G.nodes == converted_result.nodes
                    assert G.adj == converted_result.adj
                    assert type(G) is type(converted_result)
                    raise AssertionError("Graphs are not equal")
                return G
            return converted_result

        def _make_doc(self):
            """Generate the backends section at the end for functions having an alternate
            backend implementation(s) using the `backend_info` entry-point."""

            if not self.backends:
                return self._orig_doc
            lines = [
                "Backends",
                "--------",
            ]
            for backend in sorted(self.backends):
                info = backend_info[backend]
                if "short_summary" in info:
                    lines.append(f"{backend} : {info['short_summary']}")
                else:
                    lines.append(backend)
                if "functions" not in info or self.name not in info["functions"]:
                    lines.append("")
                    continue

                func_info = info["functions"][self.name]

                # Renaming extra_docstring to additional_docs
                if func_docs := (
                    func_info.get("additional_docs") or func_info.get("extra_docstring")
                ):
                    lines.extend(
                        f"  {line}" if line else line for line in func_docs.split("\n")
                    )
                    add_gap = True
                else:
                    add_gap = False

                # Renaming extra_parameters to additional_parameters
                if extra_parameters := (
                    func_info.get("extra_parameters")
                    or func_info.get("additional_parameters")
                ):
                    if add_gap:
                        lines.append("")
                    lines.append("  Additional parameters:")
                    for param in sorted(extra_parameters):
                        lines.append(f"    {param}")
                        if desc := extra_parameters[param]:
                            lines.append(f"      {desc}")
                        lines.append("")
                else:
                    lines.append("")

                if func_url := func_info.get("url"):
                    lines.append(f"[`Source <{func_url}>`_]")
                    lines.append("")

            lines.pop()  # Remove last empty line
            to_add = "\n    ".join(lines)
            if not self._orig_doc:
                return f"The original docstring for {self.name} was empty.\n\n    {to_add}"
            return f"{self._orig_doc.rstrip()}\n\n    {to_add}"

        def __reduce__(self):
            """Allow this object to be serialized with pickle.

            This uses the global registry `_registered_algorithms` to deserialize.
            """
            return _restore_dispatchable, (self.name,)

    def _restore_dispatchable(name):
        return _registered_algorithms[name].__wrapped__

    def _get_cache_key(
        *,
        edge_attrs,
        node_attrs,
        preserve_edge_attrs,
        preserve_node_attrs,
        preserve_graph_attrs,
    ):
        """Return key used by networkx caching given arguments for ``convert_from_nx``."""
        # edge_attrs: dict | None
        # node_attrs: dict | None
        # preserve_edge_attrs: bool (False if edge_attrs is not None)
        # preserve_node_attrs: bool (False if node_attrs is not None)
        return (
            frozenset(edge_attrs.items())
            if edge_attrs is not None
            else preserve_edge_attrs,
            frozenset(node_attrs.items())
            if node_attrs is not None
            else preserve_node_attrs,
        )

    def _get_from_cache(cache, key, *, backend_name=None, mutations=None):
        """Search the networkx cache for a graph that is compatible with ``key``.

        Parameters
        ----------
        cache : dict
            If ``backend_name`` is given, then this is treated as ``G.__networkx_cache__``,
            but if ``backend_name`` is None, then this is treated as the resolved inner
            cache such as ``G.__networkx_cache__["backends"][backend_name]``.
        key : tuple
            Cache key from ``_get_cache_key``.
        backend_name : str, optional
            Name of the backend to control how ``cache`` is interpreted.
        mutations : list, optional
            Used internally to clear objects gotten from cache if inputs will be mutated.

        Returns
        -------
        tuple or None
            The key of the compatible graph found in the cache.
        graph or None
            A compatible graph or None.
        """
        if backend_name is not None:
            cache = cache.get("backends", {}).get(backend_name, {})
        if not cache:
            return None, None

        # Do a simple search for a cached graph with compatible data.
        # For example, if we need a single attribute, then it's okay
        # to use a cached graph that preserved all attributes.
        # This looks for an exact match first.
        edge_key, node_key = key
        for compat_key in itertools.product(
            (edge_key, True) if edge_key is not True else (True,),
            (node_key, True) if node_key is not True else (True,),
        ):
            if (rv := cache.get(compat_key)) is not None:
                if mutations is not None:
                    # Remove this item from the cache (after all conversions) if
                    # the call to this dispatchable function will mutate an input.
                    mutations.append((cache, compat_key))
                return compat_key, rv
        if edge_key is not True and node_key is not True:
            # Iterate over the items in `cache` to see if any are compatible.
            # For example, if no edge attributes are needed, then a graph
            # with any edge attribute will suffice. We use the same logic
            # below (but switched) to clear unnecessary items from the cache.
            # Use `list(cache.items())` to be thread-safe.
            for (ekey, nkey), graph in list(cache.items()):
                if edge_key is False or ekey is True:
                    pass  # Cache works for edge data!
                elif edge_key is True or ekey is False or not edge_key.issubset(ekey):
                    continue  # Cache missing required edge data; does not work
                if node_key is False or nkey is True:
                    pass  # Cache works for node data!
                elif node_key is True or nkey is False or not node_key.issubset(nkey):
                    continue  # Cache missing required node data; does not work
                if mutations is not None:
                    # Remove this item from the cache (after all conversions) if
                    # the call to this dispatchable function will mutate an input.
                    mutations.append((cache, (ekey, nkey)))
                return (ekey, nkey), graph
        return None, None

    def _set_to_cache(cache, key, graph, *, backend_name=None):
        """Set a backend graph to the cache, and remove unnecessary cached items.

        Parameters
        ----------
        cache : dict
            If ``backend_name`` is given, then this is treated as ``G.__networkx_cache__``,
            but if ``backend_name`` is None, then this is treated as the resolved inner
            cache such as ``G.__networkx_cache__["backends"][backend_name]``.
        key : tuple
            Cache key from ``_get_cache_key``.
        graph : graph
        backend_name : str, optional
            Name of the backend to control how ``cache`` is interpreted.

        Returns
        -------
        dict
            The items that were removed from the cache.
        """
        if backend_name is not None:
            cache = cache.setdefault("backends", {}).setdefault(backend_name, {})
        # Remove old cached items that are no longer necessary since they
        # are dominated/subsumed/outdated by what was just calculated.
        # This uses the same logic as above, but with keys switched.
        # Also, don't update the cache here if the call will mutate an input.
        removed = {}
        edge_key, node_key = key
        cache[key] = graph  # Set at beginning to be thread-safe
        for cur_key in list(cache):
            if cur_key == key:
                continue
            ekey, nkey = cur_key
            if ekey is False or edge_key is True:
                pass
            elif ekey is True or edge_key is False or not ekey.issubset(edge_key):
                continue
            if nkey is False or node_key is True:
                pass
            elif nkey is True or node_key is False or not nkey.issubset(node_key):
                continue
            # Use pop instead of del to try to be thread-safe
            if (graph := cache.pop(cur_key, None)) is not None:
                removed[cur_key] = graph
        return removed

    class _LazyArgsRepr:
        """Simple wrapper to display arguments of dispatchable functions in logging calls."""

        def __init__(self, func, args, kwargs):
            self.func = func
            self.args = args
            self.kwargs = kwargs
            self.value = None

        def __repr__(self):
            if self.value is None:
                bound = self.func.__signature__.bind_partial(*self.args, **self.kwargs)
                inner = ", ".join(f"{key}={val!r}" for key, val in bound.arguments.items())
                self.value = f"({inner})"
            return self.value

    if os.environ.get("_NETWORKX_BUILDING_DOCS_"):
        # When building docs with Sphinx, use the original function with the
        # dispatched __doc__, b/c Sphinx renders normal Python functions better.
        # This doesn't show e.g. `*, backend=None, **backend_kwargs` in the
        # signatures, which is probably okay. It does allow the docstring to be
        # updated based on the installed backends.
        _orig_dispatchable = _dispatchable

        def _dispatchable(func=None, **kwargs):  # type: ignore[no-redef]
            if func is None:
                return partial(_dispatchable, **kwargs)
            dispatched_func = _orig_dispatchable(func, **kwargs)
            func.__doc__ = dispatched_func.__doc__
            return func

        _dispatchable.__doc__ = _orig_dispatchable.__new__.__doc__  # type: ignore[method-assign,assignment]
        _sig = inspect.signature(_orig_dispatchable.__new__)
        _dispatchable.__signature__ = _sig.replace(  # type: ignore[method-assign,assignment]
            parameters=[v for k, v in _sig.parameters.items() if k != "cls"]
        )