## Mercurial > repos > shellac > sam_consensus_v3

### view 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 |

line wrap: on

line source

"""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