Repository: networkx/networkx

Issue:
nan values in minimum_spanning_tree
When calculating the minimum_spanning_tree, the algorithm does not correct for (or at least warn about) edges with nan weight.  This can give very strange results, such as a few nodes with very high degree, 'or introduce more subtle bugs.

Simple MWE:

``` python
import networkx, math, random
import matplotlib.pyplot as plt
G = networkx.complete_graph(100)
for n1, n2 in G.edges_iter():
    G.edge[n1][n2]['weight'] = random.random()

# Pre-nan
f, [ax1, ax2] = plt.subplots(2, 1)
ax1.imshow(networkx.to_numpy_matrix(networkx.minimum_spanning_tree(G))!=0)
# Post-nan
G.add_edge(1, 50, {'weight' : float('nan')})
ax2.imshow(networkx.to_numpy_matrix(networkx.minimum_spanning_tree(G))!=0)
plt.show()
```


Discussion:

Patch:
diff --git a/networkx/algorithms/tree/mst.py b/networkx/algorithms/tree/mst.py
index a144e1f2e..409e56069 100644
--- a/networkx/algorithms/tree/mst.py
+++ b/networkx/algorithms/tree/mst.py
@@ -11,7 +11,9 @@ Algorithms for calculating min/max spanning trees/forests.
 
 """
 from heapq import heappop, heappush
+from operator import itemgetter
 from itertools import count
+from math import isnan
 
 import networkx as nx
 from networkx.utils import UnionFind, not_implemented_for
@@ -23,7 +25,8 @@ __all__ = [
 
 
 @not_implemented_for('multigraph')
-def boruvka_mst_edges(G, minimum=True, weight='weight', keys=False, data=True):
+def boruvka_mst_edges(G, minimum=True, weight='weight',
+                      keys=False, data=True, ignore_nan=False):
     """Iterate over edges of a Borůvka's algorithm min/max spanning tree.
 
     Parameters
@@ -48,8 +51,11 @@ def boruvka_mst_edges(G, minimum=True, weight='weight', keys=False, data=True):
         If True, yield edges `(u, v, d)`, where `d` is the attribute dict.
         If False, yield edges `(u, v)`.
 
+    ignore_nan : bool (default: False)
+        If a NaN is found as an edge weight normally an exception is raised.
+        If `ignore_nan is True` then that edge is ignored instead.
+
     """
-    opt = min if minimum else max
     # Initialize a forest, assuming initially that it is the discrete
     # partition of the nodes of the graph.
     forest = UnionFind(G)
@@ -61,16 +67,20 @@ def boruvka_mst_edges(G, minimum=True, weight='weight', keys=False, data=True):
         A return value of ``None`` indicates an empty boundary.
 
         """
-        # TODO In Python 3.4 and later, we can just do
-        #
-        #     boundary = nx.edge_boundary(G, component, data=weight)
-        #     return opt(boundary, key=lambda e: e[-1][weight], default=None)
-        #
-        # which is better because it doesn't require creating a list.
-        boundary = list(nx.edge_boundary(G, component, data=True))
-        if not boundary:
-            return None
-        return opt(boundary, key=lambda e: e[-1][weight])
+        sign = 1 if minimum else -1
+        minwt = float('inf')
+        boundary = None
+        for e in nx.edge_boundary(G, component, data=True):
+            wt = e[-1].get(weight, 1) * sign
+            if isnan(wt):
+                if ignore_nan:
+                    continue
+                msg = "NaN found as an edge weight. Edge %s"
+                raise ValueError(msg % (e,))
+            if wt < minwt:
+                minwt = wt
+                boundary = e
+        return boundary
 
     # Determine the optimum edge in the edge boundary of each component
     # in the forest.
@@ -110,7 +120,8 @@ def boruvka_mst_edges(G, minimum=True, weight='weight', keys=False, data=True):
                 forest.union(u, v)
 
 
