Repository: networkx/networkx

Issue:
nx.DiGraph.to_undirected() not working as expected for bidirectional edges when using as_view = True
Problem: When using `to_undirected()` on a DiGraph the properties are inconsistent, i.e., differ depending on if as_view was set to True or False. More precisely, the reported degree is not as expected when using `as_view = True`. I guess this might also have an effect on other properties that depend on degree.

### Current Behavior

The node degree of the undirected graph returned by `to_undirected()` is different depending on if as_view was set to True or False. If the directed graph had bidirectional edges, the degree is off by approx. a factor of 2 in the graph view. Everything works as expected if as_view is set to false.

### Expected Behavior

`G.to_undirected(as_view = False).degree()` and `G.to_undirected(as_view = True).degree()` should behave the same.

### Steps to Reproduce

```
import networkx as nx
import sys

print(sys.version) # 3.10.8 | packaged by conda-forge | (main, Nov 24 2022, 14:07:00) [MSC v.1916 64 bit (AMD64)]
print(nx.__version__) # 2.8.8

G = nx.DiGraph()
G.add_nodes_from(["v0","v1","v2"])
G.add_edges_from([("v0","v1"),("v1","v0"),("v1","v2")])
print(G.degree()) # Correct [('v0', 2), ('v1', 3), ('v2', 1)]

G_undir_1 = G.to_undirected(as_view = False)
print(G_undir_1.degree()) # Correct [('v0', 1), ('v1', 2), ('v2', 1)]

G_undir_2 = G.to_undirected(as_view = True)
print(G_undir_2.degree()) # Incorrect [('v0', 2), ('v1', 3), ('v2', 1)]
```

### Environment

<!--- Please provide details about your local environment -->

Python version: 3.10.8
NetworkX version: 2.8.8

### Additional context

n/a


Discussion:

Patch:
diff --git a/networkx/algorithms/components/connected.py b/networkx/algorithms/components/connected.py
index 2e7488092..192d0b841 100644
--- a/networkx/algorithms/components/connected.py
+++ b/networkx/algorithms/components/connected.py
@@ -101,6 +101,7 @@ def number_connected_components(G):
     return sum(1 for cc in connected_components(G))
 
 
+@nx._dispatch
 @not_implemented_for("directed")
 def is_connected(G):
     """Returns True if the graph is connected, False otherwise.
@@ -146,6 +147,7 @@ def is_connected(G):
     return sum(1 for node in _plain_bfs(G, arbitrary_element(G))) == len(G)
 
 
+@nx._dispatch
 @not_implemented_for("directed")
 def node_connected_component(G, n):
     """Returns the set of nodes in the component of graph containing node n.
diff --git a/networkx/algorithms/components/weakly_connected.py b/networkx/algorithms/components/weakly_connected.py
index 0a86a01d9..31b5b03de 100644
--- a/networkx/algorithms/components/weakly_connected.py
+++ b/networkx/algorithms/components/weakly_connected.py
@@ -104,6 +104,7 @@ def number_weakly_connected_components(G):
     return sum(1 for wcc in weakly_connected_components(G))
 
 
+@nx._dispatch
 @not_implemented_for("undirected")
 def is_weakly_connected(G):
     """Test directed graph for weak connectivity.
diff --git a/networkx/algorithms/traversal/breadth_first_search.py b/networkx/algorithms/traversal/breadth_first_search.py
index 6a8344b5e..951a9e9e7 100644
--- a/networkx/algorithms/traversal/breadth_first_search.py
+++ b/networkx/algorithms/traversal/breadth_first_search.py
@@ -236,6 +236,7 @@ def bfs_tree(G, source, reverse=False, depth_limit=None, sort_neighbors=None):
     return T
 
 
+@nx._dispatch
 def bfs_predecessors(G, source, depth_limit=None, sort_neighbors=None):
     """Returns an iterator of predecessors in breadth-first-search from source.
 
@@ -300,6 +301,7 @@ def bfs_predecessors(G, source, depth_limit=None, sort_neighbors=None):
         yield (t, s)
 
 
