Raise an Exception for disconnected Graphs in bipartite.sets

This pull request fixes #2127

When a disconnected graph is passed to `bipartite.sets` more than one
coloring solution is possible. This led to surprising results and hard
to diagnose bugs (see #2127) in algorithms that used `bipartite.sets`,
such as bipartite matching and friends. These algorithms now have a new
optional parameter that allows the user to specify the nodes in one of
the two bipartite sets, and thus allows to use disconnected graphs in
these algorithms without ambiguity.

I've added a new exception `AmbiguousSolution` in order to be more
explicit when we raise it. It might have more use cases beyond
`bipartite.sets`.

The changes in this pull request are backwards compatible for connected
graphs as the new parameter is optional. For disconnected graphs is not
backward compatible, but since the assignation of nodes to a bipartite
set depends on iteration order, that code was already subtly broken
as it would yield different results on different python versions.

1 files changed, 11 insertions, 0 deletions

diff --git a/networkx/exception.py b/networkx/exception.py
index 01aec88b..83190bdf 100644
--- a/networkx/exception.py
+++ b/networkx/exception.py
@@ -57,6 +57,17 @@ class NodeNotFound(NetworkXException):
     """Exception raised if requested node is not present in the graph"""
 
 
+class AmbiguousSolution(NetworkXException):
+    """Raised if more than one valid solution exists for an intermediary step
+    of an algorithm.
+
+    In the face of ambiguity, refuse the temptation to guess.
+    This may occur, for example, when trying to determine the
+    bipartite node sets in a disconnected bipartite graph when
+    computing bipartite matchings.
+
+    """
+
 class ExceededMaxIterations(NetworkXException):
     """Raised if a loop iterates too many times without breaking.