Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/algorithms/dominating.py @ 1:56ad4e20f292 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
author guerler
date Fri, 31 Jul 2020 00:32:28 -0400
parents
children
comparison
equal deleted inserted replaced
0:d30785e31577 1:56ad4e20f292
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