Repository: networkx/networkx

Issue:
`strategy_saturation_largest_first` endless generator
<!-- If you have a general question about NetworkX, please use the discussions tab to create a new discussion -->

<!--- Provide a general summary of the issue in the Title above -->

### Current Behavior

`strategy_saturation_largest_first` generator does not terminate. See the stopping condition here:
https://github.com/networkx/networkx/blob/9cc8b422a512e7e7819238d597fd6815ec9c1c8e/networkx/algorithms/coloring/greedy_coloring.py#L243

but neither `G` nor `colors` is updated within the loop! The result is the same `node` is yielded repeatedly.

### Expected Behavior

I would expect the generator to terminate. I don't grok this function, but endless generator doesn't seem right.

### Steps to Reproduce

```python
import networkx as nx

G = nx.empty_graph()
G.add_node(1)
list(nx.algorithms.coloring.greedy_coloring.strategy_saturation_largest_first(G, {}))
```

### Environment

Python version: 3.10
NetworkX version: dev

### Additional context

I (of course) encountered this while tinkering with dispatching machinery!

Discussion:

Patch:
diff --git a/examples/geospatial/delaunay.py b/examples/geospatial/plot_delaunay.py
similarity index 96%
rename from examples/geospatial/delaunay.py
rename to examples/geospatial/plot_delaunay.py
index edafe0635..799381fff 100644
--- a/examples/geospatial/delaunay.py
+++ b/examples/geospatial/plot_delaunay.py
@@ -58,7 +58,11 @@ positions = dict(zip(delaunay_graph.nodes, coordinates))
 
 # Now, we can plot with a nice basemap.
 ax = cells.plot(facecolor="lightblue", alpha=0.50, edgecolor="cornsilk", linewidth=2)
