diff options
Diffstat (limited to '.venv/lib/python3.12/site-packages/networkx/algorithms/dominating.py')
| -rw-r--r-- | .venv/lib/python3.12/site-packages/networkx/algorithms/dominating.py | 268 |
1 files changed, 268 insertions, 0 deletions
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/dominating.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/dominating.py new file mode 100644 index 0000000..41c102a --- /dev/null +++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/dominating.py @@ -0,0 +1,268 @@ +"""Functions for computing dominating sets in a graph.""" + +import math +from heapq import heappop, heappush +from itertools import chain, count + +import networkx as nx + +__all__ = [ + "dominating_set", + "is_dominating_set", + "connected_dominating_set", + "is_connected_dominating_set", +] + + +@nx._dispatchable +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 = nx.utils.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_nbrs = 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_nbrs + remaining_nodes -= undominated_nbrs + return dominating_set + + +@nx._dispatchable +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`. + + Returns + ------- + dominating : bool + True if `nbunch` is a dominating set of `G`, false otherwise. + + 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 + + +@nx.utils.not_implemented_for("directed") +@nx._dispatchable +def connected_dominating_set(G): + """Returns a connected dominating set. + + A *dominating set* for a graph *G* 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]_. A *connected dominating set* is a dominating set *C* that induces a + connected subgraph of *G* [2]_. + Note that connected dominating sets are not unique in general and that there + may be other connected dominating sets. + + Parameters + ---------- + G : NewtorkX graph + Undirected connected graph. + + Returns + ------- + connected_dominating_set : set + A dominating set of nodes which induces a connected subgraph of G. + + Raises + ------ + NetworkXNotImplemented + If G is directed. + + NetworkXError + If G is disconnected. + + Examples + ________ + >>> G = nx.Graph( + ... [ + ... (1, 2), + ... (1, 3), + ... (1, 4), + ... (1, 5), + ... (1, 6), + ... (2, 7), + ... (3, 8), + ... (4, 9), + ... (5, 10), + ... (6, 11), + ... (7, 12), + ... (8, 12), + ... (9, 12), + ... (10, 12), + ... (11, 12), + ... ] + ... ) + >>> nx.connected_dominating_set(G) + {1, 2, 3, 4, 5, 6, 7} + + Notes + ----- + This function implements Algorithm I in its basic version as described + in [3]_. The idea behind the algorithm is the following: grow a tree *T*, + starting from a node with maximum degree. Throughout the growing process, + nonleaf nodes in *T* are our connected dominating set (CDS), leaf nodes in + *T* are marked as "seen" and nodes in G that are not yet in *T* are marked as + "unseen". We maintain a max-heap of all "seen" nodes, and track the number + of "unseen" neighbors for each node. At each step we pop the heap top -- a + "seen" (leaf) node with maximal number of "unseen" neighbors, add it to the + CDS and mark all its "unseen" neighbors as "seen". For each one of the newly + created "seen" nodes, we also decrement the number of "unseen" neighbors for + all its neighbors. The algorithm terminates when there are no more "unseen" + nodes. + Runtime complexity of this implementation is $O(|E|*log|V|)$ (amortized). + + References + ---------- + .. [1] https://en.wikipedia.org/wiki/Dominating_set + .. [2] https://en.wikipedia.org/wiki/Connected_dominating_set + .. [3] Guha, S. and Khuller, S. + *Approximation Algorithms for Connected Dominating Sets*, + Algorithmica, 20, 374-387, 1998. + + """ + if len(G) == 0: + return set() + + if not nx.is_connected(G): + raise nx.NetworkXError("G must be a connected graph") + + if len(G) == 1: + return set(G) + + G_succ = G._adj # For speed-up + + # Use the count c to avoid comparing nodes + c = count() + + # Keep track of the number of unseen nodes adjacent to each node + unseen_degree = dict(G.degree) + + # Find node with highest degree and update its neighbors + (max_deg_node, max_deg) = max(unseen_degree.items(), key=lambda x: x[1]) + for nbr in G_succ[max_deg_node]: + unseen_degree[nbr] -= 1 + + # Initially all nodes except max_deg_node are unseen + unseen = set(G) - {max_deg_node} + + # We want a max-heap of the unseen-degree using heapq, which is a min-heap + # So we store the negative of the unseen-degree + seen = [(-max_deg, next(c), max_deg_node)] + + connected_dominating_set = set() + + # Main loop + while unseen: + (neg_deg, cnt, u) = heappop(seen) + # Check if u's unseen-degree changed while in the heap + if -neg_deg > unseen_degree[u]: + heappush(seen, (-unseen_degree[u], cnt, u)) + continue + # Mark all u's unseen neighbors as seen and add them to the heap + for v in G_succ[u]: + if v in unseen: + unseen.remove(v) + for nbr in G_succ[v]: + unseen_degree[nbr] -= 1 + heappush(seen, (-unseen_degree[v], next(c), v)) + # Add u to the dominating set + connected_dominating_set.add(u) + + return connected_dominating_set + + +@nx.utils.not_implemented_for("directed") +@nx._dispatchable +def is_connected_dominating_set(G, nbunch): + """Checks if `nbunch` is a connected dominating set for `G`. + + A *dominating set* for a graph *G* 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]_. A *connected dominating set* is a dominating + set *C* that induces a connected subgraph of *G* [2]_. + + Parameters + ---------- + G : NetworkX graph + Undirected graph. + + nbunch : iterable + An iterable of nodes in the graph `G`. + + Returns + ------- + connected_dominating : bool + True if `nbunch` is connected dominating set of `G`, false otherwise. + + References + ---------- + .. [1] https://en.wikipedia.org/wiki/Dominating_set + .. [2] https://en.wikipedia.org/wiki/Connected_dominating_set + + """ + return nx.is_dominating_set(G, nbunch) and nx.is_connected(nx.subgraph(G, nbunch)) |