Fix conflict for #1445 and use NodeNotFound exception

8 files changed, 47 insertions, 7 deletions

diff --git a/doc/source/reference/exceptions.rst b/doc/source/reference/exceptions.rst
index e5daf195..0b44a57c 100644
--- a/doc/source/reference/exceptions.rst
+++ b/doc/source/reference/exceptions.rst
@@ -17,6 +17,8 @@ Exceptions
 
 .. autoclass:: networkx.NetworkXNoPath
 
+.. autoclass:: networkx.NodeNotFound
+
 .. autoclass:: networkx.NetworkXUnbounded
 
 
diff --git a/doc/source/reference/release_2.0.rst b/doc/source/reference/release_2.0.rst
index f511f4f5..e1ce5d12 100644
--- a/doc/source/reference/release_2.0.rst
+++ b/doc/source/reference/release_2.0.rst
@@ -92,3 +92,8 @@ API changes
        # recommended
        >>> tree.minimum_spanning_tree(G, algorithm='kruskal', weight='mass')
        >>> tree.minimum_spanning_edges(G, algorithm='prim', weight='mass')
+
+* [`#1445 <https://github.com/networkx/networkx/pull/1445>`_]
+   Most of the shortest_path algorithms now raise a NodeNotFound exception
+   when a source or a target are not present in the graph.
+
diff --git a/networkx/algorithms/shortest_paths/astar.py b/networkx/algorithms/shortest_paths/astar.py
index 0c8cec70..3ec06460 100644
--- a/networkx/algorithms/shortest_paths/astar.py
+++ b/networkx/algorithms/shortest_paths/astar.py
@@ -14,7 +14,6 @@ from heapq import heappush, heappop
 from itertools import count
 
 import networkx as nx
-from networkx import NetworkXError
 from networkx.utils import not_implemented_for
 
 __all__ = ['astar_path', 'astar_path_length']
@@ -69,6 +68,10 @@ def astar_path(G, source, target, heuristic=None, weight='weight'):
     shortest_path, dijkstra_path
 
     """
+    if source not in G or target not in G:
+        msg = 'Either source {} or target {} is not in G'
+        raise nx.NodeNotFound(msg.format(source, target))
+
     if heuristic is None:
         # The default heuristic is h=0 - same as Dijkstra's algorithm
         def heuristic(u, v):
@@ -159,5 +162,9 @@ def astar_path_length(G, source, target, heuristic=None, weight='weight'):
     astar_path
 
     """
+    if source not in G or target not in G:
+        msg = 'Either source {} or target {} is not in G'
+        raise nx.NodeNotFound(msg.format(source, target))
+
     path = astar_path(G, source, target, heuristic, weight)
     return sum(G[u][v].get(weight, 1) for u, v in zip(path[:-1], path[1:]))
diff --git a/networkx/algorithms/shortest_paths/generic.py b/networkx/algorithms/shortest_paths/generic.py
index 7261b2d7..3742b383 100644
--- a/networkx/algorithms/shortest_paths/generic.py
+++ b/networkx/algorithms/shortest_paths/generic.py
@@ -156,7 +156,7 @@ def shortest_path_length(G, source=None, target=None, weight=None):
     source : node, optional
         Starting node for path.
         If not specified, compute shortest path lengths using all nodes as
-        source nodes.
+        source nodes.i
 
     target : node, optional
         Ending node for path.
@@ -244,6 +244,9 @@ def shortest_path_length(G, source=None, target=None, weight=None):
                     path_length = nx.single_source_dijkstra_path_length
                     paths = path_length(G, target, weight=weight)
     else:
+        if source not in G:
+            raise nx.NodeNotFound("Source {} not in G".format(source));
+
         if target is None:
             # Find paths to all nodes accessible from the source.
             if weight is None:
@@ -380,8 +383,13 @@ def all_shortest_paths(G, source, target, weight=None):
                                                           weight=weight)
     else:
         pred = nx.predecessor(G, source)
+
+    if source not in G :
+        raise nx.NodeNotFound('Source {} is not in G'.format(source))
+
     if target not in pred:
         raise nx.NetworkXNoPath()
+
     stack = [[target, 0]]
     top = 0
     while top >= 0:
diff --git a/networkx/algorithms/shortest_paths/tests/test_astar.py b/networkx/algorithms/shortest_paths/tests/test_astar.py
index e9acc8b4..4c279c2a 100644
--- a/networkx/algorithms/shortest_paths/tests/test_astar.py
+++ b/networkx/algorithms/shortest_paths/tests/test_astar.py
@@ -100,7 +100,7 @@ class TestAStar:
         assert_equal(nx.astar_path(G, 's', 'v'), ['s', 'u', 'v'])
         assert_equal(nx.astar_path_length(G, 's', 'v'), 2)
 
-    @raises(nx.NetworkXNoPath)
+    @raises(nx.NodeNotFound)
     def test_astar_nopath(self):
         nx.astar_path(self.XG, 's', 'moon')
 
