Merge pull request #1684 from jfinkels/simplify-is-dominating-set

Simplifies dominating set functions.

1 files changed, 37 insertions, 33 deletions

diff --git a/networkx/algorithms/dominating.py b/networkx/algorithms/dominating.py
index b53bf2f7..d8712601 100644
--- a/networkx/algorithms/dominating.py
+++ b/networkx/algorithms/dominating.py
@@ -1,21 +1,26 @@
 # -*- coding: utf-8 -*-
+"""Functions for computing dominating sets in a graph."""
+from itertools import chain
+
 import networkx as nx
+from networkx.utils import arbitrary_element
+
 __author__ = '\n'.join(['Jordi Torrents <jtorrents@milnou.net>'])
-__all__ = [ 'dominating_set', 'is_dominating_set']
+__all__ = ['dominating_set', 'is_dominating_set']
+
 
 def dominating_set(G, start_with=None):
     r"""Finds a dominating set for the graph G.
 
-    A dominating set for a graph `G = (V, E)` is a node subset `D` of `V`
-    such that every node not in `D` is adjacent to at least one member
-    of `D` [1]_.
+    A *dominating set* for a graph with node set *V* is a subset *D* of
+    *V* such that every node not in *D* is adjacent to at least one
+    member of *D* [1]_.
 
     Parameters
     ----------
-
     G : NetworkX graph
 
-    start_with : Node (default=None)
+    start_with : node (default=None)
         Node to use as a starting point for the algorithm.
 
     Returns
@@ -42,34 +47,38 @@ def dominating_set(G, start_with=None):
     """
     all_nodes = set(G)
     if start_with is None:
-        v = set(G).pop() # pick a node
-    else:
-        if start_with not in G:
-            raise nx.NetworkXError('node %s not in G' % start_with)
-        v = start_with
-    D = set([v])
-    ND = set(G[v])
-    other = all_nodes - ND - D
-    while other:
-        w = other.pop()
-        D.add(w)
-        ND.update([nbr for nbr in G[w] if nbr not in D])
-        other = all_nodes - ND - D
-    return D
+        start_with = arbitrary_element(all_nodes)
+    if start_with not in G:
+        raise nx.NetworkXError('node {} is not in G'.format(start_with))
+    dominating_set = {start_with}
+    dominated_nodes = set(G[start_with])
+    remaining_nodes = all_nodes - dominated_nodes - dominating_set
+    while remaining_nodes:
+        # Choose an arbitrary node and determine its undominated neighbors.
+        v = remaining_nodes.pop()
+        undominated_neighbors = set(G[v]) - dominating_set
+        # Add the node to the dominating set and the neighbors to the
+        # dominated set. Finally, remove all of those nodes from the set
+        # of remaining nodes.
+        dominating_set.add(v)
+        dominated_nodes |= undominated_neighbors
+        remaining_nodes -= undominated_neighbors
+    return dominating_set
+
 
 def is_dominating_set(G, nbunch):
-    r"""Checks if nodes in nbunch are a dominating set for G.
+    """Checks if ``nbunch`` is a dominating set for ``G``.
 
-    A dominating set for a graph `G = (V, E)` is a node subset `D` of `V`
-    such that every node not in `D` is adjacent to at least one member
-    of `D` [1]_.
+    A *dominating set* for a graph with node set *V* is a subset *D* of
+    *V* such that every node not in *D* is adjacent to at least one
+    member of *D* [1]_.
 
     Parameters
     ----------
-
     G : NetworkX graph
 
-    nbunch : Node container
+    nbunch : iterable
+        An iterable of nodes in the graph ``G``.
 
     See also
     --------
@@ -81,10 +90,5 @@ def is_dominating_set(G, nbunch):
 
     """
     testset = set(n for n in nbunch if n in G)
-    nbrs = set()
-    for n in testset:
-        nbrs.update(G[n])
-    if len(set(G) - testset - nbrs) > 0:
-        return False
-    else:
-        return True
+    nbrs = set(chain.from_iterable(G[n] for n in testset))
+    return len(set(G) - testset - nbrs) == 0