+@nx._dispatch
 def bfs_successors(G, source, depth_limit=None, sort_neighbors=None):
     """Returns an iterator of successors in breadth-first-search from source.
 
@@ -372,6 +374,7 @@ def bfs_successors(G, source, depth_limit=None, sort_neighbors=None):
     yield (parent, children)
 
 
+@nx._dispatch
 def bfs_layers(G, sources):
     """Returns an iterator of all the layers in breadth-first search traversal.
 
@@ -423,6 +426,7 @@ def bfs_layers(G, sources):
         current_layer = next_layer
 
 
+@nx._dispatch
 def descendants_at_distance(G, source, distance):
     """Returns all nodes at a fixed `distance` from `source` in `G`.
 
diff --git a/networkx/algorithms/traversal/edgebfs.py b/networkx/algorithms/traversal/edgebfs.py
index 5c94c1d2b..c29ef5e02 100644
--- a/networkx/algorithms/traversal/edgebfs.py
+++ b/networkx/algorithms/traversal/edgebfs.py
@@ -16,6 +16,7 @@ REVERSE = "reverse"
 __all__ = ["edge_bfs"]
 
 
+@nx._dispatch
 def edge_bfs(G, source=None, orientation=None):
     """A directed, breadth-first-search of edges in `G`, beginning at `source`.
 
diff --git a/networkx/classes/backends.py b/networkx/classes/backends.py
index 183db1708..89a200d41 100644
--- a/networkx/classes/backends.py
+++ b/networkx/classes/backends.py
@@ -128,7 +128,13 @@ def _dispatch(func=None, *, name=None):
 
     @functools.wraps(func)
     def wrapper(*args, **kwds):
-        graph = args[0]
+        if args:
+            graph = args[0]
+        else:
+            try:
+                graph = kwds["G"]
+            except KeyError:
+                raise TypeError(f"{name}() missing positional argument: 'G'") from None
         if hasattr(graph, "__networkx_plugin__") and plugins:
             plugin_name = graph.__networkx_plugin__
             if plugin_name in plugins:
@@ -168,7 +174,13 @@ def test_override_dispatch(func=None, *, name=None):
             pytest.xfail(f"'{name}' not implemented by {plugin_name}")
         bound = sig.bind(*args, **kwds)
         bound.apply_defaults()
-        graph, *args = args
+        if args:
+            graph, *args = args
+        else:
+            try:
+                graph = kwds.pop("G")
+            except KeyError:
+                raise TypeError(f"{name}() missing positional argument: 'G'") from None
         # Convert graph into backend graph-like object
         #   Include the weight label, if provided to the algorithm
         weight = None
diff --git a/networkx/classes/coreviews.py b/networkx/classes/coreviews.py
index c2b835592..5c4defe94 100644
--- a/networkx/classes/coreviews.py
+++ b/networkx/classes/coreviews.py
@@ -134,7 +134,7 @@ class UnionAtlas(Mapping):
         self._pred = pred
 
     def __len__(self):
-        return len(self._succ) + len(self._pred)
+        return len(self._succ.keys() | self._pred.keys())
 
     def __iter__(self):
         return iter(set(self._succ.keys()) | set(self._pred.keys()))
diff --git a/networkx/generators/classic.py b/networkx/generators/classic.py
index f1ed4ed54..c6dffde40 100644
--- a/networkx/generators/classic.py
+++ b/networkx/generators/classic.py
@@ -403,7 +403,7 @@ def cycle_graph(n, create_using=None):
 def dorogovtsev_goltsev_mendes_graph(n, create_using=None):
     """Returns the hierarchically constructed Dorogovtsev-Goltsev-Mendes graph.
 
-    The Dorogovtsev-Goltsev-Mendes[1_] procedure produces a scale-free graph
+    The Dorogovtsev-Goltsev-Mendes [1]_ procedure produces a scale-free graph
     deterministically with the following properties for a given `n`:
     - Total number of nodes = ``3 * (3**n + 1) / 2``
     - Total number of edges = ``3 ** (n + 1)``
@@ -433,7 +433,7 @@ def dorogovtsev_goltsev_mendes_graph(n, create_using=None):
 
     References
     ----------
-    .. [1]: Dorogotsev S.N., Goltsev A.V., and Mendes J.F.F "Pseudofractal
+    .. [1] Dorogotsev S.N., Goltsev A.V., and Mendes J.F.F "Pseudofractal
        Scale-free Web". arXiv:cond-mat/0112143
     """
     G = empty_graph(0, create_using)


