NetworkXInvalidNode exception added

11 files changed, 64 insertions, 11 deletions

diff --git a/doc/source/reference/api_2.0.rst b/doc/source/reference/api_2.0.rst
index 9e5d0088..e2604db3 100644
--- a/doc/source/reference/api_2.0.rst
+++ b/doc/source/reference/api_2.0.rst
@@ -74,3 +74,21 @@ Miscellaneous changes
 
 * [`#1192 <https://github.com/networkx/networkx/pull/1192>`_]
   Support for Python 2.6 is dropped.
+
+Algorithms changed
+==================
+
+Shortest path
+-------------
+
+single_source_shortest_path_length(), bidirectional_shortest_path(),
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+single_source_shortest_path(), predecessor(), astar_path(), 
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+astar_path_length(), bellman_ford(), goldberg_radzik(), 
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+bidirectional_dijkstra(), shortest_path_length(), all_shortest_paths()
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+   These algorithms now raise an exception when a source and a target are
+   not presented in the graph. The exception is a NetworkXInvalidNode exception.
+
diff --git a/doc/source/reference/exceptions.rst b/doc/source/reference/exceptions.rst
index e5daf195..ae95322f 100644
--- a/doc/source/reference/exceptions.rst
+++ b/doc/source/reference/exceptions.rst
@@ -17,6 +17,8 @@ Exceptions
 
 .. autoclass:: networkx.NetworkXNoPath
 
+.. autoclass:: networkx.NetworkXInvalidNode
+
 .. autoclass:: networkx.NetworkXUnbounded
 
 
diff --git a/networkx/algorithms/shortest_paths/astar.py b/networkx/algorithms/shortest_paths/astar.py
index 7e2c309c..b0e9cc37 100644
--- a/networkx/algorithms/shortest_paths/astar.py
+++ b/networkx/algorithms/shortest_paths/astar.py
@@ -67,6 +67,9 @@ def astar_path(G, source, target, heuristic=None, weight='weight'):
     shortest_path, dijkstra_path
 
     """
+    if source not in G or target not in G:
+        raise nx.NetworkXInvalidNode()
+
     if G.is_multigraph():
         raise NetworkXError("astar_path() not implemented for Multi(Di)Graphs")
 
@@ -160,5 +163,8 @@ def astar_path_length(G, source, target, heuristic=None, weight='weight'):
     astar_path
 
     """
+    if source not in G or target not in G:
+        raise nx.NetworkXInvalidNode()
+
     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 6f580b16..e13426cf 100644
--- a/networkx/algorithms/shortest_paths/generic.py
+++ b/networkx/algorithms/shortest_paths/generic.py
@@ -150,7 +150,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.
@@ -233,6 +233,9 @@ def shortest_path_length(G, source=None, target=None, weight=None):
                     paths=nx.single_source_dijkstra_path_length(G, target,
                                                                 weight=weight)
     else:
+        if source not in G:
+            raise nx.NetworkXInvalidNode;
+
         if target is None:
             ## Find paths to all nodes accessible from the source.
             if weight is None:
@@ -355,8 +358,13 @@ def all_shortest_paths(G, source, target, weight=None):
         pred,dist = nx.dijkstra_predecessor_and_distance(G,source,weight=weight)
     else:
         pred = nx.predecessor(G,source)
-    if source not in G or target not in pred:
+
+    if source not in G :
+        raise nx.NetworkXInvalidNode()
+
+    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 81ba6abc..c3445935 100644
--- a/networkx/algorithms/shortest_paths/tests/test_astar.py
+++ b/networkx/algorithms/shortest_paths/tests/test_astar.py
@@ -111,7 +111,7 @@ class TestAStar:
         assert nx.astar_path(G,'s','v')==['s', 'u', 'v']
         assert nx.astar_path_length(G,'s','v')== 2
 
-    @raises(nx.NetworkXNoPath)
+    @raises(nx.NetworkXInvalidNode)
     def test_astar_nopath(self):
         p = 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 f1c2745b..d0a00d3d 100644
--- a/networkx/algorithms/shortest_paths/tests/test_weighted.py
+++ b/networkx/algorithms/shortest_paths/tests/test_weighted.py
@@ -207,8 +207,8 @@ class TestBellmanFordAndGoldbergRadizk:
         G.add_node(0)
         assert_equal(nx.bellman_ford(G, 0), ({0: None}, {0: 0}))
         assert_equal(nx.goldberg_radzik(G, 0), ({0: None}, {0: 0}))
