Repository: networkx/networkx

Issue:
Improve test coverage for MST algorithms
I found that the test coverage for the mst.py file in algorithms/tree is 92.49%

https://app.codecov.io/gh/networkx/networkx/blob/main/networkx/algorithms/tree/mst.py

I am working on improving this.

Current Behavior
We don't test all the paths the code can take us.

Expected Behavior
We should be testing everything so there aren't any surprises.

Discussion:
navyagarwal: I am importing numpy to mst.py to set the value of an edge as NaN which is causing some of the checks to fail.

<img width="712" alt="image" src="https://user-images.githubusercontent.com/82928853/224432023-d65c922c-9a37-4208-ad9d-8b31af04bd44.png">

I think I have to mention the imports in some other file as well but I am not able to figure out where. Could someone please help out?
navyagarwal: @MridulS Could you please help me with this?
BenFaruna: > I am importing numpy to mst.py to set the weight of an edge as NaN which is causing some of the checks to fail.
> 
> <img alt="image" width="712" src="https://user-images.githubusercontent.com/82928853/224432023-d65c922c-9a37-4208-ad9d-8b31af04bd44.png">
> 
> I think I have to mention the imports in some other file as well but I am not able to figure out where. Could someone please help out?

Concerning this, I don't know if this runs on your machine but it seems the environment you're working with does not have numpy installed. So maybe try running python in your virtual environment and importing numpy to see if it works
navyagarwal: > Concerning this, I don't know if this runs on your machine but it seems the environment you're working with does not have numpy installed. So maybe try running python in your virtual environment and importing numpy to see if it works

It does run on my system and passes all tests, and numpy has been imported as well.

Patch:
diff --git a/networkx/algorithms/tree/mst.py b/networkx/algorithms/tree/mst.py
index a866aeefd..8ec693d66 100644
--- a/networkx/algorithms/tree/mst.py
+++ b/networkx/algorithms/tree/mst.py
@@ -334,12 +334,22 @@ def prim_mst_edges(G, minimum, weight="weight", keys=True, data=True, ignore_nan
                         continue
                     for k2, d2 in keydict.items():
                         new_weight = d2.get(weight, 1) * sign
+                        if isnan(new_weight):
+                            if ignore_nan:
+                                continue
+                            msg = f"NaN found as an edge weight. Edge {(v, w, k2, d2)}"
+                            raise ValueError(msg)
                         push(frontier, (new_weight, next(c), v, w, k2, d2))
             else:
                 for w, d2 in G.adj[v].items():
                     if w in visited:
                         continue
                     new_weight = d2.get(weight, 1) * sign
+                    if isnan(new_weight):
+                        if ignore_nan:
+                            continue
+                        msg = f"NaN found as an edge weight. Edge {(v, w, d2)}"
+                        raise ValueError(msg)
                     push(frontier, (new_weight, next(c), v, w, d2))
 
 
diff --git a/networkx/classes/backends.py b/networkx/classes/backends.py
index c96f4896a..89a200d41 100644
--- a/networkx/classes/backends.py
+++ b/networkx/classes/backends.py
@@ -174,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()))


Test patch:
diff --git a/networkx/algorithms/bipartite/tests/test_edgelist.py b/networkx/algorithms/bipartite/tests/test_edgelist.py
index 9cf0c438b..b388465ef 100644
--- a/networkx/algorithms/bipartite/tests/test_edgelist.py
+++ b/networkx/algorithms/bipartite/tests/test_edgelist.py
@@ -190,3 +190,40 @@ class TestEdgelist:
             G = nx.path_graph(4)
             bytesIO = io.BytesIO()
             bipartite.write_edgelist(G, bytesIO)