Test patch:
diff --git a/networkx/algorithms/flow/tests/test_mincost.py b/networkx/algorithms/flow/tests/test_mincost.py
index c49d3e796..65603d3c1 100644
--- a/networkx/algorithms/flow/tests/test_mincost.py
+++ b/networkx/algorithms/flow/tests/test_mincost.py
@@ -438,7 +438,7 @@ class TestMinCostFlow:
         pytest.raises(nx.NetworkXNotImplemented, nx.capacity_scaling, G)
         G = nx.DiGraph()
         pytest.raises(nx.NetworkXError, nx.network_simplex, G)
-        pytest.raises(nx.NetworkXError, nx.capacity_scaling, G)
+        # pytest.raises(nx.NetworkXError, nx.capacity_scaling, G)
         G.add_node(0, demand=float("inf"))
         pytest.raises(nx.NetworkXError, nx.network_simplex, G)
         pytest.raises(nx.NetworkXUnfeasible, nx.capacity_scaling, G)
diff --git a/networkx/algorithms/shortest_paths/tests/test_astar.py b/networkx/algorithms/shortest_paths/tests/test_astar.py
index 3cc4050b9..680f76efb 100644
--- a/networkx/algorithms/shortest_paths/tests/test_astar.py
+++ b/networkx/algorithms/shortest_paths/tests/test_astar.py
@@ -194,3 +194,17 @@ class TestAStar:
         G.add_edges_from(pairwise(nodes, cyclic=True))
         path = nx.astar_path(G, nodes[0], nodes[2])
         assert len(path) == 3
+
+    def test_astar_NetworkXNoPath(self):
+        """Tests that exception is raised when there exists no
+        path between source and target"""
+        G = nx.gnp_random_graph(10, 0.2, seed=10)
+        with pytest.raises(nx.NetworkXNoPath):
+            nx.astar_path(G, 4, 9)
+
+    def test_astar_NodeNotFound(self):
+        """Tests that exception is raised when either
+        source or target is not in graph"""
+        G = nx.gnp_random_graph(10, 0.2, seed=10)
+        with pytest.raises(nx.NodeNotFound):
+            nx.astar_path_length(G, 11, 9)
diff --git a/networkx/algorithms/shortest_paths/tests/test_weighted.py b/networkx/algorithms/shortest_paths/tests/test_weighted.py
index 7d5dae420..d1bfea2ac 100644
--- a/networkx/algorithms/shortest_paths/tests/test_weighted.py
+++ b/networkx/algorithms/shortest_paths/tests/test_weighted.py
@@ -342,6 +342,10 @@ class TestWeightedPath(WeightedTestBase):
         G.add_edge(9, 10)
         pytest.raises(ValueError, nx.bidirectional_dijkstra, G, 8, 10)
 
+    def test_negative_edge_cycle_empty(self):
+        G = nx.DiGraph()
+        assert not nx.negative_edge_cycle(G)
+
     def test_negative_edge_cycle_custom_weight_key(self):
         d = nx.DiGraph()
         d.add_edge("a", "b", w=-2)
diff --git a/networkx/algorithms/shortest_paths/weighted.py b/networkx/algorithms/shortest_paths/weighted.py
index de08828d2..f5ff3ee13 100644
--- a/networkx/algorithms/shortest_paths/weighted.py
+++ b/networkx/algorithms/shortest_paths/weighted.py
@@ -126,6 +126,15 @@ def dijkstra_path(G, source, target, weight="weight"):
     >>> print(nx.dijkstra_path(G, 0, 4))
     [0, 1, 2, 3, 4]
 
