Dispatch more algorithms and improve auto-test capabilities

14 files changed, 66 insertions, 4 deletions

diff --git a/networkx/algorithms/boundary.py b/networkx/algorithms/boundary.py
index 25c1e286..c74f47e9 100644
--- a/networkx/algorithms/boundary.py
+++ b/networkx/algorithms/boundary.py
@@ -8,11 +8,13 @@ A node boundary of a set *S* of nodes is the set of (out-)neighbors of
 nodes in *S* that are outside *S*.
 
 """
+import networkx as nx
 from itertools import chain
 
 __all__ = ["edge_boundary", "node_boundary"]
 
 
+@nx.dispatch("edge_boundary")
 def edge_boundary(G, nbunch1, nbunch2=None, data=False, keys=False, default=None):
     """Returns the edge boundary of `nbunch1`.
 
@@ -89,6 +91,7 @@ def edge_boundary(G, nbunch1, nbunch2=None, data=False, keys=False, default=None
     )
 
 
+@nx.dispatch("node_boundary")
 def node_boundary(G, nbunch1, nbunch2=None):
     """Returns the node boundary of `nbunch1`.
 
diff --git a/networkx/algorithms/cluster.py b/networkx/algorithms/cluster.py
index 6df4ce7f..159aba78 100644
--- a/networkx/algorithms/cluster.py
+++ b/networkx/algorithms/cluster.py
@@ -16,6 +16,7 @@ __all__ = [
 ]
 
 
+@nx.dispatch("triangles")
 @not_implemented_for("directed")
 def triangles(G, nodes=None):
     """Compute the number of triangles.
