Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / dominating.py @ 5cef0f13

History | View | Annotate | Download (2.68 KB)

1
# -*- coding: utf-8 -*-
2
"""Functions for computing dominating sets in a graph."""
3
from itertools import chain
4

    
5
import networkx as nx
6
from networkx.utils import arbitrary_element
7

    
8
__author__ = '\n'.join(['Jordi Torrents <jtorrents@milnou.net>'])
9
__all__ = ['dominating_set', 'is_dominating_set']
10

    
11

    
12
def dominating_set(G, start_with=None):
13
    r"""Finds a dominating set for the graph G.
14

15
    A *dominating set* for a graph with node set *V* is a subset *D* of
16
    *V* such that every node not in *D* is adjacent to at least one
17
    member of *D* [1]_.
18

19
    Parameters
20
    ----------
21
    G : NetworkX graph
22

23
    start_with : node (default=None)
24
        Node to use as a starting point for the algorithm.
25

26
    Returns
27
    -------
28
    D : set
29
        A dominating set for G.
30

31
    Notes
32
    -----
33
    This function is an implementation of algorithm 7 in [2]_ which
34
    finds some dominating set, not necessarily the smallest one.
35

36
    See also
37
    --------
38
    is_dominating_set
39

40
    References
41
    ----------
42
    .. [1] https://en.wikipedia.org/wiki/Dominating_set
43

44
    .. [2] Abdol-Hossein Esfahanian. Connectivity Algorithms.
45
        http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
46

47
    """
48
    all_nodes = set(G)
49
    if start_with is None:
50
        start_with = arbitrary_element(all_nodes)
51
    if start_with not in G:
52
        raise nx.NetworkXError('node {} is not in G'.format(start_with))
53
    dominating_set = {start_with}
54
    dominated_nodes = set(G[start_with])
55
    remaining_nodes = all_nodes - dominated_nodes - dominating_set
56
    while remaining_nodes:
57
        # Choose an arbitrary node and determine its undominated neighbors.
58
        v = remaining_nodes.pop()
59
        undominated_neighbors = set(G[v]) - dominating_set
60
        # Add the node to the dominating set and the neighbors to the
61
        # dominated set. Finally, remove all of those nodes from the set
62
        # of remaining nodes.
63
        dominating_set.add(v)
64
        dominated_nodes |= undominated_neighbors
65
        remaining_nodes -= undominated_neighbors
66
    return dominating_set
67

    
68

    
69
def is_dominating_set(G, nbunch):
70
    """Checks if `nbunch` is a dominating set for `G`.
71

72
    A *dominating set* for a graph with node set *V* is a subset *D* of
73
    *V* such that every node not in *D* is adjacent to at least one
74
    member of *D* [1]_.
75

76
    Parameters
77
    ----------
78
    G : NetworkX graph
79

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

83
    See also
84
    --------
85
    dominating_set
86

87
    References
88
    ----------
89
    .. [1] https://en.wikipedia.org/wiki/Dominating_set
90

91
    """
92
    testset = set(n for n in nbunch if n in G)
93
    nbrs = set(chain.from_iterable(G[n] for n in testset))
94
    return len(set(G) - testset - nbrs) == 0