-def kruskal_mst_edges(G, minimum, weight='weight', keys=True, data=True):
+def kruskal_mst_edges(G, minimum, weight='weight',
+                      keys=True, data=True, ignore_nan=False):
     """Iterate over edges of a Kruskal's algorithm min/max spanning tree.
 
     Parameters
@@ -133,17 +144,42 @@ def kruskal_mst_edges(G, minimum, weight='weight', keys=True, data=True):
         If True, yield edges `(u, v, d)`, where `d` is the attribute dict.
         If False, yield edges `(u, v)`.
 
+    ignore_nan : bool (default: False)
+        If a NaN is found as an edge weight normally an exception is raised.
+        If `ignore_nan is True` then that edge is ignored instead.
+
     """
     subtrees = UnionFind()
     if G.is_multigraph():
         edges = G.edges(keys=True, data=True)
+
+        def filter_nan_edges(edges=edges, weight=weight):
+            sign = 1 if minimum else -1
+            for u, v, k, d in edges:
+                wt = d.get(weight, 1) * sign
+                if isnan(wt):
+                    if ignore_nan:
+                        continue
+                    msg = "NaN found as an edge weight. Edge %s"
+                    raise ValueError(msg % ((u, v, f, k, d),))
+                yield wt, u, v, k, d
     else:
         edges = G.edges(data=True)
-    getweight = lambda t: t[-1].get(weight, 1)
-    edges = sorted(edges, key=getweight, reverse=not minimum)
+
+        def filter_nan_edges(edges=edges, weight=weight):
+            sign = 1 if minimum else -1
+            for u, v, d in edges:
+                wt = d.get(weight, 1) * sign
+                if isnan(wt):
+                    if ignore_nan:
+                        continue
+                    msg = "NaN found as an edge weight. Edge %s"
+                    raise ValueError(msg % ((u, v, d),))
+                yield wt, u, v, d
+    edges = sorted(filter_nan_edges(), key=itemgetter(0))
     # Multigraphs need to handle edge keys in addition to edge data.
     if G.is_multigraph():
-        for u, v, k, d in edges:
+        for wt, u, v, k, d in edges:
             if subtrees[u] != subtrees[v]:
                 if keys:
                     if data:
@@ -157,7 +193,7 @@ def kruskal_mst_edges(G, minimum, weight='weight', keys=True, data=True):
                         yield u, v
                 subtrees.union(u, v)
     else:
-        for u, v, d in edges:
+        for wt, u, v, d in edges:
             if subtrees[u] != subtrees[v]:
                 if data:
                     yield (u, v, d)
@@ -166,7 +202,35 @@ def kruskal_mst_edges(G, minimum, weight='weight', keys=True, data=True):
                 subtrees.union(u, v)
 
 
-def prim_mst_edges(G, minimum, weight='weight', keys=True, data=True):
+def prim_mst_edges(G, minimum, weight='weight',
+                   keys=True, data=True, ignore_nan=False):
+    """Iterate over edges of Prim's algorithm min/max spanning tree.
+
+    Parameters
+    ----------
+    G : NetworkX Graph
+        The graph holding the tree of interest.
+
+    minimum : bool (default: True)
+        Find the minimum (True) or maximum (False) spanning tree.
+
+    weight : string (default: 'weight')
+        The name of the edge attribute holding the edge weights.
+
+    keys : bool (default: True)
+        If `G` is a multigraph, `keys` controls whether edge keys ar yielded.
+        Otherwise `keys` is ignored.
+
+    data : bool (default: True)
+        Flag for whether to yield edge attribute dicts.
+        If True, yield edges `(u, v, d)`, where `d` is the attribute dict.
+        If False, yield edges `(u, v)`.
+
+    ignore_nan : bool (default: False)
+        If a NaN is found as an edge weight normally an exception is raised.
+        If `ignore_nan is True` then that edge is ignored instead.
+
+    """
     is_multigraph = G.is_multigraph()
     push = heappush
     pop = heappop
@@ -174,9 +238,7 @@ def prim_mst_edges(G, minimum, weight='weight', keys=True, data=True):
     nodes = list(G)
     c = count()
 
-    sign = 1
-    if not minimum:
-        sign = -1
+    sign = 1 if minimum else -1
 
     while nodes:
         u = nodes.pop(0)
@@ -186,10 +248,20 @@ def prim_mst_edges(G, minimum, weight='weight', keys=True, data=True):
             for v, keydict in G.adj[u].items():
                 for k, d in keydict.items():
                     wt = d.get(weight, 1) * sign