diff --git a/networkx/algorithms/cuts.py b/networkx/algorithms/cuts.py
index ae1cb028..271ff309 100644
--- a/networkx/algorithms/cuts.py
+++ b/networkx/algorithms/cuts.py
@@ -21,6 +21,7 @@ __all__ = [
 # TODO STILL NEED TO UPDATE ALL THE DOCUMENTATION!
 
 
+@nx.dispatch("cut_size")
 def cut_size(G, S, T=None, weight=None):
     """Returns the size of the cut between two sets of nodes.
 
@@ -83,6 +84,7 @@ def cut_size(G, S, T=None, weight=None):
     return sum(weight for u, v, weight in edges)
 
 
+@nx.dispatch("volume")
 def volume(G, S, weight=None):
     """Returns the volume of a set of nodes.
 
@@ -125,6 +127,7 @@ def volume(G, S, weight=None):
     return sum(d for v, d in degree(S, weight=weight))
 
 
+@nx.dispatch("normalized_cut_size")
 def normalized_cut_size(G, S, T=None, weight=None):
     """Returns the normalized size of the cut between two sets of nodes.
 
@@ -177,6 +180,7 @@ def normalized_cut_size(G, S, T=None, weight=None):
     return num_cut_edges * ((1 / volume_S) + (1 / volume_T))
 
 
+@nx.dispatch("conductance")
 def conductance(G, S, T=None, weight=None):
     """Returns the conductance of two sets of nodes.
 
@@ -224,6 +228,7 @@ def conductance(G, S, T=None, weight=None):
     return num_cut_edges / min(volume_S, volume_T)
 
 
+@nx.dispatch("edge_expansion")
 def edge_expansion(G, S, T=None, weight=None):
     """Returns the edge expansion between two node sets.
 
@@ -270,6 +275,7 @@ def edge_expansion(G, S, T=None, weight=None):
     return num_cut_edges / min(len(S), len(T))
 
 
+@nx.dispatch("mixing_expansion")
 def mixing_expansion(G, S, T=None, weight=None):
     """Returns the mixing expansion between two node sets.
 
@@ -317,6 +323,7 @@ def mixing_expansion(G, S, T=None, weight=None):
 
 # TODO What is the generalization to two arguments, S and T? Does the
 # denominator become `min(len(S), len(T))`?
+@nx.dispatch("node_expansion")
 def node_expansion(G, S):
     """Returns the node expansion of the set `S`.
 
@@ -356,6 +363,7 @@ def node_expansion(G, S):
 
 # TODO What is the generalization to two arguments, S and T? Does the
 # denominator become `min(len(S), len(T))`?
+@nx.dispatch("boundary_expansion")
 def boundary_expansion(G, S):
     """Returns the boundary expansion of the set `S`.
 
diff --git a/networkx/algorithms/dag.py b/networkx/algorithms/dag.py
index 826b87ff..f7692d1f 100644
--- a/networkx/algorithms/dag.py
+++ b/networkx/algorithms/dag.py
@@ -36,6 +36,7 @@ __all__ = [
 chaini = chain.from_iterable
 
 
+@nx.dispatch("descendants")
 def descendants(G, source):
     """Returns all nodes reachable from `source` in `G`.
 
@@ -72,6 +73,7 @@ def descendants(G, source):
     return {child for parent, child in nx.bfs_edges(G, source)}
 
 
+@nx.dispatch("ancestors")
 def ancestors(G, source):
     """Returns all nodes having a path to `source` in `G`.
 
diff --git a/networkx/algorithms/dominating.py b/networkx/algorithms/dominating.py
index 32fff4d9..3f2da907 100644
--- a/networkx/algorithms/dominating.py
+++ b/networkx/algorithms/dominating.py
@@ -64,6 +64,7 @@ def dominating_set(G, start_with=None):
     return dominating_set
 
 
+@nx.dispatch("is_dominating_set")
 def is_dominating_set(G, nbunch):
     """Checks if `nbunch` is a dominating set for `G`.
 
diff --git a/networkx/algorithms/isolate.py b/networkx/algorithms/isolate.py
index e81e7227..d59a46c4 100644
--- a/networkx/algorithms/isolate.py
+++ b/networkx/algorithms/isolate.py
@@ -1,10 +1,12 @@
 """
 Functions for identifying isolate (degree zero) nodes.
 """
+import networkx as nx
 
 __all__ = ["is_isolate", "isolates", "number_of_isolates"]
 
 
+@nx.dispatch("is_isolate")
 def is_isolate(G, n):
     """Determines whether a node is an isolate.
 
@@ -37,6 +39,7 @@ def is_isolate(G, n):
     return G.degree(n) == 0
 
 
+@nx.dispatch("isolates")
 def isolates(G):
     """Iterator over isolates in the graph.
 
@@ -82,6 +85,7 @@ def isolates(G):
     return (n for n, d in G.degree() if d == 0)
 
 
+@nx.dispatch("number_of_isolates")
 def number_of_isolates(G):
     """Returns the number of isolates in the graph.
 
diff --git a/networkx/algorithms/regular.py b/networkx/algorithms/regular.py
index 630f1fd2..89b98742 100644
--- a/networkx/algorithms/regular.py
+++ b/networkx/algorithms/regular.py
@@ -5,6 +5,7 @@ from networkx.utils import not_implemented_for
 __all__ = ["is_regular", "is_k_regular", "k_factor"]
 
 
+@nx.dispatch("is_regular")
 def is_regular(G):
     """Determines whether the graph ``G`` is a regular graph.
 
@@ -40,6 +41,7 @@ def is_regular(G):
         return in_regular and out_regular
 
 
+@nx.dispatch("is_k_regular")
 @not_implemented_for("directed")
 def is_k_regular(G, k):
     """Determines whether the graph ``G`` is a k-regular graph.
diff --git a/networkx/algorithms/simple_paths.py b/networkx/algorithms/simple_paths.py
index e19e4e4b..0ddacabb 100644
--- a/networkx/algorithms/simple_paths.py
+++ b/networkx/algorithms/simple_paths.py
@@ -13,6 +13,7 @@ __all__ = [
 ]
 
 
+@nx.dispatch("is_simple_path")
 def is_simple_path(G, nodes):
     """Returns True if and only if `nodes` form a simple path in `G`.
 
diff --git a/networkx/algorithms/smetric.py b/networkx/algorithms/smetric.py
index b851e1ee..a97bb8d9 100644
--- a/networkx/algorithms/smetric.py
+++ b/networkx/algorithms/smetric.py
@@ -3,6 +3,7 @@ import networkx as nx
 __all__ = ["s_metric"]
 
 
+@nx.dispatch("s_metric")
 def s_metric(G, normalized=True):
     """Returns the s-metric of graph.
 
diff --git a/networkx/algorithms/structuralholes.py b/networkx/algorithms/structuralholes.py
index 55cdfe47..9762587e 100644
--- a/networkx/algorithms/structuralholes.py
+++ b/networkx/algorithms/structuralholes.py
@@ -5,6 +5,7 @@ import networkx as nx
 __all__ = ["constraint", "local_constraint", "effective_size"]
 
 
+@nx.dispatch("mutual_weight")
 def mutual_weight(G, u, v, weight=None):
     """Returns the sum of the weights of the edge from `u` to `v` and
     the edge from `v` to `u` in `G`.
diff --git a/networkx/algorithms/tournament.py b/networkx/algorithms/tournament.py
index 278a1c42..60d09f31 100644
--- a/networkx/algorithms/tournament.py
+++ b/networkx/algorithms/tournament.py
@@ -61,6 +61,7 @@ def index_satisfying(iterable, condition):
         raise ValueError("iterable must be non-empty") from err
 
 
+@nx.dispatch("is_tournament")
 @not_implemented_for("undirected")
 @not_implemented_for("multigraph")
 def is_tournament(G):
@@ -179,6 +180,7 @@ def random_tournament(n, seed=None):
     return nx.DiGraph(edges)
 
 
+@nx.dispatch("score_sequence")
 @not_implemented_for("undirected")
 @not_implemented_for("multigraph")
 def score_sequence(G):
@@ -208,6 +210,7 @@ def score_sequence(G):
     return sorted(d for v, d in G.out_degree())
 
 
+@nx.dispatch("tournament_matrix")
 @not_implemented_for("undirected")
 @not_implemented_for("multigraph")
 def tournament_matrix(G):
diff --git a/networkx/algorithms/triads.py b/networkx/algorithms/triads.py
index 22adf85b..0042f5c3 100644
--- a/networkx/algorithms/triads.py
+++ b/networkx/algorithms/triads.py
@@ -275,6 +275,7 @@ def triadic_census(G, nodelist=None):
     return census
 
 
+@nx.dispatch("is_triad")
 def is_triad(G):
     """Returns True if the graph G is a triad, else False.
 
diff --git a/networkx/classes/backends.py b/networkx/classes/backends.py
index c6169850..c15edc80 100644
--- a/networkx/classes/backends.py
+++ b/networkx/classes/backends.py
@@ -43,8 +43,14 @@ the backend implementation.
 Example pytest invocation:
 NETWORKX_GRAPH_CONVERT=sparse pytest --pyargs networkx
 
-The expectation is that each backend will pass all networkx tests
-to be considered a fully compliant backend.
+Any dispatchable algorithms which are not implemented by the backend
+will cause a `pytest.xfail()`, giving some indication that not all
+tests are working without causing an explicit failure.
+
+A special `mark_nx_tests(items)` function may be defined by the backend.
+It will be called with the list of NetworkX tests discovered. Each item
+is a pytest.Node object. If the backend does not support the test, it
+can be marked as xfail to indicate it is not being handled.
 """
 import os
 import sys
@@ -53,7 +59,7 @@ from functools import wraps
 from importlib.metadata import entry_points
 
 
-__all__ = ["dispatch"]
+__all__ = ["dispatch", "mark_tests"]
 
 
 known_plugins = [
@@ -122,6 +128,11 @@ if os.environ.get("NETWORKX_GRAPH_CONVERT"):
     if plugin_name not in plugins:
         raise Exception(f"No registered networkx.plugins entry_point named {plugin_name}")
 
+    try:
+        import pytest
+    except ImportError:
+        raise ImportError(f"Missing pytest, which is required when using NETWORKX_GRAPH_CONVERT")
+
     def dispatch(algo):
         def algorithm(func):
             sig = inspect.signature(func)
@@ -129,14 +140,33 @@ if os.environ.get("NETWORKX_GRAPH_CONVERT"):
             @wraps(func)
             def wrapper(*args, **kwds):
                 backend = plugins[plugin_name].load()
+                if not hasattr(backend, algo):
+                    pytest.xfail(f"'{algo}' not implemented by {plugin_name}")
                 bound = sig.bind(*args, **kwds)
                 bound.apply_defaults()
                 graph, *args = args
                 # Convert graph into backend graph-like object
                 #   Include the weight label, if provided to the algorithm
-                graph = backend.convert(graph, bound.arguments.get("weight"))
+                weight = None
+                if "weight" in bound.arguments:
+                    weight = bound.arguments["weight"]
+                elif "data" in bound.arguments and "default" in bound.arguments:
+                    # This case exists for several MultiGraph edge algorithms
+                    if bound.arguments["data"]:
+                        weight = "weight"
+                graph = backend.convert(graph, weight=weight)
                 return getattr(backend, algo).__call__(graph, *args, **kwds)
 
             return wrapper
 
         return algorithm
+
+
+def mark_tests(items):
+    # Allow backend to mark tests (skip or xfail) if they aren't
+    # able to correctly handle them
+    if os.environ.get("NETWORKX_GRAPH_CONVERT"):
+        plugin_name = os.environ["NETWORKX_GRAPH_CONVERT"]
+        backend = plugins[plugin_name].load()
+        if hasattr(backend, "mark_nx_tests"):
+            getattr(backend, "mark_nx_tests")(items)
diff --git a/networkx/conftest.py b/networkx/conftest.py
index 5c95c9fc..55bf960b 100644
--- a/networkx/conftest.py
+++ b/networkx/conftest.py
@@ -30,6 +30,10 @@ def pytest_configure(config):
 
 
 def pytest_collection_modifyitems(config, items):
+    # Allow pluggable backends to add markers to tests when
+    # running in auto-conversion test mode
+    networkx.classes.backends.mark_tests(items)
+
     if config.getoption("--runslow"):
         # --runslow given in cli: do not skip slow tests
         return