Repository: networkx/networkx

Issue:
Issues calculating max independent set
`Python 2.7.11`
`networkx 1.11`

I have the following directed acyclic graph:

![DAG](https://cloud.githubusercontent.com/assets/7001223/15185853/c0cba98a-1768-11e6-9ef4-ae6f87dd59e4.png)

I wanted to calculate the max independent set of the transitive closure of this DAG (the nodes colored in green).

``` python
from networkx import Graph, DiGraph, transitive_closure
from networkx.algorithms.bipartite import hopcroft_karp_matching, to_vertex_cover

# Build the DAG
G = DiGraph()
G.add_edge("A", "C")
G.add_edge("A", "B")
G.add_edge("C", "E")
G.add_edge("C", "D")
G.add_edge("E", "G")
G.add_edge("E", "F")
G.add_edge("G", "I")
G.add_edge("G", "H")

tc = transitive_closure(G)
btc = Graph()

# Create a bipartite graph based on the transitive closure of G
for v in tc.nodes_iter():
    btc.add_node((0, v))
    btc.add_node((1, v))

for u, v in tc.edges_iter():
    btc.add_edge((0, u), (1, v))

matching = hopcroft_karp_matching(btc)
vertex_cover = to_vertex_cover(btc, matching)
independent_set = set(G) - {v for _, v in vertex_cover}
```

I am expecting independent set to be `set(['B', 'D', 'F', 'I', 'H'])` but it is `set(['A', 'B', 'D', 'F', 'I', 'H'])` instead.  I am either doing something wrong, or there is a bug in the `to_vertex_cover` function.

References:
- http://cs.stackexchange.com/a/16829
- http://cs.stackexchange.com/a/10303/5323
- http://stackoverflow.com/a/10304235
- https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm
- https://en.wikipedia.org/wiki/Dilworth's_theorem
- https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory) - Konig’s theorem proves an equivalence between a maximum matching and a minimum vertex cover in bipartite graphs.  A minimum vertex cover is the complement of a maximum independent set for any graph


Discussion:

Patch:
diff --git a/networkx/algorithms/bipartite/__init__.py b/networkx/algorithms/bipartite/__init__.py
index f33c1d31a..7db5a174e 100644
--- a/networkx/algorithms/bipartite/__init__.py
+++ b/networkx/algorithms/bipartite/__init__.py
@@ -32,42 +32,21 @@ algorithm:
 True
 >>> bottom_nodes, top_nodes = bipartite.sets(B)
 
-list(top_nodes)
-[1, 2, 3, 4]
-list(bottom_nodes)
-['a', 'c', 'b']
-
 However, if the input graph is not connected, there are more than one possible
-colorations. Thus, the following result is correct:
-
->>> B.remove_edge(2,'c')
->>> nx.is_connected(B)
-False
->>> bottom_nodes, top_nodes = bipartite.sets(B)
-
-list(top_nodes)
-[1, 2, 4, 'c']
-list(bottom_nodes)
-['a', 3, 'b']
+colorations. In the face of ambiguity, we refuse the temptation to guess and
+raise an exc:`AmbiguousSolution` Exception.
 
 Using the "bipartite" node attribute, you can easily get the two node sets:
 
 >>> top_nodes = set(n for n,d in B.nodes(data=True) if d['bipartite']==0)
 >>> bottom_nodes = set(B) - top_nodes
 
-list(top_nodes)
-[1, 2, 3, 4]
-list(bottom_nodes)
-['a', 'c', 'b']
-
 So you can easily use the bipartite algorithms that require, as an argument, a
 container with all nodes that belong to one node set:
 
 >>> print(round(bipartite.density(B, bottom_nodes),2))
-0.42
+0.5
 >>> G = bipartite.projected_graph(B, top_nodes)
->>> list(G.edges())
-[(1, 2), (1, 4)]
 
 All bipartite graph generators in NetworkX build bipartite graphs with the 
 "bipartite" node attribute. Thus, you can use the same approach:
diff --git a/networkx/algorithms/bipartite/basic.py b/networkx/algorithms/bipartite/basic.py
index 917e18a1b..644dcf94a 100644
--- a/networkx/algorithms/bipartite/basic.py
+++ b/networkx/algorithms/bipartite/basic.py
@@ -139,20 +139,40 @@ def is_bipartite_node_set(G,nodes):
     return True
 
 