-        assert_raises(KeyError, nx.bellman_ford, G, 1)
-        assert_raises(KeyError, nx.goldberg_radzik, G, 1)
+        assert_raises(nx.NetworkXInvalidNode, nx.bellman_ford, G, 1)
+        assert_raises(nx.NetworkXInvalidNode, 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 1091ece3..59fd8db5 100644
--- a/networkx/algorithms/shortest_paths/unweighted.py
+++ b/networkx/algorithms/shortest_paths/unweighted.py
@@ -51,6 +51,9 @@ def single_source_shortest_path_length(G,source,cutoff=None):
     --------
     shortest_path_length
     """
+    if source not in G:
+        raise nx.NetworkXInvalidNode()
+
     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
@@ -134,6 +137,10 @@ 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:
+        raise nx.NetworkXInvalidNode()
+
     # call helper to do the real work
     results=_bidirectional_pred_succ(G,source,target)
     pred,succ,w=results
@@ -240,6 +247,9 @@ def single_source_shortest_path(G,source,cutoff=None):
     --------
     shortest_path
     """
+    if source not in G:
+        raise nx.NetworkXInvalidNode()
+
     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)
@@ -326,6 +336,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.NetworkXInvalidNode()
+
     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 fc417430..edff4255 100644
--- a/networkx/algorithms/shortest_paths/weighted.py
+++ b/networkx/algorithms/shortest_paths/weighted.py
@@ -570,7 +570,7 @@ def bellman_ford(G, source, weight='weight'):
 
     """
     if source not in G:
-        raise KeyError("Node %s is not found in the graph" % source)
+        raise nx.NetworkXInvalidNode("Node %s is not found in the graph" % source)
 
     for u, v, attr in G.selfloop_edges(data=True):
         if attr.get(weight, 1) < 0:
@@ -687,7 +687,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.NetworkXInvalidNode("Node %s is not found in the graph" % source)
 
     for u, v, attr in G.selfloop_edges(data=True):
         if attr.get(weight, 1) < 0:
@@ -909,6 +909,9 @@ def bidirectional_dijkstra(G, source, target, weight='weight'):
     shortest_path
     shortest_path_length
     """
+    if source not in G or target not in G:
+        raise nx.NetworkXInvalidNode()
+
     if source == target:
         return (0, [source])
     push = heappush
diff --git a/networkx/algorithms/simple_paths.py b/networkx/algorithms/simple_paths.py
index f72d4d25..e5b68ea3 100644
--- a/networkx/algorithms/simple_paths.py
+++ b/networkx/algorithms/simple_paths.py
@@ -65,9 +65,9 @@ def all_simple_paths(G, source, target, cutoff=None):
     all_shortest_paths, shortest_path
     """
     if source not in G:
-        raise nx.NetworkXError('source node %s not in graph'%source)
+        raise nx.NetworkXInvalidNode()
     if target not in G:
-        raise nx.NetworkXError('target node %s not in graph'%target)
+        raise nx.NetworkXInvalidNode()
     if cutoff is None:
         cutoff = len(G)-1
     if G.is_multigraph():
diff --git a/networkx/algorithms/tests/test_simple_paths.py b/networkx/algorithms/tests/test_simple_paths.py
index 268a8903..27b2c29c 100644
--- a/networkx/algorithms/tests/test_simple_paths.py
+++ b/networkx/algorithms/tests/test_simple_paths.py
@@ -60,13 +60,13 @@ def test_cutoff_zero():
     paths = nx.all_simple_paths(nx.MultiGraph(G),0,3,cutoff=0)
     assert_equal(list(list(p) for p in paths),[])
 
-@raises(nx.NetworkXError)
+@raises(nx.NetworkXInvalidNode)
 def test_source_missing():
     G = nx.Graph()
     G.add_path([1,2,3])
     paths = list(nx.all_simple_paths(nx.MultiGraph(G),0,3))
 
-@raises(nx.NetworkXError)
+@raises(nx.NetworkXInvalidNode)
 def test_target_missing():
     G = nx.Graph()
     G.add_path([1,2,3])
diff --git a/networkx/exception.py b/networkx/exception.py
index 5f13fe4c..aac0fdbb 100644
--- a/networkx/exception.py
+++ b/networkx/exception.py
@@ -42,6 +42,9 @@ class NetworkXNoPath(NetworkXUnfeasible):
     """Exception for algorithms that should return a path when running
     on graphs where such a path does not exist."""
 
+class NetworkXInvalidNode(NetworkXUnfeasible):
+    """Exception for situations when there is no specific Node in graph."""
+
 class NetworkXNoCycle(NetworkXUnfeasible):
     """Exception for algorithms that should return a cycle when running
     on graphs where such a cycle does not exist."""