xhs-note-crawling/python/py/Lib/site-packages/networkx/algorithms/dominating.py

"""Functions for computing dominating sets in a graph."""

import math
from heapq import heappop, heappush
from itertools import chain, count

import networkx as nx

__all__ = [
    "dominating_set",
    "is_dominating_set",
    "connected_dominating_set",
    "is_connected_dominating_set",
]


@nx._dispatchable
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 = nx.utils.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_nbrs = 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_nbrs
        remaining_nodes -= undominated_nbrs
    return dominating_set


@nx._dispatchable
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`.

    Returns
    -------
    dominating : bool
        True if `nbunch` is a dominating set of `G`, false otherwise.

    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


@nx.utils.not_implemented_for("directed")
@nx._dispatchable
def connected_dominating_set(G):
    """Returns a connected dominating set.

    A *dominating set* for a graph *G* 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]_. A *connected dominating set* is a dominating set *C* that induces a
    connected subgraph of *G* [2]_.
    Note that connected dominating sets are not unique in general and that there
    may be other connected dominating sets.

    Parameters
    ----------
    G : NewtorkX graph
        Undirected connected graph.

    Returns
    -------
    connected_dominating_set : set
        A dominating set of nodes which induces a connected subgraph of G.

    Raises
    ------
    NetworkXNotImplemented
        If G is directed.

    NetworkXError
        If G is disconnected.

    Examples
    ________
    >>> G = nx.Graph(
    ...     [
    ...         (1, 2),
    ...         (1, 3),
    ...         (1, 4),
    ...         (1, 5),
    ...         (1, 6),
    ...         (2, 7),
    ...         (3, 8),
    ...         (4, 9),
    ...         (5, 10),
    ...         (6, 11),
    ...         (7, 12),
    ...         (8, 12),
    ...         (9, 12),
    ...         (10, 12),
    ...         (11, 12),
    ...     ]
    ... )
    >>> nx.connected_dominating_set(G)
    {1, 2, 3, 4, 5, 6, 7}

    Notes
    -----
    This function implements Algorithm I in its basic version as described
    in [3]_. The idea behind the algorithm is the following: grow a tree *T*,
    starting from a node with maximum degree. Throughout the growing process,
    nonleaf nodes in *T* are our connected dominating set (CDS), leaf nodes in
    *T* are marked as "seen" and nodes in G that are not yet in *T* are marked as
    "unseen". We maintain a max-heap of all "seen" nodes, and track the number
    of "unseen" neighbors for each node. At each step we pop the heap top -- a
    "seen" (leaf) node with maximal number of "unseen" neighbors, add it to the
    CDS and mark all its "unseen" neighbors as "seen". For each one of the newly
    created "seen" nodes, we also decrement the number of "unseen" neighbors for
    all its neighbors. The algorithm terminates when there are no more "unseen"
    nodes.
    Runtime complexity of this implementation is $O(|E|*log|V|)$ (amortized).

    References
    ----------
    .. [1] https://en.wikipedia.org/wiki/Dominating_set
    .. [2] https://en.wikipedia.org/wiki/Connected_dominating_set
    .. [3] Guha, S. and Khuller, S.
           *Approximation Algorithms for Connected Dominating Sets*,
           Algorithmica, 20, 374-387, 1998.

    """
    if len(G) == 0:
        return set()

    if not nx.is_connected(G):
        raise nx.NetworkXError("G must be a connected graph")

    if len(G) == 1:
        return set(G)

    G_succ = G._adj  # For speed-up

    # Use the count c to avoid comparing nodes
    c = count()

    # Keep track of the number of unseen nodes adjacent to each node
    unseen_degree = dict(G.degree)

    # Find node with highest degree and update its neighbors
    (max_deg_node, max_deg) = max(unseen_degree.items(), key=lambda x: x[1])
    for nbr in G_succ[max_deg_node]:
        unseen_degree[nbr] -= 1

    # Initially all nodes except max_deg_node are unseen
    unseen = set(G) - {max_deg_node}

    # We want a max-heap of the unseen-degree using heapq, which is a min-heap
    # So we store the negative of the unseen-degree
    seen = [(-max_deg, next(c), max_deg_node)]

    connected_dominating_set = set()

    # Main loop
    while unseen:
        (neg_deg, cnt, u) = heappop(seen)
        # Check if u's unseen-degree changed while in the heap
        if -neg_deg > unseen_degree[u]:
            heappush(seen, (-unseen_degree[u], cnt, u))
            continue
        # Mark all u's unseen neighbors as seen and add them to the heap
        for v in G_succ[u]:
            if v in unseen:
                unseen.remove(v)
                for nbr in G_succ[v]:
                    unseen_degree[nbr] -= 1
                heappush(seen, (-unseen_degree[v], next(c), v))
        # Add u to the dominating set
        connected_dominating_set.add(u)

    return connected_dominating_set


@nx.utils.not_implemented_for("directed")
@nx._dispatchable
def is_connected_dominating_set(G, nbunch):
    """Checks if `nbunch` is a connected dominating set for `G`.

    A *dominating set* for a graph *G* 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]_. A *connected dominating set* is a dominating
    set *C* that induces a connected subgraph of *G* [2]_.

    Parameters
    ----------
    G : NetworkX graph
        Undirected graph.

    nbunch : iterable
        An iterable of nodes in the graph `G`.

    Returns
    -------
    connected_dominating : bool
        True if `nbunch` is connected dominating set of `G`, false otherwise.

    References
    ----------
    .. [1] https://en.wikipedia.org/wiki/Dominating_set
    .. [2] https://en.wikipedia.org/wiki/Connected_dominating_set

    """
    return nx.is_dominating_set(G, nbunch) and nx.is_connected(nx.subgraph(G, nbunch))