-def sets(G):
+def sets(G, top_nodes=None):
     """Returns bipartite node sets of graph G.
 
-    Raises an exception if the graph is not bipartite.
+    Raises an exception if the graph is not bipartite or if the input
+    graph is disconnected and thus more than one valid solution exists.
 
     Parameters
     ----------
     G : NetworkX graph
 
+    top_nodes : container
+
+      Container with all nodes in one bipartite node set. If not supplied
+      it will be computed. But if more than one solution exists an exception
+      will be raised.
+
     Returns
     -------
     (X,Y) : two-tuple of sets
        One set of nodes for each part of the bipartite graph.
 
+    Raises
+    ------
+    AmbiguousSolution : Exception
+
+      Raised if the input bipartite graph is disconnected and no container
+      with all nodes in one bipartite set is provided. When determining
+      the nodes in each bipartite set more than one valid solution is
+      possible if the input graph is disconnected.
+
+    NetworkXError: Exception
+
+      Raised if the input graph is not bipartite.
+
     Examples
     --------
     >>> from networkx.algorithms import bipartite
@@ -166,10 +186,22 @@ def sets(G):
     See Also
     --------
     color
+
     """
-    c = color(G)
-    X = set(n for n in c if c[n]) # c[n] == 1
-    Y = set(n for n in c if not c[n]) # c[n] == 0
+    if G.is_directed():
+        is_connected = nx.is_weakly_connected
+    else:
+        is_connected = nx.is_connected
+    if top_nodes is not None:
+        X = set(top_nodes)
+        Y = set(G) - X
+    else:
+        if not is_connected(G):
+            msg = 'Disconnected graph: Ambiguous solution for bipartite sets.'
+            raise nx.AmbiguousSolution(msg)
+        c = color(G)
+        X = {n for n, is_top in c.items() if is_top}
+        Y = {n for n, is_top in c.items() if not is_top}
     return (X, Y)
 
 def density(B, nodes):
diff --git a/networkx/algorithms/bipartite/covering.py b/networkx/algorithms/bipartite/covering.py
index deb864a02..44fcbf914 100644
--- a/networkx/algorithms/bipartite/covering.py
+++ b/networkx/algorithms/bipartite/covering.py
@@ -55,6 +55,8 @@ def min_edge_cover(G, matching_algorithm=None):
     is bounded by the worst-case running time of the function
     ``matching_algorithm``.
     """
+    if G.order() == 0: # Special case for the empty graph
+        return set()
     if matching_algorithm is None:
         matching_algorithm = hopcroft_karp_matching
     return _min_edge_cover(G, matching_algorithm=matching_algorithm)
diff --git a/networkx/algorithms/bipartite/matching.py b/networkx/algorithms/bipartite/matching.py
index 9c19738ab..85f40a6eb 100644
--- a/networkx/algorithms/bipartite/matching.py
+++ b/networkx/algorithms/bipartite/matching.py
@@ -53,7 +53,7 @@ __all__ = ['maximum_matching', 'hopcroft_karp_matching', 'eppstein_matching',
 INFINITY = float('inf')
 
 
-def hopcroft_karp_matching(G):
+def hopcroft_karp_matching(G, top_nodes=None):
     """Returns the maximum cardinality matching of the bipartite graph `G`.
 
     Parameters
@@ -62,6 +62,12 @@ def hopcroft_karp_matching(G):
 
       Undirected bipartite graph
 
+    top_nodes : container
+
+      Container with all nodes in one bipartite node set. If not supplied
+      it will be computed. But if more than one solution exists an exception
+      will be raised.
+
     Returns
     -------
     matches : dictionary
@@ -70,6 +76,15 @@ def hopcroft_karp_matching(G):
       ``matches[v] == w`` if node `v` is matched to node `w`. Unmatched
       nodes do not occur as a key in mate.
 
+    Raises
+    ------
+    AmbiguousSolution : Exception
+
+      Raised if the input bipartite graph is disconnected and no container
+      with all nodes in one bipartite set is provided. When determining
+      the nodes in each bipartite set more than one valid solution is
+      possible if the input graph is disconnected.
+
     Notes
     -----
 
