Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/mis.py @ 0:4f3585e2f14b draft default tip
"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 """ | |
2 Algorithm to find a maximal (not maximum) independent set. | |
3 | |
4 """ | |
5 import networkx as nx | |
6 from networkx.utils import not_implemented_for | |
7 from networkx.utils import py_random_state | |
8 | |
9 __all__ = ["maximal_independent_set"] | |
10 | |
11 | |
12 @py_random_state(2) | |
13 @not_implemented_for("directed") | |
14 def maximal_independent_set(G, nodes=None, seed=None): | |
15 """Returns a random maximal independent set guaranteed to contain | |
16 a given set of nodes. | |
17 | |
18 An independent set is a set of nodes such that the subgraph | |
19 of G induced by these nodes contains no edges. A maximal | |
20 independent set is an independent set such that it is not possible | |
21 to add a new node and still get an independent set. | |
22 | |
23 Parameters | |
24 ---------- | |
25 G : NetworkX graph | |
26 | |
27 nodes : list or iterable | |
28 Nodes that must be part of the independent set. This set of nodes | |
29 must be independent. | |
30 | |
31 seed : integer, random_state, or None (default) | |
32 Indicator of random number generation state. | |
33 See :ref:`Randomness<randomness>`. | |
34 | |
35 Returns | |
36 ------- | |
37 indep_nodes : list | |
38 List of nodes that are part of a maximal independent set. | |
39 | |
40 Raises | |
41 ------ | |
42 NetworkXUnfeasible | |
43 If the nodes in the provided list are not part of the graph or | |
44 do not form an independent set, an exception is raised. | |
45 | |
46 NetworkXNotImplemented | |
47 If `G` is directed. | |
48 | |
49 Examples | |
50 -------- | |
51 >>> G = nx.path_graph(5) | |
52 >>> nx.maximal_independent_set(G) # doctest: +SKIP | |
53 [4, 0, 2] | |
54 >>> nx.maximal_independent_set(G, [1]) # doctest: +SKIP | |
55 [1, 3] | |
56 | |
57 Notes | |
58 ----- | |
59 This algorithm does not solve the maximum independent set problem. | |
60 | |
61 """ | |
62 if not nodes: | |
63 nodes = {seed.choice(list(G))} | |
64 else: | |
65 nodes = set(nodes) | |
66 if not nodes.issubset(G): | |
67 raise nx.NetworkXUnfeasible(f"{nodes} is not a subset of the nodes of G") | |
68 neighbors = set.union(*[set(G.adj[v]) for v in nodes]) | |
69 if set.intersection(neighbors, nodes): | |
70 raise nx.NetworkXUnfeasible(f"{nodes} is not an independent set of G") | |
71 indep_nodes = list(nodes) | |
72 available_nodes = set(G.nodes()).difference(neighbors.union(nodes)) | |
73 while available_nodes: | |
74 node = seed.choice(list(available_nodes)) | |
75 indep_nodes.append(node) | |
76 available_nodes.difference_update(list(G.adj[node]) + [node]) | |
77 return indep_nodes |