Mercurial > repos > shellac > sam_consensus_v3

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

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author shellac
date Mon, 22 Mar 2021 18:12:50 +0000
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:4f3585e2f14b
1 """Functions for computing dominating sets in a graph."""
2 from itertools import chain
3
4 import networkx as nx
5 from networkx.utils import arbitrary_element
6
7 __all__ = ["dominating_set", "is_dominating_set"]
8
9
10 def dominating_set(G, start_with=None):
11 r"""Finds a dominating set for the graph G.
12
13 A *dominating set* for a graph with node set *V* is a subset *D* of
14 *V* such that every node not in *D* is adjacent to at least one
15 member of *D* [1]_.
16
17 Parameters
18 ----------
19 G : NetworkX graph
20
21 start_with : node (default=None)
22 Node to use as a starting point for the algorithm.
23
24 Returns
25 -------
26 D : set
27 A dominating set for G.
28
29 Notes
30 -----
31 This function is an implementation of algorithm 7 in [2]_ which
32 finds some dominating set, not necessarily the smallest one.
33
34 See also
35 --------
36 is_dominating_set
37
38 References
39 ----------
40 .. [1] https://en.wikipedia.org/wiki/Dominating_set
41
42 .. [2] Abdol-Hossein Esfahanian. Connectivity Algorithms.
43 http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
44
45 """
46 all_nodes = set(G)
47 if start_with is None:
48 start_with = arbitrary_element(all_nodes)
49 if start_with not in G:
50 raise nx.NetworkXError(f"node {start_with} is not in G")
51 dominating_set = {start_with}
52 dominated_nodes = set(G[start_with])
53 remaining_nodes = all_nodes - dominated_nodes - dominating_set
54 while remaining_nodes:
55 # Choose an arbitrary node and determine its undominated neighbors.
56 v = remaining_nodes.pop()
57 undominated_neighbors = set(G[v]) - dominating_set
58 # Add the node to the dominating set and the neighbors to the
59 # dominated set. Finally, remove all of those nodes from the set
60 # of remaining nodes.
61 dominating_set.add(v)
62 dominated_nodes |= undominated_neighbors
63 remaining_nodes -= undominated_neighbors
64 return dominating_set
65
66
67 def is_dominating_set(G, nbunch):
68 """Checks if `nbunch` is a dominating set for `G`.
69
70 A *dominating set* for a graph with node set *V* is a subset *D* of
71 *V* such that every node not in *D* is adjacent to at least one
72 member of *D* [1]_.
73
74 Parameters
75 ----------
76 G : NetworkX graph
77
78 nbunch : iterable
79 An iterable of nodes in the graph `G`.
80
81 See also
82 --------
83 dominating_set
84
85 References
86 ----------
87 .. [1] https://en.wikipedia.org/wiki/Dominating_set
88
89 """
90 testset = {n for n in nbunch if n in G}
91 nbrs = set(chain.from_iterable(G[n] for n in testset))
92 return len(set(G) - testset - nbrs) == 0