@@ -125,7 +140,7 @@ def hopcroft_karp_matching(G):
         return True
 
     # Initialize the "global" variables that maintain state during the search.
-    left, right = bipartite_sets(G)
+    left, right = bipartite_sets(G, top_nodes)
     leftmatches = {v: None for v in left}
     rightmatches = {v: None for v in right}
     distances = {}
@@ -153,7 +168,7 @@ def hopcroft_karp_matching(G):
     return dict(itertools.chain(leftmatches.items(), rightmatches.items()))
 
 
-def eppstein_matching(G):
+def eppstein_matching(G, top_nodes=None):
     """Returns the maximum cardinality matching of the bipartite graph `G`.
 
     Parameters
@@ -162,6 +177,12 @@ def eppstein_matching(G):
 
       Undirected bipartite graph
 
+    top_nodes : container
+
+      Container with all nodes in one bipartite node set. If not supplied
+      it will be computed. But if more than one solution exists an exception
+      will be raised.
+
     Returns
     -------
     matches : dictionary
@@ -170,6 +191,15 @@ def eppstein_matching(G):
       ``matching[v] == w`` if node `v` is matched to node `w`. Unmatched
       nodes do not occur as a key in mate.
 
+    Raises
+    ------
+    AmbiguousSolution : Exception
+
+      Raised if the input bipartite graph is disconnected and no container
+      with all nodes in one bipartite set is provided. When determining
+      the nodes in each bipartite set more than one valid solution is
+      possible if the input graph is disconnected.
+
     Notes
     -----
 
@@ -186,7 +216,7 @@ def eppstein_matching(G):
     """
     # Due to its original implementation, a directed graph is needed
     # so that the two sets of bipartite nodes can be distinguished
-    left = bipartite_sets(G)[0]
+    left, right = bipartite_sets(G, top_nodes)
     G = nx.DiGraph(G.edges(left))
     # initialize greedy matching (redundant, but faster than full search)
     matching = {}
@@ -363,7 +393,7 @@ def _connected_by_alternating_paths(G, matching, targets):
                                                               targets)}
 
 
-def to_vertex_cover(G, matching):
+def to_vertex_cover(G, matching, top_nodes=None):
     """Returns the minimum vertex cover corresponding to the given maximum
     matching of the bipartite graph `G`.
 
@@ -381,6 +411,12 @@ def to_vertex_cover(G, matching):
       by, for example, :func:`maximum_matching`. The dictionary *must*
       represent the maximum matching.
 
+    top_nodes : container
+
+      Container with all nodes in one bipartite node set. If not supplied
+      it will be computed. But if more than one solution exists an exception
+      will be raised.
+ 
     Returns
     -------
 
@@ -388,6 +424,15 @@ def to_vertex_cover(G, matching):
 
       The minimum vertex cover in `G`.
 
+    Raises
+    ------
+    AmbiguousSolution : Exception
+
+      Raised if the input bipartite graph is disconnected and no container
+      with all nodes in one bipartite set is provided. When determining
+      the nodes in each bipartite set more than one valid solution is
+      possible if the input graph is disconnected.
+
     Notes
     -----
 
@@ -412,7 +457,7 @@ def to_vertex_cover(G, matching):
     """
     # This is a Python implementation of the algorithm described at
     # <https://en.wikipedia.org/wiki/K%C3%B6nig%27s_theorem_%28graph_theory%29#Proof>.
-    L, R = bipartite_sets(G)
+    L, R = bipartite_sets(G, top_nodes)
     # Let U be the set of unmatched vertices in the left vertex set.
     unmatched_vertices = set(G) - set(matching)
     U = unmatched_vertices & L
diff --git a/networkx/exception.py b/networkx/exception.py
index 01aec88b1..83190bdff 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.
 


Test patch:
diff --git a/networkx/algorithms/bipartite/tests/test_basic.py b/networkx/algorithms/bipartite/tests/test_basic.py
index ec4799865..d33fe6bc6 100644
--- a/networkx/algorithms/bipartite/tests/test_basic.py
+++ b/networkx/algorithms/bipartite/tests/test_basic.py
@@ -28,10 +28,30 @@ class TestBipartiteBasic:
         assert_true(bipartite.is_bipartite(G))
 
     def test_bipartite_sets(self):