-add_basemap(ax)
+try:  # Try-except for issues with timeout/parsing failures in CI
+    add_basemap(ax)
+except:
+    pass
+
 ax.axis("off")
 nx.draw(
     delaunay_graph,
diff --git a/examples/geospatial/lines.py b/examples/geospatial/plot_lines.py
similarity index 94%
rename from examples/geospatial/lines.py
rename to examples/geospatial/plot_lines.py
index 616db3743..3de10223b 100644
--- a/examples/geospatial/lines.py
+++ b/examples/geospatial/plot_lines.py
@@ -76,7 +76,10 @@ streets.plot(color="k", ax=ax[0])
 for i, facet in enumerate(ax):
     facet.set_title(("Streets", "Graph")[i])
     facet.axis("off")
-    add_basemap(facet)
+    try:  # For issues with downloading/parsing in CI
+        add_basemap(facet)
+    except:
+        pass
 nx.draw(
     G_primal, {n: [n[0], n[1]] for n in list(G_primal.nodes)}, ax=ax[1], node_size=50
 )
@@ -92,7 +95,10 @@ streets.plot(color="k", ax=ax[0])
 for i, facet in enumerate(ax):
     facet.set_title(("Streets", "Graph")[i])
     facet.axis("off")
-    add_basemap(facet)
+    try:  # For issues with downloading/parsing in CI
+        add_basemap(facet)
+    except:
+        pass
 nx.draw(G_dual, {n: [n[0], n[1]] for n in list(G_dual.nodes)}, ax=ax[1], node_size=50)
 plt.show()
 
diff --git a/examples/geospatial/plot_points.py b/examples/geospatial/plot_points.py
index 7d9d99df8..7517069ca 100644
--- a/examples/geospatial/plot_points.py
+++ b/examples/geospatial/plot_points.py
@@ -51,7 +51,10 @@ positions = dict(zip(knn_graph.nodes, coordinates))
 f, ax = plt.subplots(1, 2, figsize=(8, 4))
 for i, facet in enumerate(ax):
     cases.plot(marker=".", color="orangered", ax=facet)
-    add_basemap(facet)
+    try:  # For issues with downloading/parsing basemaps in CI
+        add_basemap(facet)
+    except:
+        pass
     facet.set_title(("KNN-3", "50-meter Distance Band")[i])
     facet.axis("off")
 nx.draw(knn_graph, positions, ax=ax[0], node_size=5, node_color="b")
diff --git a/networkx/algorithms/coloring/greedy_coloring.py b/networkx/algorithms/coloring/greedy_coloring.py
index 661f14e01..61bc95367 100644
--- a/networkx/algorithms/coloring/greedy_coloring.py
+++ b/networkx/algorithms/coloring/greedy_coloring.py
@@ -20,7 +20,6 @@ __all__ = [
 ]
 
 
-@nx._dispatchable
 def strategy_largest_first(G, colors):
     """Returns a list of the nodes of ``G`` in decreasing order by
     degree.
@@ -32,7 +31,6 @@ def strategy_largest_first(G, colors):
 
 
 @py_random_state(2)
-@nx._dispatchable
 def strategy_random_sequential(G, colors, seed=None):
     """Returns a random permutation of the nodes of ``G`` as a list.
 
@@ -47,7 +45,6 @@ def strategy_random_sequential(G, colors, seed=None):
     return nodes
 
 
-@nx._dispatchable
 def strategy_smallest_last(G, colors):
     """Returns a deque of the nodes of ``G``, "smallest" last.
 
@@ -121,7 +118,6 @@ def _maximal_independent_set(G):
     return result
 
 
-@nx._dispatchable
 def strategy_independent_set(G, colors):
     """Uses a greedy independent set removal strategy to determine the
     colors.
@@ -146,7 +142,6 @@ def strategy_independent_set(G, colors):
         yield from nodes
 
 
-@nx._dispatchable
 def strategy_connected_sequential_bfs(G, colors):
     """Returns an iterable over nodes in ``G`` in the order given by a
     breadth-first traversal.
@@ -160,7 +155,6 @@ def strategy_connected_sequential_bfs(G, colors):
     return strategy_connected_sequential(G, colors, "bfs")
 
 
-@nx._dispatchable
 def strategy_connected_sequential_dfs(G, colors):
     """Returns an iterable over nodes in ``G`` in the order given by a
     depth-first traversal.
@@ -174,7 +168,6 @@ def strategy_connected_sequential_dfs(G, colors):
     return strategy_connected_sequential(G, colors, "dfs")
 
 
-@nx._dispatchable
 def strategy_connected_sequential(G, colors, traversal="bfs"):
     """Returns an iterable over nodes in ``G`` in the order given by a
     breadth-first or depth-first traversal.
@@ -207,7 +200,6 @@ def strategy_connected_sequential(G, colors, traversal="bfs"):
             yield end
 
 
-@nx._dispatchable
 def strategy_saturation_largest_first(G, colors):
     """Iterates over all the nodes of ``G`` in "saturation order" (also
     known as "DSATUR").
diff --git a/networkx/algorithms/similarity.py b/networkx/algorithms/similarity.py
index 765849984..24f303b13 100644
--- a/networkx/algorithms/similarity.py
+++ b/networkx/algorithms/similarity.py
@@ -20,6 +20,7 @@ from dataclasses import dataclass
 from itertools import product
 
 import networkx as nx
+from networkx.utils import np_random_state
 
 __all__ = [
     "graph_edit_distance",
@@ -1662,9 +1663,10 @@ def panther_similarity(
     return top_k_with_val
 
 
+@np_random_state(5)
 @nx._dispatchable(edge_attrs="weight")
 def generate_random_paths(
-    G, sample_size, path_length=5, index_map=None, weight="weight"
+    G, sample_size, path_length=5, index_map=None, weight="weight", seed=None
 ):
     """Randomly generate `sample_size` paths of length `path_length`.
 
@@ -1685,6 +1687,9 @@ def generate_random_paths(
     weight : string or None, optional (default="weight")
         The name of an edge attribute that holds the numerical value
         used as a weight. If None then each edge has weight 1.
+    seed : integer, random_state, or None (default)
+        Indicator of random number generation state.
+        See :ref:`Randomness<randomness>`.
 
     Returns
     -------
@@ -1718,6 +1723,10 @@ def generate_random_paths(
     """
     import numpy as np
 
+    randint_fn = (
+        seed.integers if isinstance(seed, np.random.Generator) else seed.randint
+    )
+
     # Calculate transition probabilities between
     # every pair of vertices according to Eq. (3)
     adj_mat = nx.to_numpy_array(G, weight=weight)
@@ -1729,7 +1738,7 @@ def generate_random_paths(
 
     for path_index in range(sample_size):
         # Sample current vertex v = v_i uniformly at random
-        node_index = np.random.randint(0, high=num_nodes)
+        node_index = randint_fn(num_nodes)
         node = node_map[node_index]
 
         # Add v into p_r and add p_r into the path set
@@ -1747,7 +1756,7 @@ def generate_random_paths(
         for _ in range(path_length):
             # Randomly sample a neighbor (v_j) according
             # to transition probabilities from ``node`` (v) to its neighbors
-            nbr_index = np.random.choice(
+            nbr_index = seed.choice(
                 num_nodes, p=transition_probabilities[starting_index]
             )
 
diff --git a/networkx/generators/__init__.py b/networkx/generators/__init__.py
index 7a1adc42a..324d82b7e 100644
--- a/networkx/generators/__init__.py
+++ b/networkx/generators/__init__.py
@@ -12,6 +12,7 @@ from networkx.generators.duplication import *
 from networkx.generators.ego import *
 from networkx.generators.expanders import *
 from networkx.generators.geometric import *
+from networkx.generators.harary_graph import *
 from networkx.generators.internet_as_graphs import *
 from networkx.generators.intersection import *
 from networkx.generators.interval_graph import *
diff --git a/networkx/utils/backends.py b/networkx/utils/backends.py
index 1533dc554..6c1ab0498 100644
--- a/networkx/utils/backends.py
+++ b/networkx/utils/backends.py
@@ -78,6 +78,17 @@ tests are working, while avoiding causing an explicit failure.
 If a backend only partially implements some algorithms, it can define
 a ``can_run(name, args, kwargs)`` function that returns True or False
 indicating whether it can run the algorithm with the given arguments.
+It may also return a string indicating why the algorithm can't be run;
+this string may be used in the future to give helpful info to the user.
+
+A backend may also define ``should_run(name, args, kwargs)`` that is similar
+to ``can_run``, but answers whether the backend *should* be run (converting
+if necessary). 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.
 
 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
@@ -135,10 +146,18 @@ backend_info = _get_backends("networkx.backend_info", load_and_call=True)
 _loaded_backends = {}  # type: ignore[var-annotated]
 
 
+def _always_run(name, args, kwargs):
+    return True
+
+
 def _load_backend(backend_name):
     if backend_name in _loaded_backends:
         return _loaded_backends[backend_name]
     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
 
 
@@ -579,6 +598,7 @@ class _dispatchable:
         # Only networkx graphs; try to convert and run with a backend with automatic
         # conversion, but don't do this by default for graph generators or loaders,
         # or if the functions mutates an input graph or returns a graph.
+        # Only convert and run if `backend.should_run(...)` returns True.
         if (
             not self._returns_graph
             and (
@@ -603,7 +623,7 @@ class _dispatchable:
         ):
             # Should we warn or log if we don't convert b/c the input will be mutated?
             for backend_name in self._automatic_backends:
-                if self._can_backend_run(backend_name, *args, **kwargs):
+                if self._should_backend_run(backend_name, *args, **kwargs):
                     return self._convert_and_call(
                         backend_name,
                         args,
@@ -614,10 +634,27 @@ class _dispatchable:
         return self.orig_func(*args, **kwargs)
 
     def _can_backend_run(self, backend_name, /, *args, **kwargs):
-        """Can the specified backend run this algorithms with these arguments?"""
+        """Can the specified backend run this algorithm with these arguments?"""
+        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. We plan to use the strings in the future.
+        return (
+            hasattr(backend, self.name)
+            and (can_run := backend.can_run(self.name, args, kwargs))
+            and not isinstance(can_run, str)
+        )
+
+    def _should_backend_run(self, backend_name, /, *args, **kwargs):
+        """Can/should the specified backend run this algorithm with these arguments?"""
         backend = _load_backend(backend_name)
-        return hasattr(backend, self.name) and (
-            not hasattr(backend, "can_run") or backend.can_run(self.name, args, kwargs)
+        # `backend.can_run` and `backend.should_run` may return strings that describe
+        # why they can't or shouldn't be run. We plan to use the strings in the future.
+        return (
+            hasattr(backend, self.name)
+            and (can_run := backend.can_run(self.name, args, kwargs))
+            and not isinstance(can_run, str)
+            and (should_run := backend.should_run(self.name, args, kwargs))
+            and not isinstance(should_run, str)
         )
 
     def _convert_arguments(self, backend_name, args, kwargs):


Test patch:
diff --git a/networkx/algorithms/bipartite/tests/test_matrix.py b/networkx/algorithms/bipartite/tests/test_matrix.py
index 393b71e7c..53d831151 100644
--- a/networkx/algorithms/bipartite/tests/test_matrix.py
+++ b/networkx/algorithms/bipartite/tests/test_matrix.py
@@ -39,6 +39,11 @@ class TestBiadjacencyMatrix:
         M = bipartite.biadjacency_matrix(G, X, Y, weight="weight")
         assert M[1, 2] == 2
 
+    def test_biadjacency_matrix_empty_graph(self):
+        G = nx.empty_graph(2)
+        M = nx.bipartite.biadjacency_matrix(G, [0])
+        assert np.array_equal(M.toarray(), np.array([[0]]))
+
     def test_null_graph(self):
         with pytest.raises(nx.NetworkXError):
             bipartite.biadjacency_matrix(nx.Graph(), [])
diff --git a/networkx/algorithms/tests/test_similarity.py b/networkx/algorithms/tests/test_similarity.py
index 420c709c1..3836ccfe1 100644
--- a/networkx/algorithms/tests/test_similarity.py
+++ b/networkx/algorithms/tests/test_similarity.py
@@ -845,8 +845,6 @@ class TestSimilarity:
             nx.panther_similarity(G, source=1)
 
     def test_generate_random_paths_unweighted(self):
-        np.random.seed(42)
-
         index_map = {}
         num_paths = 10
         path_length = 2
@@ -857,7 +855,7 @@ class TestSimilarity:
         G.add_edge(1, 2)
         G.add_edge(2, 4)
         paths = nx.generate_random_paths(
-            G, num_paths, path_length=path_length, index_map=index_map
+            G, num_paths, path_length=path_length, index_map=index_map, seed=42
         )
         expected_paths = [
             [3, 0, 3],