+    Find edges of shortest path in Multigraph
+
+    >>> G = nx.MultiDiGraph()
+    >>> G.add_weighted_edges_from([(1, 2, 0.75), (1, 2, 0.5), (2, 3, 0.5), (1, 3, 1.5)])
+    >>> nodes = nx.dijkstra_path(G, 1, 3)
+    >>> edges = nx.utils.pairwise(nodes)
+    >>> list((u, v, min(G[u][v], key=lambda k: G[u][v][k].get('weight', 1))) for u, v in edges)
+    [(1, 2, 1), (2, 3, 0)]
+
     Notes
     -----
     Edge weight attributes must be numerical.
@@ -2077,6 +2086,7 @@ def goldberg_radzik(G, source, weight="weight"):
     return pred, d
 
 
+@nx._dispatch
 def negative_edge_cycle(G, weight="weight", heuristic=True):
     """Returns True if there exists a negative edge cycle anywhere in G.
 
@@ -2126,6 +2136,8 @@ def negative_edge_cycle(G, weight="weight", heuristic=True):
     every node, and starting bellman_ford_predecessor_and_distance on that
     node.  It then removes that extra node.
     """
+    if G.size() == 0:
+        return False
     # find unused node to use temporarily
     newnode = -1
     while newnode in G:
diff --git a/networkx/classes/tests/test_backends.py b/networkx/classes/tests/test_backends.py
new file mode 100644
index 000000000..8d0c86a44
--- /dev/null
+++ b/networkx/classes/tests/test_backends.py
@@ -0,0 +1,14 @@
+import pytest
+
+import networkx as nx
+
+pytest.importorskip("scipy")
+pytest.importorskip("numpy")
+
+
+def test_dispatch_kwds_vs_args():
+    G = nx.path_graph(4)
+    nx.pagerank(G)
+    nx.pagerank(G=G)
+    with pytest.raises(TypeError):
+        nx.pagerank()
diff --git a/networkx/classes/tests/test_coreviews.py b/networkx/classes/tests/test_coreviews.py
index f773b8580..07fa5bfa4 100644
--- a/networkx/classes/tests/test_coreviews.py
+++ b/networkx/classes/tests/test_coreviews.py
@@ -155,7 +155,7 @@ class TestUnionAtlas:
         assert view.__slots__ == pview.__slots__
 
     def test_len(self):
-        assert len(self.av) == len(self.s) + len(self.p)
+        assert len(self.av) == len(self.s.keys() | self.p.keys()) == 5
 
     def test_iter(self):
         assert set(self.av) == set(self.s) | set(self.p)
@@ -257,7 +257,7 @@ class TestUnionMultiInner(TestUnionAdjacency):
         self.adjview = nx.classes.coreviews.UnionMultiInner(self.s, self.p)
 
     def test_len(self):
-        assert len(self.adjview) == len(self.s) + len(self.p)
+        assert len(self.adjview) == len(self.s.keys() | self.p.keys()) == 4
 
     def test_getitem(self):
         assert self.adjview[1] is not self.s[1]
diff --git a/networkx/classes/tests/test_graph.py b/networkx/classes/tests/test_graph.py
index 46d517361..5c6d4e7c1 100644
--- a/networkx/classes/tests/test_graph.py
+++ b/networkx/classes/tests/test_graph.py
@@ -1,6 +1,7 @@
 import gc
 import pickle
 import platform
+import weakref
 
 import pytest
 
@@ -71,7 +72,19 @@ class BaseGraphTester:
         G = self.Graph()
 
         def count_objects_of_type(_type):
-            return sum(1 for obj in gc.get_objects() if isinstance(obj, _type))
+            # Iterating over all objects tracked by gc can include weak references
+            # whose weakly-referenced objects may no longer exist. Calling `isinstance`
+            # on such a weak reference will raise ReferenceError. There are at least
+            # three workarounds for this: one is to compare type names instead of using
+            # `isinstance` such as `type(obj).__name__ == typename`, another is to use
+            # `type(obj) == _type`, and the last is to ignore ProxyTypes as we do below.
+            # NOTE: even if this safeguard is deemed unnecessary to pass NetworkX tests,
+            # we should still keep it for maximum safety for other NetworkX backends.
+            return sum(
+                1
+                for obj in gc.get_objects()
+                if not isinstance(obj, weakref.ProxyTypes) and isinstance(obj, _type)
+            )
 
         gc.collect()
         before = count_objects_of_type(self.Graph)