diff --git a/networkx/algorithms/shortest_paths/tests/test_weighted.py b/networkx/algorithms/shortest_paths/tests/test_weighted.py
index 5c49eb8a..f177a7ff 100644
--- a/networkx/algorithms/shortest_paths/tests/test_weighted.py
+++ b/networkx/algorithms/shortest_paths/tests/test_weighted.py
@@ -306,8 +306,8 @@ class TestBellmanFordAndGoldbergRadzik(WeightedTestBase):
         assert_equal(nx.single_source_bellman_ford(G, 0), ({0: 0}, {0: [0]}))
         assert_equal(nx.bellman_ford_predecessor_and_distance(G, 0), ({0: [None]}, {0: 0}))
         assert_equal(nx.goldberg_radzik(G, 0), ({0: None}, {0: 0}))
-        assert_raises(KeyError, nx.bellman_ford_predecessor_and_distance, G, 1)
-        assert_raises(KeyError, nx.goldberg_radzik, G, 1)
+        assert_raises(nx.NodeNotFound, nx.bellman_ford_predecessor_and_distance, G, 1)
+        assert_raises(nx.NodeNotFound, nx.goldberg_radzik, G, 1)
 
     def test_negative_weight_cycle(self):
         G = nx.cycle_graph(5, create_using=nx.DiGraph())
diff --git a/networkx/algorithms/shortest_paths/unweighted.py b/networkx/algorithms/shortest_paths/unweighted.py
index 6629932d..341a4c14 100644
--- a/networkx/algorithms/shortest_paths/unweighted.py
+++ b/networkx/algorithms/shortest_paths/unweighted.py
@@ -49,9 +49,12 @@ def single_source_shortest_path_length(G,source,cutoff=None):
     --------
     shortest_path_length
     """
+    if source not in G:
+        raise nx.NodeNotFound('Source {} is not in G'.format(source))
     seen = {}                  # level (number of hops) when seen in BFS
     level = 0                  # the current level
     nextlevel = {source:1}  # dict of nodes to check at next level
+
     while nextlevel:
         thislevel = nextlevel  # advance to next level
         nextlevel = {}         # and start a new list (fringe)
@@ -131,6 +134,11 @@ def bidirectional_shortest_path(G,source,target):
     -----
     This algorithm is used by shortest_path(G,source,target).
     """
+
+    if source not in G or target not in G:
+        msg = 'Either source {} or target {} is not in G'
+        raise nx.NodeNotFound(msg.format(source, target))
+
     # call helper to do the real work
     results=_bidirectional_pred_succ(G,source,target)
     pred,succ,w=results
@@ -237,6 +245,9 @@ def single_source_shortest_path(G,source,cutoff=None):
     --------
     shortest_path
     """
+    if source not in G:
+        raise nx.NodeNotFound("Source {} not in G".format(source));
+
     level=0                  # the current level
     nextlevel={source:1}       # list of nodes to check at next level
     paths={source:[source]}  # paths dictionary  (paths to key from source)
@@ -320,6 +331,9 @@ def predecessor(G,source,target=None,cutoff=None,return_seen=None):
     {0: [], 1: [0], 2: [1], 3: [2]}
 
     """
+    if source not in G:
+        raise nx.NodeNotFound("Source {} not in G".format(source));
+
     level=0                  # the current level
     nextlevel=[source]       # list of nodes to check at next level
     seen={source:level}      # level (number of hops) when seen in BFS
diff --git a/networkx/algorithms/shortest_paths/weighted.py b/networkx/algorithms/shortest_paths/weighted.py
index 594d0d1c..92223786 100644
--- a/networkx/algorithms/shortest_paths/weighted.py
+++ b/networkx/algorithms/shortest_paths/weighted.py
@@ -1003,7 +1003,7 @@ def bellman_ford_predecessor_and_distance(G, source, target=None, cutoff=None, w
 
     """
     if source not in G:
-        raise KeyError("Node %s is not found in the graph" % source)
+        raise nx.NodeNotFound("Node %s is not found in the graph" % source)
     weight = _weight_function(G, weight)
     if any(weight(u, v, d) < 0 for u, v, d in G.selfloop_edges(data=True)):
         raise nx.NetworkXUnbounded("Negative cost cycle detected.")
@@ -1532,7 +1532,7 @@ def goldberg_radzik(G, source, weight='weight'):
 
     """
     if source not in G:
-        raise KeyError("Node %s is not found in the graph" % source)
+        raise nx.NodeNotFound("Node %s is not found in the graph" % source)
     weight = _weight_function(G, weight)
     if any(weight(u, v, d) < 0 for u, v, d in G.selfloop_edges(data=True)):
         raise nx.NetworkXUnbounded("Negative cost cycle detected.")
@@ -1767,6 +1767,10 @@ def bidirectional_dijkstra(G, source, target, weight='weight'):
     shortest_path
     shortest_path_length
     """
+    if source not in G or target not in G:
+        msg = 'Either source {} or target {} is not in G'
+        raise nx.NodeNotFound(msg.format(source, target))
+
     if source == target:
         return (0, [source])
     push = heappush