+                    if isnan(wt):
+                        if ignore_nan:
+                            continue
+                        msg = "NaN found as an edge weight. Edge %s"
+                        raise ValueError(msg % ((u, v, k, d),))
                     push(frontier, (wt, next(c), u, v, k, d))
         else:
             for v, d in G.adj[u].items():
                 wt = d.get(weight, 1) * sign
+                if isnan(wt):
+                    if ignore_nan:
+                        continue
+                    msg = "NaN found as an edge weight. Edge %s"
+                    raise ValueError(msg % ((u, v, d),))
                 push(frontier, (wt, next(c), u, v, d))
         while frontier:
             if is_multigraph:
@@ -237,7 +309,7 @@ ALGORITHMS = {
 
 @not_implemented_for('directed')
 def minimum_spanning_edges(G, algorithm='kruskal', weight='weight',
-                           keys=True, data=True):
+                           keys=True, data=True, ignore_nan=False):
     """Generate edges in a minimum spanning forest of an undirected
     weighted graph.
 
@@ -265,6 +337,10 @@ def minimum_spanning_edges(G, algorithm='kruskal', weight='weight',
     data : bool, optional
        If True yield the edge data along with the edge.
 
+    ignore_nan : bool (default: False)
+        If a NaN is found as an edge weight normally an exception is raised.
+        If `ignore_nan is True` then that edge is ignored instead.
+
     Returns
     -------
     edges : iterator
@@ -319,12 +395,13 @@ def minimum_spanning_edges(G, algorithm='kruskal', weight='weight',
         msg = '{} is not a valid choice for an algorithm.'.format(algorithm)
         raise ValueError(msg)
 
-    return algo(G, minimum=True, weight=weight, keys=keys, data=data)
+    return algo(G, minimum=True, weight=weight, keys=keys, data=data,
+                ignore_nan=ignore_nan)
 
 
 @not_implemented_for('directed')
 def maximum_spanning_edges(G, algorithm='kruskal', weight='weight',
-                           keys=True, data=True):
+                           keys=True, data=True, ignore_nan=False):
     """Generate edges in a maximum spanning forest of an undirected
     weighted graph.
 
