Skip to main content
`Ctrl`+`K`

# Source code for networkx.algorithms.approximation.dominating_set

    """Functions for finding node and edge dominating sets.

    A `dominating set`_ for an undirected graph *G* with vertex set *V*
    and edge set *E* is a subset *D* of *V* such that every vertex not in
    *D* is adjacent to at least one member of *D*. An `edge dominating set`_
    is a subset *F* of *E* such that every edge not in *F* is
    incident to an endpoint of at least one edge in *F*.

    .. _dominating set: https://en.wikipedia.org/wiki/Dominating_set
    .. _edge dominating set: https://en.wikipedia.org/wiki/Edge_dominating_set

    """

    import networkx as nx

    from ...utils import not_implemented_for
    from ..matching import maximal_matching

    __all__ = ["min_weighted_dominating_set", "min_edge_dominating_set"]

    # TODO Why doesn't this algorithm work for directed graphs?

    @not_implemented_for("directed")
    @nx._dispatchable(node_attrs="weight")
    def min_weighted_dominating_set(G, weight=None):
        r"""Returns a dominating set that approximates the minimum weight node
        dominating set.

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

        weight : string
            The node attribute storing the weight of an node. If provided,
            the node attribute with this key must be a number for each
            node. If not provided, each node is assumed to have weight one.

        Returns
        -------
        min_weight_dominating_set : set
            A set of nodes, the sum of whose weights is no more than `(\log
            w(V)) w(V^*)`, where `w(V)` denotes the sum of the weights of
            each node in the graph and `w(V^*)` denotes the sum of the
            weights of each node in the minimum weight dominating set.

        Examples
        --------
        >>> G = nx.Graph([(0, 1), (0, 4), (1, 4), (1, 2), (2, 3), (3, 4), (2, 5)])
        >>> nx.approximation.min_weighted_dominating_set(G)
        {1, 2, 4}

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

        Notes
        -----
        This algorithm computes an approximate minimum weighted dominating
        set for the graph `G`. The returned solution has weight `(\log
        w(V)) w(V^*)`, where `w(V)` denotes the sum of the weights of each
        node in the graph and `w(V^*)` denotes the sum of the weights of
        each node in the minimum weight dominating set for the graph.

        This implementation of the algorithm runs in $O(m)$ time, where $m$
        is the number of edges in the graph.

        References
        ----------
        .. [1] Vazirani, Vijay V.
               *Approximation Algorithms*.
               Springer Science & Business Media, 2001.

        """
        # The unique dominating set for the null graph is the empty set.
        if len(G) == 0:
            return set()

        # This is the dominating set that will eventually be returned.
        dom_set = set()

        def _cost(node_and_neighborhood):
            """Returns the cost-effectiveness of greedily choosing the given
            node.

            `node_and_neighborhood` is a two-tuple comprising a node and its
            closed neighborhood.

            """
            v, neighborhood = node_and_neighborhood
            return G.nodes[v].get(weight, 1) / len(neighborhood - dom_set)

        # This is a set of all vertices not already covered by the
        # dominating set.
        vertices = set(G)
        # This is a dictionary mapping each node to the closed neighborhood
        # of that node.
        neighborhoods = {v: {v} | set(G[v]) for v in G}

        # Continue until all vertices are adjacent to some node in the
        # dominating set.
        while vertices:
            # Find the most cost-effective node to add, along with its
            # closed neighborhood.
            dom_node, min_set = min(neighborhoods.items(), key=_cost)
            # Add the node to the dominating set and reduce the remaining
            # set of nodes to cover.
            dom_set.add(dom_node)
            del neighborhoods[dom_node]
            vertices -= min_set

        return dom_set

    @nx._dispatchable
    def min_edge_dominating_set(G):
        r"""Returns minimum cardinality edge dominating set.

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

        Returns
        -------
        min_edge_dominating_set : set
          Returns a set of dominating edges whose size is no more than 2 * OPT.

        Examples
        --------
        >>> G = nx.petersen_graph()
        >>> nx.approximation.min_edge_dominating_set(G)
        {(0, 1), (4, 9), (6, 8), (5, 7), (2, 3)}

        Raises
        ------
        ValueError
            If the input graph `G` is empty.

        Notes
        -----
        The algorithm computes an approximate solution to the edge dominating set
        problem. The result is no more than 2 * OPT in terms of size of the set.
        Runtime of the algorithm is $O(|E|)$.
        """
        if not G:
            raise ValueError("Expected non-empty NetworkX graph!")
        return maximal_matching(G)