diff env/lib/python3.9/site-packages/networkx/algorithms/dominating.py @ 0:4f3585e2f14b draft default tip

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/env/lib/python3.9/site-packages/networkx/algorithms/dominating.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,92 @@
+"""Functions for computing dominating sets in a graph."""
+from itertools import chain
+
+import networkx as nx
+from networkx.utils import arbitrary_element
+
+__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 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)
+        Node to use as a starting point for the algorithm.
+
+    Returns
+    -------
+    D : set
+        A dominating set for G.
+
+    Notes
+    -----
+    This function is an implementation of algorithm 7 in [2]_ which
+    finds some dominating set, not necessarily the smallest one.
+
+    See also
+    --------
+    is_dominating_set
+
+    References
+    ----------
+    .. [1] https://en.wikipedia.org/wiki/Dominating_set
+
+    .. [2] Abdol-Hossein Esfahanian. Connectivity Algorithms.
+        http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
+
+    """
+    all_nodes = set(G)
+    if start_with is None:
+        start_with = arbitrary_element(all_nodes)
+    if start_with not in G:
+        raise nx.NetworkXError(f"node {start_with} is not in G")
+    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):
+    """Checks if `nbunch` is a dominating set for `G`.
+
+    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 : iterable
+        An iterable of nodes in the graph `G`.
+
+    See also
+    --------
+    dominating_set
+
+    References
+    ----------
+    .. [1] https://en.wikipedia.org/wiki/Dominating_set
+
+    """
+    testset = {n for n in nbunch if n in G}
+    nbrs = set(chain.from_iterable(G[n] for n in testset))
+    return len(set(G) - testset - nbrs) == 0