+        G = nx.path_graph(4)
+        X, Y = bipartite.sets(G)
+        assert_equal(X, {0, 2})
+        assert_equal(Y, {1, 3})
+
+    def test_bipartite_sets_directed(self):
+        G = nx.path_graph(4)
+        D = G.to_directed()
+        X, Y = bipartite.sets(D)
+        assert_equal(X, {0, 2})
+        assert_equal(Y, {1, 3})
+
+    def test_bipartite_sets_given_top_nodes(self):
         G=nx.path_graph(4)
-        X,Y=bipartite.sets(G)
-        assert_equal(X,set([0,2]))
-        assert_equal(Y,set([1,3]))
+        top_nodes = [0, 2]
+        X, Y = bipartite.sets(G, top_nodes)
+        assert_equal(X, {0, 2})
+        assert_equal(Y, {1, 3})
+
+    @raises(nx.AmbiguousSolution)
+    def test_bipartite_sets_disconnected(self):
+        G = nx.path_graph(4)
+        G.add_edges_from([(5, 6), (6, 7)])
+        X, Y = bipartite.sets(G)
 
     def test_is_bipartite_node_set(self):
         G=nx.path_graph(4)
diff --git a/networkx/algorithms/bipartite/tests/test_generators.py b/networkx/algorithms/bipartite/tests/test_generators.py
index 5ae64e4a9..41551c074 100644
--- a/networkx/algorithms/bipartite/tests/test_generators.py
+++ b/networkx/algorithms/bipartite/tests/test_generators.py
@@ -204,7 +204,7 @@ class TestGeneratorsBipartite():
     def test_gnmk_random_graph(self):
         n = 10
         m = 20
-        edges = 100
+        edges = 200
         G = gnmk_random_graph(n, m, edges)
         assert_equal(len(G),30)
         assert_true(is_bipartite(G))
@@ -213,4 +213,3 @@ class TestGeneratorsBipartite():
         assert_equal(set(range(n)),X)
         assert_equal(set(range(n,n+m)),Y)
         assert_equal(edges, len(list(G.edges())))
-
diff --git a/networkx/algorithms/bipartite/tests/test_matching.py b/networkx/algorithms/bipartite/tests/test_matching.py
index 890d46e60..c30582a19 100644
--- a/networkx/algorithms/bipartite/tests/test_matching.py
+++ b/networkx/algorithms/bipartite/tests/test_matching.py
@@ -11,7 +11,7 @@ import itertools
 
 import networkx as nx
 
-from nose.tools import assert_true
+from nose.tools import assert_true, assert_equal, raises
 
 from networkx.algorithms.bipartite.matching import eppstein_matching
 from networkx.algorithms.bipartite.matching import hopcroft_karp_matching
@@ -30,12 +30,47 @@ class TestMatching():
         vertices and the next six numbers are the right vertices.
 
         """
+        self.simple_graph = nx.complete_bipartite_graph(2, 3)
+        self.simple_solution = {0: 2, 1: 3, 2: 0, 3: 1}
+
         edges = [(0, 7), (0, 8), (2, 6), (2, 9), (3, 8), (4, 8), (4, 9),
                  (5, 11)]
+        self.top_nodes = set(range(6))
         self.graph = nx.Graph()
         self.graph.add_nodes_from(range(12))
         self.graph.add_edges_from(edges)
 
+        # Example bipartite graph from issue 2127
+        G = nx.Graph()
+        G.add_nodes_from([
+            (1, 'C'), (1, 'B'), (0, 'G'), (1, 'F'),
+            (1, 'E'), (0, 'C'), (1, 'D'), (1, 'I'),
+            (0, 'A'), (0, 'D'), (0, 'F'), (0, 'E'),
+            (0, 'H'), (1, 'G'), (1, 'A'), (0, 'I'),
+            (0, 'B'), (1, 'H'),
+        ])
+        G.add_edge((1, 'C'), (0, 'A'))
+        G.add_edge((1, 'B'), (0, 'A'))
+        G.add_edge((0, 'G'), (1, 'I'))
+        G.add_edge((0, 'G'), (1, 'H'))
+        G.add_edge((1, 'F'), (0, 'A'))
+        G.add_edge((1, 'F'), (0, 'C'))
+        G.add_edge((1, 'F'), (0, 'E'))
+        G.add_edge((1, 'E'), (0, 'A'))
+        G.add_edge((1, 'E'), (0, 'C'))
+        G.add_edge((0, 'C'), (1, 'D'))
+        G.add_edge((0, 'C'), (1, 'I'))
+        G.add_edge((0, 'C'), (1, 'G'))
+        G.add_edge((0, 'C'), (1, 'H'))
+        G.add_edge((1, 'D'), (0, 'A'))
+        G.add_edge((1, 'I'), (0, 'A'))
+        G.add_edge((1, 'I'), (0, 'E'))
+        G.add_edge((0, 'A'), (1, 'G'))
+        G.add_edge((0, 'A'), (1, 'H'))
+        G.add_edge((0, 'E'), (1, 'G'))
+        G.add_edge((0, 'E'), (1, 'H'))
+        self.disconnected_graph = G
+
     def check_match(self, matching):
         """Asserts that the matching is what we expect from the bipartite graph
         constructed in the :meth:`setup` fixture.