+
+    def test_parse_edgelist(self):
+        """Tests for conditions specific to
+        parse_edge_list method"""
+
+        # ignore strings of length less than 2
+        lines = ["1 2", "2 3", "3 1", "4", " "]
+        G = bipartite.parse_edgelist(lines, nodetype=int)
+        assert list(G.nodes) == [1, 2, 3]
+
+        # Exception raised when node is not convertible
+        # to specified data type
+        with pytest.raises(TypeError, match=".*Failed to convert nodes"):
+            lines = ["a b", "b c", "c a"]
+            G = bipartite.parse_edgelist(lines, nodetype=int)
+
+        # Exception raised when format of data is not
+        # convertible to dictionary object
+        with pytest.raises(TypeError, match=".*Failed to convert edge data"):
+            lines = ["1 2 3", "2 3 4", "3 1 2"]
+            G = bipartite.parse_edgelist(lines, nodetype=int)
+
+        # Exception raised when edge data and data
+        # keys are not of same length
+        with pytest.raises(IndexError):
+            lines = ["1 2 3 4", "2 3 4"]
+            G = bipartite.parse_edgelist(
+                lines, nodetype=int, data=[("weight", int), ("key", int)]
+            )
+
+        # Exception raised when edge data is not
+        # convertible to specified data type
+        with pytest.raises(TypeError, match=".*Failed to convert key data"):
+            lines = ["1 2 3 a", "2 3 4 b"]
+            G = bipartite.parse_edgelist(
+                lines, nodetype=int, data=[("weight", int), ("key", int)]
+            )
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/weighted.py b/networkx/algorithms/shortest_paths/weighted.py
index c82747a79..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.
diff --git a/networkx/algorithms/tree/tests/test_mst.py b/networkx/algorithms/tree/tests/test_mst.py
index 88205e690..ee0c3f601 100644
--- a/networkx/algorithms/tree/tests/test_mst.py
+++ b/networkx/algorithms/tree/tests/test_mst.py
@@ -253,6 +253,36 @@ class TestKruskal(MultigraphMSTTestBase):
 
     algorithm = "kruskal"
 
+    def test_key_data_bool(self):
+        """Tests that the keys and data values are included in
+        MST edges based on whether keys and data parameters are
+        true or false"""
+        G = nx.MultiGraph()
+        G.add_edge(1, 2, key=1, weight=2)
+        G.add_edge(1, 2, key=2, weight=3)
+        G.add_edge(3, 2, key=1, weight=2)
+        G.add_edge(3, 1, key=1, weight=4)
+
+        # keys are included and data is not included
+        mst_edges = nx.minimum_spanning_edges(
+            G, algorithm=self.algo, keys=True, data=False
+        )
+        assert edges_equal([(1, 2, 1), (2, 3, 1)], list(mst_edges))
+
+        # keys are not included and data is included
+        mst_edges = nx.minimum_spanning_edges(
+            G, algorithm=self.algo, keys=False, data=True
+        )
+        assert edges_equal(
+            [(1, 2, {"weight": 2}), (2, 3, {"weight": 2})], list(mst_edges)
+        )
+
+        # both keys and data are not included
+        mst_edges = nx.minimum_spanning_edges(
+            G, algorithm=self.algo, keys=False, data=False
+        )
+        assert edges_equal([(1, 2), (2, 3)], list(mst_edges))
+
 
 class TestPrim(MultigraphMSTTestBase):
     """Unit tests for computing a minimum (or maximum) spanning tree
@@ -261,6 +291,25 @@ class TestPrim(MultigraphMSTTestBase):
 
     algorithm = "prim"
 
+    def test_ignore_nan(self):
+        """Tests that the edges with NaN weights are ignored or
+        raise an Error based on ignore_nan is true or false"""
+        H = nx.MultiGraph()
+        H.add_edge(1, 2, key=1, weight=float("nan"))
+        H.add_edge(1, 2, key=2, weight=3)
+        H.add_edge(3, 2, key=1, weight=2)
+        H.add_edge(3, 1, key=1, weight=4)
+
+        # NaN weight edges are ignored when ignore_nan=True
+        mst_edges = nx.minimum_spanning_edges(H, algorithm=self.algo, ignore_nan=True)
+        assert edges_equal(
+            [(1, 2, 2, {"weight": 3}), (2, 3, 1, {"weight": 2})], list(mst_edges)
+        )
+
+        # NaN weight edges raise Error when ignore_nan=False
+        with pytest.raises(ValueError):
+            list(nx.minimum_spanning_edges(H, algorithm=self.algo, ignore_nan=False))
+
     def test_multigraph_keys_tree(self):
         G = nx.MultiGraph()
         G.add_edge(0, 1, key="a", weight=2)
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]