@@ -352,6 +429,10 @@ def maximum_spanning_edges(G, algorithm='kruskal', weight='weight',
     data : bool, optional
        If True yield the edge data along with the edge.
 
+    ignore_nan : bool (default: False)
+        If a NaN is found as an edge weight normally an exception is raised.
+        If `ignore_nan is True` then that edge is ignored instead.
+
     Returns
     -------
     edges : iterator
@@ -382,7 +463,7 @@ def maximum_spanning_edges(G, algorithm='kruskal', weight='weight',
     Find maximum spanning edges by Prim's algorithm
 
     >>> G = nx.cycle_graph(4)
-    >>> G.add_edge(0,3,weight=2) # assign weight 2 to edge 0-3
+    >>> G.add_edge(0, 3, weight=2) # assign weight 2 to edge 0-3
     >>> mst = tree.maximum_spanning_edges(G, algorithm='prim', data=False)
     >>> edgelist = list(mst)
     >>> sorted(edgelist)
@@ -405,10 +486,12 @@ def maximum_spanning_edges(G, algorithm='kruskal', weight='weight',
         msg = '{} is not a valid choice for an algorithm.'.format(algorithm)
         raise ValueError(msg)
 
-    return algo(G, minimum=False, weight=weight, keys=keys, data=data)
+    return algo(G, minimum=False, weight=weight, keys=keys, data=data,
+                ignore_nan=ignore_nan)
 
 
-def minimum_spanning_tree(G, weight='weight', algorithm='kruskal'):
+def minimum_spanning_tree(G, weight='weight', algorithm='kruskal',
+                          ignore_nan=False):
     """Returns a minimum spanning tree or forest on an undirected graph `G`.
 
     Parameters
@@ -425,6 +508,10 @@ def minimum_spanning_tree(G, weight='weight', algorithm='kruskal'):
        choices are 'kruskal', 'prim', or 'boruvka'. The default is
        'kruskal'.
 
+    ignore_nan : bool (default: False)
+        If a NaN is found as an edge weight normally an exception is raised.
+        If `ignore_nan is True` then that edge is ignored instead.
+
     Returns
     -------
     G : NetworkX Graph
@@ -451,7 +538,8 @@ def minimum_spanning_tree(G, weight='weight', algorithm='kruskal'):
     See :mod:`networkx.tree.recognition` for more detailed definitions.
 
     """
-    edges = minimum_spanning_edges(G, algorithm, weight, keys=True, data=True)
+    edges = minimum_spanning_edges(G, algorithm, weight, keys=True,
+                                   data=True, ignore_nan=ignore_nan)
     T = G.__class__()  # Same graph class as G
     T.graph.update(G.graph)
     T.add_nodes_from(G.node.items())
@@ -459,7 +547,8 @@ def minimum_spanning_tree(G, weight='weight', algorithm='kruskal'):
     return T
 
 
-def maximum_spanning_tree(G, weight='weight', algorithm='kruskal'):
+def maximum_spanning_tree(G, weight='weight', algorithm='kruskal',
+                          ignore_nan=False):
     """Returns a maximum spanning tree or forest on an undirected graph `G`.
 
     Parameters
@@ -476,6 +565,10 @@ def maximum_spanning_tree(G, weight='weight', algorithm='kruskal'):
        choices are 'kruskal', 'prim', or 'boruvka'. The default is
        'kruskal'.
 
+    ignore_nan : bool (default: False)
+        If a NaN is found as an edge weight normally an exception is raised.
+        If `ignore_nan is True` then that edge is ignored instead.
+
 
     Returns
     -------
@@ -504,7 +597,8 @@ def maximum_spanning_tree(G, weight='weight', algorithm='kruskal'):
     See :mod:`networkx.tree.recognition` for more detailed definitions.
 
     """
-    edges = maximum_spanning_edges(G, algorithm, weight, keys=True, data=True)
+    edges = maximum_spanning_edges(G, algorithm, weight, keys=True,
+                                   data=True, ignore_nan=ignore_nan)
     edges = list(edges)
     T = G.__class__()  # Same graph class as G
     T.graph.update(G.graph)


Test patch:
diff --git a/networkx/algorithms/tree/tests/test_mst.py b/networkx/algorithms/tree/tests/test_mst.py
index 539b6146e..509ba1f4e 100644
--- a/networkx/algorithms/tree/tests/test_mst.py
+++ b/networkx/algorithms/tree/tests/test_mst.py
@@ -11,12 +11,13 @@
 from unittest import TestCase
 
 from nose.tools import assert_equal
-from nose.tools import raises
+from nose.tools import raises, assert_raises
 
 import networkx as nx
-from networkx.testing import (assert_graphs_equal,assert_nodes_equal,
+from networkx.testing import (assert_graphs_equal, assert_nodes_equal,
                               assert_edges_equal)
 
+
 @raises(ValueError)
 def test_unknown_algorithm():
     nx.minimum_spanning_tree(nx.Graph(), algorithm='random')
@@ -84,6 +85,23 @@ class MinimumSpanningTreeTestBase(object):
         expected = [(u, v) for u, v, d in self.minimum_spanning_edgelist]
         assert_edges_equal(actual, expected)
 
+    def test_nan_weights(self):
+        # Edge weights NaN never appear in the spanning tree. see #2164
+        G = self.G
+        G.add_edge(0, 12, weight=float('nan'))
+        edges = nx.minimum_spanning_edges(G, algorithm=self.algo,
+                                          data=False, ignore_nan=True)
+        actual = sorted((min(u, v), max(u, v)) for u, v in edges)
+        expected = [(u, v) for u, v, d in self.minimum_spanning_edgelist]
+        assert_edges_equal(actual, expected)
+        # Now test for raising exception
+        edges = nx.minimum_spanning_edges(G, algorithm=self.algo,
+                                          data=False, ignore_nan=False)
+        assert_raises(ValueError, list, edges)
+        # test default for ignore_nan as False
+        edges = nx.minimum_spanning_edges(G, algorithm=self.algo, data=False)
+        assert_raises(ValueError, list, edges)
+
     def test_minimum_tree(self):
         T = nx.minimum_spanning_tree(self.G, algorithm=self.algo)
         actual = sorted(T.edges(data=True))