@@ -70,21 +105,67 @@ class TestMatching():
         algorithm produces a maximum cardinality matching.
 
         """
-        self.check_match(eppstein_matching(self.graph))
+        self.check_match(eppstein_matching(self.graph, self.top_nodes))
 
     def test_hopcroft_karp_matching(self):
         """Tests that the Hopcroft--Karp algorithm produces a maximum
         cardinality matching in a bipartite graph.
 
         """
-        self.check_match(hopcroft_karp_matching(self.graph))
+        self.check_match(hopcroft_karp_matching(self.graph, self.top_nodes))
 
     def test_to_vertex_cover(self):
         """Test for converting a maximum matching to a minimum vertex cover."""
-        matching = maximum_matching(self.graph)
-        vertex_cover = to_vertex_cover(self.graph, matching)
+        matching = maximum_matching(self.graph, self.top_nodes)
+        vertex_cover = to_vertex_cover(self.graph, matching, self.top_nodes)
         self.check_vertex_cover(vertex_cover)
 
+    def test_eppstein_matching_simple(self):
+        match = eppstein_matching(self.simple_graph)
+        assert_equal(match, self.simple_solution)
+
+    def test_hopcroft_karp_matching_simple(self):
+        match = hopcroft_karp_matching(self.simple_graph)
+        assert_equal(match, self.simple_solution)
+
+    @raises(nx.AmbiguousSolution)
+    def test_eppstein_matching_disconnected(self):
+        match = eppstein_matching(self.disconnected_graph)
+
+    @raises(nx.AmbiguousSolution)
+    def test_hopcroft_karp_matching_disconnected(self):
+        match = hopcroft_karp_matching(self.disconnected_graph)
+
+    def test_issue_2127(self):
+        """Test from issue 2127"""
+        # Build the example DAG
+        G = nx.DiGraph()
+        G.add_edge("A", "C")
+        G.add_edge("A", "B")
+        G.add_edge("C", "E")
+        G.add_edge("C", "D")
+        G.add_edge("E", "G")
+        G.add_edge("E", "F")
+        G.add_edge("G", "I")
+        G.add_edge("G", "H")
+
+        tc = nx.transitive_closure(G)
+        btc = nx.Graph()
+
+        # Create a bipartite graph based on the transitive closure of G
+        for v in tc.nodes():
+            btc.add_node((0, v))
+            btc.add_node((1, v))
+
+        for u, v in tc.edges():
+            btc.add_edge((0, u), (1, v))
+
+        top_nodes = {n for n in btc if n[0]==0}
+        matching = hopcroft_karp_matching(btc, top_nodes)
+        vertex_cover = to_vertex_cover(btc, matching, top_nodes)
+        independent_set = set(G) - {v for _, v in vertex_cover}
+        assert_equal({'B', 'D', 'F', 'I', 'H'}, independent_set)
+
 
 def test_eppstein_matching():
     """Test in accordance to issue #1927"""